编译原理( 陈火旺)第2章 高级语言及其语法描述

第2章高级语言及其语法描述本章概述高级语言的结构和主要的共同特征，并介绍程序语言的语法描述方法。要学习和构造编译程序，理解和定义高级语言是必不可少的与机器语言或汇编语言比较，高级语言的优点：较接近数学语言和工程语言，比较直观、自然和易于理解便于验证其正确性，易于改错编写效率高易于移植2常用的高级语言FORTRAN 数值计算COBOL 事务处理PASCAL 结构程序设计ADA 大型程序、嵌入式实时系统PROLOG 逻辑程序设计ALGOL 算法语言C/C++ 系统程序设计Java Internet程序设计31程序语言的定义2高级语言的一般特性3程序语言的语法描述4任何语言实现的基础是语言的定义在语言定义方面：语言用户把语言定义理解为用户使用手册而编译程序研制者与一般用户有所不同，他们对哪些构造允许出现更感兴趣。即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它程序语言主要由两方面定义：语法语义1程序语言的定义5语法任何语言程序都可以看成是一定字符集（称为字母表）上的字符串（有限序列）。但是，什么样的字符串才算是一个合式的程序呢所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合式(well-formed)的程序。这些规则一部分称为词法规则，另一部分称为语法规则（或产生规则）不规范的总结：语法=形式结构=词法规则+语法规则=合式的程序1程序语言的定义6语法词法规则：单词符号的形成规则单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等描述工具：有限自动机语法规则：语法单位的形成规则语法单位通常包括：表达式、语句、分程序、过程、函数、程序等描述工具：上下文无关文法1程序语言的定义7语法语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义问题A→0|0B B→1CC→0|0BE→iE→E+EE→E*EE→(E)1程序语言的定义8语义对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题离开语义，语言只不过是一堆符号的集合。在许多语言中有形式上完全相同的语法单位（一样的源代码字符串片段），但含义却不一样。例如：加减乘除运算的结合律和交换律方向不同是否允许函数计算产生副作用相同until语句的不同翻译语义是指这样的一组规则，使用它可以定义一个程序的意义目前还没有公认的形式系统可自动构造出实用的编译程序我们采用基于属性文法的语法制导翻译方法。虽然这还不是一种形式系统，但比较接近形式化1程序语言的定义9语义一个程序语言的基本功能是描述数据和对数据的运算。所谓程序，从本质上来说是描述一定数据的处理过程程序的层次结构：1程序语言的定义程序子程序或分程序语句表达式数据引用算符函数调用10语义自上而下看上述层次结构：顶端是程序本身，它是完整的执行单位。一个程序通常是由若干个子程序或分程序组成的，它们常常含有自己的数据（局部名）。子程序或分程序是由于语句组成的。而组成语句的成分是各种类型的表达式。表达式是描述数据运算的基本结构，它通常含有数据引用、算符和函数调用自下而上看上述层次结构：我们希望通过对下层成分的理解来掌握上层成分，从而掌握整个程序1程序语言的定义11语义程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义：当从数学上考虑时，我们注重它的逻辑意义当从计算机角度来看时，我们注重它在机内的表示和实现的可能性与效率举例：一个表示实数的名字从逻辑上说，可以看成是一个变量或一个可用于保存实数的场所从计算机实现上说，可以看成是一个或若干个相继的存储单元，这些存储单元的每位都有特殊的解释（如符号位、阶码和尾数），它们能表示一个一定大小和精度的数值1程序语言的定义121程序语言的定义2高级语言的一般特性3程序语言的语法描述13高级语言的分类程序结构数据类型与操作语句与控制结构2高级语言的一般特性14高级语言的分类强制式语言(ImperativeLanguge)也称过程式语言：命令驱动，面向语句如：FORTRAN、C、Pascal，Ada应用式语言（ApplicativeLanguage）：注重程序所表示的功能，而不是一个接一个语句地执行如：LISP、ML基于规则的语言（Rule-basedLanguage）：检查一定的条件，当它满足值，则执行适当的动作如：Prolog面向对象语言（Object-OrientedLanguage）：封装性、继承性和多态性如：Smalltalk，C++，Java2高级语言的一般特性15程序结构FORTRAN一个程序由一个主程序段和若干辅程序段组成辅程序段可以是子程序、函数段或数据块每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译模块结构，没有嵌套和递归各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字2高级语言的一般特性16程序结构FORTRAN2高级语言的一般特性主程序 PROGRAM… …end辅程序1

