解决 LL(1) 中的 PREDICT/PREDICT 冲突

Question

我正在开发一个简单的 LL(1) 解析器生成器，我运行遇到了一个问题，即给定某些输入语法时 PREDICT/PREDICT 冲突。例如，给定如下输入语法：

E  → E + E
   | P

P  → 1

我可以从E中去掉左递归，用一个大致等价的右递归规则替换它，从而得到语法：

E  → P E'

E' → + E E'
   | ε

P  → 1

接下来，我可以为语法计算相关的 FIRST 和 FOLLOW 集，并得到以下结果：

FIRST(E)  = { 1 }
FIRST(E') = { +, ε }
FIRST(P)  = { 1 }

FOLLOW(E)  = { +, EOF }
FOLLOW(E') = { +, EOF }
FOLLOW(P)  = { +, EOF }

最后，使用PREDICT(A → α) = { FIRST(α) - ε } ∪ (FOLLOW(A) if ε ∈ FIRST(α) else ∅)构造语法的PREDICT集，结果集如下。

PREDICT(1. E  → P E')   = { 1 }
PREDICT(2. E' → + E E') = { +, EOF }
PREDICT(3. E' → ε)      = { +, EOF }
PREDICT(4. P  → 1)      = { 1 }

所以这就是我运行与 PREDICT(2) = PREDICT(3) 冲突的地方，因此，我无法生成解析 table，因为语法不是 LL(1)，因为解析器将无法选择应应用哪个规则。

我真正想知道的是是否可以解决冲突或分解语法以避免冲突，并生成合法的 LL(1) 语法，而不必直接修改原始输入语法.

Answer 1

这里的问题是你原来的语法有歧义。

E → E + E
E → P

表示 P + P + P 可以解析为 (P + P) + P 或 P + (P + P)。消除左递归并不能解决歧义，所以修改后的文法也是有歧义的。歧义语法不能是 LL(k)（或者就此而言，LR(k)）。

所以你需要使语法明确：

E → E + P
E → P

（这是常见的左关联版本。）一旦你消除了左递归，你最终会得到：

E  → P E'
E' → + P E'
   | ε

现在 + 不在 FOLLOW(E') 中。

（这个例子是直接从 Dragon book 中提取的，但是被简化了；它是我有的相当破旧的旧副本中的例子 4.8。）

值得注意的是，这里使用的转换保留了语法派生的字符串集，而不是推导。由修改后的语法产生的解析树实际上是右结合的，因此需要重新处理以恢复所需的解析。 Dragon 书的作者相当简短地提到了这个事实：

Although left-recursion elimination and left factoring are easy to do, they make the resulting grammar hard to read and difficult to use for translation purposes. (My emphasis)

他们继续建议运算符优先级解析可用于表达式，然后提到如果 LR 解析器生成器可用，则不再需要将语法分为预测部分和运算符优先级部分。

解决 LL(1) 中的 PREDICT/PREDICT 冲突

Resolving PREDICT/PREDICT conflicts in LL(1)

algorithm

parsing

grammar

ll