parsing - 如何使用解析表证明左递归语法不在LL（1）中

Question

我有一个语法，想证明它不在 LL(1) 中：

S->SA|A
A->a

由于它是一个左递归语法，为了找到第一个和后续集合，我消除了左递归并得到：

S->AS'
S'->AS'|Empty
A->a

first of A={a}      follow of S={$}
first of s'={a,ε}   follow of S'={$}
first of S={a}       follow of A={a,$}

但是当我填写解析表时，我没有得到任何包含 2 个条目的单元格。那么如何证明给定的文法不在 LL(1) 中呢？

score 4 · Accepted Answer

首先，您会在删除左递归的语法上找到 FIRST 和 FOLLOW。因此，如果您尝试创建 LL(1) 解析表，肯定不会有任何 2 个条目，因为左递归被删除并且语法是明确的。

语法[ S->SA|A A->a ] 不是 LL(1)，因为存在左递归。要通过构造 LL(1) 解析表来证明这一点，您只需在此语法上找到 FIRST 和 FOLLOW 而无需修改它。

从底部 A->a 开始，给出 FIRST(A)={a}

S->A ，给出 FIRST(S)=FIRST(A)={a}

S->SA ，给出 FIRST(S)=FIRST(S) ，我认为这里出现了问题。在这样的递归调用中，规则说计算 FIRST(S) 直到它改变，即直到元素被添加到 FIRST(S) 中继续计算。一旦它停止变化，那就是你的答案

因此 FIRST(S)=FIRST(S)={a} ，您尽可能多次调用 FIRST(S) 它不会改变。解析表：

      a
------------ 
S   S->SA
    S->A
-------------
A   A->a

所以 (S,a) 有两个条目。因此它不是 LL(1)

score 0 · Accepted Answer

对于这个左递归文法：

S->SA|A
A->a

我们可以消除左递归，因为它会给出与先前左递归语法相同的结果。

S->AS'
S'->AS'|Empty
A->a

first of A={a}      follow of S={$}
first of s'={a,ε}   follow of S'={$}
first of S={a}       follow of A={a,$}

因此，实际上，对于上述情况，我们正在检查LL(1)修改后的左递归语法（因为它是相同的）。但是对于遵循左递归语法：-

E -> E+n/n

我们不能修改那个语法，它会改变+运算符的关联性。

所以，我们唯一要做的就是在不修改的情况下检查 LL(1)

(E->E+n/n ).

所以，我们可以说E->E+n/n不是LL(1)。

2 回答 2