编译原理：第二章 高级语言及其语法描述.ppt

合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所编译原理第二章第二章 高级语言及其语法描述高级语言及其语法描述 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所第二章第二章 高级语言及其语法描述高级语言及其语法描述 o常用的高常用的高级语言言n FORTRANFORTRAN数数值计算算n COBOLCOBOL事事务处理理n PASCALPASCAL结构程序构程序设计n ADAADA大型程序、嵌入式大型程序、嵌入式实时系系统n PROLOGPROLOG逻辑程序程序设计n ALGOLALGOL算法算法语言言n C/C+C/C+系系统程序程序设计n JavaJavaInternetInternet程序程序设计合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o与机器与机器语言或言或汇编语言比言比较，高高级语言的言的优点：点：n较接近于数学接近于数学语言和工程言和工程语言言，比比较直直观、自然和易于理解自然和易于理解;n便于便于验证其正确性其正确性，易于改易于改错;n编写效率高写效率高;n易于移植易于移植.合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.12.1 程序语言的定义程序语言的定义o程序程序语言是一个言是一个记号系号系统o程序程序语言由两方面定言由两方面定义：n语法法n语义n语用用合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所一一.语法语法o程序本程序本质上是一定字符集上的字符串。上是一定字符集上的字符串。o语法法：一：一组规则，用它可以形成和用它可以形成和产生一个生一个合式合式(well-formed)的程序（形式上正确的程的程序（形式上正确的程序）序）。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所语语 法法o词法法规则：单词符号的形成符号的形成规则。n单词符号是符号是语言中具有独立意言中具有独立意义的最基本的最基本结构构。一般包括：常数、一般包括：常数、标识符、基本字、算符、界符、基本字、算符、界符等。符等。n描述工具：有限自描述工具：有限自动机机o语法法规则：语法法单位的形成位的形成规则。n规定了如何从定了如何从单词符号形成符号形成语法法单位；位；n语法法单位通常包括：表达式、位通常包括：表达式、语句、分程序、句、分程序、过程、函数、程序等程、函数、程序等;n描述工具：上下文无关文法描述工具：上下文无关文法合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o EiEiEE+EEE+EEE*EEE*EE(E)E(E)o语法法规则和和词法法规则定定义了程序的的形式了程序的的形式结构，是判断构，是判断输入字符串是否构成一个形入字符串是否构成一个形式上正确的程序的依据。式上正确的程序的依据。o定定义语法法单位的意位的意义属于属于语义问题。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所二二.语义语义o对于于语言来言来说，不，不仅要要给出它的出它的词法、法、语法法规则，而且，而且要定要定义它的它的单词符号和符号和语法符号的意法符号的意义。离开了。离开了语义的的语言只是一堆符号的集合。各种言只是一堆符号的集合。各种语言中有形式上完言中有形式上完全相同的全相同的语法法单位，含位，含义却不相同。却不相同。o语义：对某种某种语言，定言，定义一一组规则，用它可以定用它可以定义一个一个程序的意程序的意义，称，称为语义规则。o描述方法：描述方法：n自然自然语言描述：言描述：隐藏藏错误、二、二义性和不完整性性和不完整性n形式描述：操作形式描述：操作语义(PL/1)(PL/1)、指称指称语义(ADA)(ADA)、代数代数语义(PASCAL)(PASCAL)。o目前大多数目前大多数编译程序使用基于属性文法的程序使用基于属性文法的语法制法制导翻翻译方法来分析方法来分析语义。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所三程序语言的基本功能和层次结构三程序语言的基本功能和层次结构o程序程序语言的基本功能：描述数据和言的基本功能：描述数据和对数据的数据的运算。运算。o所所谓程序，本程序，本质上上说是描述一定数据的是描述一定数据的处理理过程。程。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所程序的层次结构程序的层次结构程序程序|子程序或分程序、子程序或分程序、过程、函数程、函数|语句句|表达式表达式|数据引用数据引用 算符算符 函数函数调用用合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所程序语言每个组成成分的逻辑和实现意义程序语言每个组成成分的逻辑和实现意义 o抽象的抽象的逻辑的意的意义n数学意数学意义 o计算机算机实现的意的意义n具体具体实现合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.2 2.2 高级语言的一般特性（自学）高级语言的一般特性（自学）o高高级语言的分言的分类 n强制式语言强制式语言(Imperative(Imperative LangugeLanguge)也称也称过程式程式语言：命令言：命令驱动，面向，面向语句句oFORTRANFORTRAN、C C、PascalPascal，AdaAda n应用式语言应用式语言（Applicative LanguageApplicative Language）：注重程序所）：注重程序所表示的功能，而不是一个表示的功能，而不是一个语句接一个句接一个语句地句地执行行oLISPLISP、ML ML 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所n基于规则的语言基于规则的语言（Rule-based LanguageRule-based Language）：）：检查一定的条件，当它一定的条件，当它满足足值，则执行适当的行适当的动作作oProlog Prolog n面向对象语言面向对象语言（Object-Oriented LanguageObject-Oriented Language）：）：封封装性装性、继承性继承性和和多态性多态性oSmalltalkSmalltalk，C+C+，Java Java 2.2.1 2.2.1 高级语言的分类高级语言的分类 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所FORTRANFORTRANn一个程序由一个主程序段和若干一个程序由一个主程序段和若干辅程序段程序段组成。成。n辅程序段可以是子程序、函数段或数据程序段可以是子程序、函数段或数据块。n每个程序段有一系列的每个程序段有一系列的说明明语句和句和执行行语句句组成。成。各段可以独立各段可以独立编译。n模模块结构，没有嵌套和构，没有嵌套和递归n各程序段中的名字相互独立各程序段中的名字相互独立，同一个，同一个标识符在不符在不同的程序段中代表不同的名字同的程序段中代表不同的名字。2.2.2 2.2.2 程序结构程序结构合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所主程序主程序 PROGRAM PROGRAM end end辅程序辅程序1 1 SUBROUTINE SUBROUTINE end end辅程序辅程序2 2 FUNCTION FUNCTION end end合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所oPASCALnPASCAL程序本身可以看成是一个操作系程序本身可以看成是一个操作系统所所调用的用的过程，程，过程可以嵌套和程可以嵌套和递归。n一个一个PASCAL过程：程：过程程头；说明段（由一系列的明段（由一系列的说明明语句句组成）；成）；begin执行体（由一系列的行体（由一系列的执行行语句句组成）；成）；end合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所n作用域作用域：一个名字能被使用的区域范：一个名字能被使用的区域范围围称作称作这这个名字的作用域。个名字的作用域。n允允许同一个同一个标识符在不同的符在不同的过程中代表程中代表不同的名字。不同的名字。n名字作用域名字作用域规则规则-最近嵌套原最近嵌套原则则 o一个在子程序一个在子程序B1中中说明的名字明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；o如果如果B2是是B1的一个内的一个内层子程序且子程序且B2中中对标识符符X没有新的没有新的说明，明，则原来的名字原来的名字X在在B2中仍然有效。如果中仍然有效。如果B2对X重新作了重新作了说明，那么，明，那么，B2对X的任何引用都是指重新的任何引用都是指重新说明明过的的这个个X。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所program main var A,B:real;procedure P1 var B:boolean;begin end procedure P2 var A:integer;begin endbegin endA(real)B(real)B(bool)A(integer)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所nPASCAL提供了丰富的数据提供了丰富的数据类型和运算型和运算方式，它允方式，它允许用用户动态地申地申请和退和退还存存贮空空间。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所oADAn程程序序包包(package)：把把数数据据和和操操作作代代码封封装装在在一起，支持数据抽象。一起，支持数据抽象。n一个程序包分一个程序包分为两部分：两部分：o可可见的的规范范说明部分，它定明部分，它定义了程序包外面可以了程序包外面可以访问的的对象。象。o程序包体，它程序包体，它实际定定义程序包的程序包的实现细节。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所packageSTACKSistypeELEMisprivate;typeSTACKislimitedprivate;procedurepush(S:inoutSTACK;E:inELEM);procedurepop(S:inoutSTACK;E:outELEM);endSTACK;packagebodySTACKSisprocedurepush(S:inoutSTACK;E:inELEM);begin实现细节endpush;procedurepop(S:inoutSTACK;E:outELEM);begin实现细节endpop;end;合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所oJAVAnJava是一种面向是一种面向对象的高象的高级语言言o类（Class）o继承承(Inheritance)o多多态性性(Polymorphism)和和动态绑定定(Dynamic binding)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所classCarintcolor_number;intdoor_number;intspeed;push_break()add_oil()classTrash_Carextendscardoubleamount;fill_trash()合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.2.3 2.2.3 数据类型与操作数据类型与操作 o一个数据一个数据类型通常包括以下三种要素：型通常包括以下三种要素：n用于区用于区别这种种类型数据型数据对象的属性象的属性n这种种类型的数据型的数据对象可以具有的象可以具有的值n可以作用于可以作用于这种种类型的数据型的数据对象的操作象的操作合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所一初等数据一初等数据类型型n数数值类型：整型、型：整型、实型、复数、双精度，型、复数、双精度，运运算：算：+，-，*，/等等n逻辑类型：布型：布尔运算：运算：，n字符字符类型：符号型：符号处理理n指指针类型型合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所标识符与名字标识符与名字o标识符符：以字母开：以字母开头的的，由字母数字由字母数字组成的成的字符串字符串。o标识符符与与名字名字两者有本两者有本质区区别：n标识符符是是语法概念法概念n名字名字有确切的意有确切的意义和属性和属性合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所Jordan?标识符！?合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所标识符与名字标识符与名字o名字：名字：n值：单元中的内容元中的内容n属性：属性：类型和作用域型和作用域o名字的性名字的性质的的说明方式：明方式：n由由说明明语句来明确句来明确规定的定的n隐含含说明：明：FORTRAN FORTRAN 以以I,J,K,I,J,K,N N为首的名首的名字代表整型，否字代表整型，否则为实型。型。n动态确定：走到哪里，是什么，算什么确定：走到哪里，是什么，算什么 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所二二 数据结构数据结构1 1 数数组o逻辑上，数上，数组是由同一是由同一类型数据所型数据所组成的成的某种某种n n维矩形矩形结构，沿着每一构，沿着每一维的距离，称的距离，称为下下标。n数数组可可变与不可与不可变：编译时能否确定其存能否确定其存贮空空间的大小。的大小。n访问：给出数出数组名和下名和下标值n存放方式存放方式:按行存放按行存放,按列存放按列存放合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所数组元素地址计算数组元素地址计算o数数组A10,20A10,20的的A1A1，11为a a，各各维维下下标为标为1 1，按行存放，那么按行存放，那么AiAi，jj地址地址为：a+(i-1)*20+(j-1)a+(i-1)*20+(j-1)o数数组元素地址元素地址计算公式算公式合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所内情向量内情向量o把数把数组的有关信息的有关信息记录在一个在一个“内情向量内情向量”中，每个数中，每个数组的内情向量必的内情向量必须包括：包括：维数，各数，各维的上、下限，首地址，以及数的上、下限，首地址，以及数组（元素）的（元素）的类型。型。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2 2 记录记录o逻辑上上说，记录结构由已知构由已知类型的数据型的数据组合在一起的一种合在一起的一种结构。构。recordcharNAME20;integerAGE;boolMARRIED;CARD1000o访问：复合名：复合名 CARDk.NAMECARDk.NAMEo存存储：连续存放存放o域的地址域的地址计算：相算：相对于于记录结构起点的相构起点的相对数数OFFSETOFFSET。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所3 3 字符串、表格、栈字符串、表格、栈o字符串：符号字符串：符号处理、公式理、公式处理理o表格：本表格：本质上是一种上是一种记录结构构o线性表：一性表：一组顺序化的序化的记录结构构o栈：一种：一种线性表，后性表，后进先出，先出，POP,PUSHPOP,PUSH合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所三三 抽象数据类型抽象数据类型 o一个抽象数据一个抽象数据类型包括：型包括：n数据数据对象的一个集合；象的一个集合；n作用于作用于这些数据些数据对象的抽象运算的集合；象的抽象运算的集合；n这种种类型型对象象的的封封装装，即即，除除了了使使用用类型型中中所所定定义的运算外，用的运算外，用户不能不能对这些些对象象进行操作。行操作。o程序程序设计语言言对抽象数据抽象数据类型的支持型的支持nAda语言言通通过程程序序包包（package）提提供供了了数数据据封封装装的的支持支持nSmalltalk、C+和和Java语言言则通通过类（Class）对抽象数据抽象数据类型提供支持。型提供支持。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.2.4 2.2.4 语句与控制结构语句与控制结构一表达式一表达式n表达式由运算量（也称操作数，即数据引用或表达式由运算量（也称操作数，即数据引用或函数函数调用）和算符（操作符）用）和算符（操作符）组成。成。n形式：中形式：中缀、前、前缀、后、后缀 X*Y -A PX*Y -A Pn表达式形成表达式形成规则合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所算符的优先次序算符的优先次序o一般的一般的规定定nPASCALPASCAL：左左结结合合A+B+C=(A+B)+CnFORTRANFORTRAN：对于于满足左、右足左、右结合的算符可任合的算符可任取一种，如取一种，如A+B+CA+B+C就可以就可以处理成理成(A+B)+C(A+B)+C，也可以也可以处理成理成A+(B+C)A+(B+C)。o注意两点：注意两点：n代数性代数性质能引用到什么程度能引用到什么程度视具体的具体的语言言不同而不同；不同而不同；n在数学上成立的代数性在数学上成立的代数性质在在计算机上未必算机上未必完全成立。完全成立。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所二语句二语句o赋值语句：句：A:=B A:=B n名字左名字左值：该名字代表的那个名字代表的那个单元（地址）称元（地址）称为该名字的左名字的左值。(所代表的存所代表的存贮单元的地址元的地址)n右右值：一个名字的：一个名字的值称称为该名字的右名字的右值。(所所代表的存代表的存贮单元的内容元的内容)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o控制控制语句：句：l无条件转移语句无条件转移语句 goto Ll条件语句条件语句 if B then S if B then S1 else S2l循环语句循环语句 while B do S repeat S until B for i:=E1 step E2 until E3 do Sl过程调用语句过程调用语句 call P(X1,X2,.,Xn)l返回语句返回语句 return(E)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o说明明语句：定句：定义各种不同数据各种不同数据类型的型的变量或量或运算，定运算，定义名字的性名字的性质。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所简单句和复合句简单句和复合句o简单句：不包含其他句：不包含其他语句成分的基本句句成分的基本句o复合句：句中有句的复合句：句中有句的语句句合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所复习：程序语言的定义复习：程序语言的定义o程序程序语言由两方面定言由两方面定义：n语法法：一：一组规则，用它可以形成和用它可以形成和产生一个合式生一个合式(well-formed)的程序的程序o词法法规则：单词符号的形成符号的形成规则。n常数、常数、标识符、基本字、算符、界符等。符、基本字、算符、界符等。n有限自有限自动机机o语法法规则：语法法单位的形成位的形成规则。n表达式、表达式、语句、分程序、句、分程序、过程、函数、程序等程、函数、程序等;n上下文无关文法上下文无关文法n语义:一一组规则，用它可以定用它可以定义一个程序的意一个程序的意义合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所复习：程序语言的基本功能和层次结构复习：程序语言的基本功能和层次结构o程序程序语言的基本功能：描述数据和言的基本功能：描述数据和对数据的运算。数据的运算。o所所谓程序，本程序，本质上上说是描述一定数据的是描述一定数据的处理理过程。程。程序程序|子程序或分程序、过程、函数子程序或分程序、过程、函数|语句语句|表达式表达式|数据引用数据引用 算符算符 函数调用函数调用合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所复习：复习：高级语言的一般特性高级语言的一般特性 o高高级语言的分言的分类 o程序程序结构构o数据数据类型与操作型与操作n初等数据初等数据类型型n数据数据结构构n抽象数据抽象数据类型型o语句与控制句与控制结构构合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.32.3 程序语言的语法描述程序语言的语法描述 o几个概念几个概念:n考考虑虑一个一个有有穷 字母表字母表 字符集字符集n其中每一个元素称其中每一个元素称为为一个一个字符字符（符号：是符号：是语言中最基言中最基本的不可再分的本的不可再分的单位）位）n上的上的字字(也叫也叫字符串字符串、符号串符号串)是指由是指由中的字符中的字符所构成的一个有所构成的一个有穷穷序列序列n不包含任何字符的序列称不包含任何字符的序列称为为空字空字（空串）空串），记为记为n用用*表示表示上的所有字的全体上的所有字的全体,包含空字包含空字例如例如:设 =a=a，bb，则 *=,a,b,aa,ab,ba,bb,aaa,.,a,b,aa,ab,ba,bb,aaa,.合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o*的子集的子集U和和V的的连接接（积）定）定义为UV|U&V o设：U a,aa V b,bb o那么：那么：UV=ab,abb,aab,aabb 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o*的子集的子集U和和V的的连接接（积）定）定义为UV|U&V oV自身的自身的 n次次积记为Vn=VVVo规定定V0=，令，令 V*=V0V1V2V3 称称V*是是V的的闭包包;o记 VVV*，称，称V+是是V的正的正规闭包。包。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o设：U a,aa o那么：那么：U*=,a,aa,aaa,aaaa,U=a,aa,aaa,aaaa,合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.3.1 2.3.1 上下文无关文法上下文无关文法o文法文法：描述描述语言的言的语法法结构的形式构的形式规则oHegavemeabook.He He me me book book a a gave gave合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o上下文无关文法的定上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中nV VT T：终结符集合符集合(非空非空)nV VN N：非：非终结符集合符集合(非空非空)，且，且V VT T V VN N=nS S：文法的开始符号，：文法的开始符号，S S V VN NnP P：产生式集合生式集合(有限有限)，每个，每个产生式形式生式形式为P P，P P V VN N，(V VT T V VN N)*n开始符开始符S S至少必至少必须在某个在某个产生式的左部出生式的左部出现一一次。次。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o例，定例，定义只含只含+，*的算的算术表达式的文法表达式的文法 G=，其中，其中，P由下列由下列产生式生式组成：成：E iE E+EE E*EE (E)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o几点几点规定：定：n“”也可以用也可以用“:=表示，表示，这种表示称种表示称为巴巴科斯范式科斯范式(BNF)n P 1 P 2 可可缩写写为 P 1|2|n P n 其中，其中，“|”读成成“或或”，称，称为P的一个候的一个候选式。式。n表示一个文法表示一个文法时，通常只，通常只给出开始符号和出开始符号和产生生式，如上例，可表示式，如上例，可表示为：G(E)：E i|E+E|E*E|(E)n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=，其中，其中，P由下列产生式组成：由下列产生式组成：E iE E+EE E*EE (E)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o定定义：称：称 A 直接推出直接推出，即，即 A 仅当当A 是一个是一个产生式，生式，且且，(VT VN)*。o如果如果 1 2 n，则我我们称称这个序列个序列是从是从 1到到 n的一个的一个推推导。若存在一个从。若存在一个从 1到到 n的推的推导，则称称 1可以可以推推导出出 n。o对文法文法G(E)：E i|E+E|E*E|(E)E (E)(E+E)(i+E)(i+i)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所n通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步，可以推出一步或若干步，可以推出 n n。用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。所以所以 ：即即 或或q定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全体所产生的句子的全体是一个是一个语言语言，将它记为，将它记为 L(G)L(G)。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o例：例：(i*i+i)是文法是文法G(E)：E i|E+E|E*E|(E)的一个句子。的一个句子。证明：明：E (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E*E+E)，(i*i+i)是句型。是句型。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所q例：文法例：文法G1(A)：A c|AbG1(A)的语言的语言?L(G1)=c，cb，cbb，以以c开头，后继若干个开头，后继若干个b合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o例：文法例：文法G2(S)：S ABA aA|aB bB|bG2(S)的的语言言?L(G2)=ambn|m，n0合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所q例：给出产生语言为例：给出产生语言为anbn|n 1的文法。的文法。G3(S)：S aSb S ab合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所q例：给出产生语言为例：给出产生语言为ambn|1 n m 2n的文法。的文法。G4(S)：S aSb|aaSb S ab|aab 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o从一个句型到另一个句型的推从一个句型到另一个句型的推导往往不唯一。往往不唯一。E+Ei+Ei+i E+EE+ii+io最左推最左推导：任何一步：任何一步 都是都是对 中的最左中的最左非非终结符符进行替行替换。最右推最右推导：任何一步：任何一步 都是都是对 中的最右中的最右非非终结符符进行替行替换。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.3.2 2.3.2 语法树与二义性语法树与二义性o用一用一张图表示一个句型的推表示一个句型的推导,称称为语法法树。o(i*(i*i+ii+i)的的语法法树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)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o如果使用最左如果使用最左(右右)推推导，则一个最左一个最左(右右)推推导与与语法法树一一一一对应。o一个句型是否只一个句型是否只对应唯一一棵唯一一棵语法法树？合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o定定义义：如果一个文法存在某个句子如果一个文法存在某个句子对应对应两两颗颗不同的不同的语语法法树树，则说这则说这个个文法是二文法是二义义的的。G(E)：E i|E+E|E*E|(E)是二是二义文法。文法。o语言的二言的二义性：一个性：一个语言是二言是二义性的性的，如果，如果对它不存在无二它不存在无二义性的文法。性的文法。n可能存在可能存在G和和G，一个，一个为二二义的，一个的，一个为无无二二义的。但的。但L(G)=L(G)o二二义性性问题是不可判定是不可判定问题，即不存在一个，即不存在一个算法，它能在有限步算法，它能在有限步骤内，确切地判定一个内，确切地判定一个文法是否是二文法是否是二义的。的。o可以找到一可以找到一组无二无二义文法的充分条件。文法的充分条件。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所二二义文法：文法：G(E)：E i|E+E|E*E|(E)表达式表达式 项项|表达式表达式+项项项项 因子因子|项项*因子因子因子因子 (表达式表达式)|i无二义文法：无二义文法：G(E)：E T|E+T T F|T*F F (E)|i合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所)EEEFFTTTTi+*(EFiiE T F (E)(E+T)(T+T)(T*F+T)(F*F+T)(i*F+T)(i*i+T)(i*i+F)(i*i+i)考虑句子考虑句子(i*i+i)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o描述程序描述程序设计语言言时，对于上下文无关文法于上下文无关文法的限制的限制 ：1 1 不含不含P PP P形式的形式的产生式生式2 2 每个非每个非终结符符P P必必须有用有用处即：即：合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2.3.3 2.3.3 形式语言鸟瞰形式语言鸟瞰oChomsky于于1956年建立形式年建立形式语言体系，言体系，他把文法分成四种他把文法分成四种类型：型：0，1，2，3型。型。o与上下文无关文法一与上下文无关文法一样，它，它们都由四部分都由四部分组成，但成，但对产生式的限制有所不同。生式的限制有所不同。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所0型型(短短语语文法，文法，图图灵机灵机)：产生式形如：生式形如：其中：其中：(VT VN)*且至少含有一个非且至少含有一个非终结符；符；(VT VN)*1型型(上下文有关文法，上下文有关文法，线线性界限自性界限自动动机机)：产生式形如：生式形如：其中：其中：|，仅 S 例外。例外。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)：产生式形如：产生式形如：A 其中：其中：A VN；(VT VN)*。3型型(正规文法，有限自动机正规文法，有限自动机)：产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN 产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN右线性文法右线性文法左线性文法左线性文法合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所四种类型描述能力比较四种类型描述能力比较0型型1型型2型型3型型合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所oL5=anbn|n 1 不能由正不能由正规文法文法产生，但可生，但可由上下文无关文法由上下文无关文法产生：生：G5(S)：S aSb|aboL6=anbncn|n 1不能由上下文无关文法不能由上下文无关文法产生，生，但但可由上下文有关文法可由上下文有关文法产生：生：G6(S)：S aSBC|aBC CB BC aB ab bB bb bC bc cC cc合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o程序程序设计语设计语言不是上下文无关言不是上下文无关语语言，甚至不言，甚至不是上下文有关是上下文有关语语言言。oL7=c|(a|b)*不能由上下文无关文法不能由上下文无关文法产生，甚至生，甚至连上下文有关文法也不能上下文有关文法也不能产生，生，只能由只能由0 0型文法型文法产生。生。n标识标识符引用符引用n过过程程调调用用过过程中，程中，形形-实实参数地参数地对应对应性性(如如个数，个数，顺顺序和序和类类型一致性型一致性)o现今程序今程序设计语言的言的语言言结构，用上下文无构，用上下文无关文法描述就足关文法描述就足够了。了。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所作业oP36-6，7，8，9，10，11