这个语法LL(1)？

Question

我已经得出以下语法:

S -> a | aT
T -> b | bR
R -> cb | cbR

我理解为了使语法成为LL(1),它必须是非模糊的和右递归的.问题是我不完全理解左递归和右递归语法的概念.我不知道以下语法是否正确递归.我真的很感激左递归和右递归语法概念的简单解释,如果我的语法是LL(1).

非常感谢.

Answer 1

这个语法不是LL(1).在LL(1)解析器中,始终可以根据当前的非终结符号和输入的下一个标记来确定接下来要使用的生产.

让我们来看看这个产品,例如:

S→a | 在

现在,假设我告诉你当前的非终结符号是S而下一个输入符号是a.你能确定使用哪种产品吗？不幸的是,没有更多的上下文,你不能这样做:也许你假设使用S→a,也许你应该使用S→aT.使用类似的推理,您可以看到所有其他产品都有类似的问题.

这与左或右递归没有任何关系,而是LL(1)语法中相同非终结符的两个产生都不能具有非空公共前缀.实际上,用于检查语法是否不是 LL(1)的简单启发式方法是查看是否可以找到这样的两个生产规则.

希望这可以帮助!