parsing - 这个语法是左递归还是因子？

Question

我是左递归和左因子这个话题的新手，请帮助我确定这个语法是左递归还是左因子，如果是，那为什么？

S-> aAd | bBd | 阿贝 | 氨基酸 | 钙| CB

Answer 1

它是左递归的吗？回答：没有。

根据定义，“如果我们能找到某个非终结符 A，它最终会导出一个以自身为左符号的句子形式，那么文法就是左递归的。”

示例：立即左递归出现在以下形式的规则中

A -> Aa | b

其中a和b是非终结符和终结符的序列，并且b不以A开头。

显然不是这样：

S-> aAd | bBd | 阿贝 | 氨基酸 | 钙| CB

是左因子吗？回答：是的。

根据定义，在左保理中，不清楚选择哪两个替代生产，以扩展一个非终端。

当您有两个以相同终端/非终端开始的替代生产时，就会出现这种歧义。在您的情况下，我可以看到三次，两条替代路径：

S-> aAd | aBe 

S-> bBd |  bAe 

S-> cA | cB

如果我删除左因子，则语法变为：

S-> aA'

A'-> Ad | Be

S-> bB'

B'-> Bd | Ae

S-> cC'

C'-> A | B

这张幻灯片用更简单的语言解释了相同的内容