grammar - 为什么LL语法不能是左递归的？

Question

在dragon book中，LL语法定义如下：

当且仅当对于任何产生式A -> a|b时，以下两个条件均适用，语法为LL。


FIRST(a)和FIRST(b)不相交。这意味着它们不能同时导出EMPTY
如果b可以派生EMPTY，则a不能派生任何以FOLLOW(A)开头的字符串，即FIRST(a)并且FOLLOW(A)必须不相交。


而且我知道LL语法不能保留递归，但是正式原因是什么？我猜左递归语法将与规则2相矛盾，对吗？例如，我写了以下语法：

S->SA|empty
A->a

因为FIRST(SA) = {a, empty}和FOLLOW(S) ={$, a}，所以FIRST(SA)和FOLLOW(S)并非不相交，因此此语法不是LL。但是我不知道是否是FIRST(SA)和FOLLOW(S)不相左的左递归，还是有其他原因？换句话说，每个左递归语法都会产生违反LL语法条件2的情况吗？

Answer 1

好吧，我知道了，如果一个语法包含左递归产生，例如：

S->SA

然后以某种方式必须包含另一个生产来“完成”递归，例如：

S->B

并且由于FIRST（B）是FIRST（SA）的子集，因此它们是联合的，这违反了条件1，因此在填充与FIRST（B）和FIRST（SA）中的终端相对应的解析表条目时必须存在冲突。总而言之，左递归语法可能导致两个或多个生产的FIRST集具有共同的末端，从而违反了条件1。