代码之家 › 专栏 › 技术社区 › Don Wakefield

Antlr的优势(相对于Say,Lex/Yacc/Bison)[关闭]

bison yacc antlr c++

124

Don Wakefield · 技术社区 · 16 年前

在过去,我曾为各种项目使用lex和yacc(通常是bison),通常是翻译器(例如,edif的一个子集流到eda应用程序中)。此外,我还必须支持几十年前基于lex/yacc语法的代码。所以我知道如何使用这些工具,尽管我不是专家。

我以前在各种论坛上都看到过关于安特尔的正面评论,我很好奇我可能会错过什么。所以,如果你同时使用了两者,请告诉我什么是更好或更先进的ANTLR。我目前的限制是,我在一个C++商店中工作,并且我们装运的任何产品都不包括Java,所以最终的解析器必须遵循这个规则。

5 回复 | 直到 12 年前

1

134

chrisaycock spacemanspiff 12 年前

一个主要的区别是antlr生成一个ll(*)解析器,而yacc和bison都生成一个lalr解析器。这是许多应用程序的一个重要区别,最明显的是运算符:

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

Antlr完全无法处理这种语法。要使用antlr(或任何其他ll解析器生成器),您需要将此语法转换为非递归的语法。然而,野牛对这种形式的语法没有问题。您需要将“+”和“-”声明为左关联运算符,但这不是左递归的严格要求。一个更好的例子是分派:

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

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

注意这两个 expr 以及 actuals 规则保持递归。这在代码生成时产生了一个更高效的AST,因为它避免了多个寄存器和不必要的溢出(左树可以折叠,而右树不能)。

就个人品味而言,我认为LALR语法更容易构造和调试。缺点是你必须处理一些神秘的错误,比如移位减少和(可怕的)减少减少。这些都是Bison在生成解析器时捕捉到的错误,因此它不会影响最终用户体验,但它可以使开发过程更有趣。由于这个原因,一般认为Antlr比Yacc/Bison更容易使用。

2

102

trijezdci 15 年前

yacc/bison和antlr之间最显著的区别是这些工具可以处理的语法类型。yacc/bison处理lalr语法,antlr处理ll语法。

通常,与Lalr语法一起工作很长时间的人会发现与所有语法一起工作更困难,反之亦然。这并不意味着语法或工具本身就更难使用。你觉得哪个工具更容易使用,主要是为了熟悉语法类型。

就优势而言,有一些方面,拉尔语法比所有语法都有优势,还有一些方面,所有语法都比拉尔语法有优势。

yacc/bison生成表驱动的解析器,这意味着“处理逻辑”包含在解析器程序的数据中,而不是解析器代码中。回报是,即使是非常复杂语言的解析器,其代码占用空间也相对较小。在20世纪60年代和70年代,硬件非常有限,这一点更为重要。表驱动的解析器生成器可以追溯到这个时代,小代码占用是当时的主要需求。

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

ANTLR生成的解析器通常在10000行代码及更多代码附近。手写递归下降解析器通常位于同一个大致位置。Wirth的Oberon编译器可能是最紧凑的编译器,它有大约4000行代码,包括代码生成,但是Oberon是一种非常紧凑的语言,只有大约40条生产规则。

正如有人已经指出的,Antlr的一个大优点是图形化的IDE工具,称为AntlWorks。它是一个完整的语法和语言设计实验室。它在您键入语法规则时将其可视化,如果发现任何冲突,它将以图形方式向您显示冲突是什么以及导致冲突的原因。它甚至可以自动重构和解决冲突,如左递归。一旦您有了一个无冲突的语法,您就可以让AntlWorks解析您的语言的输入文件,并为您构建一个解析树和AST,并在IDE中以图形方式显示该树。这是一个非常大的优势,因为它可以节省您许多小时的工作:在开始编码之前,您将在语言设计中发现概念错误!我还没有为Lalr语法找到任何这样的工具,似乎没有这样的工具。

即使对于那些不希望生成解析器但手工编写代码的人来说,AntlWorks也是一个很好的语言设计/原型设计工具。很可能是最好的工具。不幸的是,如果您想要构建LALR解析器,这对您没有帮助。从LALR转换到LL只是为了利用AntlWorks可能是值得的,但是对于某些人来说,转换语法类型可能是一个非常痛苦的经历。换句话说:YMMV。

3

30

Cristian Diaconescu 15 年前

Antlr的几个优点:

可以输出各种语言的解析器,Java不需要运行生成的解析器。
出色的GUI使语法调试变得简单(例如,您可以在GUI中看到生成的AST,不需要额外的工具)
生成的代码实际上是人类可读的(这是ANTLR的目标之一),并且它生成ll解析器的事实在这方面肯定有帮助。
终端的定义也是上下文无关的(与(f)lex中的regex相反),因此允许,例如,定义终端包含右括号

我的02美元

4

8

John with waffle 16 年前

Antrl的另一个优点是可以使用 ANTLRWORKS 虽然我不能说这是一个严格的优势,因为其他发电机也可能有类似的工具。

5

7

Perception Paul 12 年前

Bison和Flex导致较小的内存占用,但您没有图形化的IDE。
Antlr使用更多的内存,但您有AntlWorks,一个图形化的IDE。

bison/flex内存的使用量通常是兆字节左右。与Antlr相比——假设它为您想要解析的文件中的每个令牌使用512字节的内存。400万个令牌,32位系统上的虚拟内存不足。

如果您希望解析的文件很大,那么antlr可能会耗尽内存,因此如果您只想解析一个配置文件,那么它将是一个可行的解决方案。否则,如果您想解析一个包含大量数据的文件,请尝试bison。