ANTLR指南v30.docx
《ANTLR指南v30.docx》由会员分享，可在线阅读，更多相关《ANTLR指南v30.docx（58页珍藏版）》请在冰点文库上搜索。
ANTLR指南v30
ANTLR指南（v3.0）
第一章HelloWorld
ANTLR是ANotherToolforLanguageRecognition的缩写“又一个语言识别工具”。
从名字上可以看出在ANTLR出现之前已经存在其它语言识别工具了（如LEX[1]，YACC[2]）。
ANTLR的官方定义为：
根据一种可以嵌入如Java,C++或C#等辅助代码段的文法，来构筑出相对该文法的识别器，编译器或翻译器的一种语言工具框架。
这个定义说明了ANTLR的功能是根据给定文法自动生成编译器，其过程为先编写相应语言的文法然后生成相应语言编译器。
定义提到的语言识别器，编译器和翻译器我们以后统称为语法分析器。
事实上ANTLR是生成相应语言编译器的源代码，我们还需要编译它。
那么ANTLR可以生成哪些方语言的语法分析器源代码语言的代码呢？
这是程序员很关心的问题。
幸运的是ANTLR现在已经支持了多种当前流行的开发语言，包括Java、C#、C、C++、Objective-C、Python和Ruby.1等。
你可以根据需要生成其中任何一种语言的语法分析器。
本书主要介绍java，C#两种语言，有详细的操作步骤包括如何编译、执行和如何使用ANTLRWorks开发环境编写文法等。
读者可以顺利上手，避免实际操作的障碍。
后面章节还会指出在Java和C#开发中应注意的细微差别，确保程序的顺利运行。
1.1开发HelloWorld示例
本章将开发一个简单示例让读者对ANTLR有一个初步的认识，并搭建开发环境以便后续的学习。
读者在示例中遇到不懂的地方也不必担心，我们的目的是搭建开发环境学会编译运行语法分析器。
用ANTLR开发一个语法分析器大致分三步，第一步：
写出要分析内容的文法。
第二步：
用ANTLR生成相对该文法的语法分析器的代码。
第三步：
编译运行语法分析器。
和多数编译书籍一样，本章也用解析简单的表达式作为示例。
要解析的表达式中有二种数据类型：
整数如“23”,“5”和字符串如“HelloWorld”。
表达式中以算术表达式为主也包括赋值表达式。
我们列举两个表达式语句：
23+4*（5+1）;str=“HelloWorld”;
第一条语句是一个算术表达式，括号改变了运算顺序，计算结果不赋给任何变量。
第二条是一个赋值表达式，将字符串赋给一个变量。
后面我们要开发一个语法分析器来分析这两条语句。
在开发之前先简单提一下语法树的概念，在语法分析中一般用树来表示语法结构，表达式的语法树是以操作符为根节点操作数为子节点的树形结构，23+4*（5+1）的语法树根据操作符的优先级如下。
图1.1
算术表达式先计算5+1，5+1在括号中操作符的优先级最高在语法树中的深度最大，然后是4*（5+1），最后是23+4*（5+1）。
可以看出语法树的求值顺序是从下向上的，先计算深度大的操作符5+1结果为6，然后是4*6结果为24，然后是23+24表达式的结果为47。
下面再看一下赋值表达式的语法树结构：
图1.2
赋值操作符“=”做为根节点变量str作为左子树，而字符串表达式“HelloWorld”作为右子树。
了解了语法树后我们开始录入文法源文件。
ANTLR中文法文件是扩展名为“.g”的文本文件，“.g”文件就是我们的源文件。
这里新建一个叫“E.g”的文法文件，在文件中输入如下文法定义：
grammarE;
options{output=AST;}
program:
statement+;
statement:
（expression|VAR'='expression）';';
expression:
（multExpr（（'+'|'-'）multExpr）*）|STRING;
multExpr:
atom（'*'atom）*;
atom:
INT|'（'expression'）';
VAR:
（'a'..'z'|'A'..'Z'）+;
INT:
'0'..'9'+;
STRING:
'"'（（'A'..'Z'|'a'..'z'|''）+）'"';
WS:
（''|'\t'|'\n'|'\r'）+{skip（）;};
文件的第一行grammarE的E为文法的名称它与文件名一致。
第二行是文法的设置部分options{output=AST;}，output=AST表示让语法分析器返回包含语法树的信息。
第三行开始是文法定义部分，文法是用EBNF1推导式来描述的（有关EBNF会在后面章节中讲解），文法定义中分两大部分以小写字母开头的语法描述和全大写的词法描述。
其中每一行都是一个规则（rule）或叫做推导式、产生式，每个规则的左边是文法中的一个名字，代表文法中的一个抽象概念。
中间用一个“:
”表示推导关系，右边是该名字推导出的文法形式。
下面逐行介绍文法的规则定义：
statement:
（expression|VAR'='expression）';'
statement代表表达式语句，前面说了语句有两种，在推导式中以“|”分隔代表“或”关系。
表达式本身是合法的语句，表达式也可以出现在赋值表达式中组成赋值语句，两种语句都以“;”字符结束。
expression:
（multExpr（（'+'|'-'）multExpr）*）|STRING
expression代表表达式，“|”的左边是算术表达式的形式，“|”的右边是字符串表达式。
我们通过规则的推导顺序可以看出，规则按操作符的优先级首先推导优先级最低的运算“+”，“-”运算。
multExpr:
atom（'*'atom）*;
然后是'*'的运算。
为了使示例简单，表达式中没有除法运算。
atom:
'（'expression'）'|INT;
最后是“（）”运算，括号中又可以是一个表达式，这样也就实现了括号的嵌套关系。
以“|”分隔与括号并列的可以出现参与运算的整型数。
VAR:
（'a'..'z'|'A'..'Z'）+;
INT:
'0'..'9'+;
STRING:
'"'（（'A'..'Z'|'a'..'z'|''）+）'"';
WS:
（''|'\t'|'\n'|'\r'）+{skip（）;};
以大写形式表达的是词法描述部分，VAR表示变量由一个或多个大小写字母组成，INT表示整型，整型由一个或多个0到9的数字组成，STRING表示字符串，和变量类似一个或多个大小写字母组成但要用“"”括起来。
WS表示空白，它的作用是可以滤掉空格、TAB、回车换行这样的无意义字符。
{skip（）;}的作用是跳过这些字符。
1.2下载ANTLR
本章我们的目的是运行第一个示例，后面章节会详细介绍文法定义的写法，所以暂时有不清楚的地方不必担心。
这里应该注意的是：
文法中单词的大小写，ANTLR文法是大小写敏感的，文法名称要和文件名一致。
下面我们用ANTLR生成该文法的java分析器代码。
我们先下载ANTLR的Runtime和开发环境，到http:
//www.antlr.org/download.htmlANTLR的下载页，www.antlr.org为ANTLR的官方网站，ANTLR是一个开源项目可以免费下载。
图1.1为开发环境ANTLRWorks的下载页面，图1.2为开发环境ANTLRRuntime3.01的下载页面。
您的机器上需要安装JDK1.5或更高版本的javaSDK。
其中ANTLRWorks的下载文件名叫antlrworks-1.1.7.jar安装JDK后可以直接双击运行打开ANTLRWorks开发环境。
（图1.3）ANTLRWorks下载页面
（图1.4）ANTLRRuntime下载页面
（图1.5）ANTLRWorksIDE
1.3Java环境的运行
下面录入文法文件，运行ANTLRWorks点击“File–New”菜单新建文法文件，在新文件中将前面的文法录入。
（我的网站中有本书所有示例源代码，但我建议您还是手工录入一遍。
这样您会有更好的学习效果。
）录入文法后点击“File–Save”菜单文件名为“E.g”。
然后点击“Generate–GenerateCode”，如果ANTLRWorks提示“Thegrammarhasbeensuccessfullygeneratedinpath…”说明ANTLRWorks成功生成了语法分析器的代码。
会在“E.g”的当前目录中生成“ELexer.java”、“EParser.java”、“E.tokens”和“E__.g”四个文件，其中有两个java源文件。
“ELexer.java”为词法分析部分的代码，“EParser.java”为语法分析部分的代码。
那么为什么会生成java代码呢？
ANTLR在不指定目标语言的情况下默认是java语言。
我们也可以在文法文件中加入options项指定目标语言。
grammarE;
options{output=AST;language=Java;}
program:
statement+;
……
生成了代码后，我们来编译运行语法分析器。
刚才生成的是java代码，所以先来看看java如何编译运行。
首先要有一个执行程序的main方法，这个类如下：
importorg.antlr.runtime.*;
importorg.antlr.runtime.tree.*;
publicclassrun
{
publicstaticvoidmain（String[]args）throwsException
{
ANTLRInputStreaminput=newANTLRInputStream（System.in）;
ELexerlexer=newELexer（input）;
CommonTokenStreamtokens=newCommonTokenStream（lexer）;
EParserparser=newEParser（tokens）;
EParser.program_returnr=parser.program（）;
System.out.println（（（BaseTree）r.getTree（））.toStringTree（））;
}
}
把这段代码存入run.java文件中，main方法功能是从命令行接收输入的表达式，通过词法分析和语法分析两个步骤来获得这个表达式的语法树，并以字符串的形式输出语法树的内容。
ANTLRInputStreaminput=newANTLRInputStream（System.in）;
ELexerlexer=newELexer（input）;
CommonTokenStreamtokens=newCommonTokenStream（lexer）;
词法分析步骤是从命令行接收输入的表达式，通过ANTLR内部ANTLRInputStream类，生成一个ANTLRInputStream类的实例input，再将input传给ELexer类。
ELexer类是词法分析类，把input中的输入内容进行词法分析，词法分析后会产生词号流（tokenstream）交给语法分析类，为语法分析提拱前提。
EParserparser=newEParser（tokens）;
EParser.program_returnr=parser.program（）;//此处进行了语法分析
System.out.println（（（BaseTree）r.getTree（））.toStringTree（））;
语法分析步骤是根据词法分析产生的词号流生成语法分析类的实例parser。
然后调用parser的方法program（）。
这个方法名和我们文法中的第一条规则program:
statement+;的名字是一致的，这说明我们要用整个文法进行分析，program是文法的启点。
调用program（）方法后就进行了语法分析，program（）方法返回语法分析的信息其中包括语法树。
r.getTree（）可以返回语法树，getTree（）返回的是Object类型所以这里做一个类型转换（BaseTree）r.getTree（）并调用其toStringTree（）方法获得语法树的字符串形式输出。
到现在完成了源代码的录入工作，接下来编译所有的代码。
编译的命令行字符串为：
javac-classpath.;.....\antlr-3.0.1\lib\antlr-3.0.1.jar*.java
run.java中的importorg.antlr.runtime.*;importorg.antlr.runtime.tree.*;所引用的类包含在antlr-3.0.1.jar中，解压我们之前下载的antlr-3.0.1.tar.gz文件，在其中的lib目录中可以找到antlr-3.0.1.jar。
编译字符串中的-classpath参数中给出.....\antlr-3.0.1\lib\antlr-3.0.1.jar的实现路径。
运行程序的命令行字符串与编译字符串相似：
java-classpath.;.....\antlr-3.0.1\lib\antlr-3.0.1.jarrun
好的我们来执行这两个字符串来编译并执行程序，执行程序后命令行光标会等待输入，把之前准备分析的两个表达式输入，然后按Ctrl+Z（Windows系统Ctrl+Z，UNIX系统Ctrl+D）表示输入结束，然后回车。
23+4*（5+1）;
str="helloworld";
^Z
23+4*（5+1）;str="helloworld";
程序输出23+4*（5+1）;str="helloworld";这表示程序执行成功了。
我们的语法分析器已经正确的解析了这两个表达式。
您可以试着用不规则的格式输入两个表达式会得到相同的输出，因为已经正确分析了表达式的语法，所以输出格式化的字符串对我们的分析器来说是很简单的事情了。
23+4*（5+1
）;str
="helloworld"
;
^Z
23+4*（5+1）;str="helloworld";
1.4.NET环境的运行
我们再说说.NET的编译执行。
首先生成C#的语法分析器代码，在文法中的options设置中修改目标语言为CSharp，还要把WS中的skip（）改成Skip（）。
Java版和.NET版的ANTLRRuntime都使用了各自语言的命名规范，所以名称上略微有些区别。
options{output=AST;language=CSharp;}
……
WS:
（''|'\t'|'\n'|'\r'）+{Skip（）;};
然后用ANTLRWorks中的Generate菜单生成代码，这时目录中会生成四个文件“ELexer.cs”、“EParser.cs”、“E.tokens”和“E__.g”。
E.tokens和E__.g文件与之前Java开发中生成的两个同名文件是一样的，另外ELexer.cs为词法分析器，EParser.cs为语法分析器。
在.NET开发中我们采用VisualStudio.NET2005做为开发环境，让我们的示例和真正的开发贴近一些。
在VisualStudio.NET2005中先新建一个名称为“HelloWorld”的C#WindowApplication项目，将生成的ELexer.cs、EParser.cs文件拷贝并加入到项目中。
再将.NET版的ANTLRRuntime的DLL引用到项目中来。
本示例需要Antlr3.Runtime.dll和antlr.runtime.dll，这两个文件在antlr-3.0.1.tar.gz解压后的antlr-3.0.1\antlr-3.0.1\runtime\CSharp\bin\net-2.0目录中可以找到。
这些操作都完成之后，我们在程序窗体上放一个多行文本框，一个按钮和一个Label。
在窗体的代码文件Form1.cs中加入：
usingAntlr.Runtime;
usingAntlr.Runtime.Tree;
我们要实现在文本框中输入表达式语句，点击按钮语法树结果显示在Label控件中。
在按钮的事件中加入如下代码：
ICharStreaminput=newANTLRStringStream（textBox1.Text）;
ELexerlex=newELexer（input）;
CommonTokenStreamtokens=newCommonTokenStream（lex）;
EParserparser=newEParser（tokens）;
EParser.program_returnprogReturn=parser.program（）;
label1.Text=（（BaseTree）progReturn.Tree）.ToStringTree（）;
这里由于表达式是从界面文本框中获得，所以第一行代码和上面java的示例有些不同使用ANTLRStringStream类来接收录入的内容。
后面的代码和java版本中的几乎一致，只是有一些java与.NET在命名规则方面的区别。
Java方法名首字母为小写而.NET是大写。
（图1.6）.NET版HelloWord的运行结果
1.5改进示例
到此我们已经学习了java和.NET开发语法分析器的全过程。
读者可能觉得做完这个示例成就感不大，因为输入和输出是一样的，并没有看到前面提到的语法树结构。
下面我们修进一下示例在文法中添加一些构造语法树的符号，使程序构造出如图1.1、图1.2的语法树。
文法修改如下：
grammarE;
options{output=AST;}
program:
statement+;
statement:
（expression|VAR'='^expression）';';
expression:
（multExpr（（'+'^|'-'^）multExpr）*）|STRING;
multExpr:
atom（'*'^atom）*;
atom:
INT|'（'!
expression'）'!
;
VAR:
（'a'..'z'|'A'..'Z'）+;
INT:
'0'..'9'+;
STRING:
'"'（（'A'..'Z'|'a'..'z'|''）+）'"';
WS:
（''|'\t'|'\n'|'\r'）+{skip（）;};
修改后的文法中所有操作符的后面都添加了一个“^”符号，这表示操作符会在构造语法树时作为根节点。
“statement:
（expression|VAR'='^expression）';'!
;”一行中的“;”字符与“atom:
INT|'（'!
expression'）'!
;”的“（）”字符后面添加了“!
”符号，表示不让“（）”和“;”出现在语法树中，因为语法树已经体现了操作求值顺序，所以括号没有必要出现在语法树中。
代表语句结束的“;”是为语法分析服务的，语法分析后语法树中的也没有必要加入“;”。
我们会在以后的章节中更详细讲解如何构造语法树。
现在先用修改后的文法来生成代码，编译运行程序，输入同样的表达式我们会得到如下结果：
23+4*（5+1）;
str="helloworld";
^Z
（+23（*4（+51）））（=str"helloworld"）
程序的输出结果了发生了变化：
算术表达式的语法树输出字符串形式为：
（+23（*4（+51）））我们已经使“（）”不出现在语法树中了，所以输出字符串中的括号并不是我们输入的表达式括号，这些括号表示语法树的结构。
由于我们让操作符为根节点，所以这里“+”、“*”操作符出现在前面，其后是它的左子树，再往后是它的右子树，内层括号是外号括号子树。
按照这个规则我们可以绘出语法树：
+
23*
4+
51
绘出语法树和前面图1.1中的语法树是一样的，这说明我们已经正确的生成了语法树。
赋值表达式亦然。
我们可以在VisualStudio.NET2005中运行。
在程序中设置断点并查看progReturn.Tree的对象内存情况。
图1.7
语法树是BaseTree类型，BaseTree有一个children集合用来存放子语法树，子语法树也是BaseTree类型，可以利用VS.NET内存监视功能一级一级展开，看一看ANTLR的语法树的对象表现形式。
BaseTree类有一个GetChild（inti）方法可以获取第N个子树，还有一个ChildCount属性代表子树的个数。
结合这两个属性和方法可以用如下的代码遍历子语法树。
for（inti=0;iBaseTreecurrTree=（BaseTree）tree.GetChild（i）;
}
1.5本书结构
好，完成HelloWorld示例的开发后，先来介绍一下本书的结构。
本书后面章节大体顺序是：
先学习文法、推导式等编译原理基础知识，使没有编译原理知识基础的读者铺平道路。
然后全面学习ANTLR开发技术，主要包括词法、语法、语法树以及字符模板的内容。
在ANTLR全学习之后再强化学习一下编译原理的知识（如DFA）然后学习如何解决ANTLR开发中的较难的问题。
第二章：
编译原理基础知识。
第三章：
词法分析。
第四章：
语法分析。
第五章：
嵌入文法中的代码。
第六章：
构造语法树。
第七章：
字符串模板。
第八章：
编译错误处理。
第九章：
进一些学习编译原理知识。
第十章：
文法编写中的错误。
第十一章：
ANTLRAPI。
第十二章：
开发实例。
1.6本章小结
本章开发表达式语法分析器示例详细地向读者介绍了ANTLR的开发过程，如何建立ANTLR的开发环境以及如何在Java和.NET环境中编译和运行程序。
本书后面出现的示例希望读者都要亲手完成，只有亲自做出正确运行的程序才算是真正学会。
Java,C,C++,C#,Objective-C,Python,andRuby.1
tailrecursion尾递归Left-Recursive左递归
第二章编译原理基础知识
编译是将计算机高级语言如C++、Java、C#编写的源程序翻译成可以在计算机上执行的机器语言的翻译过程。
编译过程中分：
词法分析、语法分析、语义分析、源代码优化、代码生成和目标代码优化几个过程。
ANTLR解决的是词法分析和语法分析的问题，下面介绍一下编译原理中有关词法分析和语法分析的基本知识。
词法分析是对源程序一个一个字符地读取，从字符中识别出标识符、关键字、常量等相对独立的记号（token，也叫符号或单词），形成记号序列记号流的过程。
如c、l、a、s、s五个字符构成了关键字class，2、3构成了一个整型数23。
词法分析过程中会滤掉源程序中的空格、换行符和注释等不属于源程序的字符，还可以将记号归类，哪些记号
升级会员 