且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

Antlr的优点(相对于lex / yacc / bison)

更新时间:2022-01-20 01:05:21

一个主要区别是ANTLR生成一个LL(*)解析器,而YACC和Bison都生成LALR的解析器。这是许多应用程序的一个重要区别,最显而易见的是操作符:

One major difference is that ANTLR generates an LL(*) parser, whereas YACC and Bison both generate parsers that are LALR. This is an important distinction for a number of applications, the most obvious being operators:

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

ANTLR完全不能处理这种语法。要使用ANTLR(或任何其他LL解析器生成器),您需要将此语法转换为不是左递归的东西。然而,Bison对这种形式的语法没有问题。你需要声明'+'和' - '作为左相关运算符,但是这不是左递归的严格要求。一个更好的例子可能是dispatch:

ANTLR is entirely incapable of handling this grammar as-is. To use ANTLR (or any other LL parser generator), you would need to convert this grammar to something that is not left-recursive. However, Bison has no problem with grammars of this form. You would need to declare '+' and '-' as left-associative operators, but that is not strictly required for left recursion. A better example might be dispatch:

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

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

请注意 expr code> actuals 规则是左递归的。当代码生成的时候,这产生了更高效的AST,因为它避免了对多个寄存器和不必要的溢出(左倾树可能崩溃,而右倾树不能)。

Notice that both the expr and the actuals rules are left-recursive. This produces a much more efficient AST when it comes time for code generation because it avoids the need for multiple registers and unnecessary spilling (a left-leaning tree can be collapsed whereas a right-leaning tree cannot).

在个人品味方面,我认为LALR语法更容易构建和调试。缺点是你必须处理有些神秘的错误,如shift-reduce和(可怕的)reduce-reduce。这些是Bison在生成解析器时捕获的错误,因此它不会影响最终用户体验,但它可以使开发过程更有趣。因此,ANTLR通常被认为比YACC / Bison更容易使用。

In terms of personal taste, I think that LALR grammars are a lot easier to construct and debug. The downside is you have to deal with somewhat cryptic errors like shift-reduce and (the dreaded) reduce-reduce. These are errors that Bison catches when generating the parser, so it doesn't affect the end-user experience, but it can make the development process a bit more interesting. ANTLR is generally considered to be easier to use than YACC/Bison for precisely this reason.