SUBROUTINE… …end辅程序2

FUNCTION… …end17程序结构PASCALPASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。一个PASCAL过程：过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end2高级语言的一般特性18程序结构PASCAL作用域：一个名字能被使用的区域范围称作这个名字的作用域。允许同一个标识符在不同的过程中代表不同的名字名字作用域规则："最近嵌套原则"一个在子程序B1中说明的名字X只在B1中有效（局部于B1）如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X2高级语言的一般特性19程序结构PASCAL2高级语言的一般特性programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integer)20程序结构PASCALPASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申请和退还存贮空间2高级语言的一般特性21程序结构ADA程序包(package)：把数据和操作代码封装在一起，支持数据抽象一个程序包分为两部分：可见的规范说明部分，它定义了程序包外面可以访问的对象程序包体，它实际定义程序包的实现细节2高级语言的一般特性22程序结构ADA2高级语言的一般特性packageSTACKSis typeELEMisprivate; typeSTACKislimitedprivate; procedurepush(S:inoutSTACK;E:inELEM); procedurepop(S:inoutSTACK;E:outELEM); …endSTACK;packagebodySTACKSis procedurepush(S:inoutSTACK;E:inELEM); begin ……实现细节 endpush; procedurepop(S:inoutSTACK;E:outELEM); begin ……实现细节 endpop;end;23程序结构JAVAJava是一种面向对象的高级语言类（Class）继承(Inheritance)多态性(Polymorphism)和动态绑定(Dynamicbinding)2高级语言的一般特性24程序结构JAVA2高级语言的一般特性classCar{ intcolor_number; intdoor_number; intspeed; … push_break(){ … } add_oil(){ … }}

classTrash_Carextendscar{ doubleamount; fill_trash(){ … }}25数据类型与操作一个数据类型通常包括以下三种要素：用于区别这种类型数据对象的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作2高级语言的一般特性26数据类型与操作初等数据类型数值类型：可施行算术运算：+，-，*，/等整型、实型、复数、双精度逻辑类型：可施行布尔运算：∨，∧，┑等字符类型：可施行符号处理指针类型：指针的值指向另一些数据。假定P是指针，P:=addr(X)意味着P指向X，或说P的值将是变量X的地址有些语言用P↑表示指针P的内容。在P:=addr(X)的情况下，如令P↑:=0.3，则意味着X的值是0.32高级语言的一般特性27数据类型与操作初等数据类型标识符与名字标识符：以字母开头的，由字母数字组成的字符串标识符与名字两者有本质区别：标识符只是语法概念名字有确切的意义和属性2高级语言的一般特性28数据类型与操作初等数据类型标识符与名字2高级语言的一般特性Jordan?29数据类型与操作初等数据类型标识符与名字名字：值：单元中的内容属性：类型和作用域名字的性质的说明方式：静态确定：由说明语句来明确规定的隐含说明：FORTRAN中以I,J,K,…N为首的名字代表整型，否则为实型动态确定：走到哪里，是什么，算什么2高级语言的一般特性30数据类型与操作初等数据类型用计算机术语来说，名字可以看成是代表一个抽象的存储单元。这个单元的内容则认为是此名字的值。名字的值就是它所表示的对象此外，我们还必须指出名字的属性一个名字的属性包括类型和作用域：名字的类型决定了它能具有什么样的值，值在计算机内的表示方式，以及对他能施加什么运算名字的作用域规定了他的值存在范围只有在作用域内，名字才有对应的存储单元2高级语言的一般特性31数据类型与操作数据结构许多程序语言提供了一种由初级数据定义复杂数据的手段。下面我们将概述其中常见的定义方式：数组逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标数组可变与不可变：编译时能否确定其存贮空间的大小访问：给出数组名和下标值存放方式：按行存放，按列存放2高级语言的一般特性32数据类型与操作数据结构数组编译程序要做的就是实现地址计算公式，使数组元素得到正确的引用在编译过程中，当碰到数组说明时，必须把数组的有关的信息记录在一个“内情向量”之中，以便以后计算数组元素的地址时引用这些信息每个数组的内情向量必须包括：维数，各维的上下限，首地址，以及数组元素的类型等2高级语言的一般特性33数据类型与操作数据结构数组数组元素地址计算：数组A[10,20]的A[1，1]为a，各维下标为1，按行存放，那么A[i，j]地址为：a+(i-1)*20+(j-1)2高级语言的一般特性34数据类型与操作数据结构数组数组元素地址计算公式：2高级语言的一般特性35数据类型与操作数据结构数组内情向量包括：维数，各维的上、下限，首地址，以及数组（元素）的类型2高级语言的一般特性atypeCndnunln………d2u2l2d1u1l136数据类型与操作数据结构记录从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构如：Pascal语言采用下面形式定义记录：CARD:recordNAME:array[1…20]ofchar;

