如何使用解析表证明左递归文法不在 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) 中呢？

Answer 1

首先，您将找到已删除左递归的语法的 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)