提问人:Andrea Goldoni 提问时间:11/13/2023 更新时间:11/13/2023 访问量:25
我在将语法简化为 LL(1) 时遇到了问题
I have a problem in reducing a grammar to LL(1)
问:
在大学里,我正在学习正式语言,我正在练习我在互联网上找到的这个练习。
G:
S -> A B d |C d A -> C d
h |S e
C -> g B |h f
B -> 克 |ε
来源:https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php/Top-Down_Parsing/Example_2
我需要重写语法,使语言为LL(1)。我试图像这样解决它:
- 我注意到一个左递归 S=>ABd=>SeBd,并用替换将其删除,得到:
G:
S -> A B d |C d A -> C d
h |A B d e |C d e
C -> g B |h f
B -> 克 |ε
- 我注意到终端 A 上立即出现左递归并将其删除:
G:
S -> A B d |C d A -> C d
h A' |C d e A' A' -> B d e
A' |ε
C -> g B |h f
B -> 克 |ε
- 我注意到终端 A 上的左因式分解并将其删除,得到:
G:
S -> A B d |C d A -> C d
B'
B' -> h A' |e A'
A' -> B d e a |ε
C -> g B |h f
B -> 克 |ε
现在,如果我尝试构造解析表,然后计算第一个并遵循,您可以立即看到语法不是 LL(1),因为 first(ABd)=first(Cd)。有人可以解释为什么,因为既不存在左递归,也不存在右因式分解,而且语法似乎并不模棱两可。我做错了什么?
答: 暂无答案
下一个:eBNF 语法中的运算符优先级
评论