这个语法是左因子吗？

Question

考虑以下语法

S --> A|B  
A --> aa   
B --> ab

这个语法是左因式的吗？

我觉得这个语法没有左因子，因为 S 的两个产生式之间的选择不明确，我们可以重写产生式以推迟这个决定，直到看到足够多的输入，我们可以做出正确的选择。

我是不是遗漏了什么或者这不是左因素？

Answer 1

语法不是 LL(1) 有几个原因。在这种情况下，S -> A 和 S -> B 之间存在 FIRST/FIRST 冲突 ：因为 FIRST(A) 和 FIRST(B) 重叠，有时候你不知道该选哪个作品。

通常教导解决这些冲突的技术是左因式分解和左递归移除，但是这个语法已经是左因式分解的（对于每个非终结符，每个产生式有一个不同的前缀）并且它没有任何左递归。

但是，您可以使用另一种技术：替换。在您的情况下，您可以通过将 S -> A 替换为 S -> aa.

来删除规则 A -> aa

要解决语法冲突，首先必须将 A 和 B 替换为 S:

S -> aa | ab

现在 S 的两个产生式之间仍然存在 FIRST/FIRST 冲突，但这一次，我们可以通过左因式分解来解决它：

S -> a T
T -> a | b

语法现在没有 LL(1) 冲突。

（不幸的是，我对解析器构造不够精通，无法知道一种机械方法来确定何时何地应该应用替换。不过，这是一种有效的技术。）

Is this grammar left factored?