18

龙书中，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}and FOLLOW(S) ={$, a}, then FIRST(SA)andFOLLOW(S)不是不相交的，所以这个文法不是 LL。但我不知道是左递归makeFIRST(SA)而FOLLOW(S)不是不相交，还是有其他原因？换句话说，是否每个左递归文法都会有一个违反 LL 文法条件 2 的产生式？

4

3 回答 3

15

好的，我弄清楚了，如果语法包含左递归产生式，例如：

S->SA

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

S->B

并且由于FIRST(B)是FIRST(SA)的子集，所以它们是联合的，这违反了条件1，在填充FIRST(B)和FIRST(SA)中的终端对应的解析表条目时必然存在冲突。总而言之，左递归语法可能导致两个或多个产生式的 FIRST 集具有公共终结符，从而违反条件 1。

于 2013-04-23T10:07:00.167 回答
12

考虑你的语法：

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。我们应该使用哪一个？

于 2013-04-23T09:22:40.230 回答
9

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).

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

于 2013-04-23T20:12:12.547 回答