LALR vs LL解析器

Question

LALR vs LL解析器

K J*_*K J 15 parsing yacc antlr lalr ll-grammar

我一直在使用lex/yacc,现在我正在尝试切换到ANTLR.主要关注的是ANTLR是一个LL(*)解析器,与yacc不同,它是LALR.我习惯于自下而上思考,我不知道LL语法的优点是什么.人们说LL语法现在更容易理解,更受欢迎.但似乎LR解析器更强大,例如LL解析器无法处理左递归,尽管似乎有一些解决方法.

那么问题是LL语法比LALR有什么优势？如果有人能给我一些例子,我会很感激.有用文章的链接也很棒.

感谢您的帮助!

(我认为这是一个很好的资源:LL解析器对LR解析器有什么优势？但是对于一些例子它会更好.)

Answer 1

Pup*_*ppy 13

LR解析器比LL解析器更强大,此外,LALR解析器可以像LL解析器一样在O(n)中运行.所以你不会发现LL相对于LR的任何功能优势.

因此,LL的唯一优点是LR状态机相当复杂且难以理解,并且LR解析器本身并不是特别直观.另一方面,自动生成的LL解析器代码可以非常容易理解和调试.

Answer 2

Aus*_*ley 11

我看到LL解析器的最大优点是它们易于理解和实现!您可以使用与语法紧密匹配的代码手写递归下降解析器.

LR通常被认为更强大,也更快,但我知道有一些权衡:

LR解析器只能使用合成属性; 他们无法传递继承的属性.
LR语法中的动作可以导致语法不确定,但不会导致LL.

但是,您会发现LL(*)也非常强大.

是的,它的有趣和人员构建解析器应该知道它们.随着你的语法变得越来越大,将它强制成LL形状是不方便的,并且在某些(非常小的)点上,LR的便利性胜过你头脑中的概念简单性.如果你没有构建解析器生成器,LR很容易理解,并且它不像周围没有很多. (3认同)
如果有人给你解析器生成器，根据定义它所做的就是“易于实现”。在这种情况下，您可以选择可以轻松处理最大类语言的解析器生成器，以最大程度地减少您的工作量。从这个角度来看，恕我直言，LR 轻松击败 LL。GLR 轻松击败 LR。 (2认同)

归档时间：	13 年，1 月前
查看次数：	7270 次
最近记录：	13 年，1 月前