相对于Lex/yacc/bison,Antlr的优势?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (92)

我过去曾在各种项目中使用过lex和yacc(通常是bison)。

最近,我在各种论坛上看到过关于Antlr的积极评论。我好奇它的优势是什么?

提问于
用户回答回答于

ANTLR生成一个LL(*)解析器,而YACC和Bison都生成LALR解析器。这是1个重要区别,最明显的是操作符:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR完全不能按原样处理这种语法。若要使用ANTLR(或任何其他LL解析器生成器),需要将此语法转换为非递归的语法。然而,Bison对这种形式的语法没有问题。需要声明‘+’和‘-’为左关联运算符,但这对于左递归并不是严格要求的。一个更好的例子可能是分派:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

注意,两个expractuals规则是左递归的.。当涉及到代码生成时,这会产生一个更有效的AST,因为它避免了多个寄存器和不必要的溢出(左倾树可以折叠,而右倾树不能)。

用户回答回答于

YACC/Bison和ANTLR最显著的区别在于这些工具可以处理的语法类型。YACC/Bison处理LALR语法,ANTLR处理LL语法。

通常,长期使用LALR语法的人会发现使用LL语法更加困难,反之亦然。这并不意味着语法或工具本身就更难使用。但你认为更容易使用的工具主要取决于对语法类型的熟悉程度。

就优势而言,LALR语法在某些方面比LL语法具有优势,还有一些方面LL语法比LALR语法具有优势。

YACC/Bison生成表驱动的解析器,这意味着“处理逻辑”包含在解析器程序的数据中,而不是在解析器的代码中。结果是,即使是对于非常复杂的语言的解析器,代码占用也相对较少。这在1960年代和1970年代更为重要,当时硬件非常有限。表驱动的解析器生成器可以追溯到这个时代,当时的主要需求是小代码占用。

ANTLR生成递归下降解析器,这意味着“处理逻辑”包含在解析器的代码中,因为语法的每个生成规则都由解析器代码中的一个函数表示。好处是,通过读取解析器的代码可以更容易地理解解析器正在做什么。此外,递归下降解析器通常比表驱动的解析器更快。但是,对于非常复杂的语言,代码占用将更大。这在1960年代和1970年代是个问题。当时,由于硬件的限制,只有相对较小的语言(例如Pascal)才以这种方式实现。

扫码关注云+社区