parsing - 制作语法 LL(1)

Question

我有以下语法：

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

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

S-> aSbT | ε

T->bFaF| ε

F-> ε

有人可以帮忙吗？

Answer 1

在他关于 LR 解析的原始论文中，Knuth 给出了这种语言的以下语法，他推测“这是这种语言的最简短的可能明确的语法：”

S → ε | 抗体 | bBaS

A → ε | 抗体

B → ε | bBaB

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

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

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

FIRST(A) = { ε, a }

FIRST(B) = { ε, b }

关注(S) = { $ }

跟随(A) = { b }

跟随(B) = {一个}

基于此，我们得到以下 LL(1) 解析表：

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

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

希望这可以帮助！