制作语法LL(1)

Question

我有以下语法：

S → a S b S | b S a S | ε

由于我正在尝试为其编写一个小型编译器，因此我想将其设为 LL(1)。我发现这里似乎存在 FIRST/FOLLOW 冲突，我知道我必须使用替换来解决它，但我不太确定如何解决它。这是我建议的语法，但我不确定它是否正确：

S-> aSbT | ε

T->bFaF| ε

F->epsilon

有人可以帮忙吗？

Answer 1

在他的关于 LR 解析的原始论文中，Knuth 给出了该语言的以下语法，他推测“这是该语言的最简短的无歧义语法：”

S → ε |抗体 | bBaS

A → ε | aAbA

B → ε |巴巴巴

直观地说，这试图将任何 As 和 B 串分解成完全平衡的块。有些块以 a 开头，以 b 结束，而另一些块以 b 开头，以 a 结束。

我们可以计算 FIRST 和 FOLLOW 集如下：

FIRST(S) = { ε, a, b }

FIRST(A) = { ε, a }

FIRST(B) = { ε, b }

关注（S）= { $ }

FOLLOW(A) = { b }

跟随(B) = { a }

据此，我们得到如下LL(1)解析表：

   |   a   |   b   |   $   
 --+-------+-------+-------
 S | aAbS  | bBaS  |  e
 A | aAbA  |   e   |
 B |   e   | bBaB  |

所以这个文法不仅是 LR(1)，而且也是 LL(1)。

希望这有帮助！