AGE:integer;

MARRIED:booleanend;2高级语言的一般特性37数据类型与操作数据结构记录假定CARD的首地址为a，那么：CARD.NAME 地址为 aCARD.AGE 地址为 a+20CARD.MARRIED 地址为 a+24每个CARD记录需用25B，由于整型量AGE必须从字（4B大小）的边界开始。因此每个CARD记录最好用28B。其中MARRIED占4B仅用1B，浪费3B2高级语言的一般特性38数据类型与操作数据结构字符串、表格、栈和队列字符串：符号处理、公式处理表格：本质上是一种记录结构线性表：一组顺序化的记录结构栈：一种线性表，后进先出，POP，PUSH2高级语言的一般特性39数据类型与操作抽象数据类型一个抽象数据类型包括：数据对象的一个集合作用于这些数据对象的抽象运算的集合这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作程序设计语言对抽象数据类型的支持Ada语言通过程序包（package）提供数据封装的支持Smalltalk、C++和Java语言则通过类（Class）对抽象数据类型提供支持2高级语言的一般特性40语句与控制结构表达式表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。形式：中缀：如X*Y、前缀：如-A、后缀：如P↑表达式形成规则：变量（包括下标变量）、常数是表达式若E1、E2为表达式，θ为二元算符，则E1θE2为表达式（一般采用中缀形式）若E为表达式，θ为一元算符，则θE（或Eθ）为表达式若E为表达式，则(E)是表达式2高级语言的一般特性41语句与控制结构表达式在多数语言中算术和逻辑算符的优先顺序一般规定如下：乘幂 （**或↑）一元负 （-）乘、除 （*，/，÷）加、减 （+，-）关系符 （<，=，>，<=，<>，>=）非 （﹁，not，或.NOT.）与 （∧，&，and或.AND.）或 （∨，∣，or或.OR.）隐含 （或imp）等值 （≡，～或equi）2高级语言的一般特性42语句与控制结构表达式算符的代数性质（交换率、结合率和分配率）常常可用来优化目标程序的质量。但是必须注意两点：代数性质引用到什么程度视具体语言的不同而不同如在ALGOL中把A*B+C*D处理成C*D+A*B，则至少是对ALGOL不够忠实数学上成立的代数性质在计算机上未必完全成立如：(A+B)+C=A+(B+C)在计算机上并不普遍成立2高级语言的一般特性43语句与控制结构语句从功能上说，语句大体可分两大类：说明性语句旨在定义不同数据类型的变量或运算执行性语句旨在描述程序的动作。执行性语句又可分：赋值语句控制语句输入/输出语句从形式上说，语句还可分为：简单句、复合句和分程序等2高级语言的一般特性44语句与控制结构语句赋值语句每个名字有两方面的特征：一方面它代表一定的存储单元另一方面它又以该单元的内容作为值赋值语句A:=B的意义：“把B的值送入A所代表的单元”对赋值号右边的B我们需要的是它的值（右值）对左边的A我们需要的是它所代表的存储单元的地址（左值）2高级语言的一般特性45语句与控制结构语句控制语句多数语言中所含的控制语句有：无条件转移语句：gotoL条件语句： ifBthenS ifBthenS1elseS2循环与句： whileBdoS repeatSuntilB fori:=E1stepE2untilE3doS过程调用语句： callP(X1,X2,…,Xn)返回语句： return(E)2高级语言的一般特性46语句与控制结构语句说明语句说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否相一致。许多说明语句没有相应的代码。但有些语句，如过程说明语句，和可变数组说明语句则有相应的目标代码简单句和复合句简单句是指那些不含其它语句成分的基本句，如赋值句、goto句等复合句则指那些句中有句的语句2高级语言的一般特性471程序语言的定义2高级语言的一般特性3程序语言的语法描述48上下文无关文法语法分析树与二义性形式语言鸟瞰3程序语言的语法描述49在引入文法定义前，首先介绍几个概念：设Σ是一个有穷字母表，它的每个元素称为一个符号Σ上的一个符号串是指由Σ中的符号所构成的一个有穷序列不包含任何符号的序列称为空字，记为ε用Σ*表示Σ上的所有符号串的全体，空字ε也包括在其中举例：若Σ={a,b}则Σ*={ε,a,b,aa,ab,bb,aaa,…}Φ表示不含任何元素的空集{}这里要注意ε、{}和{ε}的区别3程序语言的语法描述50在引入文法定义前，首先介绍几个概念：Σ*的子集U和V中的（连接）积定义为： UV={αβ∣α∈U&β∈V}即集合UV中的符号串是由U和V的符号串连接而成的。注意，一般UVVU，但(UV)W=U(VW)。V自身的n次（连接）积记为： Vn=VV…V(n个V)规定V0={ε}。令 V*=V0∪V1∪V2∪V3∪…称V*是V的闭包。记V+=VV*，称V+是V的正则闭包闭包V*中的每个符号都是由V中的符号串经有限次连接而成的3程序语言的语法描述51在引入文法定义前，首先介绍几个概念：举例1： 设： U＝{a，aa}，V＝{b，bb} 那么： UV={ab，abb，aab，aabb}举例2： 设： U＝{a，aa} 那么： U*={ε，a，aa，aaa，aaaa，…} U+={a，aa，aaa，aaaa，…}3程序语言的语法描述52上下文无关文法文法是描述语言的语法结构的形式规则（即语法规则）所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的在自然语言中，语法性质和所处的上下文往往有密切的关系。因此，上下文无关文法当然不适宜于描述任何自然语言，但对程序语言来说基本是够用了3程序语言的语法描述53上下文无关文法举例：Hegavemeabook<句子>→ <主语><谓语><间接宾语><直接宾语><主语>→ <代词><谓语>→ <动词><间接宾语>→ <代词><直接宾语>→ <冠词><名词><代词>→ He<代词>→ me<名词>→ book<冠词>→ a<动词>→ gave3程序语言的语法描述54上下文无关文法举例：Hegavemeabook<句子>⇒<主语><谓语><间接宾语><直接宾语>⇒<代词><谓语><间接宾语><直接宾语>⇒He<谓语><间接宾语><直接宾语>⇒He<动词><间接宾语><直接宾语>⇒Hegave<间接宾语><直接宾语>⇒Hegave<代词><直接宾语>⇒Hegaveme<直接宾语>⇒Hegaveme<冠词><名词>⇒Hegavemea<名词>⇒Hegavemeabook3程序语言的语法描述55上下文无关文法归纳起来，一个上下文无关文法G包括四个组成部分：一组终结符号一组非终结符一个开始符号以及一组产生式3程序语言的语法描述56上下文无关文法终结符号所谓终结符号乃是组成语言的基本符号，即在程序语言中以前屡次提到的单词符号，如基本字，标识符，常数，算符和界符等非终结符所谓非终结符号（也称语法变量）用来代表语法范畴。如“算术表达式”、“布尔表达式”、“过程”等。一个非终结符代表一个一定的语法概念。因此非终结符是一个类（或集合）记号，而不是一个个体记号3程序语言的语法描述57上下文无关文法开始符号开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴，这个语法范畴通常称为“句子”。但在程序语言中我们最终感兴趣的是“程序”这个语法范畴，而其他的语法范畴都只不过是构造“程序”的一块块砖石产生式产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。一个产生式的形式是A→α，其中箭头左边的A是一个终结符，称为产生式的左部符号；箭头右边的α是终结符号或与非终结符号组成的一符号串，称为产生式的右部产生式是用来定义语法范畴的3程序语言的语法描述58上下文无关文法产生式举例：定义一类含+、*的算术表达式这个定义可以这样给出：变量是一个算术表达式若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式对于这个定义，若用产生式来描述，可将它写成：

