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
有人可以帮忙吗?
在他关于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).
希望这可以帮助!