ANTLR指南（v3.0）第一章Hello WorldJVM.NET ANTLR文法ANTLR RuntimeC#生成Javacsc.exe语法分析器编译javac.exee语法分析器编译CC++Python… …嵌入C#，java…代码片段ANTLR是ANother Tool for Language Recognition的缩写“又一个语言识别工具”从名字上可以看出在ANTLR出现之前已经存在其它语言识别工具了（如LEX[1] 一种词法分析器（分描器）的自动产生系统，用正则表达式来描述文法结构[1]，YACC[2] 一种语法分析程序的自动产生器，可以处理能用LALR(1)文法表示的上下文无关语言[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示例本章将开发一个简单示例让读者对ANTLR有一个初步的认识，并搭建开发环境以便后续的学习读者在示例中遇到不懂的地方也不必担心，我们的目的是搭建开发环境学会编译运行语法分析器用ANTLR开发一个语法分析器大致分三步，第一步：写出要分析内容的文法第二步：用ANTLR生成相对该文法的语法分析器的代码第三步：编译运行语法分析器和多数编译书籍一样，本章也用解析简单的表达式作为示例要解析的表达式中有二种数据类型：整数 如“23”, “5” 和字符串 如“Hello World”表达式中以算术表达式为主也包括赋值表达式我们列举两个表达式语句：23+4*(5+1); str=“Hello World”;第一条语句是一个算术表达式，括号改变了运算顺序，计算结果不赋给任何变量。
第二条是一个赋值表达式，将字符串赋给一个变量后面我们要开发一个语法分析器来分析这两条语句在开发之前先简单提一下语法树的概念，在语法分析中一般用树来表示语法结构，表达式的语法树是以操作符为根节点操作数为子节点的树形结构，23+4*(5+1)的语法树根据操作符的优先级如下23*4+51图1.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表示让语法分析器返回包含语法树的信息第三行开始是文法定义部分，文法是用EBNF1 EBNF：BNF是被用来形式化定义语言的语法，以使其规则没有歧义EBNF在BNF基础上改进了定义形式比BNF更写法更简洁推导式来描述的（有关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.html ANTLR的下载页，www.antlr.org为ANTLR的官方网站，ANTLR是一个开源项目可以免费下载图1.1为开发环境ANTLRWorks的下载页面，图1.2为开发环境ANTLR Runtime3.01的下载页面您的机器上需要安装JDK1.5或更高版本的java SDK其中ANTLRWorks的下载文件名叫antlrworks-1.1.7.jar安装JDK后可以直接双击运行打开ANTLRWorks开发环境图1.3）ANTLRWorks下载页面（图1.4）ANTLR Runtime下载页面（图1.5）ANTLRWorks IDE1.3 Java环境的运行下面录入文法文件，运行ANTLRWorks点击“File – New”菜单新建文法文件，在新文件中将前面的文法录入我的网站中有本书所有示例源代码，但我建议您还是手工录入一遍这样您会有更好的学习效果。
录入文法后点击“File – Save” 菜单文件名为“E.g”然后点击“Generate–Generate Code”，如果ANTLRWorks提示“The grammar has been successfully generated in path…”说明ANTLRWorks成功生成了语法分析器的代码会在“E.g”的当前目录中生成“ELexer.java”、“EParser.java”、“E.tokens”和“E__.g”四个文件，其中有两个java源文件ELexer.java”为词法分析部分的代码，“EParser.java”为语法分析部分的代码那么为什么会生成java代码呢？ANTLR在不指定目标语言的情况下默认是java语言我们也可以在文法文件中加入options项指定目标语言grammar E;options { output=AST; language=Java; }program : statement + ;……生成了代码后，我们来编译运行语法分析器刚才生成的是java代码，所以先来看看java如何编译运行首先要有一个执行程序的main方法，这个类如下：import org.antlr.runtime.*;import org.antlr.runtime.tree.*;public class run{ public static void main(String[] args) throws Exception { ANTLRInputStream input = new ANTLRInputStream(System.in); ELexer lexer = new ELexer(input); CommonTokenStream tokens = new CommonTokenStream(lexer); EParser parser = new EParser(tokens); EParser.program_return r = parser.program(); System.out.println(((BaseTree)r.getTree()).toStringTree()); }}把这段代码存入run.java文件中，main方法功能是从命令行接收输入的表达式，通过词法分析和语法分析两个步骤来获得这个表达式的语法树，并以字符串的形式输出语法树的内容。
ANTLRInputStream input = new ANTLRInputStream(System.in);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);EParser.program_return r = 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 *.javarun.java中的import org.antlr.runtime.*;import org.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.jar run好的我们来执行这两个字符串来编译并执行程序，执行程序后命令行光标会等待输入，把之前准备分析的两个表达式输入，然后按Ctrl+Z（Windows系统Ctrl+Z，UNIX系统Ctrl+D）表示输入结束，然后回车23+4*(5+1);str="hello world";^Z23 + 4 * ( 5 + 1 ) ; str = "hello world" ;程序输出23 + 4 * ( 5 + 1 ) ; str = "hello world" ;这表示程序执行成功了我们的语法分析器已经正确的解析了这两个表达式您可以试着用不规则的格式输入两个表达式会得到相同的输出，因为已经正确分析了表达式的语法，所以输出格式化的字符串对我们的分析器来说是很简单的事情了 23 +4*( 5+ 1);str= " hello world ";^Z23 + 4 * ( 5 + 1 ) ; str = " hello world " ;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菜单生成代码，这时目录中会生成四个文件“ELexer.cs”、“EParser.cs”、“E.tokens”和“E__.g”E.tokens和E__.g文件与之前Java开发中生成的两个同名文件是一样的，另外ELexer.cs为词法分析器，EParser.cs为语法分析器在.NET开发中我们采用Visual Studio.NET2005做为开发环境，让我们的示例和真正的开发贴近一些在Visual Studio.NET2005中先新建一个名称为“HelloWorld”的C# WindowApplication项目，将生成的ELexer.cs、EParser.cs文件拷贝并加入到项目中。
再将.NET版的ANTLR Runtime的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中加入：using Antlr.Runtime;using Antlr.Runtime.Tree;我们要实现在文本框中输入表达式语句，点击按钮语法树结果显示在Label控件中在按钮的事件中加入如下代码：ICharStream input = new ANTLRStringStream(textBox1.Text);ELexer lex = new ELexer(input);CommonTokenStream tokens = new CommonTokenStream(lex);EParser parser = new EParser(tokens);EParser.program_return progReturn = 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的语法树文法修改如下：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);str="hello world";^Z(+ 23 (* 4 ( + 5 1 ))) (= str "hello world" )程序的输出结果了发生了变化：算术表达式的语法树输出字符串形式为：(+ 23 (* 4 (+ 5 1))) 我们已经使“（）”不出现在语法树中了，所以输出字符串中的括号并不是我们输入的表达式括号，这些括号表示语法树的结构由于我们让操作符为根节点，所以这里“+”、“*”操作符出现在前面，其后是它的左子树，再往后是它的右子树，内层括号是外号括号子树。
按照这个规则我们可以绘出语法树：+23 * 4 + 5 1绘出语法树和前面图1.1中的语法树是一样的，这说明我们已经正确的生成了语法树赋值表达式亦然我们可以在Visual Studio.NET 2005中运行在程序中设置断点并查看progReturn.Tree的对象内存情况图1.7语法树是BaseTree类型，BaseTree有一个children集合用来存放子语法树，子语法树也是BaseTree类型，可以利用VS.NET内存监视功能一级一级展开，看一看ANTLR的语法树的对象表现形式BaseTree类有一个GetChild(int i) 方法可以获取第N个子树，还有一个ChildCount属性代表子树的个数结合这两个属性和方法可以用如下的代码遍历子语法树for (int i = 0; i < tree.ChildCount; i++) { BaseTree currTree = (BaseTree)tree.GetChild(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.1tail recursion 尾递归 Left-Recursive左递归第二章 编译原理基础知识编译是将计算机高级语言如C++、Java、C#编写的源程序翻译成可以在计算机上执行的机器语言的翻译过程。
编译过程中分：词法分析、语法分析、语义分析、源代码优化、代码生成和目标代码优化几个过程ANTLR解决的是词法分析和语法分析的问题，下面介绍一下编译原理中有关词法分析和语法分析的基本知识词法分析语法分析语义分析源代码优化代码生成记号语法树注释树代码生成目标代码优化目标代码目标代码图2.1源程序字符串词法分析是对源程序一个一个字符地读取，从字符中识别出标识符、关键字、常量等相对独立的记号（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 ( ) { } }进行语法分析后形成语法树： 类类名属性方法T属性名名名句方法名类型名名句返回值NamestringGetValueobject我们这里不介绍编译原理的其它部分，因为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.22.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 => aAA=> bABcA=>aB=>dS2AabABadcK[S2]文法对于语型abadc的推导树为：推导的过程中优先选择不同的规则进行推导会使推导过程有所不同下面举一个例子K[S3]文法：S3 => ABDA=>aB=>bCC=>cD=>d下面是对于句型abcd的三种不同推导过程① S3=> ABD => aBD => abCD => abcD => abcd② S3=> ABD =>AbCD=>AbcD=>abcD=>abcdS3ABDabCcd③ S3=> ABD =>ABd=>AbCd=>Abcd=>abcd我们可以注意到①过程中所有推导都是选择的最左边的非终结符进行替换③过程中所有推导都是选择的最右边的非终结符进行替换其中①被称为最左推导，③被称为最右推导。
这三种推导都对应一棵语法树，这说明语法树反应了此句型的所有推导过程但是对于有些句型来说，它对应的语法树不一定唯一的也不是说一棵语法树不一定能反应一个句型的所有推导过程，如下面给定文法S4[E]文法：E => E + EE => E * EE => (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规则，不管选择哪个规则都是最左推导下面有两棵语法树与之对应对于一个文法的句型如果有多于一棵的语法树与之对应，则这个文法是有二义性的文法也可以用另一种方法判断，如果一个文法的最左或最右推导的过程是不唯一的也可以说这个文法是有二义性的文法推导②的语法树推导①的语法树EEEEE+*EEEEE*+iiiiii二义性文法是在开发语法分析器时需要解决的问题，我们将S4[E]加入操作符优先关系改成下面形式可以去掉文法的二义性。
S5[E]文法：E => T + TE => TT => F * FT => FF => (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 * iETTFF+*iiiF由于文法简单所以二义性比较容易解决，但是当文法很复杂的时候，检查文法中是否存在二义性就困难了但ANTLR的开发者不用担心，ANTLR会象我们编译普通源程序那样提示文法中的问题，其中包括文法的二义性问题，这使我们可以很容易的找到存在二义性的规则2.5分析方法前面讲到了句型的推导过程和生成语法树的过程，有了语法树就已经很清晰的看到了句型的结构，我们可以很容易的从语法树中获得我们相要的信息，这个过程就是语法分析如图2.3显示了对于SELECT F1, F2 FROM Table1 WHERE F1=”a”的语句进了语法分析后生成的语法树，利用非终结符节点SeletctList很容易对应Select语句的F1,F2部分SeletctStatementSeletctListSELECTFROMSeletctItemSeletctItemF1F1TableSourceTable1WhereConditionWHEREExprF1=“a”图2.3我们前面的推导是靠自己主观判断，选择适当的规则进行推导的。
那么如何用程序来实现这个过程呢？语法分析方法分两大类：自顶向下的分析方法和自下而上的分析方法ANTLR使用的是自顶向下的分析方法自顶向下的分析方法的思路是从起始规则开始选择适当的规则反复推导，直到推导出待分析的语型如果推导失败则反回选择其它规则进行推导（这个过程叫做回朔（backtrack）），如果所有规则都失败说明这个句型是非法的下面举一个分析的示例D1[S]文法：S => aBdB => bB = > bc对于abcd句型进行自顶向下分析，第一步唯一的选择规则S => aBd，第二步对非终结符B的推导，先选择B => b推导出S => abd这和句型abcd不同所以推导失败现在返回到对B的推导，选择另一个规则B => bc行出S => abcd这次推导成功SSSaBdBcbad自下而上的分析方法与自顶向下分析方法相反，过程是逐个的扫描句型的符号使用适当的规则进行反复归约，直到归约成启始规则S如果这个过程失败，则返回选择其它规则进行归约我们使用自下而上的分析方法对D1[S]示例进行分析首先是扫描到了第一个符号a，a无法归约没有象X => a这样的规则然后继续扫描符号b，b可以用B = > b来归约得出aB。
然后扫描到符号c，这时aBc不能继续进行归约造成过程失败所以要返回前一步使用B => bc来归约得出aBd，aBd可以用S => aBd归约到SaBBcbadcbabcS不管是自下而上的分析方法还是自顶向下分析方法如果选择的规则不正确，就要返回重新尝试用其它规则进行推导或归约这在实际操作中会浪费很多时间分析程序的执行效率会降低为了解决这个问题，在编译技术中使用一种向前探测符号的方法（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。