为什么LL语法不能是左递归的? [英] Why can't a LL grammar be left-recursive?

问题描述

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

In the dragon book, LL grammar is defined as follows:

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

A grammar is LL if and only if for any production A -> a|b, the following two conditions apply.

1. FIRST(a)和FIRST(b)是不相交的.这意味着它们不能同时导出EMPTY

1. FIRST(a) and FIRST(b) are disjoint. This implies that they cannot both derive EMPTY

如果b可以派生EMPTY，则a不能派生任何以FOLLOW(A)开头的字符串，即FIRST(a)和FOLLOW(A)必须不相交.

If b can derive EMPTY, then a cannot derive any string that begins with FOLLOW(A), that is FIRST(a) and FOLLOW(A) must be disjoint.

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

And I know that LL grammar can't be left recursive, but what is the formal reason? I guess left-recursive grammar will contradict rule 2, right? e.g., I've written following grammar:

S->SA|empty
A->a

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

Because FIRST(SA) = {a, empty} and FOLLOW(S) ={$, a}, then FIRST(SA) and FOLLOW(S) are not disjoint, so this grammar is not LL. But I don't know if it is the left-recursion make FIRST(SA) and FOLLOW(S) not disjoint, or there is some other reason? Put it in another way, is it true that every left-recursive grammar will have a production that will violate condition 2 of LL grammar?

推荐答案

好的，如果语法包含左递归生成，例如:

OK, I figure it out, if a grammar contains left-recursive production, like:

S->SA

然后以某种方式必须包含另一个生产内容以完成"递归，例如:

Then somehow it must contain another production to "finish" the recursion,say:

S->B

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

And since FIRST(B) is a subset of FIRST(SA), so they are joint, this violates condition 1, there must be conflict when filling parse table entries corresponding to terminals both in FIRST(B) and FIRST(SA). To summarize, left-recursion grammar could cause FIRST set of two or more productions to have common terminals, thus violating condition 1.

这篇关于为什么LL语法不能是左递归的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！