分享
 
 
 

利用ANTLR生成C++描述的分析程序

王朝c/c++·作者佚名  2007-02-08
窄屏简体版  字體: |||超大  

摘要

ANTLR(ANother Tool for Language Recognition)是一种基于LL(k)文法的语法分析程序(以下简称分析器)生成工具。其生成的分析器默认使用Java描述,而不是更高效的C++。本文介绍了在Windows平台下,借助VC6.0进行组织工程,使用ANTLR生成C++描述的分析器的方法,并给出了一个实例。最后,本文对ANTLR本身做出了一点小小的改进。

关键字

ANTLR,语法分析器,语法分析器生成工具

ANTLR简介

分析器的自动生成一直是编译理论研究的一个方向。早期的程序员手工编写分析器,不但费时费力,而且编写的分析器不稳定、不易修改和移植。在自动化大潮冲击之下,越来越多的程序员抛弃了这种手工做法。

由旧金山大学的Terence Parr 领导开发的ANTLR(以前叫做PCCTS,Purdue Compiler Construction Tool Set,普渡大学编译器构建工具集)是一种分析器自动生成工具,它可以接受语言的文法描述,并能产生识别这些语言的程序。而且我们可以在文法描述中插入特定的语义动作,告诉ANTLR怎样去创建抽象语法树(AST)和怎样产生输出。

现在ANTLR越来越流行(有评论说ANTLR的出现是一个里程碑),不仅因为它功能更强、容易扩展、开源,而且ANTLR生成的代码和使用递归下降方法(手工生成分析器的主要方法)生成的代码很相似,易于阅读理解。与之相比,另外一种著名的分析器生成工具YACC(Yet Another Compiler-Compiler,基于LR分析方法)生成的程序就比较晦涩。

