将语法转换为LL(1)语法:一些问题

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

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

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'') = {=} + {#}

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

如果对于任何非终结符， 和中将有任何公共元素，且与 的产生式不同，则语法不会是 LL(1)。NFIRST(N -> a)FIRST(N -> b)N -> aN -> bN

N -> id=正如您所看到的，在任何其他地方添加作品都会违反该规则。

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

另外，如果你再看一遍所提供的语法：

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

我在上述解决方案中制定的运算符优先级很可能是适合实际应用的正确优先级。一探究竟！