compiler-construction - 带有 LL(1) 解析的歧义文法

Question

我在解决这个问题时遇到了问题。我必须重写以下语法以使其适用于 LL(1) 解析

S → 名词 | 名词和名词| M、名词和名词

M → M, 名词 | 名词

我注意到的第一个问题是语法在带有头 M 的生产中是递归的，我像这样修复它

M → 名词 NewPro

NewPro → , 名词 NewPro

但后来我注意到带有标题 S 的产生是模棱两可的，但我不知道如何解决它，我试图“分解”这个名词，但我实际上并不确定。

你能帮我吗？

谢谢您的回答。

Answer 1

您的左递归消除M不完整-您忘记了规则 NewPro → ε

添加后，您就会遇到 的问题S，这不是模棱两可的，但需要左因式分解。由于 FIRST(M) ⊆ FIRST(S)，你需要先将 M 代入 S：

S → 名词 | 名词和名词| 名词 NewPro、名词和名词

然后你可以简单地把它留在

S → 名词 S'
S' → ε | 和名词 | NewPro、名词和名词

现在你遇到了这个语法是 LL(4) 而不是 LL(1) 的问题，因为你需要 4 个标记前瞻才能找到NewPros 序列的结尾。这是一个更难处理的问题，但可以解决。首先，您需要将其拉, noun,入 NewPro：

S' → ε | 和名词 | NewPro 和名词
NewPro → , 名词, | , 名词 NewPro

然后是左因子 NewPro：

NewPro → , 名词 NewPro'NewPro
' → , | 新宝

然后代入NewPro'：

新Pro' → , | , 名词 NewPro'

还有左边的因素：

NewPro' → , NewPro'' NewPro'' → ε | 名词 NewPro'

给出最终的语法：

S → 名词 S'
S' → ε | 和名词 | NewPro 和名词
NewPro → , 名词 NewPro'NewPro
' → , NewPro''
NewPro'' → ε | 名词 NewPro'

这是 LL(1)，可以直接使用或通过将 NewPro 替换回 S' 并重命名规则以摆脱 '-suffixes 来稍微简化一下：

S → 名词 A
A → ε | 和名词 | , 名词 B 和名词
B → , C
C → ε | 名词 B