1

所以我有一些语法不适用于自上而下的解析器，因为它有左递归：

L::= A a | B b
A::= L b | a a
B::= b B b | b a

所以为了解决这个问题，我必须删除左递归。为此，我做了一些类似替代的事情：

L::= A a | B b
A::= A a b | B b b | a a (I plugged in the possible values of "L")

A然后转向（我相信）：

A::= a a A' | B b b
A'::= a b A' | ε

我相当肯定我是正确的（不过，如果我不是，也不会感到惊讶）。我现在正在苦苦挣扎的地方是从“B b b”中删除左递归。我已经尝试了很多方法，但我认为它们中的任何一个都不起作用。这似乎是最合乎逻辑的，但也很丑陋（因此说它可能是错误的）。从操作 B::= b B b | 开始 巴

B::= b B b | b a
B::= b B' (they both start with b, so maybe i can pull it out?)
B'::= B b | a
B'::= b B' b | a (substituted B's value in)
B'::= b B" | a
B"::= b B" |a B" | ε

所以我想展示最终确定的 B 是什么：

B::= b B'
B'::= b B" | a
B"::= b B" | a B" | ε

这似乎太丑了，不正确。特别是因为我必须将它插入我创建的新“A”终端。

有人可以帮我吗？不知道我是否以正确的方式解决这个问题。之后我应该能够创建一个 LL(1) 解析表（应该能够自己完成那部分）。

谢谢。

4

1 回答 1

0

在尝试从左侧扩展非终结符的解析器中，如果某个非终结符可以扩展为一个自身位于左侧的字符串，则解析器可能会永远扩展该非终结符而不实际解析任何内容。这是左递归。另一方面，如果非终结符扩展为左侧具有不同非终结符的字符串，只要没有扩展链生成左侧原始非终结符的字符串，则完全没问题。同样，如果非终结符在展开式中不是一直向右，只要它们不是一直向左就可以。

tl;博士B b bor没有任何问题b B b。您已经删除了所有左递归。你不需要继续前进。

于 2014-02-13T06:02:30.707 回答