E→i E→E＋E E→E＊E E→(E)其中E代表“算术表达式”，ｉ代表“变量”。3程序语言的语法描述59上下文无关文法形式上说，一个上下文无关文法Ｇ是一个四元式(VT，VN，S，P)，其中VT是一个非空有限集，它的每个元素称为终结符号VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=ΦS是一个非终结符号，称为开始符号P是一个产生式（有限）集合，每个产生式形式是A→α，其中，A∈VN，α∈(VT∪VN)*。开始符号S至少必须在某一产生式的左部出现一次3程序语言的语法描述60上下文无关文法几点规定：“→”也可以用“::="表示，称为巴科斯范式(BNF) P→α1 P→α2 …

P→αn

可缩写为P→α1|α2|…|αn其中，“|”读成“或”，称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式如上例，可表示为：G(E)：E→i|E+E|E*E|(E)3程序语言的语法描述61上下文无关文法定义：称αAβ直接推出αγβ，即

αAβ⇒αγβ仅当A→γ是一个产生式，且α、β∈(VT∪VN)*如果α1⇒α2⇒…⇒αn，则我们称这个序列是从α1到αn的一个推导若存在一个从α1到αn的推导，则称α1可以推导出αn定义：α1⇒+αn：从α1出发，经过一步或若干步，可以推出αnα1⇒*αn：从α1出发，经过0步或若干步，可以推出αn换言之，α⇒*β意味着：或者α=β或者α⇒+β3程序语言的语法描述62上下文无关文法定义：假定G是一个文法，S是它的开始符号。如果S⇒*α，则α称α是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G) L(G)={α|S⇒+α，α∈VT*}举例：终结符号串(i*i+i)是文法E→E+E|E*E|(E)|i的一个句子。是因为有从开始符号E至(i*i+i)的一个推导：E⇒(E)⇒(E+E)⇒(E*E+E)⇒(i*E+E)⇒(i*i+E)⇒(i*i+i)E,(E),(E*E+E)等是文法的句型3程序语言的语法描述63上下文无关文法下面介绍几个简单文法的例子：举例1：考虑一个文法G1(S)：

