我如何制作这个语法 LL(1)？

Question

假设我有这个语法

E -> T+Ex | F
T -> T*Fy | w
F -> E | z | ε

现在我需要把它变成 LL(1)。我一直在按照这些步骤操作，但我提出的解决方案似乎不太正确。拳头让我们消除 ε-productions

E -> T+Ex | F | T+x
T -> T*Fy | w | T*y
F -> E | z

现在我们将消除循环

E -> T+Ex | T+x | z
T -> T*Fy | w | T*y
F -> T+Ex | T+x | z

不，我们将消除直接左递归

E -> T+Ex | T+x | z
T -> wT'
T' -> *FyT' | *yT' | ε
F -> T+Ex | T+x | z

最后，我们将替换 T 出现的某些 RHS 作品

E -> wT'+Ex | wT'+x | z
T -> wT'
T' -> *FyT' | *yT' | ε
F -> wT'+Ex | wT'+x | z

现在这对我来说似乎不是 LL(1)，因为由此生成的解析 table 将有多个终端的多个条目。我似乎缺少什么？

Answer 1

我知道怎么做了，最后一步我们有了这个配置

E -> wT'+Ex | wT'+x | z
T -> wT'
T' -> *FyT' | *yT' | ε
F -> wT'+Ex | wT'+x | z

我们现在需要执行左因式分解以移除形式为

的产生式

S -> aB | aC

并把它们变成合适的形式

S -> aA
A -> B | C

使用这个我们可以将我们的语法转换成

E -> wT'+E' | z
E' -> Ex | x
T -> wT'
T' -> *T'' | ε
T'' -> FyT' | yT'
F -> wT'+F' | z
F' -> Ex | x

因为 F 和 F' 与 E 和 E' 相同，我们可以删除这个产生式，所以我们剩下了。

E -> wT'+E' | z
E' -> Ex | x
T -> wT'
T' -> *T'' | ε
T'' -> EyT' | yT'

How do I make this grammar LL(1)?