我在将语法简化为 LL(1) 时遇到了问题

I have a problem in reducing a grammar to LL(1)

提问人:Andrea Goldoni 提问时间:11/13/2023 更新时间:11/13/2023 访问量:25

问:

在大学里,我正在学习正式语言,我正在练习我在互联网上找到的这个练习。

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)。我试图像这样解决它:

  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 -> 克 |ε

  1. 我注意到终端 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 -> 克 |ε

  1. 我注意到终端 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)。有人可以解释为什么,因为既不存在左递归,也不存在右因式分解,而且语法似乎并不模棱两可。我做错了什么?

解析 上下文无关语法

评论

0赞 Quack E. Duck 11/16/2023
这是一个理论问题(不是编程问题),如果在 Computer Science SE 上提问可能比在 StackOverflow 上提问更好。以下是其描述的链接:cs.stackexchange.com/help/on-topic

答: 暂无答案