S→bA

A→aA|aG1(S)定义了一个什么语言呢？从开始符S出发，我们可以推出如下句子：

S⇒bA⇒ba

S⇒bA⇒baA⇒baa

S⇒bA⇒baA⇒…⇒baa…a可以写为：L(G1)={ban|n≥1}3程序语言的语法描述64上下文无关文法下面介绍几个简单文法的例子：举例2：考虑一个文法G2(S)：

S→AB

A→aA|a

B→bB|bG2(S)定义了一个什么语言呢？L(G2)={ambn|m，n≥1}3程序语言的语法描述65上下文无关文法下面介绍几个简单文法的例子：举例3：构造一个文法G3使

L(G3)={anbn|n≥1}可得G3(S)：S→aSb|ab3程序语言的语法描述66上下文无关文法定义：从一个句型到另一个句型的推导往往不唯一。例如：

E+E⇒i+E⇒i+i

E+E⇒E+i⇒i+i最左推导：任何一步α⇒β都是对α中的最左非终结符进行替换最右推导：任何一步α⇒β都是对α中的最右非终结符进行替换3程序语言的语法描述67语法分析树与二义性可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称语法树：语法树的根结由开始符号所标记随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生出下一代新结。每个新结和其父结间都有一条连线在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型3程序语言的语法描述68语法分析树与二义性一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导这样的一棵语法树是这些不同推导过程的共性抽象，是它们的代表如果我们坚持使用最左（最右）推导，那么一棵语法树就完全等价于一个最左（最右）推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致性3程序语言的语法描述69语法分析树与二义性举例：语法树是这些不同推导过程的共性抽象3程序语言的语法描述E⇒(E)⇒(E+E)⇒(E*E+E)⇒(i*E+E)⇒(i*i+E)⇒(i*i+i)最左推导E⇒(E)⇒(E+E)⇒(E+i)⇒(E*E+i)⇒(E*i+i)⇒(i*i+i)最右推导G(E)：E→i|E+E|E*E|(E)(i*i+i)的语法树70语法分析树与二义性一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有唯一的一个最左（最右)推导呢？----不尽然举例：文法G(E)：E→i|E+E|E*E|(E)中(i*i+i)的最左推导如下3程序语言的语法描述E⇒(E)⇒(E+E)⇒(E*E+E)⇒(i*E+E)⇒(i*i+E)⇒(i*i+i)E⇒(E)⇒(E*E)⇒(i*E)⇒(i*E+E)⇒(i*i+E)⇒(i*i+i)71语法分析树与二义性定义：如果一个文法存在某个句子对应两棵不同的语法树（或者有两个不同的最左/最右推导），则称此文法是二义的。如：文法G(E)：E→i|E+E|E*E|(E)是二义文法定义：文法的二义性和语言的二义性是两个不同的概念一个语言是二义性的，如果它不存在无二义性的文法即能产生该语言的所有文法都是二义文法可能存在G和G’，一个为二义文法，一个为无二义文法。但两文法产生的语言是相同的：L(G)=L(G’)3程序语言的语法描述72语法分析树与二义性我们常常希望对每个语句的分析是唯一的，希望程序语言的文法是无二义的。但是只要能够控制和驾驭文法的二义性，则文法二义性的存在并不一定是一件坏事参考第五章中对两个二义性LR表项目集冲突的修改：算术运算文法G(E)：E→i|E+E|E*E|(E)IFELSE文法G(S)：S→iSeS|iS|a定义：二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的可以找到一组无二义文法的充分条件举例：以下是二义文法和无二义文法的等价变换3程序语言的语法描述73语法分析树与二义性举例：二义文法和无二义文法的等价变换二义文法：

G(E)：E→i|E+E|E*E|(E)无二义文法：

G(E)：E → T|E+T T → F|T*F F → (E)|i

表达式→ 项|表达式+项 项 → 因子|项*因子 因子 → (表达式)|i3程序语言的语法描述74语法分析树与二义性举例：二义文法和无二义文法的等价变换句子(i*