LL与LR解析器的局限性？

Question

我知道LL与LR解析器的基本区别.我也知道GLR,SLR和LALR都是LR解析器的扩展.所以我的问题更多细节是......

给定一个LL(*)解析器和LR解析器的任何变体,是否有任何语言可以在一个而不是另一个中描述？或者更简单的是,是否有任何功能或属性无法表达？

作为一个具体的例子.如果我要使用LL(*)解析器创建一种语言,我是否会遇到我想要添加到我的语言中的所需功能/属性,这只能通过LR解析器实现(反之亦然)？

Answer 1

这里有几个意见,你可以考虑点和对点:

Answer 2

当然.LL解析器无法处理左递归的任何语法.固定k的L(AL)R(k)解析器将无法解析LL(*)解析器可以处理的一些事情,因为k <*.

如果你愿意重写语法,你可以让大多数解析器"解析"真正语言的超集'; 然后,您可以编写其他测试以删除无关的部分.问题是,你愿意去做多少工作？OP的原始问题是关于LL(*)与LALR(k)的强度. (3认同)

Answer 3

您可能会在维基百科中发现这段有趣的内容,即LL(*)语法是LR(k)语法的子集:http: //en.wikipedia.org/wiki/Context-free_grammar#Restrictions 因此您可以解析更多语言使用LR解析方法.

Answer 4

有些语法不能被LR解析器解析的LL解析器“重写”以进行解析。一个例子：给定一个简单的语法，该语法用减法构造术语：

S -> S - S | num

您显然在这里有左递归，LL解析器无法处理。要使此语法可被LL解析，您必须消除左递归：

S -> num S'

S' -> - num S' | epsilon

现在，您的LL解析器可以处理此语法。但是，当为诸如4-2 -1之类的术语构建语法树时，对该树进行深度优先搜索将为您提供4-（2-1）= 3而不是（4-2）-1 = 3如您所料。

这样做的原因是，您必须在语法中使用左递归规则来处理左关联运算符（如减法）。但是左递归规则不能由LL分析器处理。

因此，这里有LL无法处理的一类语言。