ANTLR一个编译简单的两数相加的例子

BuZhiDaoen 2007-06-12

如同程序设计语言入门大多采用“Hello World”一样,编译领域的入门往往选择计算器。一个只能计算两个数相加的计算器,也就是说,它可以计算“1+1”

编译过程分两步走:

1 先要能识别1+1这样的格式<o:p></o:p>

检查输入的正确性,只有对正确的输入进行计算才是有意义的。如同写文章有形式和内容之分,这里的检查也要细分一下,这个过程叫做词法分析。在我们的计算器中,我们只接受整数和加号,其它的一概不理。这里我们说的是“整数”,而非 “1”、“2”……,对我们来说,它们代表着同一类的东西,编译原理称为叫做token

编写语法文件<o:p></o:p>

制订好自己的语言规则之后,我们需要以Antlr的语言把它描述出来。

下面便是以Antlr的语言描述的语法:

classCaculatorParserextendsParser;

expr:   INT PLUS INT; <o:p></o:p>

class CaculatorLexer extends Lexer;

PLUS:'+';

INT   : ('0'..'9')+ ;<o:p></o:p>

Antlr的语法文件通常会保存在一个“.g”的文件中,我们的语法文件叫做“caculator.g”。<o:p></o:p>

先来看看Lexer部分,它便是我们前面所说的词法分析器。首先声明自己的Lexer:

classCaculatorLexerextendsLexer;

这句话有两个作用,其一,为生成代码中的词法分析器定义名字,其二,告诉Antlr,我要定义词法规则了。既然说到词法规则,紧接着我们就定义了两条词法规则:

PLUS:'+';

INT:('0'..'9')+;

这里的规则很容易看懂:

*PLUS定义的token,就是一个单一的“+”

* INT定义的token,由从'0'到'9'之间任意的数字组成,后面的加号表示它是可以重复一次到多次<o:p></o:p>

定义好Lexer之后,便轮到Parser了:

classCaculatorParserextendsParser;

它的作用同Lexer的定义一样,之后是语法规则:

expr:   INT PLUS INT;

<o:p> </o:p>

编译语法文件<o:p></o:p>

使用Antlr提供工具对我们的语法文件进行编译,不同 于日常的编译器输出可执行文件,这里的输出是程序语言的源文件。Antlr缺省目标语言是Java语言,它也可以支持C++和C#语言。<o:p></o:p>

将antlr.jar加到classpath中,然后把语法文件的名称作为参数传给语法编译器:java antlr.Tool caculator.g<o:p></o:p>

在确保命令正确执行,且语法文件编写正确的情况下,Antlr为我们生成了几个文件:

CaculatorLexer.java

CaculatorLexerTokenTypes.java

CaculatorLexerTokenTypes.txt

CaculatorParser.java

CaculatorParserTokenTypes.java

CaculatorParserTokenTypes.txt<o:p></o:p>

这里主要关心的是CaculatorLexer.java和CaculatorParser.java,它们就是我们在语法文件中定义的Lexer和Parser。其它几个文件只是定义了一些常量,让我们暂时忽略它们的存在。<o:p></o:p>

运行程序

生成代码之后,就是如何使用这些生成的代码。下面就是我们的主程序,它负责将Lexer和Parser驱动起来:

publicclassMain{

publicstaticvoidmain(String[]args)throwsException{

CaculatorLexerlexer=newCaculatorLexer(System.in);

CaculatorParserparser=newCaculatorParser(lexer);

try{

parser.expr();

}catch(Exceptione){

System.err.println(e);

}

}

}

从这段代码中可以清晰的看出,Lexer的输入是一个字符流,而Parser则需要Lexer的协助来完成工作。我们可以输入一些内容,看它是否能够通过验证。事实证明,我们的程序可以轻松识别“1+1”,而对于不合法的东西,它会产生一些异常。

2 可以对其编译进行计算。<o:p></o:p>

目标是计算出“1+1”的结果,而现在这个程序刚刚能够识别出“1+1”,还需要步骤。可以有两种方法来解析,分部是SAX和DOM方式:

SAX属于边解析边处理,而DOM则是把所有的内容解析全部解析完(在内存中形成语法树)之后,再统一处理。Antlr的SAX方式是在Parser中加入处理动作(Action)处理将随着解析的过程进行, 而DOM的伙伴则是解析形成一棵抽象语法树(Abstract Syntax Tree,AST),再对树进行处理。<o:p></o:p>

SAX方式:<o:p></o:p>

加入Action<o:p></o:p>

因为处理动作是加在Parser中的,所以,我们的Lexer保持不变,下面是修改过的Parser。

classCaculatorParserextendsParser;

exprreturns[intvalue=0]

