algorithm - 解决 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(1. E  → P E')   = { 1 }
PREDICT(2. E' → + E E') = { +, EOF }
PREDICT(3. E' → ε)      = { +, EOF }
PREDICT(4. P  → 1)      = { 1 }

所以这就是我遇到 PREDICT(2) = PREDICT(3) 冲突的地方，因此，我无法生成解析表，因为语法不是 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 书，但进行了简化；它是我拥有的相当破旧的旧副本中的示例 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 解析器生成器可用，则不再需要将语法分为预测部分和运算符优先级部分。