目前国内介绍ANTLR的文章不多,仅有的文章也是介绍使用ANTLR生成使用java描述的分析器。其实ANTLR也可以生成C++描述的源程序(从2.7.3版本开始,ANTLR开始支持C#,将来还会支持Python),不过需要一些准备工作。本文将详细地介绍其中的具体步骤。

最新版本的ANTLR可以去ANTLR的官方网站(http://www.ANTLR.org)下载。截止到2004年6月,ANTLR的最新版本是2.7.4。下载的文件是一个不到1.3M的tar.gz形式的压缩包,将其解压到某个目录(下文用<ANTLRpath>表示)。

ANTLR是使用Java开发的,需要JDK的支持。本文假设您的机器已经安装JDK,并正确设置了classpath。

文法文件

文法就是语言识别的规则。它是ANTLR生成程序的依据。文法文件是ANTLR的核心,是程序员和ANTLR进行交流的接口。

文法文件的编写基本是面向被解决的问题的。程序员只需要集中精力思考解决问题的逻辑,而不是羁绊于某种程序设计语言的实现细节,因此降低了出现错误的可能性。

文法文件的语法简介

本文只是简单地介绍一个文法文件的语法,具体内容可以参阅ANTLR的相关文档。

文法文件一般包括header块、options块、文法分析器类(parser)及规则定义、词法分扫描器类(lexer)及token定义。其中最为重要的是规则和token的定义。

规则的定义形式和编译理论中的扩展巴科斯范式(EBNF)极为相似,包括规则名、规则体、一个用作结束标志的分号和异常处理部分(可省略)。例如如下的规则就描述了C语言中的赋值语句的语法:

assignment_stat:

id '=' expr ';'

;

其意义是:一条赋值语句是由一个id、一个等号、一个表达式和一个分号顺序组成的。

Token的定义方法与规则类似。例如如下的token定义就表示一个十进制的整数:

NUM:

('1'..'9')('0'..'9')*

;

其意义是:数字(NUM)的第一字符是‘1’到‘9’中的一个字符,后面是0个或多个‘0’到‘9’之间的字符。

需要注意的一点是:规则的名字必须是小写字母开始,而token的名字则必须是大写字母开始。

设定ANTLR生成的语言

ANTLR有很多选项,可以通过在文法文件中的options块中进行设置,其中包括ANTLR最终生成的语言。如果要生成C++描述的分析器程序,就要如下设定:

options

{

language="Cpp";

// Other options

}

language选项的默认值是“Java”。如果您希望生成的程序是C#的,将language设为“Csharp”就可以了。

C++程序的例子

下面就给出一个ANTLR生成的C++描述的分析器的实例。该分析器的功能是分析用户输入的一个算术表达式,给出该表达式的最终结果。在该表达式中允许出现的运算符除了加减乘除之外,还包括求幂运算符“^”,以及sin、cos和tan三个三角函数。

在开始之前,我们首先要生成编译链接ANTLR生成的程序时需要的库文件。

构建静态链接库

构建(build)由ANTLR生成的C++程序需要一个运行库的支持。该运行库的源代码也是完全开放的,位于<ANTLRpath>\antlr-2.7.4\lib\cpp目录下。我们可以选择这些代码其编译为静态链接库或者动态链接库。对于2.7.4版本的ANTLR,编译动态链接库需要VC7.0以上的编译环境。这里我们将其编译为静态库。

首先使用VC6.0新建一个名为ANTLRLib的Win32的静态链接库的工程,不要选择“Pre-compiled Header”和“MFC support”选项。

点击菜单“Project”à“Add to Project”à“Files…”,将Antlr-2.7.4\lib\cpp\src下面的除了dll.cpp之外的所有文件加入到工程中(注意一定不要加入dll.cpp,否则无法通过编译)。

为了让VC6.0找到所需要的头文件,需要将<ANTLRpath>\antlr-2.7.4\lib\cpp加入到头文件搜索路径中。具体方法是点击“Project”à“Settings…”,在弹出的对话框中选择“Debug”标签页,在下拉列表中选择“Preprocessor”,在“Additional include path”中,如图填入:

<ANTLRpath>\antlr-2.7.4\lib\cpp

此时build整个工程,就可以生成ANTLR的运行库文件ANTLRLib.lib(有些文档说需要在工程设置中开启RTTI选项,但是似乎不这样做也没有太大的影响)。

编写文法文件

根据需求,不难写出如下的文法文件:

header{

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

}

options

{

language="Cpp";

}

class ExprParser extends Parser;

{

}

// rules

expr returns [double value=0]

{double x;}

:

value=term

(

PLUS x=term {value+=x;}

|

MINUS x=term{value-=x;}

)*

;

exception

catch [ANTLR_USE_NAMESPACE(antlr)ANTLRException& ex] {

// catch all exceptions and report it

reportError(ex.toString());

}

term returns [double value=0]

{double x;}

:

value=factor

(

STAR x=factor {value*=x;}

|

SLASH x=factor { value /= x;}

)*

;

factor returns [double value =0 ]

{double x;}

:

value = atom

(

TOK_POW x = atom { value = pow(value,x); }

)*

;

atom returns [double value=0]

{double x;}

:

i:NUM

{

value=atof((i->getText()).c_str());

}

|

TOK_SIN x = atom { value = sin (x);}

|

TOK_COS x = atom { value = cos (x);}

|

TOK_TAN x = atom { value = tan (x);}

|

LPAREN value=expr RPAREN

;

exception

catch [ANTLR_USE_NAMESPACE(antlr)ANTLRException& ex] {

reportError(ex.toString());

}

class ExprLexer extends Lexer;

options{

k=1;

caseSensitive = false;

}

// tokens

LPAREN :'(';

RPAREN :')';

PLUS :'+';

MINUS :'-';

STAR :'*';

SLASH :'/';

NUM :('0'..'9')('0'..'9')*('.'('0'..'9')*)?;

RETURN :'\n';

// math token

TOK_SIN :"sin";

TOK_COS :"cos";

TOK_TAN :"tan";

TOK_POW :'^';

// white space

WS :

(

' '

|

'\t'

)

{$setType(ANTLR_USE_NAMESPACE(antlr)Token::SKIP);}

;

将该文件保存为test.g(‘g’是默认的文法文件的扩展名)。

在该文法文件中,定义了一个分析器类ExprParser和一个词法扫描器类ExprLexer。ANTLR会为两个类分别生成头文件和实现文件。

使用VC6.0组织工程

现在需要由文法文件生成分析器的源代码,然后再添加其他的一些代码,最后编译这些代码,过程略显繁琐。因此这里借助VC6.0作为开发环境来组织工程,简化步骤。

新建工程

使用VC6.0新建一个名为AntlrCpp的Win32控制台的项目。选择新建一个空的工程。点击“Project”à“Add To Project”à“Files”,将文法文件test.g添加到工程中。

在VC的FileView中右键点击该文法文件,在弹出菜单中选择“Settings…”,弹出如图所示的对话框,选择“Custom Build”标签页,如图所示:

在“Commands”里面填入调用ANTLR编译文法文件的命令:

java -cp <ANTLRpath>\antlr-2.7.4\antlr.jar antlr.Tool -o "$(WkspDir)" $(InputName).g

在“Outputs”里面填入ANTLR编译文法文件后要生成的所有文件的名字,如下:

ExprLexer.cpp

ExprLexer.hpp

ExprParser.cpp

ExprParser.hpp

ExprParserTokenTypes.hpp

ExprParserTokenTypes.txt

生成分析器源代码

设置完成之后,就可以编译该文法文件了:选中该文法文件,按Ctrl+F7(或者点击工具栏中的编译按钮),执行编译操作。在VC的Output窗口里面会显示出如下的内容:

--------------------Configuration: AntlrCpp - Win32 Debug--------------------

Performing Custom Build Step on .\testjava.g

ANTLR Parser Generator Version 2.7.4 1989-2004 jGuru.com

ExprLexer.cpp - 0 error(s), 0 warning(s)

此时,分析器的源代码已经生成。再次点击菜单“Project”à“Add To Project”à“Files”,将生成的所有cpp文件和hpp文件添加到工程中。

指定输入方式

ANTLR生成的源代码只是分析器的核心部分,程序员还需要指定分析器的输入。为此还需要新建一个main.cpp文件,指定分析器的输入。

若希望让分析器分析通过键盘输入的字符串,则代码如下:

#include "ExprParser.hpp"

#include "ExprLexer.hpp"

#include <iostream>

using namespace std;

void main()

{

ExprLexer lexer( cin );

ExprParser parser( lexer );

double x = 0;

x = parser.expr();

cout << "The Result is :" << x << endl;

}

若希望让分析器分析一个文件里面的字符串的话,则相应代码如下:

#include "ExprParser.hpp"

#include "ExprLexer.hpp"

#include <iostream>

#include <fstream>

using namespace std;

void main()

{

fstream from("test.in");

ExprLexer lexer(from);

ExprParser parser( lexer );

double x = 0;

x = parser.expr();

cout << "The Result is :" << x << endl;

}

编译得到最终的结果

在构建工程之前,也需要让VC6.0知道上哪里去找所需的头文件。添加头文件搜索路径的方法前面已经介绍过,不再赘述,如图所示。

如果现在就Build工程的话,您一定会看到很多的链接错误。这是因为编译后的目标文件没有和运行库链接在一起。指定链接库的方法是在上面的设置工程属性的对话框中选择“Link”标签页,在“Object/library modules:”中加入“antlrlib.lib”(要注意正确的路径)。

此时就可以Build整个工程了。生成的可执行文件运行的效果如图所示:

对ANTLR一个小小改进

ANTLR的下载文件中包括了全部的源代码,而且允许修改。我们可以针对自己的特殊需要改进ANTLR。

问题的提出

如果在某条规则(经过ANTLR编译后就会变为一个函数)中,指定了参数的默认值,那么在生成的程序中,我们可能看到相应函数的实现中,隐去了该参数的默认值(否则就会违反C++的语法)。但是考虑到程序的可读性,我们希望做出一点改进:在函数实现中,将参数的默认值使用注释符号(“/*”和“*/”)括起来,而不是完全的隐去。

代码的修改

找到<ANTLRpath>\antlr-2.7.4\antlr\cppcodegenerator.java文件,修改其3502行到3526行。原来的程序为:

String oldarg = rblk.argAction;

String newarg = "";

String comma = "";

int eqpos = oldarg.indexOf( '=' );

if( eqpos != -1 )

{

int cmpos = 0;

while( cmpos != -1 )

{

newarg = newarg + comma + oldarg.substring( 0, eqpos ).trim();

comma = ", ";

cmpos = oldarg.indexOf( ',', eqpos );

if( cmpos != -1 )

{

// cut off part we just handled

oldarg = oldarg.substring( cmpos+1 ).trim();

eqpos = oldarg.indexOf( '=' );

}

}

}

else

newarg = oldarg;

println( newarg );

修改如下:

String oldarg = rblk.argAction;

String newarg = "";

String comma = "";

int eqpos = oldarg.indexOf( '=' );

if( eqpos != -1 )

{

int cmpos = 0;

while( cmpos != -1 )

{

newarg = newarg + comma + oldarg.substring( 0, eqpos ).trim() + " /* ";

comma = ", ";

cmpos = oldarg.indexOf( ',', eqpos );

if( cmpos != -1 )

{

// get the default value of the argument

newarg = newarg + oldarg.substring( eqpos, cmpos ) + " */ ";

// cut off part we just handled

oldarg = oldarg.substring( cmpos+1 ).trim();

eqpos = oldarg.indexOf( '=' );

}else {

newarg = newarg + oldarg.substring( eqpos ).trim() + " */";

}

}

}

else

newarg = oldarg;

println( newarg );

重新编译ANTLR

重新编译ANTLR的步骤是:

开启一个命令行的环境,改变当前路径为<ANTLRpath>\antlr-2.7.4\antlr\build,输入如下命令:

javac *.java

然后改变当前路径为<ANTLRpath>\ antlr-2.7.4,输入如下命令,编译源程序:

java -cp <ANTLRpath>\antlr-2.7.4\antlr.jar antlr.build.Tool build

最后重新生成jar文件,输入如下命令:

java -cp <ANTLRpath>\antlr-2.7.4\antlr.jar antlr.build.Tool jar

至此,ANTLR已经被更新。

总结

经过本文的介绍,相信您对ANTLR有了更多的了解。充分利用ANTLR可以极大的减轻编写分析的负担。结合高效的C++,ANTLR生成的分析器的效率和手工编写的分析器相差不多。相信ANTLR会有美好的明天。

编译环境

Windows2000 SP4,VC6.0,ANTLR 2.7.4,J2SDK 1.4.1

参考文献

ANTLR-2.7.4文档

www.antlr.org

ANTLR: A Predicated-LL_k_ Parser Generator,T. J. PARR,SOFTWARE-PRACTICE AND EXPERIENCE, VOL. 25(7), 789–810(JULY1995)

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有