2 
E -> E+E|E*E|(E)|a

给定语法，如何将语法转换为 LL(1) 形式？

E->aX|(E)
X->+E|*E|epsilon

这是 LL(1) 语法吗？

4

2 回答 2

1

原始文法是左递归的，因此不是 LL(1)，实际上对于任何 k 都不是 LL(k)。

幸运的是，可以删除左递归。标准算法通过分别处理立即左递归（正如我们在这里）和间接左递归来做到这一点。立即左递归是两者中较简单的情况。维基百科的文章在这里解释了它。

基本上你将递归引用之后的部分移动到一个新的生产（尾部）中，它也有一个ε替代方案，

   X -> ε|+E|*E

然后你从原始生产中删除左递归替代方案，并允许X遵循所有剩余的非递归替代方案，

   E -> (E)X|aX

请注意，您的提案错过X了括号中的表达式，因此它不能识别相同的语言。

于 2013-08-17T09:49:07.993 回答
-1

) 为该文法求 FIRST(S) 和 FOLLOW(S)： S → d S a S → c S b S → ε

于 2017-03-26T20:40:03.167 回答