为什么LL语法不能左递归？

Question

在龙书中,LL语法定义如下:

语法是LL,当且仅当适用于任何生产时A -> a|b,以下两个条件适用.

1. FIRST(a)并且FIRST(b)是不相交的.这意味着它们不能同时衍生出来EMPTY

2. 如果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.

Answer 2

考虑你的语法:

S->SA|empty
A->a

这是三条规则的简写:

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

现在考虑字符串aaa.它是如何产生的？如果你没有前瞻,你一次只能读一个字符,所以你就这样开始(你有S开始符号):

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

好的,你已经制作了第一个a.但现在你不能再申请任何规则,因为没有更多的非终端.你被卡住了!

你应该做的是这样的:

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

但是如果不阅读整个字符串,你就不知道这一点.你需要无限量的前瞻.

在一般意义上,是的,每个左递归语法都可以有不明确的字符串而没有无限的前瞻.再看一下这个例子:有两个不同的规则S.我们应该使用哪一个？

Answer 3

一个LL(k)语法是允许仅具有确定性的,下降解析器的结构k先行的符号.左递归的问题在于,在检查完整的输入字符串之前,无法确定应用哪个规则,这使得所需的k可能无限.

使用您的示例,选择a k,并为解析器提供一个长度为输入的序列n >= k:

aaaaaaa...

解析器无法决定它是应该应用S->SA还是S->empty通过查看k前面的符号,因为决定将取决于S->SA之前选择了多少次,这是解析器没有的信息.

解析器必须选择S->SA确切的n时间和S->empty一次,并且通过查看k输入流中的第一个符号来确定哪个是正确的是不可能的.

要知道,解析器必须同时检查完整的输入序列,并记录S->SA已选择的次数,但这样的解析器将超出定义LL(k).

请注意,无限前瞻不是解决方案,因为解析器在有限的资源上运行,因此总会有一个有限的输入序列,其长度足以使解析器在生成任何输出之前崩溃.