parsing - 制作语法 LL(1)

Question

我有以下语法:

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

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

S-> aSbT |厄普西隆

T-> bFaF|厄普西隆

F-> ε

有人可以帮忙吗？

Answer 1

在他的 original paper on LR parsing , Knuth 给出了这种语言的以下语法，他推测“是这种语言可能的最简短的无歧义语法:”

S → ε | aAbS | bBaS

A → ε | aAbA

B → ε | bBaB

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

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

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

FIRST(A) = { ε, a }

FIRST(B) = { ε, b }

FOLLOW(S) = { $ }

FOLLOW(A) = { b }

FOLLOW(B) = { a }

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

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

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

希望这可以帮助!