制作语法LL(1)

Joh*_*rts 7 grammar parsing programming-languages context-free-grammar ll-grammar

我有以下语法:

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

因为我正在尝试为它编写一个小编译器,所以我想把它变成LL(1).我看到这里似乎存在FIRST/FOLLOW冲突,我知道我必须使用替换来解决它,但我不确定如何解决它.这是我提出的语法,但我不确定它是否正确:

S-> aSbT | 小量

T-> bFaF | 小量

F-> epsilon

有人可以帮忙吗?

tem*_*def 5

在他关于LR解析的原始论文中,Knuth给出了这种语言的以下语法,他猜想"这是这种语言最简洁的语法:"

S→ε| aAbS | BBAS

A→ε| AABA

B→ε| BBAB

直觉上,这会尝试将任何字符串的As和B分解为完全平衡的块.一些块以a开头,以b结尾,而其他块以b开头,以a结尾.

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

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

第一(A)= {ε,a}

第一(B)= {ε,b}

跟随(S)= {$}

跟随(A)= {b}

跟随(B)= {a}

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

   |   a   |   b   |   $   
 --+-------+-------+-------
 S | aAbS  | bBaS  |  e
 A | aAbA  |   e   |
 B |   e   | bBaB  |
Run Code Online (Sandbox Code Playgroud)

所以这个语法不仅是LR(1),而且它也是LL(1).

希望这可以帮助!