ANTLR指南(v3.0).doc

ANTLR指南（v3.0）
第一章Hello World
JVM

.NET

ANTLR文法

ANTLR Runtime

C#

生成

Java

csc.exe

语法分析器

编译

javac.exee

语法分析器

编译

C

C++

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

+

5

1

图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 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”的当前目录中生成“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 *.java
run.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";
^Z
23 + 4 * ( 5 + 1 ) ; str = "hello world" ;

程序输出23 + 4 * ( 5 + 1 ) ; str = "hello world" ;这表示程序执行成功了。我们的语法分析器已经正确的解析了这两个表达式。您可以试着用不规则的格式输入两个表达式会得到相同的输出，因为已经正确分析了表达式的语法，所以输出格式化的字符串对我们的分析器来说是很简单的事情了。
23 +4*( 5+ 1
);str
= " hello world "
;
^Z
23 + 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.1
tail 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

属性名
名名句

方法名

类型
名名句

返回值

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

a

b

A

B

a

d

c

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

B

D

a

b

C

c

d

③ 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

E

E

E

E

*

+

i

i

i

i

i

i

二义性文法是在开发语法分析器时需要解决的问题，我们将S4[E]加入操作符优先关系改成下面形式可以去掉文法的二义性。
S5[E]文法：
E => T + T
E => T
T => F * F
T => F
F => (E)
F => i
使用S5[E]文法对于 i + i * i 句型的推导过程和语法