admin管理员组文章数量:1597400
2024年5月11日发(作者：)
ANTLR指南（v3.0）
第一章Hello World
ANTLR文法
ANTLR Runtime
生成
嵌入C#，java…
代码片段
C#
编译
语法分析器
Java
编译
C C++ Python
.NET
语法分析器
JVM
… …
ANTLR是ANother Tool for Language Recognition的缩写“又一个语言识别工具”。从名
字上可以看出在ANTLR出现之前已经存在其它语言识别工具了（如LEX
1[1]
，YACC
2[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开发Hello World示例
1[1]
2[2]
一种词法分析器（分描器）的自动产生系统，用正则表达式来描述文法结构。
一种语法分析程序的自动产生器，可以处理能用LALR(1)文法表示的上下文无关语言。
本章将开发一个简单示例让读者对ANTLR有一个初步的认识，并搭建开发环境以便后
续的学习。读者在示例中遇到不懂的地方也不必担心，我们的目的是搭建开发环境学会编译
运行语法分析器。用ANTLR开发一个语法分析器大致分三步，第一步：写出要分析内容的
文法。第二步：用ANTLR生成相对该文法的语法分析器的代码。第三步：编译运行语法分
析器。
和多数编译书籍一样，本章也用解析简单的表达式作为示例。要解析的表达式中有二种
数据类型：整数 如“23”, “5” 和字符串 如“Hello World”。表达式中以算术表达式为主也包
括赋值表达式。我们列举两个表达式语句：
23+4*(5+1); str=“Hello World”;
第一条语句是一个算术表达式，括号改变了运算顺序，计算结果不赋给任何变量。第二
条是一个赋值表达式，将字符串赋给一个变量。后面我们要开发一个语法分析器来分析这两
条语句。在开发之前先简单提一下语法树的概念，在语法分析中一般用树来表示语法结构，
表达式的语法树是以操作符为根节点操作数为子节点的树形结构，23+4*(5+1)的语法树根据
操作符的优先级如下。
4
5
图1.1
+
23 *
+
1
算术表达式先计算5+1，5+1在括号中操作符的优先级最高在语法树中的深度最大，然
后是4*(5+1)，最后是23+4*(5+1)。可以看出语法树的求值顺序是从下向上的，先计算深度
大的操作符5+1结果为6，然后是4*6结果为24，然后是23+24表达式的结果为47。下面
再看一下赋值表达式的语法树结构：
=
str
“Hello World”
图1.2
赋值操作符“=”做为根节点变量str作为左子树，而字符串表达式“Hello World” 作为右
子树。了解了语法树后我们开始录入文法源文件。ANTLR中文法文件是扩展名为“.g”的文
本文件，“.g”文件就是我们的源文件。这里新建一个叫“E.g”的文法文件，在文件中输入如下
文法定义：
grammar E;
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();} ;
文件的第一行grammar E的E为文法的名称它与文件名一致。第二行是文法的设置部
分options{ output=AST;}，output=AST表示让语法分析器返回包含语法树的信息。第三行开
始是文法定义部分，文法是用EBNF
1
推导式来描述的（有关EBNF会在后面章节中讲解），
文法定义中分两大部分以小写字母开头的语法描述和全大写的词法描述。其中每一行都是一
个规则（rule）或叫做推导式、产生式，每个规则的左边是文法中的一个名字，代表文法中
的一个抽象概念。中间用一个“:”表示推导关系，右边是该名字推导出的文法形式。下面逐
行介绍文法的规则定义：
statement : (expression | VAR '=' expression) ';'
statement代表表达式语句，前面说了语句有两种，在推导式中以“|”分隔代表“或”关系。
表达式本身是合法的语句，表达式也可以出现在赋值表达式中组成赋值语句，两种语句都以
“;”字符结束。
expression
:
(multExpr (('+' |'-' ) multExpr)*) | STRING
expression
代表表达式，“|”的左边是算术表达式的形式，“|”的右边是字符串表达式。
我们通过规则的推导顺序可以看出，规则按操作符的优先级首先推导优先级最低的运算“+”，
“-”运算。
1
EBNF：BNF是被用来形式化定义语言的语法，以使其规则没有歧义。EBNF在BNF基础上改进了定义
形式比BNF更写法更简洁。
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和开发环境，到/ ANTLR的
下载页，为ANTLR的官方网站，ANTLR是一个开源项目可以免费下载。图
1.1为开发环境ANTLRWorks的下载页面，图1.2为开发环境ANTLR Runtime3.01的下载页
面。您的机器上需要安装JDK1.5或更高版本的java SDK。其中ANTLRWorks的下载文件
名叫安装JDK后可以直接双击运行打开ANTLRWorks开发环境。
（图1.3）ANTLRWorks下载页面
（图1.4）ANTLR Runtime下载页面
（图1.5）ANTLRWorks IDE
1.3 Java环境的运行
下面录入文法文件，运行ANTLRWorks点击“File – New”菜单新建文法文件，在新文件
中将前面的文法录入。（我的网站中有本书所有示例源代码，但我建议您还是手工录入一遍。
这样您会有更好的学习效果。）录入文法后点击“File – Save” 菜单文件名为“E.g”。然后点击
“Generate–Generate Code”，如果ANTLRWorks提示“The grammar has been successfully
generated in path…”说明ANTLRWorks成功生成了语法分析器的代码。会在“E.g”的当前目录
中生成“”、“”、“”和“E__.g”四个文件，其中有两个java源文
件。“”为词法分析部分的代码，“”为语法分析部分的代码。那么为什
么会生成java代码呢？ANTLR在不指定目标语言的情况下默认是java语言。我们也可以在
文法文件中加入options项指定目标语言。
grammar E;
options { output=AST; language=Java; }
program : statement + ;
……
生成了代码后，我们来编译运行语法分析器。刚才生成的是java代码，所以先来看看
java如何编译运行。首先要有一个执行程序的main方法，这个类如下：
import e.*;
import .*;
public class run
{
public static void main(String[] args) throws Exception
{
ANTLRInputStream input = new ANTLRInputStream();
ELexer lexer = new ELexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
EParser parser = new EParser(tokens);
m_return r = m();
n(((BaseTree)e()).toStringTree());
}
}
把这段代码存入文件中，main方法功能是从命令行接收输入的表达式，通过词
法分析和语法分析两个步骤来获得这个表达式的语法树，并以字符串的形式输出语法树的内
容。
ANTLRInputStream input = new ANTLRInputStream();
ELexer lexer = new ELexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
词法分析步骤是从命令行接收输入的表达式，通过ANTLR内部ANTLRInputStream类，
生成一个ANTLRInputStream类的实例input，再将input传给ELexer类。ELexer类是词法
分析类，把input中的输入内容进行词法分析，词法分析后会产生词号流（token stream）交
给语法分析类，为语法分析提拱前提。
EParser parser = new EParser(tokens);
m_return r = m();//此处进行了语法分析
n(((BaseTree)e()).toStringTree());
语法分析步骤是根据词法分析产生的词号流生成语法分析类的实例parser。然后调用
parser的方法program()。这个方法名和我们文法中的第一条规则program : statement + ;的名
字是一致的，这说明我们要用整个文法进行分析，program是文法的启点。调用program()
方法后就进行了语法分析，program()方法返回语法分析的信息其中包括语法树。e()
可以返回语法树，getTree()返回的是Object类型所以这里做一个类型转换(BaseTree)e()
并调用其toStringTree()方法获得语法树的字符串形式输出。
到现在完成了源代码的录入工作，接下来编译所有的代码。编译的命令行字符串为：
javac -classpath .;..... *.java
中的import e.*;import .*;所引用的类包含在
中，解压我们之前下载的文件，在其中的lib目录中可以找到
。编译字符串中的-classpath参数中给出.....的实现路
径。运行程序的命令行字符串与编译字符串相似：
java -classpath .;..... run
好的我们来执行这两个字符串来编译并执行程序，执行程序后命令行光标会等待输入，
把之前准备分析的两个表达式输入，然后按Ctrl+Z（Windows系统Ctrl+Z，UNIX系统Ctrl+D）
表示输入结束，然后回车。
程序输出23 + 4 * ( 5 + 1 ) ; str = "hello world" ;这表示程序执行成功了。我们的语法分析
器已经正确的解析了这两个表达式。您可以试着用不规则的格式输入两个表达式会得到相同
的输出，因为已经正确分析了表达式的语法，所以输出格式化的字符串对我们的分析器来说
是很简单的事情了。
23 1
1.4 .NET环境的运行
我们再说说.NET的编译执行。首先生成C#的语法分析器代码，在文法中的options设
置中修改目标语言为CSharp，还要把WS中的skip()改成Skip()。Java版和.NET版的ANTLR
Runtime都使用了各自语言的命名规范，所以名称上略微有些区别。
options { output=AST; language=CSharp; }
……
WS : (' ' |'t' |'n' |'r' )+ {Skip();} ;
然后用ANTLRWorks中的Generate菜单生成代码，这时目录中会生成四个文件
“”、“”、“”和“E__.g”。和E__.g文件与之前Java开发中
生成的两个同名文件是一样的，另外为词法分析器，为语法分析器。
在.NET开发中我们采用Visual 2005做为开发环境，让我们的示例和真正的开发
贴近一些。在Visual 2005中先新建一个名称为“HelloWorld”的C#
WindowApplication项目，将生成的、文件拷贝并加入到项目中。再将.NET
版的ANTLR Runtime的DLL引用到项目中来。本示例需要和
，这两个文件在解压后的antlr-3.0.1antlr-3.0.1
runtimeCSharpbinnet-2.0目录中可以找到。这些操作都完成之后，我们在程序窗体上放一
个多行文本框，一个按钮和一个Label。在窗体的代码文件中加入：
using e;
using ;
我们要实现在文本框中输入表达式语句，点击按钮语法树结果显示在Label控件中。在
按钮的事件中加入如下代码：
ICharStream input = new ANTLRStringStream();
ELexer lex = new ELexer(input);
CommonTokenStream tokens = new CommonTokenStream(lex);
EParser parser = new EParser(tokens);
m_return progReturn = m();
= ((BaseTree)).ToStringTree();
这里由于表达式是从界面文本框中获得，所以第一行代码和上面java的示例有些不同
使用ANTLRStringStream类来接收录入的内容。后面的代码和java版本中的几乎一致，只
是有一些java与.NET在命名规则方面的区别。Java方法名首字母为小写而.NET是大写。
（图1.6）.NET版HelloWord的运行结果
1.5 改进示例
到此我们已经学习了java和.NET开发语法分析器的全过程。读者可能觉得做完这个示
例成就感不大，因为输入和输出是一样的，并没有看到前面提到的语法树结构。下面我们修
进一下示例在文法中添加一些构造语法树的符号，使程序构造出如图1.1、图1.2的语法树。
文法修改如下：
grammar E;
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))) 我们已经使“（）”不出现在语法树中了，所以输出字符串中的括号并不是我们输入的表
达式括号，这些括号表示语法树的结构。由于我们让操作符为根节点，所以这里“+”、“*”
操作符出现在前面，其后是它的左子树，再往后是它的右子树，内层括号是外号括号子树。
按照这个规则我们可以绘出语法树：
23+4*(5+1);
str="hello world";
^Z
(+ 23 (* 4 ( + 5 1 ))) (= str "hello world" )
+
23 *
4 +
5 1
绘出语法树和前面图1.1中的语法树是一样的，这说明我们已经正确的生成了语法树。
赋值表达式亦然。我们可以在Visual 2005中运行。在程序中设置断点并查看
的对象内存情况。
图1.7
语法树是BaseTree类型，BaseTree有一个children集合用来存放子语法树，子语法树也
是BaseTree类型，可以利用内存监视功能一级一级展开，看一看ANTLR的语法树
的对象表现形式。BaseTree类有一个GetChild(int i) 方法可以获取第N个子树，还有一个
ChildCount属性代表子树的个数。结合这两个属性和方法可以用如下的代码遍历子语法树。
for (int i = 0; i < ount; i++) {
BaseTree currTree = (BaseTree)ld(i);
}
1.5本书结构
好，完成Hello World示例的开发后，先来介绍一下本书的结构。本书后面章节大体顺
序是：先学习文法、推导式等编译原理基础知识，使没有编译原理知识基础的读者铺平道路。
然后全面学习ANTLR开发技术，主要包括词法、语法、语法树以及字符模板的内容。在
ANTLR全学习之后再强化学习一下编译原理的知识（如DFA）然后学习如何解决ANTLR
开发中的较难的问题。
第二章：编译原理基础知识。
第三章：词法分析。
第四章：语法分析。
第五章：嵌入文法中的代码。
第六章：构造语法树。
第七章：字符串模板。
第八章：编译错误处理。
第九章：进一些学习编译原理知识。
第十章：文法编写中的错误。
第十一章：ANTLR API。
第十二章：开发实例。
1.6本章小结
本章开发表达式语法分析器示例详细地向读者介绍了ANTLR的开发过程，如何建立
ANTLR的开发环境以及如何在Java和.NET环境中编译和运行程序。本书后面出现的示例
希望读者都要亲手完成，只有亲自做出正确运行的程序才算是真正学会。
Java, C, C++, C#, Objective-C, Python, and Ruby.1
tail recursion 尾递归 Left-Recursive左递归
第二章 编译原理基础知识
编译是将计算机高级语言如C++、Java、C#编写的源程序翻译成可以在计算机上执行的
机器语言的翻译过程。编译过程中分：词法分析、语法分析、语义分析、源代码优化、代码
生成和目标代码优化几个过程。ANTLR解决的是词法分析和语法分析的问题，下面介绍一下
编译原理中有关词法分析和语法分析的基本知识。
词法分析是对源程序一个一个字符地读取，从字符中识别
源程序
字符串
出标识符、关键字、常量等相对独立的记号（token，也叫符
号或单词），形成记号序列记号流的过程。如c、l、a、s、s 五
词法分析
记号
个字符构成了关键字class，2、3构成了一个整型数23。词法
分析过程中会滤掉源程序中的空格、换行符和注释等不属于源
程序的字符，还可以将记号归类，哪些记号属于标识符，哪些
记号属于关键字、整数、浮点数等。记号流是语法分析的基础。
语法分析是根据词法分析输出的记号流，分析源程序的语
法结构，并添加代表语法结构的抽象单词（如：表达式、类、
语法分析
语法树
语义分析
方法等），按照语法结构生成语法树的过程。前面讲的词法分
析后形成的记号序列是描述程序的直接标识符序列，是线性
的。它没有反映出源程序的结构。而语法分析后生成的语法树
注释树
是可以表示源程序结构的数据结构，语法树的叶子节点就是记
号。下面举一个简单的例子说明词法分析和语法分析之关的系
统，有如下的源程序：
class T {
string Name;// name of T
object GetValue() {
}
}
进行词法分析后形成记号流：
class T { string Name ; object GetValue ( ) { } }。
进行语法分析后形成语法树：
源代码优化
代码生成
代码生成
目标代码
目标代码优化
目标代码
图2.1
类
类名
属性 方法
T
属性名 类型
方法名 返回值
Name string
GetValue
object
我们这里不介绍编译原理的其它部分，因为ANTLR只涉及到了词法分析和语法分析这两
个部分。读者可以去参考原理的书籍。了解ANTLR在编译过程中所处的位置后。我们来详细
学习一下有关词法分析和语法分析的基础概念。
2.1什么是文法
一种程序设计语言的语法是规定源程序的写法是否合法的规则，它存在于词法分析和语
法分析两个阶段。如：词法分析中 123表示合法整数，1_23是不合法整数。在语法分析中
if(boolVar) {}是合法的语句，if(boolVar) { 是不合法的语句。那么我们怎样来定义语法
规则呢？定义语法规则的工具是文法（grammar），文法是由若干定义语法规则的推导式组成
的。下面例子中用文法定义了人类语言的语法规则：
语言 =>（句子）+
句子 => 主语 谓语
谓语 => 动词 宾语
主语 => 名词
宾语 => 名词
名词 =>‘张三’| ‘代码’
动词 =>‘编写’
如，‘张三编写代码’这句话在文法中的推导过程是：
语言 => 主语 谓语
=> 张三 动词宾语
=> 张三 编写名词
=> 张三编写 代码
另外编译原理中一般用大写字母表示一个文法的名称，再加上文法的启始规则组成文法
的表示符号。如上面的文法如果名称为G，可以表示为G[语言]文法。
2.2符号表、符号串、推导式和句子
不管是人类语言还是计算机语言都是用符号组成的，英文由字母、数字和标点符号等组
成，中文由汉字、数字和标点符等组成，计算机语言由关键字、字母、数字和一些专用符号
组成。
这些组成语言的基本符号加上推导出基本符号的抽象符号集合在一起称为符号表，用V
来表示，符号表是不允许为空的。如G[语言]文法的符号表是：{语言，句子，主语，谓语，
宾语，名词，动词，‘张三’，‘代码’，‘编写’}，符号表中可以继续推导的中间符号称为非
终结符，用Vn表示，不能再继续推导的符号称为终结符，用Vt表示。G[语言]文法的非终
结符集合为：{语言，句子，主语，谓语，宾语，名词，动词}，终结符集合为{‘张三’，‘代
码’，‘编写’}。
符号表中符号的任意有穷组合序列称为符号串。‘张三张三’、‘张三代码编写’、‘张三
语言句子宾语宾语’都是G[语言]文法符号串。很明显一种文法的符号串不一定是这种文法
的合法句子。符号串是有长度的，它的长度是符号的个数，如‘张三张三’的长度是2，张
三语言句子宾语宾语’的长度是5。
文法是定义语法规则的工具，语法规则简称规则（rule）又称推导式或产生式。假设a
和b都是一个文法的符号串，我们用a => b表示一个规则，其中a不能为空。也就是说“句
子 =>”是合法的规则“ => 主语”是不合法的，一个文法要由至少要有一个规则。规则a =>
b使用b来替换a的过程叫做推导，反用b来替换a的过程叫归约。
如G[S]是一个文法，S为启始规则，从S推导若干次后形成的符号串叫做G[S]文法的
句型。如果推导出的符号串全都由终结符组成此符号串叫做G[S]的句子。前面示例中“张
三动词 宾语”是G[语言]文法的句型，而“张三编写 代码”是G[语言]文法的句子。编译
原理中也使用四元组来表示文法G[Vn,Vt,P,S]，其中G为文法句称，Vn为非终结符的集合，
Vt为终结符的集合，P是文法规则的集合，S为启始规则。
2.3文法的类型
一个文法G[S]，S为启始规则，如果它的所有规则符合形如：a => b 其中a和b都是
G[S]文法的符号串，但a中至少要有一个非终结符，这时G[S]文法是短语文法。G[语言]为
例“宾语张三 => 名词张三”是短语文法的规则，“张三编写=> 名词张三”则不是短语文法，
因为“张三”和“编写”都是终结符规则左则没有非终结符。我们可以看出短语文法是对规
则做了一些限制后形成的，下面的文法是对短语文法做进一步限制形成的。
如果G[S]的所有规则都满足形如：a => b其中a的长度要小于等于b，这时G[S]文法
是上下文有关文法（context-free grammars）。上下文有关文法的更形象的定义是：文法的
所有规则满足aBc => abc的形式，其中B是非终结符，a、b、c是符号串。也就是说B => b
只在前面有a后面有c的情况下才能推导，所以是上下文有关的。例如：“张三动词程序 =>
张三编写程序”是上下文有关文法的规则。
如果G[S] 的所有规则都满足形如：a => b其中a是一个非终结符，b是符号串，这时
G[S]文法是上下文无关文法（context-sensitive grammars）。就是说a推导出b与其前后
是什么符号串无关。上面G[语言]的文法就是上下文无关文法。
如果G[S] 的所有规则都满足形如：A=> aB或A=>a其中A和B是非终结符，a是终结
符，这时G[S]文法是正规文法（regular grammars）。就是说规则的右则要以终结符开头。
如：“谓语 => 编写 宾语”，“动词 => 编写” 都是正规文法的规则简称正规式，“谓语 =>
动词 宾语” 就不是正规式。
这四种文法是对规则的限制逐步加强形成的。正规文法是上下文无关文法的特例，上下
文无关文法是上下文有关文法的特例，上下文有关文法是短语文法的的特例。文法产生的
语言就是该文法的语言，如：上下文无关文法产生的语言就是上下文无关语言，正规文法
产生的语言就是正规语言。文法是语言模型。计算机语言中普遍采用上下文无关文法来定
短语文法
上下文有
关文法
上下文无
关文法
正规文法
义语法规则。下面我们介绍上下文无关文法的语法树。
图2.2
2.4语法树
编译技术中用语法树来更直观的表示一个句型的推导过程。前面我们已经提到过语法
树，相信读者已经对语法树有了一定的认识，这里我们给出上下文无关文法语法树的定义：
给定上下文无关文法G[S]，它的语法树的每一个节点都有一个G[S]文法的符号与之对应。S
为语法树的根节点。如果一个节点有子节点。则这个节点对应的符号一定是非终结符。如果
一个节点对应的符号为A，它的子节点对应的符号分别为A1，A2，A3…..Ak，那么G[S]文
法中一定有一个规则为：A=>A1 A2 A3 …..Ak。满足这些规定的树语法树也叫推导树。下面
给出一下文法K[S2]和K[S2]文法的一个语型，我们用语法树来显示这个语型的推导过程。
K[S2]文法： S2 => aA
A=> bABc
A=>a
B=>d
S2
a
b
A
A
a
B
c
d
K[S2]文法对于语型abadc的推导树为：
推导的过程中优先选择不同的规则进行推导会使推导过程有所不同。下面举一个例子。
K[S3]文法：S3 => ABD
A=>a
B=>bC
C=>c
D=>d
下面是对于句型abcd的三种不同推导过程。
① S3=> ABD => aBD => abCD => abcD => abcd
② S3=> ABD =>AbCD=>AbcD=>abcD=>abcd
S3
A
a
b
B
D
C
d
c
③ S3=> ABD =>ABd=>AbCd=>Abcd=>abcd
我们可以注意到①过程中所有推导都是选择的最左边的非终结符进行替换。③过程中所
有推导都是选择的最右边的非终结符进行替换。其中①被称为最左推导，③被称为最右推导。
这三种推导都对应一棵语法树，这说明语法树反应了此句型的所有推导过程。
但是对于有些句型来说，它对应的语法树不一定唯一的。也不是说一棵语法树不一定能
反应一个句型的所有推导过程，如下面给定文法。
S4[E]文法：
E => E + E
E => E * E
E => (E)
E => i
对于 i + i * i 句型，我们可以写出下面两种最左推导的过程：
① E => E + E => E + E * E => i + E * E => i + i * E
② E => E * E => E + E * E => i + E * E => i + i * E
①过程中第一步使用了E => E + E规则，②过程中第一步使用了E => E * E规则，不
管选择哪个规则都是最左推导。下面有两棵语法树与之对应。对于一个文法的句型如果有多
于一棵的语法树与之对应，则这个文法是有二义性的文法。也可以用另一种方法判断，如果
一个文法的最左或最右推导的过程是不唯一的也可以说这个文法是有二义性的文法。
E
E
E + E
E * E
i
i
i
i
E * E
i
E + E
i
推导②的语法推导①的语法
二义性文法是在开发语法分析器时需要解决的问题，我们将S4[E]加入操作符优先关系
改成下面形式可以去掉文法的二义性。
S5[E]文法：
E => T + T
E => T
T => F * F
T => F
F => (E)
F => i
使用S5[E]文法对于 i + i * i 句型的推导过程和语法树是唯一的：
E => T + T => T + F * F => F + F * F => i + F * F => i + i * F => i + i * i
E
T
由于文法简单所以二义性比较容易解决，但是当文法
T
*
F
很复杂的时候，检查文法中是否存在二义性就困难了。但
ANTLR的开发者不用担心，ANTLR会象我们编译普通源程
序那样提示文法中的问题，其中包括文法的二义性问题，
这使我们可以很容易的找到存在二义性的规则。
+
F
F
i
i
i
2.5分析方法
前面讲到了句型的推导过程和生成语法树的过程，有了语法树就已经很清晰的看到了句
型的结构，我们可以很容易的从语法树中获得我们相要的信息，这个过程就是语法分析。如
图2.3显示了对于SELECT F1, F2 FROM Table1 WHERE F1=”a”的语句进了语法分析后生
成的语法树，利用非终结符节点SeletctList很容易对应Select语句的F1,F2部分。
SeletctStatement
SELECT
SeletctList
FROM
TableSource WhereCondition
SeletctItem
SeletctItem
Table1
WHERE Expr
F1
F1
图2.3
F1
=
“a”
我们前面的推导是靠自己主观判断，选择适当的规则进行推导的。那么如何用程序来实
现这个过程呢？语法分析方法分两大类：自顶向下的分析方法和自下而上的分析方法。
ANTLR使用的是自顶向下的分析方法。自顶向下的分析方法的思路是从起始规则开始选择适
当的规则反复推导，直到推导出待分析的语型。如果推导失败则反回选择其它规则进行推导
（这个过程叫做回朔（
backtrack
）），如果所有规则都失败说明这个句型是非法的。下面
举一个分析的示例。
D1[S]文法：
S => aBd
B => b
B = > bc
对于abcd句型进行自顶向下分析，第一步唯一的选择规则S => aBd，第二步对非终结
符B的推导，先选择B => b推导出S => abd这和句型abcd不同所以推导失败。现在返回
到对B的推导，选择另一个规则B => bc行出S => abcd这次推导成功。
S
S
S
a
a
d
d
B
自下而上的分析方法与自顶向下分析方法相反，过程是逐个的扫描句型的符号使用适当
B
c
b
的规则进行反复归约，直到归约成启始规则S。如果这个过程失败，则返回选择其它规则进
行归约。我们使用自下而上的分析方法对D1[S]示例进行分析。首先是扫描到了第一个符号
a，a无法归约没有象X => a这样的规则。然后继续扫描符号b，b可以用B = > b来归约
得出aB。然后扫描到符号c，这时aBc不能继续进行归约造成过程失败。所以要返回前一步
使用B => bc来归约得出aBd，aBd可以用S => aBd归约到S。
S
a
d
B
a
B
不管是自下而上的分析方法还是自顶向下分析方法如果选择的规则不正确，就要返回重
a
c
b c
b
c
b
新尝试用其它规则进行推导或归约。这在实际操作中会浪费很多时间分析程序的执行效率会
降低。为了解决这个问题，在编译技术中使用一种向前探测符号的方法（lookahead）保证
可以正确选择规则。如D1[S]示例的自顶向下分析的第二步如果选择B => b则得出ab句型
后面的符号为c，如果选择B => b规则推导将得出abd，所以不能选择B => b规则。如果
选择B => bc可以得出abc和后面的符号d相符，所以应该选择B => bc规则。
在自下而上的分析方法中读取前两个符号ab时b可以用规则B=>b归约，这时向前探测
一符号为c可以得出aBc，但aBc没有规则可以归约。所以再读取一个符号c符，选择B=>bc
规则归约。向前探测一符号为d，aBd可以规约成S分析成功。
2.6有害规则
在文法可能会出现一些无用的、造成文法二义性的规则。如左右两侧相同的规则A =>A，
这种规则在文法中没有意义，如果还有一条规则S => A，当我们用A归约时A=>A会干扰使
分析器不知道应该用哪一个规则归约同，如果不断使A => A归约会造成死循环。如果一个
非终结符不出现在任何规则的右部，那么这个非终结符是不可达的，也就是说没有句型在推
导或归约过过程中会用到这个非终结符。如一个文法中有规则 A => a但是没有形如X => A
的规则那么A=>a在文法中是多余的。还有一种叫做不可终止的非终结符，如一个文法中对
于A非终结符来说只有A => Aa这个规则，可以看出A无法推导出一个句子它也是多余的。
这些规则应该在文法中删除。
2.7左递归、右递归
形如A => Ab的规则，A的定义是递归的可以推导出Abbbb…b，左侧的非终结符A可以
不断地推导出Ab，这种处于规则左侧的递归叫左递归。递归也可能出现在多个非终结符之
间A=>Bd，B=>Bc这里的A=>Bd也是左递归。例如我们要定义一个整型数其规则为：INT => INT
Digital，Digital => 0|1|2|3|4|5|6|7|8|9，规则INT用左递归实现了多位整型数的定义。
相反形如A => bA的规则，A的定义也是递归的但和左递归相反非终结符A在规则的右侧这
样递归叫做右递归。我们可以把整型数定义的规则用右递归的方法定义为INT => Digital
INT，Digital => 0|1|2|3|4|5|6|7|8|9。使用这两种递归的方法时，要看语法分析程序的
分析方式，如果语法分析程序是从左向右分析的，那么使用右递归比较适合，反之使用左递
归比较适合。
2.8文法定义基础
ANTLR的文法定义使用了类似EBNF（Extended Backus-Naur Form）的定义方式，是一
种强大简洁的文法定义方式。本章前面的文法定义的写法比较繁琐，定义复杂的文法时非常
不便，文法的可读性也会较差。ANTLR的文法定义方式形象直观，可以用很短的行数描述以
前要很多行才能表示的文法内容。
规则的表示：文法是由规则组成的，本章前面的规则都是用A=>a形式来表示的。ANTLR
用A : a;来表示规则，“:”代替了“=>”。ANTLR的规则要以分号“;”结束。在规则中有几
种运算关系，选择、连接、重复、可选。
连接“ ”：规则A : a b c; a、b、c之间用空格分隔。此规则接收句型abc，符号a、
b、c是按顺序连接起来的关系。
选择“| ”：规则A : a | b | c; “|”表示“或”的关系，符号A可以推导出a或b
或c，也就是在a、b、c中选择。这要比写成A : a; A : b; A : c;方便得多。连接和选择
可以联合起来使用，如A : a b c | c d e;。有进也会使句型的数量增多如：A : B D; B :
a | b; D : c | d;这时符号A推导出的句型有 ac、ad、bc、bd四种。
重复“*，+”：规则A : a*; “*”表示a可以出现0次或多次。A : a*; 相当于A : A
a | ;。这样可以避免递归的定义，可文法定义中递归往往引起文法的二义性。如果a至少
要出现一次可以表示为A : a+; “+”表示a可以出现1次或多次。相当于A : A a | a;。
重复可以和连接、选择一起使用如：A : a* b | c+ d;。
可选“？”：规则A : a?; “?”表示a可以出现0次或1次，即a可有可无。相当于A :
a | ;。可选可以和连接、选择、重复一起使用如：A : a* b? | c+ d?;。
子规则“（）”：规则A : (a b) | b; a与b在括号中，这样“(a b)”形成了一个子规
则，也就是说可以把规则写成A : B | b; B : a b;两个规则表示，我们把B规则用括号括
起来放到A规则中这样就是A规则的子规则了。利用子规则也可以把多个符一起进行描述，
A : (a b c)* 规则中a、b、c三个符号可以一起重复0次或多次。子规则有利于我们把很
复杂的多个规则写到一起，有时这样写会使文法既简练又直观。子规则和前面的各种特性用
到一起可以把复杂的文法写的很浓缩。如：A : (a b c)* | (c d)+ e?;。
值得注意的是如果我们的规则中有“()”的字符该如何表示？因为子规则也是用“()”
表示的。在ANTLR中表示字符要用“’”单引号括起来，用‘(’ ‘)’来表示括号字符。前
面讲到的表示文法规则的符号“| * + () ?”叫做文法的元符号。
注释“// /**/”：和一般编程语言一样，ANTLR在文法定义中也可以添加注释。用//
来添加单行注释，如规则E : ‘(’ E ‘)’ | INT // E表示算术表达式。用/*…*/添加
多行注释，与C++相同。
2.9本章小结
本章学习了编译原理的基础知识。包括：什么叫词法分析和语法分析，ANTLR在编译技
术中所处的位置。什么叫文法，规则。什么叫短语文法，上下有关文法，上下文法无关文法，
正规文法。语法树，句型的最左推导最右推导和文法的二义性，自顶向下的分析方法和自下
而上的分析方法。ANTLR的文法定义方法。
第三章 词法分析
词法分析是编译过程的第一步，是编译过程的基础。词法分析除了上一章讲过它为语法
分析提拱记号流，滤掉编译过程不关心的内容以外，还有一个重要的作用是有了词法分析可
以大大提高编译的效率。可能有人曾有过疑问，为什么一定要有词法分析？词法分析和语法
分析的关系与其它编译过程有些不同，如：语义分析，生成代码在编译过程中是独立的步骤
与其它步骤有明显的区别。而词法分析和语法分析在形式上很相似，都要用文法去定义语言
的结构。可以想象一下如果把词法分析和语法分析合并会有什么不同，也就是说我们直接对
源代码做语法分析。如C#源代码中当我们遇到一个字符“c”这时它可能会是关键字“class”
标识符“c1”等等。如果是class关键字那么接下是要分析一个类代码，如果是标识符那要
看它的具体上下文而定。这样的话与一个字符“c”有可能对应的情况太多了。所以要先做
一遍词法分析把源程序的基础组成单位先分析出来。词法分析是语法分析的一个缓冲，可以
大大提高编译效率。
3.1词法分析的规定
与第二章中的例子不同，在ANTLR中词法分析定义的规则名必须以大写字母开头如
“LETTER”，“NewLine”。我们在第一章示例中的词法分析部分与语法分析部分合写到一个
E.g文件中，ANTLR允许把词法分析部分和语法分析写分别写到两个文件中。
T.g文件存放语法定义：
grammar T;
Options {tokenVocab = T2;}
a : B*;
T2.g文件存放词法定义：
lexer grammar T2;
B : ‘b’;
将词法分析放到单独的文件中时文法的名称也要和文件的名称相同，在grammar关键字
之前要加入lexer关键字。上例中的T.g文件生成语法分析类TParser，T2.g文件生成词法
分析类T2Lexer。在T.g中要加入一个设置项tokenVocab来指定语法文件所需的词法单词
是来自T2.g。这样就可以按照第一章示例中的方法编译运行分析器了。
3.2字符编码定义
词法分析与源代码直接接触，因为源代码是由字符串组成的，所以我们需要定义字符的
方法。ANTLR有两种方法定义字符，第一种方法是：ANTLR可以直接使用字符本身很简单直
观的定义基本符号。
CHAR : ‘a’ | ‘b’ | ‘c’;
但这种定义只限于ASCII码的字符，下面的定义是不合法的。
CHAR : ‘代码’;
定义汉字这样除ASCII码以外的字符只能用第二种方法十六进制编码定义法。使用“u”
开头加四位十六进制数定义来定义一个字符。
CHAR : ‘u0040’;
C#中使用("{0:x} {1:x}", 32('代'),
32('码'));可以获得汉字的编码。如上面的CHAR : ‘代码’;我们可以定义
为：
CHAR : 'u4ee3' 'u7801';
编码有很多种GB2312的编码范围是A1A1 ~ FEFE，去掉未定义的区域之后可以理解为
实际编码范围是A1A1 ~ F7FE。GBK的整体编码范围是为8140 ~ FEFE。 BIG5字符编码范围
是A140 ~ F97E。
字符集
GB2312
GBK
BIG5
Unicode
UTF-8
编码范围
A1A1 ~ 7E7E
8140 ~ FEFE
A140 ~ F97E
000000
~
10FFFF
000000
~
10FFFF
其中汉字在GB2312中的编码范围为：‘uB0A1' .. 'uF7FE'，汉字在Unicode编码范
围为：’u4E00’ .. ‘u9FA5’ | ‘uF900’ .. ‘uFA2D’。
3.3终结符定义方法
LETTER : ‘A’ | ‘B’ | ‘C’ | ‘D’ | ‘E’ | ‘F’ | ‘G’ | ‘H’ | ‘I’ | ‘J’ | ‘K’ | ‘L’ | ‘M’ | ‘N’ | ‘O’ | ‘P’ | ‘Q’ |
‘R’ | ‘S’ | ‘T’ | ‘U’ | ‘V’ | ‘W’ | ‘X’ | ‘Y’ | ‘Z’ | ‘a’ | ‘b’ | ‘c’ | ‘d’ | ‘e’ | ‘f’ | ‘g’ | ‘h’ | ‘i’ | ‘j’ | ‘k’ | ‘l’ |
‘m’ | ‘n’ | ‘o’ | ‘p’ | ‘q’ | ‘r’ | ‘s’ | ‘t’ | ‘u’ | ‘v’ | ‘w’ | ‘x’ | ‘y’ | ‘z’;
“..”符号，从上面的LETTER示例可以看出，定义一个表示英文字母的符号写起来非
常繁琐。为了让定义变得简单ANTLR加入“..”符号通过指定首尾的字符可以很方便的定义
一定范围内的字符。
LETTER : ‘A’ .. ‘Z’ | ‘a’ .. ‘z’;
“~”符号，如果我们想表示除某些符号以外的符号时，可以使用“~”符号。“~”代表
取反的意思。
A : ~ ‘B’;
符号A匹配除字符“B”以外的所有字符。
A : ~ (‘A’ | ‘B’); B : ~(‘A’ .. ‘B’); C : ~‘u00FF';
上面的例子中定义三个符号。符号A匹配除字符“A”和“B”以外的所有字符，符号B
匹配除大写字符母以外的所有字符。符号C匹配除编码为“u00FF”的字符以外的所有字符。
“.”符号，ANTLR中可以用“.”表示单个任意字符，起通配符的作用。
A : .; B : .*; C : .* ‘C’; D : ~ .;//error
上面的例子中符号A匹配一个任意字符，符号B符号匹配0到多个任意字符，符号C
匹配0到多个任意字符直到遇到字符“C”为止。D的定义是错误的，不能定义任意字符以
外的字符。
3.4 skip()方法
有些字符是不属于源程序范畴内的，这些字符在分析过程中应该忽略掉。在ANTLR中可
以在词法定义中加入skip();，(如果是C#为目标语言为Skip();)。在规则的定义的之后与
表示定义结束的分号之前加入“{skip();}”。例如下面定义了一个跳过空白的词法定义。
WS : ( ' ' | 't' | 'n' | 'r' ) + {skip();} ;
空白符号WS中有空格符、制表符、回车和换行符，当遇到这些字符时词法分析程序会
调用skip()方法跳过这些字符。
B : 'A' | 'B' {Skip();} | 'C' ;
上面的例子中符号B只在匹配字符“B”时跳过，从这个例子可以看出{Skip();}要写在
忽略内容的后面，如果它处于某选择分支中那么它只对某分支起作用。下面我们定义一些实
际中经常出现的词法定义。
INT : DIGIT+;
DIGIT : ‘0’ .. ‘9’;
INT 定义了整型数，整型数是由1个或多0到9的数字组成的。下面我们来定义浮点数，
浮点数的整数部分至少要有一位数字，小数部分是可有可无的，如要有小数部分则至少要有
1位小数位。
FLOAT : DIGIT+ (‘.’ DIGIT+)?;
下面是一个对于java语言中注释的定义。
COMMENT : '/*' . * '*/' {skip();} ;
LINE_COMMENT : '//' ~ ('n' | 'r') * 'r'? 'n' {skip();} ;
/* */ 和 // 代表的注释部分被忽略掉，下面我们给出完全的示例并运行它。
grammar T;
options {
language=CSharp;
output=AST;
}
a : INT;
INT : DIGIT+;
DIGIT : ‘0’ .. ‘9’;
COMMENT : '/*' . * '*/' {Skip();} ;
LINE_COMMENT : '//' ~ ('n' | 'r') * 'r'? 'n' {Skip();} ;
WS : ( ' ' | 't' | 'n' | 'r' ) + {Skip();} ;
文法中的COMMENT、LINE_COMMENT和WS规则只是为了滤掉相应内容，没有必要与语法
规则关联，这样它们也可以正确的工作。COMMENT符号使用了“.”符号来匹配一切字符直
到匹配“/”字符为止。LINE_COMMENT从“//”字符开始匹配除了“rn”以外的所有字符
直到匹配“rn”为止。其中有可以没有回车符只有换行符所以“r”是可选项。
将如下源代码保存到与exe同目录的文件中。
/* 这是
注释 */
234//这是注释
/* 这是
注释 */
下面是运行分析器的代码。
TestSkipLexer lex = new TestSkipLexer(new ANTLRFileStream(""));
CommonTokenStream tokenStream = new CommonTokenStream(lex);
TestSkipParser parser = new TestSkipParser(tokenStream);
TestSkipParser.a_return aReturn = parser.a();
在Visual 2005中单步执行上面几行代码，当执行到
TestSkipParser.a_return aReturn = parser.a();时用内存监视查看可以看
到语法树中只有234一个子节点它的chinaren属性为空，这说明所有空白和注释的内容都
被忽略了。
3.5 $channel = HIDDEN
有时象注释这样的部分在编译时并不是完全放弃的，如java中在/**….*/的注释形式
中可以添加说明最终生成程序的文档，在.NET中使用 /// 注释形式也有类似的功能。也就
是说我们在编译代码时忽略这些注释，而在分析生成文档时又要用到这些注释。这样的话就
不能使用skip();方法了，skip()方法是抛弃其内容。所以ANTLR中加入了channel属性用
来指定当前匹配的内容是属于哪一个频道，分析过程中关心哪个频道就可以只接收哪个频道
的内容。ANTLR中定义有两个频道常量DEFAULT_CHANNEL和HIDDEN_CHANNEL，一般情况下匹
配的内容都中放到DEFAULT_CHANNEL中。我们可以指定让当前匹配的内容放到哪个频道中。
前面示例中的词法规则可以改成如下形式。
COMMENT : '/*' . * '*/' {$channel=HIDDEN;} ;
LINE_COMMENT : '//' ~ ('n' | 'r') * 'r'? 'n' {$channel=HIDDEN;} ;
WS : ( ' ' | 't' | 'n' | 'r' ) + {$channel=HIDDEN;};
COMMENT、LINE_COMMENT和WS词法规则后面加入{$channel=HIDDEN;}，这样匹配的字
符就会被存放到HIDDEN频道中。下面将这个修改后的文法编译运行，其结果和使用skip()
方法时是一样的。这就是说存在于HIDDEN频道中的内容被语法分析器忽略了，因为在默认
情况下ANTLR语法分析程序只分析DEFAULT_CHANNEL中的内容。
Channel这个概念是介于词法分析和语法分析之间的一个概念，将存放匹配的内容存放
到各个频道中是在词法分析时进行的，而语法分析时可以有选择的读某一个频道中的内容。
那么如何让语法分析程序处理示例中的注释内容呢？我们再次修改文法因为我们只关心注
释所以把WS : ( ' ' | 't' | 'n' | 'r' ) + {Skip();};改回成skip()方法因为空白
我们是不关心的，下面给出全部的文法。
grammar TestHidden;
options {
language=CSharp;
output=AST;
}
a : b INT b;
b : (COMMENT | LINE_COMMENT)*;
INT : DIGIT+;
DIGIT : '0' .. '9';
COMMENT : '/*' . * '*/' {$channel=HIDDEN;} ;
LINE_COMMENT : '//' ~ ('n' | 'r') * 'r'? 'n' {$channel=HIDDEN;} ;
WS : ( ' ' | 't' | 'n' | 'r' ) + {Skip();} ;
下面是运行代码，运行代码中加入了enTypeChannel方法。
TestSkipLexer lex = new TestSkipLexer(new ANTLRFileStream(""));
CommonTokenStream tokenStream = new CommonTokenStream(lex);
TestSkipParser parser = new TestSkipParser(tokenStream);
enTypeChannel(T,
T_CHANNEL);
enTypeChannel(_COMMENT,
T_CHANNEL);
TestSkipParser.a_return bReturn = parser.a();
Nil（根节点）
/* 这是
注释 */
234 //这是注释
/* 这是
注释 */
SetTokenTypeChannel方法是将指定的频道中的符号加入到分析程序关心的范围内，第
一个参数是词法符号，第二个参数是这个符号所处频道。两条SetTokenTypeChannel语句将
DEFAULT_CHANNEL 频道中的COMMENT、LINE_COMMENT加入到语法分析程序
channelOverrideMap集合中，语法分析程序会分析channelOverrideMap集中注册的类型，
此示例运行后的语法树有四个子节点：
3.6 options {greedy=false;}
ANTLR词法分析中还可以加入greedy设置项，当greedy=true时当前规则会尽可能的
匹配可以匹配的输入。ANTLR中默认情况greedy为true，所以COMMENT : '/*' . * '*/'
{$channel=HIDDEN;} ;规则中符号“.”可以匹配“*/”字符，也就是说当遇到“*/”字符
时它是匹配“.”还是匹配’*/’出现了二义的情况，前面的例子中已经显示出在这种情况
下分析器是可以正确分析的，但加入greedy=false后可以消除这种二义性，就是说
greedy=false时分析器遇到“*/”字符时会很确定的做为注释结束符号来匹配，这样的话
就消除了二义性。
COMMENT : '/*' ( options {greedy=false;} : . ) * '*/' {$channel=HIDDEN;} ;
options {greedy=false;} : 是一种局部设置的写法，其格式为：( options
{«option-assignmen ts»} : «subrule-alternatives» )。关键字options后面用“{}”将
设置项括起来，使用“:”符号表示对后面部分进行设置，这种设置的方法必须在子规则中
设置它只能在子规则中有效。如：'/*' options {greedy=false;} : . * '*/' 这样的定
义是不无法的。
下面给出一个更加明显的例子。
grammar TestGreedy;
options {
language=CSharp;
output=AST;
}
c : A B;
A : 'a' 'b' ?;
B : 'b';
此例子中c规则有A和B两个词法符号，其中A匹配的是“a”或“ab”字符，B匹配
的是“b”字符。这时会出现一个问题就是当输入为“ab”时这个“b”是规则A的b还是规
则B的b，这属于二义性问题。此示例在实际运行时如果输入为“abb”时可以正确生成有
两个子节点的语法树。
Nil（根节点）
ab
b
如果输入为“ab”会出现MismatchedTokenException异常，因为现在分析器的greedy
属性为true。这时分析器会尽可能的匹配输入的字符“ab”被规则A匹配，这时规则B就
没有了可匹配的字符，所以出现了MismatchedTokenException异常。
如果我们将规则A中可选的’b’定义为greedy=false;代码如下。
c : A B;
A : 'a' (options {greedy=false;} : 'b')?;
B : 'b';
当输入“ab”和“abb”时生成的语法树同样为：
Nil（根节点）
a
b
规则A中的’b’由于是可选项并且其后规则B中也需要匹配’b’字符所以在Greedy
属性为false时规则A不去匹配字符’b’。这样输入的字符串中第一个’b’字符与规则B
匹配，第二个’b’字符无处匹配。
3.7“.”相关注意
词法定义中有一些与通配符“.”有关的注意事项，下面给出一个示例。
d : C ANY PLUS;
C : 'c';
PLUS : '+';
ANY : ( options {greedy=false;} : . ) *;
这个文法是要匹配输入字符“c”和“+”，字符“c”与“+”之间可以是一些不确定的
内容所以用通配符“.”进行匹配，如前面学到的应该使用greedy=false设置。但是此文法
运行时会出现死循环情况。我们可以使用其它方法改写定义，由于字符“c”与“+”之间不
应该出现“c”与“+”字符，所以ANY规则可以修改成以下的定义方法。
ANY : ~(C | PLUS)*;
不过如何正确使用“.”通配符呢？在使用通配符定义规则时要在当前的规则中明确的
指定开始和结束字符。前面的示例中定义/**/注释时就是指定了开始结束字符。本示例只能
改成：
d : CANYPLUS;
CANYPLUS : ‘c’ ( options {greedy=false;} : . ) * ‘+’;
所以“.”的使用范围是有限的。
3.8 fragment词法规则
ANTLR文法中语法规则是在词法规则基础上建立的。但不一定每个词法规则都会被语法
规则直接使用。这就象一个类的公有成员和私有成员，公有成员是对外公开的会被外界直接
调用。而私有成员不对外公开是由公有成员间接调用的。在词法规则中那些不会被语法规则
直接调用的词法规则可以用一个fragment关键字来标识，fragment标识的规则只能为其它
词法规则提供基础。
grammar TestFragment;
options {
language=CSharp;
output=AST;
}
a : INT;
INT : DIGIT+;
fragment DIGIT : '0' .. '9';
此示例中词法符号INT定义了整型数，而DIGIT定义了一位数字。语法规则a对DIGIT
规则的使用是间接的，这时使用fragment来标识DIGIT规则，DIGIT规则将不能被语法规
则直接调用。如果如下例语法规则a直接调用DIGIT规则，运行时语法分析器会死循环。
a : DIGIT;
INT : DIGIT+;
fragment DIGIT : '0' .. '9';
在不使用fragment关键字的时候，有时语法规则也不能直接使用某些词法规则。请看
下面的示例。
a : DIGIT;
INT : DIGIT+;
DIGIT : '0' .. '9';
运行后输入“9”分析器生成的语法树为空，使用java命令行运行时提示“line 1:0
mismatched input '0' expecting DIGIT ”。这是因为DIGIT规则匹配的内容对INT规则来
说也是匹配的，INT规则干扰了DIGIT规则的匹配，造成DIGIT规则没有匹配的内容。
a : DIGIT;
fragment INT : DIGIT+;
DIGIT : '0' .. '9';
如果在INT前加入fragment则分析器可以生成有一个节点“9” 的语法树，不过在实
际中不应该这样定义。在第五章我们会学到fragment词法规则是可以带参数的，这样可以
在词法分析的过程中灵活的控制，fragment词法规则具有更大的意义。
3.9 filter=true
我们在分析源代码时有时只想获得其中一部分信息，例如：我们想知道一个java文件
中的类的类名，类有哪些方法，方法的参数和返回值及其类型，属性及其类型和此类继承了
什么类。但是我们必须写出java的全部文法才可以分析java文件，这很有难度也没有必要。
ANTLR中加入了一个叫filter的设置项，filter为布尔类型默认为false。filter为true
时词法分析器可以处于一种过滤状态，我们只需定义出我们关心部分的词法结构，其它部分
全部被忽略掉。
filter=true模式中的词法规则是有优先顺序的，写在最前面的词法规则优先级最高之
后从高到低依次排列。这样规定是因为有些规则会被其它规则所包含造成一些规则无法被识
别出来。请看下面的示例：
lexer grammar TestFilter;
options {
filter=true;
language=CSharp;
}
A : aText=AA{ine("A: "+$);};
B : bText=BB{ine("B: "+$);};
AA : 'ab';
BB : 'a';
执行代码为：
ICharStream input = new ANTLRFileStream("");
FuzzyJava2Lexer lex = new FuzzyJava2Lexer(input);
ITokenStream tokens = new CommonTokenStream(lex);
ng();
此文法中规则AA匹配字符串“ab”，规则BB匹配字符串“a”，规则AA包含规则BB。
文件中的内容为“xxxxxxabxxxxx”。我们看一看是内容规则A匹配优先还是规则B优
先匹配，这可以反应出优先关系。这个例中输出为：“A : ab”。这说明规则A优先匹配了。
下面修改一下文法：
B : bText=BB{ine("B: "+$);};
A : aText=AA{ine("A: "+$);};
BB : 'a';
AA : 'ab';
相同的输入这次输出为：B : a。这说明规则B优先匹配了。但是如果将规则BB改为匹
配字符“b”则输出为“A : ab”。
B : bText=BB{ine("B: "+$);};
A : aText=AA{ine("A: "+$);}; //输出为 A : ab
BB : 'b';
AA : 'ab';
下面给出一个从java文件中读取类，方法，属性信息的示例。
lexer grammar FuzzyJava2;
options {
filter=true;
}
IMPORT : 'import' WS name=QIDStar WS? ';'
{ine("Import: "+$);};
PACKAGE : 'package' WS name=QID WS?';'
{ine("Package: "+$);};
CLASS : 'class' WS name=ID WS? ('extends' WS QID WS?)?
('implements' WS QID WS? (',' WS? QID WS?)*)? '{'
{ine("Class: "+$);};
METHOD : type1=TYPE WS name=ID WS?
'(' ( ARG WS? (',' WS? ARG WS?)* )? ')' WS?
('throws' WS QID WS? (',' WS? QID WS?)*)? '{'
{ine("Method: "++" "+$ + "()");};
FIELD : defvisi=DEFVISI WS TYPE WS name=ID '[]'? WS? (';'|'=')
{ine("Field:"+$+"
"+$+";");};
DEFVISI : 'public' | 'protected' | 'private';
USECOMMENT : '/**' (options {greedy=false;} : . )* '*/' ;
COMMENT : '/*' (options {greedy=false;} : . )* '*/'
//{ine("found comment "+Text);};
SL_COMMENT : '//' (options {greedy=false;} : . )* 'r'?'n' ;
WS : (' '|'t'|'r'|'n' )+ ;
STRING : '"' (options {greedy=false;}: ESC | .)* '"';
CHAR : ''' (options {greedy=false;}: ESC | .)* ''';
fragment QID : ID ('.' ID)*;
fragment QIDStar : ID ('.' ID)* '.*'? ;
fragment TYPE : QID '[]'?;
fragment ARG : type=TYPE WS name=ID
{ine("Param: "+$ + " "+$ + " ,
");};
fragment ID : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*;
fragment ESC : '' ('"'|'''|'');
分析此java源代码。
/* [The "BSD licence"] Copyright (c) 2005-2006 Terence Parr
All rights reserved.*/
package is;
import ;
import dHashSet;
import ;
import r;
import .*;
public class DFAState extends State {
public DFA dfa;
public DFAState(DFA dfa) {
= dfa;
}
public int addTransition(DFAState target, Label label) {
( new Transition(label, target) );
return ()-1;
}
/** Print all NFA states plus what alts they predict */
public int getLookaheadDepth() {
return k;
}
public void setLookaheadDepth(int k) {
this.k = k;
if ( k > _k ) { // track max k for entire DFA
_k = k;
}
}
}
如果将上面的java程序分析后会输出下面的结果。
Package: is
Import:
Import: dHashSet
Import:
Import: r
Import: .*
Class: DFAState
Field:public dfa;
Param: DFA dfa ,
Method: public DFAState()
Param: DFAState target ,
Param: Label label ,
Method: int addTransition()
Method: int getLookaheadDepth()
Param: int k ,
Method: void setLookaheadDepth()
3.10常用词法规则
下面给出一组很常用的词法定义规则：
grammar Abstract;
NAME :
(LETTER | UNDERLINE | CHINESECHAR)
(LETTER | UNDERLINE | DIGIT | CHINESECHAR)* ;
LETTER : ('A'..'Z' | 'a'..'z');
CHINESECHAR : 'u4E00' .. 'u9FA5' | 'uF900' .. 'uFA2D';
INT : DIGIT+;
DIGIT : '0' .. '9';
COLON : ':' ;
COMMA : ',' ;
SEMICOLON : ';' ;
LPAREN : '(' ;
RPAREN : ')' ;
LSQUARE : '[' ;
RSQUARE : ']' ;
LCURLY : '{';
RCURLY : '}';
DOT : '.' ;
UNDERLINE : '_';
ASSIGNEQUAL : '=' ;
NOTEQUAL1 : '<>' ;
NOTEQUAL2 : '!=' ;
LESSTHANOREQUALTO1 : '<=' ;
LESSTHAN : '<' ;
GREATERTHANOREQUALTO1 : '>=' ;
GREATERTHAN : '>' ;
DIVIDE : '/' ;
PLUS : '+' ;
MINUS : '-' ;
STAR : '*' ;
MOD : '%' ;
AMPERSAND : '&' ;
TILDE : '~' ;
BITWISEOR : '|' ;
BITWISEXOR : '^' ;
POUND : '#';
DOLLAR : '$';
COMMENT : '/*' . * '*/' {$channel=HIDDEN;} ;
LINE_COMMENT : '//' ~ ('n' | 'r') * 'r'? 'n' {$channel=HIDDEN;} ;
WS : ( ' ' | 't' | 'n' | 'r' ) + {Skip();} ;
3.11大小写敏感
ANTLR中没有大小写是否敏感的设置项，所以只能象下面的词法规则这样定义大小写不
敏感的单词。
SELECT : ('S'|'s')('E'|'e')('L'|'l')('E'|'e')('C'|'c')('T'|'t') ;
FROM : ('F'|'f')('R'|'r')('O'|'o')('M'|'m');
还有一种方法是重载输入的Stream类的LA方法在其中将输入的内容大小写不敏感。
package e;
import .*;
/** @author Jim Idle */
public class ANTLRNoCaseFileStream extends ANTLRFileStream {
public ANTLRNoCaseFileStream(String fileName) throws IOException {
super(fileName, null);
}
public ANTLRNoCaseFileStream(String fileName, String encoding)
throws IOException {
super(fileName, encoding);
}
public int LA(int i) {
if ( i==0 ) {
return 0; // undefined
}
if ( i<0 ) {
i++; // e.g., translate LA(-1) to use offset 0
}
if ( (p+i-1) >= n ) {
return ;
}
return rCase(data[p+i-1]);
}
}
C#代码如下：（注 可是在lookahead时临时转换成小写，原来输入字符不会受到影响。）
public class CaseInsensitiveStringStream : ANTLRStringStream {
public
public CaseInsensitiveStringStream() {}
public CaseInsensitiveStringStream(string input) : base(input) {}
public override int LA(int i) {
if (i == 0) {
return 0;
}
if (i < 0) {
i++;
}
if (((p + i) - 1) >= n) {
return (int) ;
}
return rInvariant(data[(p + i) - 1]);
CaseInsensitiveStringStream(char[] data, int
numberOfActualCharsInArray) : base(data,
numberOfActualCharsInArray) {}
}
}
3.11本章小结
本章讲述了ANTLR如何定义词法规则，包括：定义各种编码的字符，通配符“.”和“..”、
“~”、“.”符号的用法，skip()方法的用法，$channel = HIDDEN输入频道，greedy=false
的用法和注意事项，fragment词法规则的用法。这些内容为ANTLR中词法分析中基础，后
面章节还会讲述词法规则中潜入代码和词法中的二义性的内容。学完本章后读者应该可以定
义一种语言的基本词法规则，下一章我们讲述如何在词法规则的基础上定义语法规则的内
容。
第四章 语法分析
语法分析是编译过程的第二步，在词法分析提供的记号流的基础上，对源代码的结构做
总体的分析。无论分析的内容有多大语法分析总是由一个启始规则开始的，最后总是生成一
棵语法树。一般情况语法规则是一个文法的主体部分，也是编写文法的难点。本章用几个示
例来讲述如何用ANTLR定义语法规则。
4.1语法分析的方法
在ANTLR中语法分析定义的规则名必须以小写字母开始大写如“baseClass”，
“subfixSymbol”。如果词法规则与语法规则写在同一个文件时，虽然ANTLR中并没有严格
定义规则的先后顺序，但一般情况下语法规则写到词法规则的上面，因为整个文法的启始规
则是从语法规则开始的，这样可以从上到下查看整个文法。
ANTLR中语法定义的方法与词法基本相同请看下面一个SQL文法的片段示例:
grammar Test;
sqlStatement : selectStatement | insertStatement | deleteStatement;
selectStatement : SELECT (ALL | DISTINCT)? SelectList FROM tableSource;
SelectList : SelectItem+;
tableSource : TableName | '(' selectStatement ') ';
4.2递归定义
定义文法时通常出现递归的情况，比如上例中tableSource中的子查询就是一个递归定
义。在C++，C#，java语言中类名这样的符号是用“.”分隔的多个标识符组成的，如，
等这种情况需要使用递归的方法来定义，递归有左递归和右递归。
左递归:
qualifiedName : qualifiedName '. ' Identifier;
qualifiedName : Identifier;
Identifier : ('a'.. 'z' | 'A'.. 'Z' | '_') ('a'.. 'z' | 'A'.. 'Z' | '_' | '0'..
'9')*;
右递归:
qualifiedName : Identifier '.' QualifiedName
qualifiedName : Identifier;
Identifier : ('a'.. 'z' | 'A'.. 'Z' | '_') ('a'.. 'z' | 'A'.. 'Z' | '_'| '0'..
'9')*;
不过在ANTLR中不允许左递归定义，ANTLR会提示:“rule is left-recursive”错误。
ANTLR中还有别一种定义方法，象类名这样的符号递归定义使用这种方法是最好的方案。原
因我们会在后面章节讲述。
qualifiedName : Identifier ('.' Identifier)*;
Identifier : ('a'.. 'z' | 'A'.. 'Z' | '_') ('a'.. 'z' | 'A'.. 'Z' | '_' | '0'..
'9')*;
4.3 java方法的文法示例
下面来看一个定义java方法的文法，些文法是从ANTLR自带的java.g示例中选出的一
段:
methodDeclaration :type Identifier
(('(' (variableModifier* type formalParameterDeclsRest?)? ')')
('[' ']')*
('throws' qualifiedNameList)?
( methodBody
| ';'
)) ;
formalParameterDeclsRest :
variableDeclaratorId
(',' (variableModifier* type formalParameterDeclsRest?))?
| '...' variableDeclaratorId
;
type : Identifier (typeArguments)?
('.' Identifier (typeArguments)? )* ('[' ']')*
|
;
primitiveType ('[' ']')*
variableModifier : 'final' | annotation ;
formalParameterDeclsRest :
variableDeclaratorId
(',' (variableModifier* type formalParameterDeclsRest?))?
| '...' variableDeclaratorId
;
variableDeclaratorId : Identifier ('[' ']')* ;
Identifier : ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')*;
typeArguments : '<' typeArgument (',' typeArgument)* '>' ;
typeArgument : type
| '?' (('extends' | 'super') type)? ;
qualifiedNameList :qualifiedName (',' qualifiedName)* ;
qualifiedName :Identifier ('.' Identifier)* ;
methodDeclaration为方法定义的起始规则，后面type Identifier为方法的返回值和
方法名，( '(' (variableModifier* type formalParameterDeclsRest?)? ')' ) ('[' ']')*
中的variableModifier为参数前的标识符，type为参数的类型formalParameterDeclsRest
是对参数其余部分的定义，参数表在“（）”中，后面是“[]”字符，这是数组类型为返回值
时需要的，因为数据可以是多维的后是用('[' ']')*来定义。
formalParameterDeclsRest用来定义参数表部分，variableDeclaratorId为参数名，
如何有一个以上参数(',' (variableModifier* type formalParameterDeclsRest?))?部分
字义了第二个到第N个参数的规则，这里使用了右递归方法。Java1.5中支持可变参数 '...'
variableDeclaratorId为可变参数的定义。
另外typeArguments配合Identifier来定义泛型类型，使用“<>”括起来一个类型列
表，如List
Hashtable
4.4 | 作用范围
上例中的typeArgument : type | '?' (('extends' | 'super') type)? 规则无须写
成typeArgument:type | ('?' (('extends' | 'super') type)?)。在同一规则或子规则
中“|”使其两侧的内容为并列的选择关系，如果有多个“|”则一起为并列的选择关系，需
要改变优先顺序时才使用“（）”。
4.5 SELECT语句文法示例
下面给出一个SQL SELECT语句文法片段的例子。
grammar Select;
statement
: selectStatement (SEMICOLON)?;
selectStatement
: queryExpression (computeClause)? (forClause)? (optionClause)?;
queryExpression
: subQueryExpression (unionOperator subQueryExpression)* (orderByClause)?
;
subQueryExpression
: querySpecification | ‘(‘ queryExpression ‘)’
;
querySpecification
:
;
selectClause
: SELECT (ALL | DISTINCT)? (TOP Integer (PERCENT)?)? selectList
;
whereClause
: WHERE searchCondition
;
orderByClause
: ORDER BY expression (ASC | DESC)? (COMMA expression (ASC | DESC)? )*
;
groupByClause
:GROUP BY (ALL)? expression (COMMA expression)* (WITH (CUBE | ROLLUP) )?
;
havingClause
: HAVING searchCondition
;
SEMICOLON : ';';
我们对SELECT语句都比较熟悉，看一下SELECT语句文法的大体结构。selectStatement
规则表示整个SELECT语句体系，queryExpression表示查询语句可能由多个子查询用UNION
到一起unionOperator代表UNION或UNION ALL关键字，orderByClause子句出现在SELECT
语句的最后，这里subQueryExpression和queryExpression之间形成了递归定义，子查询
selectClause (fromClause)? (whereClause)?
(havingClause)? )?
(groupByClause
中还可以有子查询。whereClause子句和havingClause子句后面都是查询过滤表达式后成
它们共用searchCondition规则。
4.6 HTML文法示例
下面再看一个HTML文法片段示例:
grammar HTML;
options {language=CSharp; output=AST;}
document : OHTML body CHTML;
body : obody (body_content)* CBODY ;
body_content : body_tag | text;
body_tag : block; // | heading | ADDRESS
text : text_tag;
text_tag : form;// phrase | special | font
block : table;//paragraph | list | preformatted | div | center | blockquote
| HR |
table : otable (tr)+ CTABLE;
tr : o_tr (th_or_td)* (C_TR)? ;
th_or_td : o_th_or_td (body_content)* (C_TH_OR_TD )?;
form : oform (form_field | body_content)* CFORM;//
oform : '
form_field : inputField;// | select | textarea;
inputField : '
obody : '
CBODY : '
OHTML : '';
CHTML : '';
otable : '
CTABLE : '';
o_tr : '
C_TR : '';
o_th_or_td : ('
C_TH_OR_TD : '' | '';
CFORM : '';
ATTR : WORD ('=' (WORD ('%')? | ('-')? INT | STRING | HEXNUM))?;
HEXNUM : '#' ('0'..'9' | 'a'..'f')+;
INT : (DIGIT)+;
DIGIT : '0'..'9';
WORD : (LCLETTER | '.' | '/') (LCLETTER | DIGIT | '.')+;
STRING : '"' (~'"')* '"' | ''' (~''')* ''';
LCLETTER : 'a'..'z';
WS : ( ' ' | 't' | 'n' | 'r' ) + {Skip();} ;
这个可运行的简化的HTML文法中只支持