制作语法LL(1)

Question

我有以下语法：

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

因为我想为它写一个小的编译器，所以我想把它设为LL(1)。我看到这里似乎有一个FIRST/FOLLOW冲突，我知道我必须使用替换来解决它，但我不太确定如何解决它。以下是我建议的语法，但我不确定它是否正确：

S-> aSbT | epsilon

T-> bFaF| epsilon

F-> epsilon

有人能帮上忙吗？

Answer 1

在他的original paper on LR parsing中，Knuth给出了这种语言的以下语法，他猜想“这是这种语言最简短、最明确的语法：”

S→ε| aAbS | bBaS

aAbA |→ε

B→ε|B

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

我们可以先计算集合，然后再计算，如下所示：

优先(S)={ε，a，b}

FIRST(A) ={ε，a}

FIRST(B) ={ε，b}

FOLLOW(S) ={$}

FOLLOW(A) ={b}

跟随(B)={a}

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

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

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

希望这能有所帮助！