:a:INTPLUSb:INT{

intaValue=Integer.parseInt(a.getText());

intbValue=Integer.parseInt(b.getText());

value=aValue+bValue;

};

这里有常用的字符串转整数的方法,这里定义Action的方法采用就是Java语言,因为我们生成的目标是Java,那这里的代码就要你需要的目标语言来编写。<o:p></o:p>

action完全是在原有的规则基础上改造的来。首先用returns定义了这个Action的返回值,它将返回value这个变量的值,其类型是int,我们还顺便定义这个变量的初始值——“<st1:chmetcnv unitname="”" sourcevalue="0" hasspace="False" negative="False" numbertype="1" tcsc="0" w:st="on">0”</st1:chmetcnv>。接下来,用a、b拿住了两个token的值,我们前面说过,在检查的过程中,我们并 不关心每个token具体的内容,只要token的类型满足需要即可,但在action中,我们要计算结果,那必须使用token具体的内容,所以,我们 用变量拿住了token。在生成的代码中,a的类型antlr.Token,因此,我们通过a.getText()来获得token的具体值。剩下的动作 就很简单了,把文本转换为数字,进行加法运算。<o:p></o:p>

然后生成全新的Parser。稍微修改一下主程序,就可以对1+1进行编译计算了

publicclassMain{

publicstaticvoidmain(String[]args)throwsException{

CaculatorLexerlexer=newCaculatorLexer(System.in);

CaculatorParserparser=newCaculatorParser(lexer);

try{

System.out.println(parser.expr());

}catch(Exceptione){

System.err.println(e);

}

}

}

在输入的时候 输入1+1 就可以得到结果了。

<o:p> </o:p>

DOM方式

使用DOM方式,首先需建立一个AST语法树:

建立AST的方式很简单,只要我们Antlr一个建立AST的选项即可,下面就是新的Parser:

class CaculatorParser extends Parser;<o:p></o:p>

options {

buildAST=true;

}<o:p></o:p>

expr:   INT PLUS^ INT;<o:p></o:p>

稍微有些不同的地方在PLUS上面的“^”,这个符号用来告诉Antlr创建一个节点,以此作为当前树的根节点。<o:p></o:p>

下面将DOM方式的重点部分TreeParser:class CaculatorTreeParser extends TreeParser;<o:p></o:p>

expr returns [int value = 0;]  //定义规则

:#(PLUSa:INTb:INT){

intaValue=Integer.parseInt(a.getText());

intbValue=Integer.parseInt(b.getText());

value=aValue+bValue;

};

Antlr 可以接受三种类型语法规范——Lexer、Parser和Tree-Parser。如果说Lexer处理的是字符流、Parser处理的是Token流, 那么TreeParser处理的则是AST。前面Action的处理方式中,我们看到,规则同处理放到了一起,显得有些混乱,而采用了AST的处理方式, 规则同处理就完全分离了:在Parser中定义规则,在TreeParser中定义处理,如果我们需要对同样的语法进行另外的处理,我们只要重新 TreeParser,从而降低耦合度,Hibernate采用的就是这种方式!!<o:p></o:p>

可以参考前面ACTION,来看TreeParser如何编写也就简单许多,需要说明的就是:

#(PLUSa:INTb:INT)

除去变量的说明,简化一下这段代码

#(PLUSINTINT)

第一个符号PLUS对应了表示着根节点,两个INT则分别代表了两棵子树。<o:p></o:p>

再来看看重新打造的主程序

publicclassMain{

publicstaticvoidmain(String[]args){

CaculatorLexerlexer=newCaculatorLexer(System.in);

CaculatorParserparser=newCaculatorParser(lexer);

try{

parser.expr();

ASTt=parser.getAST();

CaculatorTreeParsertreeParser=newCaculatorTreeParser();

System.out.println(treeParser.expr(t));

}catch(Exceptione){

System.err.println(e);

}

}

}<o:p></o:p>

在输入的时候 输入1+1 就可以得到结果了。

<o:p> </o:p>

由此再参考Hibernate的处理方式,会发现很容易理解:<o:p></o:p>

Session s = factory.openSession();<o:p></o:p>

List auctions = s.createQuery("…");<o:p></o:p>

createQuery()的调用过程<o:p></o:p>

通过QueryPlanCache的getHQLQueryPlan()方法获得查询计划HQLQueryPlan的一个实例,而后者主要是调用了 QueryTranslator的compile方法,编译HQL语句。在QueryTranslator的继承类 QueryTranslatorImpl的doCompile观察这个过程:<o:p></o:p>

PHASE 1 : Parse the HQL into an AST.<o:p></o:p>

PHASE 2 : Analyze the HQL AST, and produce an SQL AST.<o:p></o:p>

PHASE 3 : Generate the SQL.<o:p></o:p>

相关推荐