LL解析器比LR解析器有什么优势?

如果您想要一个解析树/林,并且不介意黑盒,那么GLR是很好的。它可以让你输入任何 CFG 您需要在解析时通过详尽的测试检查歧义,而不是静态地解决LR/LALR冲突。有人说这是一个很好的权衡。IRABAXTER的DMS工具或ELKHOND,它有一个免费的C++语法,对于这类问题是有用的。 ANTLR 对于大型语言应用程序类也很有用,但使用自顶向下的方法,生成允许语义谓词的递归下降解析器LL(*)。我将在这里不加证明地声明,谓词允许您在cfg之外解析上下文敏感语言。程序员喜欢在语法中插入动作,比如良好的错误处理,以及喜欢单步调试。我三个都很好。这是我们手工做的,所以更容易理解。别相信 wikipedia nonsense about LR being better at handling errors . 也就是说,如果使用ANTLR进行大量回溯,使用LL(*)时错误确实更严重(PEGs有这个问题)。

重新回溯。GLR也会像PEGs、ANTLR和其他非确定性策略一样进行推测(即回溯)。在任何不确定的LR状态下,GLR“分叉”子解析器来尝试任何可行的路径。无论如何,LL有很好的上下文来处理错误。如果LR知道它匹配一个表达式,就知道它是赋值中的表达式,或者 IF

GLR是 O(n^3) 最坏的情况。packrat/PEG是 O(n) 最坏的情况。蚂蚁是 O(n^2) O(n) 在实践中。没什么大不了的。GLR足够快了。

是 一个 T型 ool用于 昂 右

坦白地说,和很多80年代的年轻程序员一样,我不理解LALR,也不喜欢黑匣子(现在我喜欢GLR引擎的优点,但还是更喜欢LL)。我构建了一个基于LL(k)的商业编译器,并决定构建一个工具来生成我手工构建的代码。ANTLR不适合所有人,像C++这样的边缘情况可以更好地处理GLR,但是很多人发现ANTLR适合他们的舒适区。自2008年1月以来,在ANTLRWorks中,ANTLR的二进制jar已经有13.4万次下载,source zips的下载总量也达到了13.4万次(根据Google分析)。见 our paper 有大量的经验数据。

如果必须手工编写一个代码,递归下降(L L)是可以实际执行的;人们不能手工构建L(AL)R解析器。

事实上,我更喜欢 GLR parsers ,它几乎可以用上下文无关语法解析任何内容。不用担心复发。不转移/减少冲突担忧。没有前瞻性限制。

一 GLR解析引擎可以处理(包括著名的难以解析的LL/LALR语言,C++),你可以看看 here .

另一件事是自顶向下的方法通常意味着更高的复杂性(关于空间或时间),因为它必须在解析的同时存储整个树,并且它可以增长很多直到歧义得到解决。

我所熟悉的唯一优点是,您可以轻松地手工编写LL解析器。LR解析器很难手工编写(通常使用解析器生成器)。

(但是没有人会写O(n^4)语法。)

https://en.wikipedia.org/wiki/Top-down_parsing

我想到的一个原因是,做一门语言 需要 咳嗽 在LL范式中的C++。