compiler-construction - 将语法转换为 LL(1) 语法 : some problems

Question

这不完全是家庭作业，但与我的学习有关:

语法例如如下:

E -> E+E|E*E|-E|(E)|id

消除歧义后，它变成(从最低优先级运算符开始)

E->-F|F
F->F+G|G
G->G*H|H
H->(E)|id

删除左递归和左因子分解(本例中不需要)后，最终的 LL1 语法为:

E->-F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

这给出了一个工作正常的无错误解析器表。 现在关于我面临的问题，假设语法是这样的:

E -> E+E|E*E|id=E|(E)|id

现在我无法生成没有冲突的解析表，这意味着我的最终语法不是 LL1。步骤如下:

消除歧义后:

E->id=F|F
F->F+G|G
G->G*H|H
H->(E)|id

去掉左递归和左分解后，语法变成:

E->id=F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

但是解析器表中存在我无法删除的冲突，这意味着我错过了某些步骤，或者步骤中存在一些我无法找到的错误。请告诉我我做错了什么，以及如何解决这个问题。我已经研究这个问题很长时间了。

Answer 1

这么说吧:

E -> E+E|E*E|id=E|(E)|id

将变成:

E -> E+E|E*E|(E)|E'
E' -> id=E|id

然后你可以消除歧义和左手递归并得到:

E -> GF       FIRST(E) = FIRST(G)
F -> +GF|e
G -> HG'      FIRST(G) = FIRST(H)
G' -> *HG'|e
H -> (E)|E'   FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE''   FIRST(E') = {id}
E'' -> =E|e   FIRST(E'') = {=} + {#}

当然，问题是，您失去了给定的运算符优先级。

如果对于任何非终结符 N，语法不会是 LL(1)， 中将存在任何公共(public)元素 FIRST(N -> a) 和 FIRST(N -> b) 对于 N -> a、N -> b与 N 不同的产品。

如您所见，在任何其他位置添加生产 N -> id= 都会违反该规则。

您可以创建一个 LL(2) 语法(但这可能不是您想要的)，它可以在任何地方产生 id=E 产生式。 (FIRST2 集合由 2 元素字符串组成)。

此外，如果您再看一遍所提供的语法:

E -> E+E|E*E|id=E|(E)|id

我在上面的解决方案中设置的运算符优先级很有可能是适合实际应用的。看看吧!