parsing - 一个 LL(1) 文法可以有多个以同一个非终结符开头的规则吗？

Question

给定一个由定义的文法 G

A -> Ca
B -> Cb
C -> e|f

这是文法 LL(1) 吗？

我意识到我们可以将其压缩成一行，但这不是这个问题的重点。

主要是，一个 LL(1) 文法可以有多个以同一个非终结符开头的规则吗？

作为后续问题，如何为上述语法构建解析表？

我已经解决了以下问题：

FIRST(A) = {e,f}
FIRST(B) = {e,f}
FIRST(C) = {a,b}

FOLLOW(A) = {}
FOLLOW(B) = {}
FOLLOW(C) = {a,b}

我看了这篇文章，但不明白他们是如何从 FIRST 和 FOLLOW 变成一张桌子的。

Answer 1

您给出的语法不是 LL(1)，因为两个产生式 A → Ca 和 A → Cb 之间存在 FIRST/FIRST 冲突。

通常，以相同非终结符开头的同一非终结符具有多个产生式的文法不会是 LL(1)，因为您会遇到 FIRST/FIRST 冲突。有这个属性的文法是 LL(1)，尽管它们本质上是退化的情况。例如，考虑以下语法：

A → E

A → Eb

E → ε

在这里，非终结符 E 仅扩展为空字符串 ε，因此实际上并不存在。因此，上述文法为 LL(1)，因为两个产生式之间不存在 FIRST/FIRST 冲突。要看到这一点，这是解析表：

     a  b  $
A    Ea Eb -
E    ε  ε  -

希望这可以帮助！

Answer 2

我在 2 种情况下解决您的问题：

第一种情况，如果终端是 {a,b,e,f}

第二种情况，如果终端是 {a,b,f} 并且 e 是 epsilon

所以没有多重条目这是LL（1）。

有关更多信息：请查看以下说明和示例：

此致