《高级程序设计语言编译原理》由会员分享，可在线阅读，更多相关《高级程序设计语言编译原理（104页珍藏版）》请在金锄头文库上搜索。
1、第二章 高级语言及其语法描述n程序设计语言的语法n程序设计语言的语义n程序设计语言的特点n程序设计语言的语法描述精选pptn任何语言实现的基础是语言的定义。任何语言实现的基础是语言的定义。n在定义方面，编译程序研制者与一般用户有在定义方面，编译程序研制者与一般用户有所不同所不同u用户关心语言如何使用用户关心语言如何使用u开发人员关心文法的定义。他们对开发人员关心文法的定义。他们对哪些构造允许哪些构造允许出现出现更感兴趣。即使一时不能看出某种构造的实更感兴趣。即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的
2、定义实现它。但仍必须严格根据语言的定义实现它。n程序语言主要由程序语言主要由语法语法和和语义语义两方面定义。两方面定义。2.1 2.1 程序语言的定义程序语言的定义精选ppt2.1.1 2.1.1 语法语法u所谓一个语言的所谓一个语言的语法语法是指这样的一组是指这样的一组规规则则，用它可以形成和产生一个合适的程，用它可以形成和产生一个合适的程序。序。u这些规则一部分称为这些规则一部分称为词法规则词法规则，另一部，另一部分能称为分能称为语法规则语法规则（或产生规则）。（或产生规则）。精选ppt几个概念几个概念a.a.一个语言只是用一个有限字符集作为一个语言只是用一个有限字符集作为字母表字母表；b
3、.b.词法规则词法规则是指单词符号的形成规则。是指单词符号的形成规则。单词符号单词符号一般包括：各类型的常数、标识符、基本字、一般包括：各类型的常数、标识符、基本字、算符和界符等。算符和界符等。C.C.语言的语言的语法规则语法规则规定了如何从单词符号形成更规定了如何从单词符号形成更大的结构（即大的结构（即语法单位语法单位或或语法范畴语法范畴），换言之，），换言之，语法规则是语法单位的形成规则。一般程序语语法规则是语法单位的形成规则。一般程序语言的语法单位有：表达式、语句、分程序、函言的语法单位有：表达式、语句、分程序、函数、过程和程序等。数、过程和程序等。精选ppt n对于一个语言来说，不仅要
4、给出它的词对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。号和语法单位的意义。这就是语义问题。n语义语义是指这样的一组规则，使用它可是指这样的一组规则，使用它可以定义一个程序的意义。以定义一个程序的意义。n我们采用的方法为：属性文法和基于属我们采用的方法为：属性文法和基于属性文法的语法制导翻译方法。性文法的语法制导翻译方法。2.1.2 2.1.2 语义语义精选ppt n程序语言的基程序语言的基本功能是描述本功能是描述数据和对数据数据和对数据的运算。所谓的运算。所谓程序程序，从本质，从本质上来说是描述上来说
5、是描述一定数据的处一定数据的处理过程。理过程。程序程序子程序子程序或或分程序分程序语句语句表达式表达式算符算符函数调用函数调用数据引用数据引用程序程序精选ppt程序设计语言的定义程序设计语言的定义n建立在有限字母集之上的一个建立在有限字母集之上的一个符号系统符号系统n有一定的有一定的语法语法和和语义语义规则规则n语法规则：词法规则和语法规则语法规则：词法规则和语法规则n语义规则：描述语法单位的功能和含义语义规则：描述语法单位的功能和含义n程序设计语言的程序设计语言的功能功能是描述数据和对数是描述数据和对数据的运算据的运算精选ppt2.2 2.2 高级语言的一般特性高级语言的一般特性2.2.1
6、2.2.1 高级语言分类高级语言分类2.2.2 2.2.2 程序结构程序结构2.2.3 2.2.3 数据类型与操作数据类型与操作2.2.4 2.2.4 语句与控制结构语句与控制结构精选ppt2.2.1 2.2.1 高级语言分类高级语言分类 从不同的角度看，对高级程序设计语言有不同的分类方法。从不同的角度看，对高级程序设计语言有不同的分类方法。如果我们从语言范型分类，当今的大多数程序设计语言可划分为四如果我们从语言范型分类，当今的大多数程序设计语言可划分为四类。类。 一、强制式语言一、强制式语言 强制式语言也称过程式语言。其特点是命令驱动，面向语句。强制式语言也称过程式语言。其特点是命令驱动，面
7、向语句。一个强制式语言程序由一系列的语句组成，每个浯句的执行引起若一个强制式语言程序由一系列的语句组成，每个浯句的执行引起若干存储单元中的值的改变。这种语言的语法形式通常具有如下形式：干存储单元中的值的改变。这种语言的语法形式通常具有如下形式： 语句语句1 1； 语句语句2 2； 语句语句n n； 许多广为使用的语言，如许多广为使用的语言，如FORTRANFORTRAN、C C、PascalPascal，等等，属于这，等等，属于这类语言。类语言。精选ppt2.2.1 2.2.1 高级语言分类高级语言分类 二、应用式语言二、应用式语言 与强制式语言不同的是，应用式语言更注重程序所表示的与强制式语
8、言不同的是，应用式语言更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。行操作直至最终的函数可以用于从初始数据计算出最终的结果。这种语言通常的语法形式是：这种语言通常的语法形式是： 函数函数n(n(函数函数2(2(函数函数1(1(数据数据)因此，这种语言也称函数式语言。因此，这种语言也称函数式语言。LISP(LISP(20 20 世纪世纪 50 50 年代末
9、由年代末由麻省理工学院为研究人工智能而开发的麻省理工学院为研究人工智能而开发的) )和和MLML(20(20世纪世纪7070年代年代, ,由由爱丁堡大学开发的一个通用的函数式编程语言爱丁堡大学开发的一个通用的函数式编程语言) )属于这种语言。属于这种语言。精选ppt2.2.1 2.2.1 高级语言分类高级语言分类三、基于规则的语言三、基于规则的语言 基于规则的语言程序的执行过程是：检查一基于规则的语言程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。定的条件，当它满足值，则执行适当的动作。最有代表性的基于规则语言是最有代表性的基于规则语言是PrologProlog，它也称，它也称
10、逻辑程序设计语言，因为它的基本允许条件是逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。这类语言的语法形式通常为：谓词逻辑表达式。这类语言的语法形式通常为： 条件条件11动作动作l l 条件条件22动作动作2 2 条件条件nn动作动作3 3精选ppt2.2.1 2.2.1 高级语言分类高级语言分类四、面向对象语言四、面向对象语言 面向对象语言如今已成为最流行、最重要的面向对象语言如今已成为最流行、最重要的语言。它主要的特征是支持语言。它主要的特征是支持封装性封装性、继承性继承性和和多态性多态性等。把复杂的数据和用于这些数据的操等。把复杂的数据和用于这些数据的操作封装在一起，构成对象；对
11、简单对象进行扩作封装在一起，构成对象；对简单对象进行扩充、继承简单对象的特性，从而设计出复杂的充、继承简单对象的特性，从而设计出复杂的对象。通过对象的构造可以使面向对象程序获对象。通过对象的构造可以使面向对象程序获得强制式语言的有效性，通过作用于规定数据得强制式语言的有效性，通过作用于规定数据的函数的构造可以获得应用式语言的灵活性和的函数的构造可以获得应用式语言的灵活性和可靠性。可靠性。精选ppt2.2.2 2.2.2 程序结构程序结构n不同程序语言都有各自的程序结构不同程序语言都有各自的程序结构nC C语言程序可以包含多个函数语言程序可以包含多个函数nPascal Pascal 支持过程的嵌
12、套定义支持过程的嵌套定义n程序结构的不同，决定了符号表构造方法程序结构的不同，决定了符号表构造方法的不同的不同精选pptPascal Pascal 是一个允许子程序嵌套定义的语言是一个允许子程序嵌套定义的语言 program main procedure P1; procedure P11; begin end; begin end; procedure P2; begin end; begin end 精选ppt 程序设计语言支持特定的数据类型与操作。程序设计语言支持特定的数据类型与操作。一个数据类型通常包括以下三种要素：一个数据类型通常包括以下三种要素：na.a.用于区别这种类型的数据对象
13、的用于区别这种类型的数据对象的属性属性nb.b.这种类型的数据对象可以具有的这种类型的数据对象可以具有的值值nc.c.可以作用于这种类型数据对象的可以作用于这种类型数据对象的操作操作2.2.3 数据类型与操作数据类型与操作精选ppt一一. .初等数据类型（基本数据类型）初等数据类型（基本数据类型） 常见的初等数据类型有：常见的初等数据类型有：a.a.数值数据数值数据 b.b.逻辑数据逻辑数据c.c.字符数据字符数据d.d.指针类型指针类型不同的数据类型占不同的数据类型占存储空间不同，表存储空间不同，表示的数的范围也不示的数的范围也不相同相同精选ppt名字和标识符名字和标识符n标识符标识符：无意
14、义的符号串：无意义的符号串 n名字名字：可以看成是代表一个抽象的存储单元可以看成是代表一个抽象的存储单元n名字的值名字的值：名字所代表的单元的内容则认为是：名字所代表的单元的内容则认为是此名字的此名字的值值。n名字的属性名字的属性： 一个名字的属性包括一个名字的属性包括类型类型和和作用作用域域。n标识符、名字与存储空间的关系标识符、名字与存储空间的关系: :同一标识符同一标识符可以表示不同的名字；同一名字可以表示不同可以表示不同的名字；同一名字可以表示不同的存储空间；同一存储空间可以有多个名字的存储空间；同一存储空间可以有多个名字精选ppt二二. .构造数据类型构造数据类型 a. a. 数组数
15、组n特点特点：一个数组是由：一个数组是由同一类型同一类型数据所组成的某数据所组成的某种种n n维矩形结构。每个元素占相同的存储空间维矩形结构。每个元素占相同的存储空间n下标下标：沿着每一维的距离称为一个下标。：沿着每一维的距离称为一个下标。n数组元素的命名数组元素的命名：数组名：数组名+ +下标下标n确定数组与可变数组确定数组与可变数组：在编译时数组所需的存：在编译时数组所需的存储空间是否确定储空间是否确定n数组元素的存储与地址的计算数组元素的存储与地址的计算n内情向量表：内情向量表：数据类型，数组的维数，下标的数据类型，数组的维数，下标的变化范围，首地址变化范围，首地址设计符号表的构造设计符
16、号表的构造方法，需要在符号方法，需要在符号表中存储更多的信表中存储更多的信息，并需要定义不息，并需要定义不同的属性文法以便同的属性文法以便对其语义进行描述对其语义进行描述精选pptb.b.记录记录 从逻辑上说，记录结构是由已知类型从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构。的数据组合起来的一种结构。 记录结构是许多程序语言的一类重要记录结构是许多程序语言的一类重要的数据结构。的数据结构。精选pptPascal语言采用下面形式定义记录：语言采用下面形式定义记录：CARD: record NAME: array1.20 of char; AGE:integer; MARRIED:bo
17、olean end;精选pptn多种基本数据类型组成的新的数据类型多种基本数据类型组成的新的数据类型n记录分量的访问：记录名记录分量的访问：记录名. .分量名分量名n记录的存放：连续存放记录的存放：连续存放n记录的长度：每个分量的长度之和记录的长度：每个分量的长度之和n记录分量地址的计算：首地址记录分量地址的计算：首地址+ +各分量相各分量相对于首地址的偏移（对于首地址的偏移（offsetoffset）特点：特点：精选ppt如：就如：就CARDCARD而言，而言，NAME,AGE,MARRIED NAME,AGE,MARRIED 的相的相对数对数OFFSETOFFSET分别为分别为0 0、20
18、20、2424。于是，假。于是，假定定CARDCARD的首地址为的首地址为a a，那么，那么， CARD.NAME CARD.NAME 地址为地址为 a a CARD.AGE CARD.AGE 地址为地址为 a+20 a+20 CARD.MARRIED CARD.MARRIED 地址为地址为 a+24 a+24 精选ppt2.2.4 语句与控制结构语句与控制结构n表达式表达式 数值、关系、逻辑、字符串数值、关系、逻辑、字符串n语句语句 赋值语句赋值语句 控制语句控制语句（无条件、条件、循环、过程调用、返回）（无条件、条件、循环、过程调用、返回） 说明句说明句 简单句和复合句简单句和复合句精选p
19、pt 一一. .表达式表达式 组成组成：运算量（亦称操作数，即数据引用或函数：运算量（亦称操作数，即数据引用或函数调用）和算符组成的。调用）和算符组成的。表示形式表示形式: :前缀式：前缀式： +a*bc +a*bc 中缀式：中缀式：a+b*ca+b*c后缀式：后缀式：abc*+abc*+精选ppt表达式中的算符表达式中的算符算符的优先级和结合性算符的优先级和结合性 乘幂乘幂 （ * * 或或 ）一元负一元负 （ - - ）乘、除乘、除 （ * * ， / /， ）加、减加、减 （ + + ， - - ）关系符关系符 （ , =, , = ) , =, , = ) 非非 （ ， not, no
20、t, 或或 .NOT. ) .NOT. )与与 （， &, and &, and 或或 .AND. ) .AND. )或或 （ ， or or 或或 .OR . ) .OR . )消除文法的二消除文法的二义性义性精选ppt算符的代数性质算符的代数性质n作用：（交换率、结合率和分配率）常作用：（交换率、结合率和分配率）常常可用来优化目标程序的质量常可用来优化目标程序的质量。但是必但是必须注意两点：须注意两点：n代数性质引用到什么程度视具体语言的不同代数性质引用到什么程度视具体语言的不同而不同。如在而不同。如在ALGOLALGOL中把中把nA*B+C*D A*B+C*D 处理成处理成C*D+A*B
21、, C*D+A*B, 则至少是对则至少是对ALGOLALGOL不够不够忠实。忠实。n数学上成立的代数性质在计算机上未必完全数学上成立的代数性质在计算机上未必完全成立。如：成立。如：(A+B)+C=A+(B+C)(A+B)+C=A+(B+C)在计算机上并在计算机上并不普遍成立。不普遍成立。决定了在优化的决定了在优化的过程中应采取的过程中应采取的优化策略优化策略精选ppt二二. .语句语句n从功能上说语句大体可分从功能上说语句大体可分执行性语句执行性语句和和说明性语句说明性语句，说说明性语句旨在定义不同数据类型的变量或运算。明性语句旨在定义不同数据类型的变量或运算。n执行性语句旨在描述程序的动作。
22、执行性语句旨在描述程序的动作。n对不同的语句，编译器的处理方式不同。对不同的语句，编译器的处理方式不同。n执行性语句又可分赋值语句、控制语句和输入执行性语句又可分赋值语句、控制语句和输入/ /输出语输出语句句. .n从形式上说，语句还可分为简单句、复合句和分程序等。从形式上说，语句还可分为简单句、复合句和分程序等。根据属性文法的定义根据属性文法的定义进行处理进行处理精选ppt2.3 2.3 程序语言的语法描述程序语言的语法描述n对于高级程序语言及编译程序而言，对于高级程序语言及编译程序而言，语言的语法定义是非常重要的。语言的语法定义是非常重要的。n本节将介绍语法结构的形式描述问本节将介绍语法结
23、构的形式描述问题。题。精选pptn字母表：字母表：由若干元素组成的由若干元素组成的有限非空集有限非空集合，用合，用 表示，表示，它的每个元素称为一个它的每个元素称为一个符号符号。n符号串：符号串： 由由 中的符号所构成的有穷序列。中的符号所构成的有穷序列。n符号串的前缀和后缀及子串符号串的前缀和后缀及子串：设：设x x是一个符号串，将是一个符号串，将x x的的尾（前）部删掉几个字符后形成的符号串，称为尾（前）部删掉几个字符后形成的符号串，称为x x的前的前（后）缀；从一个符号串中删去他的一个前缀和后缀后（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为所剩下部分称为x x的子串。的
24、子串。与文法定义相关的几个概念和术语：与文法定义相关的几个概念和术语：精选pptn空串（字）空串（字）：不包含符号的序列称为：不包含符号的序列称为空串（字）空串（字） ，记，记为为 。n用用 * *表示表示 上的所有符号串的全体，空字也包括在其中。上的所有符号串的全体，空字也包括在其中。如：若如：若 =a,b=a,b则则 * *= ,a,b,aa,ab,bb,aaa,a,b,aa,ab,bb,aaa,。 表示不含人何元素的空集表示不含人何元素的空集。这里要注意。这里要注意 、和和 的区别。的区别。与文法定义相关的几个概念和术语：与文法定义相关的几个概念和术语：精选ppt符号串及符号串集合的运算
25、符号串及符号串集合的运算n符号串的连接运算符号串的连接运算：设：设x x和和y y是两个符号串，如果将是两个符号串，如果将y y直直接拼接在接拼接在x x之后，称这种操作为符号串的连接之后，称这种操作为符号串的连接, ,记作：记作： x.yx.yn符号串的方幂符号串的方幂：一个符号串与其自身的：一个符号串与其自身的n-1n-1的任意连接的任意连接称为符号串的称为符号串的n n次幂，记作：次幂，记作：x xn n x xn n = x= xn-1n-1.x=x.x.x=x.xn-1n-1n特别地特别地: :x x0 0= = 精选ppt应用举例应用举例表示、术语表示、术语 令令X1=“abc”,
26、 X2=“def”|X1| |abc|= 3 |= 0X1.X2 “abc”“def”=“abcdef”Xn “abc”3 =“abcabcabc”X1的前缀的前缀 “abc”的前缀可以是：的前缀可以是：，a，ab, abcX1的后缀的后缀“abc”的后缀可以是：的后缀可以是：，c，bc, abcX1的子串的子串 “abc”的子串可以是：的子串可以是： ，a，b, c, ab, bc ，abc X1的真前缀的真前缀“abc”的真前缀可以是：的真前缀可以是：a，abX1的真后缀的真后缀c，bcX1的真子串的真子串a，b, c, ab, bc 精选ppt符号串及符号串集合的运算符号串及符号串集合的
27、运算n字符串集合的和字符串集合的和( (等价于集合的并运算等价于集合的并运算) )：设设A A、B B是两个是两个符号串的集合，则将集合符号串的集合，则将集合A A、B B的和记为的和记为A+BA+B或或AB,AB,定义定义为：为：AB=w|wAB=w|w A A或或w w BBn符号串集合的连接符号串集合的连接： * *的子集的子集U U和和V V中的中的（连接）积连接）积定义定义为为: : UV= UV=U & U & V V 即集合即集合UVUV中的符号串是由中的符号串是由U U和和V V的符号串连接而成的。注的符号串连接而成的。注意，一般意，一般UVUV VUVU，但（，但（UV)W=
28、U(VW).UV)W=U(VW).精选pptn符号串集合符号串集合V V自身的自身的n n次（连接）积次（连接）积记为：记为： V Vn n = V VV =V= V VV =Vn-1n-1V V =VV=VVn-1 n-1 (n(n个个V)V)规定规定 V V0 0 = = .nV V的闭包的闭包：令：令： V V* * = V = V0 0 V V1 1 V V2 2 称称 V V* *是是V V的的闭包闭包。nV V的正则包（正闭包，正则闭包）的正则包（正闭包，正则闭包）：记记V V+ + = VV = VV* *, , 称称 V V+ +是是V V的的正则包，即正则包，即V V+ +
29、=V=V1 1 V V2 2 V V3 3 。精选ppt一个例子一个例子n有一个字母表：有一个字母表：A=a,b,cnA0=nA1=？nA2=？nA3=？nA*=？ A+=?精选ppt作业：作业：课后练习课后练习P35 3. 4.精选ppt 文法文法是描述语言的语法结构的是描述语言的语法结构的形式规则形式规则（即语法（即语法规则）。规则）。所谓所谓上下文无关文法上下文无关文法是这样一种文法，它所定义是这样一种文法，它所定义的语法范畴（或语法单位的语法范畴（或语法单位) )是完全独立于这种是完全独立于这种范畴可能出现的环境的。范畴可能出现的环境的。特点：独立性特点：独立性缺点：不能用来描述自然语
30、言，但对于程序语言缺点：不能用来描述自然语言，但对于程序语言基本上够用，所以以后凡基本上够用，所以以后凡“文法文法”一词，若无一词，若无特殊说明，均指特殊说明，均指上下文无关文法上下文无关文法2.3.1 上下文无关文法上下文无关文法精选ppt引例引例例子：对于英文句子：例子：对于英文句子：He gave me a book.He gave me a book.是由如下语法规则产生的：是由如下语法规则产生的：精选ppt由语法规则由语法规则“推导推导”出句子的过程出句子的过程精选ppt“推导推导” 过程对应的语法分析树过程对应的语法分析树精选ppt上下文无关文法的定义上下文无关文法的定义n一个一个
31、上下文无关文法上下文无关文法G包括四个组成部分：包括四个组成部分：一组一组终结符号终结符号，一组，一组非终结符非终结符，一个，一个开开始符号始符号，以及一组，以及一组产生式产生式。n形式上定义一个上下文无关文法形式上定义一个上下文无关文法是一是一个四元式（个四元式（，P）精选ppt上下文无关文法的形式定义上下文无关文法的形式定义形式上定义一个上下文无关文法形式上定义一个上下文无关文法是一个四元式是一个四元式（，P P）其中）其中是一个非空有限集，它的每一个元素称为终结符号；是一个非空有限集，它的每一个元素称为终结符号；是一个非空有限集，它的每一个元素称为非终结符号，是一个非空有限集，它的每一个
32、元素称为非终结符号， ；是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；P P是一个产生式（有限）集合，每个产生式形式是是一个产生式（有限）集合，每个产生式形式是AA ，其中，其中，AA， （）开始符号开始符号S S至至少必须在某一产生式的左部出现一次。少必须在某一产生式的左部出现一次。精选ppt上下文无关文法的举例上下文无关文法的举例一个上下文无关文法一个上下文无关文法G(Z)是一个四元式是一个四元式（，P P）其中其中=a，b，c=Z，A，B，=ZP=ZAB，A aAb| ， B cB|c精选ppt上下文无关文法的定义上下文无关文法的定义1.1.所谓所谓终结符号终结符号乃是
33、组成语言的基本符号，乃是组成语言的基本符号，“终结终结”含义在于是具有独立意义的最含义在于是具有独立意义的最小语法单位，即不能再分解了的语法单小语法单位，即不能再分解了的语法单位，如，位，如， HeHe， bookbook，如程序语言中的，如程序语言中的基本字，标识符，常数，算符和界符等基本字，标识符，常数，算符和界符等. .如：如： *,+, *,+,a,b,ca,b,c,(,),+,-,(,),+,-n终结符号一般用小写字母表示终结符号一般用小写字母表示精选ppt上下文无关文法上下文无关文法2. 2. 所谓所谓非终结符号非终结符号（也称语法变量）用来代表（也称语法变量）用来代表语法范畴。如
34、语法范畴。如“算术表达式算术表达式”、“布尔表达布尔表达式式”、“过程过程”等。一个非终结符代表一个等。一个非终结符代表一个一定的语法概念。因此非终结符是一个类一定的语法概念。因此非终结符是一个类（或集合）记号，而不是个体记号。（或集合）记号，而不是个体记号。非终结符号一般用大写字母表示非终结符号一般用大写字母表示如：如：EE，T T，FF精选ppt3. 开始符号开始符号是一个特殊的是一个特殊的非终结符号非终结符号，它，它代表所定义的语言中我们最感兴趣的语代表所定义的语言中我们最感兴趣的语法范畴。法范畴。 上下文无关文法上下文无关文法精选ppt4. 4. 产生式产生式（也称为产生规则或简称规则
35、）是定义（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。语法范畴的一种书写规则。 一个产生式的形式是一个产生式的形式是 A 其中箭头左边的其中箭头左边的A A是一个是一个非终结符非终结符，称为产生式，称为产生式的左部符号；的左部符号；箭头右边的箭头右边的是终结符号或与非终结符号组成的是终结符号或与非终结符号组成的一符号串，称为产生式的右部，或称一符号串，称为产生式的右部，或称候选式候选式。上下文无关文法上下文无关文法精选ppt文法简写约定文法简写约定n只写出产生式集合；只写出产生式集合；n第一个产生式的左部符号约定为文法的开始符第一个产生式的左部符号约定为文法的开始符号号n所有产生式
36、中的大写字母组成文法的非终结符所有产生式中的大写字母组成文法的非终结符号集；小写字母组成文法的终结符号集；号集；小写字母组成文法的终结符号集；一个上下文无关文法一个上下文无关文法G(Z)是一个四元是一个四元式（式（，P P）其中）其中=a，b，c，=Z,A,B，=ZP=ZAB，A aAb| ， B cB|cG(Z)：ZAB A aAb| B cB|c简写简写精选ppt产生式实例产生式实例变量是一个算术表达式变量是一个算术表达式；若若E1E1和和E2E2是算术表达式，是算术表达式，E1+E2E1+E2是算术表达式是算术表达式E1*E2E1*E2是算术表达式是算术表达式(E1)(E1)是算术表达式
37、是算术表达式 Ei （）（）精选ppt关于产生式关于产生式n可能用多个产生式对一个非终结符进行定义可能用多个产生式对一个非终结符进行定义 EiEi （）（）n定义产生式，可以采用递归的形式定义产生式，可以采用递归的形式n直接递归直接递归n间接递归间接递归精选ppt利用语法规则进行分析的方法利用语法规则进行分析的方法n推导推导对于当前符号串中的非终结符，用对对于当前符号串中的非终结符，用对应的产生式的右部去替换之。应的产生式的右部去替换之。n构造语法树构造语法树文法的开始符号作为根结点，文法的开始符号作为根结点，每推导一步，将非终结符作为父结点，对应每推导一步，将非终结符作为父结点，对应的产生式
38、的右部作为其孩子结点。的产生式的右部作为其孩子结点。精选ppt推导与直接推导推导与直接推导n直接推导：仅当直接推导：仅当A A 是一个产生式，有是一个产生式，有A A 该推导称为直接推导（直接导出）该推导称为直接推导（直接导出）n推导的描述形式：推导的描述形式：n：任意次推导：任意次推导n：至少一次推导：至少一次推导*+精选ppt句型与句子句型与句子假定假定G G是一个是一个文法文法，S S是它的开始符号。如果是它的开始符号。如果S S( (表示从表示从S S出发，经出发，经0 0步或若干步可推出步或若干步可推出 ），则称），则称 是一个是一个句型句型。仅含终结符号的句型。仅含终结符号的句型是
39、一个是一个句子句子。文法。文法G G所产生的句子的全体是一所产生的句子的全体是一个语言，将它记为个语言，将它记为L(G).L(G). L(G)= L(G)= |S |S & & VVT T* * *+精选ppt句型与句子句型与句子例如：终结符号串例如：终结符号串（i*i+i)i*i+i)是文法是文法 EE+E|E*E|(E)| EE+E|E*E|(E)| 的一个句子。的一个句子。因为存在一个从开始符号因为存在一个从开始符号E E至至(i*i+i)(i*i+i)的推导：的推导： E E(E)(E)(E+E) (E+E) (E*E+E) (E*E+E) (i*E+E) (i*E+E) (i*i+E
40、) (i*i+E) (i*i+i) (i*i+i)而而E,(E),(E*E+E)E,(E),(E*E+E)等是文法的句型。等是文法的句型。精选ppt用文法定义语言的方法用文法定义语言的方法n采用推导的方法：采用推导的方法： 从文法的开始符号，利用产生式，从文法的开始符号，利用产生式，对非终结符进行替换、展开，推导出全对非终结符进行替换、展开，推导出全部句子的集合。部句子的集合。 精选ppt 例例2.1 2.1 考虑一个文法考虑一个文法G1:G1: SbA SbA AaA|a AaA|a 它定义了一个什么语言呢？它定义了一个什么语言呢？解：从开始符号解：从开始符号S S出发，我们可以推出如下句子
41、：出发，我们可以推出如下句子： S SbA bA baba S SbA bA baA baA baabaa S SbA bA baA baA baaa baaa可以写为：可以写为：L(G1)=baL(G1)=ban n|n1|n1精选ppt例例2.2 2.2 设有文法设有文法G2G2 SP|aPb SP|aPb Pba|bQa Pba|bQa Qab Qab 求语言求语言L(G2)L(G2)。 解：解： L(G2)=ba,baba,abab,ababab L(G2)=ba,baba,abab,ababab精选ppt例例2.3 2.3 设有文法设有文法G3G3 SAB SAB AaA|a AaA
42、|a BbB|b BbB|b 求语言求语言L(G3)L(G3)。 解：解： L(G3)= L(G3)=a am mb bn n|m,n1|m,n1 精选ppt例例2.4 2.4 构造一个文法构造一个文法G4G4使使 L(G4)=a L(G4)=an n|n1|n1 解解: : G4: SaS|a G4: SaS|a精选ppt例例2.5 2.5 构造一个文法构造一个文法G5G5使使 L(G5)=a L(G5)=an nb|n1b|n1 解解: : G5: SaS|ab G5: SaS|ab精选ppt例例2.6 2.6 构造一个文法构造一个文法G6G6使使 L(G6)=a L(G6)=an nb
43、bm m|n1,m 1|n1,m 1 解解: : G6: SAB G6: SAB AaA|a AaA|a BbB|b BbB|b精选ppt例例2.7 2.7 构造一个文法构造一个文法G7G7使使 L(G7)=a L(G7)=an nb bn n|n0|n0 解解: : G7: SaSb| G7: SaSb| 精选ppt 例例2.8： 已知语言已知语言L=anbbn| n 1, 写出产生写出产生L的的文法。文法。解解： GS: S aAb A aAb|b如果写成如果写成GS: S aSb|b 可不可以？可不可以？如果写成如果写成GS: S aSb|abb 可不可以？可不可以？精选ppt例例2.9
44、： 试构造生成语言试构造生成语言L=anbnci|n 0, i 1的文法的文法 解：解：G(Z): ZAB A aAb| B cB|c精选ppt 例例2.102.10： 已知语言已知语言L=x | L=x | x x a,b,ca,b,c* *, ,且且x x的排列是对称的的排列是对称的（aabcbaa,aabbaa,aabcbaa,aabbaa,等等) ) 写出该语言的文写出该语言的文法。法。解：解：G(Z)G(Z)： Z Z aZa|bZb|cZc|a|b|c|aZa|bZb|cZc|a|b|c| 精选ppt最左（右）推导最左（右）推导最左推导或最右推导最左推导或最右推导：所谓最左推导是指
45、：所谓最左推导是指：任何一步任何一步都是对都是对 中的中的最左最左非终结符进非终结符进行替换的。同样，可定义最右推导。行替换的。同样，可定义最右推导。对于文法：对于文法：EE+E|E*E|(E)|关于关于 (i*i+i) 的的最左推导：最左推导：E(E)(E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)精选ppt语法分析树：语法分析树：简称语法树。用来表示推导过程。简称语法树。用来表示推导过程。2.3.2 语法分析树与二义性语法树的构造语法树的构造： 1.1.语法树的根结点由开始符号所标记。语法树的根结点由开始符号所标记。2.2.随着推导的展开，当某个非终结符被它的某个
46、候选式随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生了下一代所替换时，这个非终结符的相应结点就产生了下一代新结点。每个新结点和其父亲结点间都有一条连线。新结点。每个新结点和其父亲结点间都有一条连线。3.3.在一棵语法树在一棵语法树生长过程中的任何时刻生长过程中的任何时刻，所有那些没有，所有那些没有后代的端末结点自左至右排列起来就是一个句型。后代的端末结点自左至右排列起来就是一个句型。精选ppt语法树示例语法树示例 例如对于文法例如对于文法 EE+E|E*E|(E)|EE+E|E*E|(E)|, ,关于关于（i*i+i)i*i+i)的推导形成语法树如图的推导
47、形成语法树如图精选ppt语法树的不唯一性语法树的不唯一性 一个句型是否只对应唯一的一棵语法树呢？也一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有唯一的一个最左（最右就是说它是否只有唯一的一个最左（最右) )推导推导呢？呢？ 精选ppt语法树的不唯一性语法树的不唯一性对于文法：对于文法：EE+E|E*E|(E)|EE+E|E*E|(E)|, ,关于关于（i*i+i)i*i+i)的最左推导有的最左推导有2 2个：个：E E(E) (E) ( (E*EE*E) ) (i*E) (i*E) (i*E+E)(i*E+E) (i*i+E) (i*i+E) (i*i+i)(i*i+i)E E(E)
48、(E)( (E+EE+E) ) (E*E+E) (E*E+E) (i*E+E) (i*E+E) (i*i+E) (i*i+E) (i*i+i) (i*i+i)精选ppt EE+E|E*E|(E)|EE+E|E*E|(E)|, ,关于（关于（i*i+i)i*i+i)的语法树的语法树关于（关于（i*i+i)i*i+i)的语法树也有的语法树也有2 2棵棵精选ppt文法的二义性文法的二义性二义文法二义文法：如果一个文法存在如果一个文法存在某个句子某个句子对应两棵不同的语法树，则称这个文对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法法是二义的。也就是说，若一个文法存在某个句子，它有两个
49、不同的最左存在某个句子，它有两个不同的最左（最右（最右) )推导，则这个文法是法是推导，则这个文法是法是二义二义的的。 精选ppt文法二义性的几个问题文法二义性的几个问题n文法二义不等于语言二义文法二义不等于语言二义n文法的二义性是不可判定的文法的二义性是不可判定的n文法的二义性证明：找出一个句子，它文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导有两个不同的最左推导或最右推导n文法二义性的消除：给每个产生式定义文法二义性的消除：给每个产生式定义优先级优先级精选ppt消除文法二义性示例消除文法二义性示例n一个二义文法一个二义文法nE-E+EE-E+EnE-E*EE-E*EnE-
50、(E)E-(E)nE-iE-in二义原因分析二义原因分析n没有定义运算符优先级和结合性没有定义运算符优先级和结合性n消除方法消除方法n定义优先级和结合性定义优先级和结合性n给每个候选式定义一个优先级给每个候选式定义一个优先级n引入新的非终结符，建立新的产生引入新的非终结符，建立新的产生式式精选pptn一个二义文法一个二义文法nEE+EEE+EnEE*EEE*EnE(E)E(E)nEiEin一个无二义文法一个无二义文法nET|E+TET|E+TnTF|T*FTF|T*FnF(E)F(E)nFiFi精选ppt形式语言分类形式语言分类 乔姆斯基把文法分为四种类型乔姆斯基把文法分为四种类型0 0型型1
51、 1型型2 2型型3 3型型 0 0型强于型强于1 1型，型，1 1型强于型强于2 2型，型，2 2型强型强于于3 3型。这几文法的差别在于对产生型。这几文法的差别在于对产生式施加不同的限制。式施加不同的限制。 精选ppt0 0型文法型文法G=(VG=(VT T ,V,VN N ,S ,S ,P P) ) 是一个是一个0 0型文法型文法，如果它的每个产生式，如果它的每个产生式是这样的结构是这样的结构 (V(VN NVVT T) )* * 且至少有一个非终结符，而且至少有一个非终结符，而(V(VN NVVT T) )* * 。0 0型文法也称短语文法型文法也称短语文法0 0型文法的描述能力相当于
52、图灵机型文法的描述能力相当于图灵机该文法所描述的语言称为该文法所描述的语言称为0 0型语言，或者称递归可枚举语型语言，或者称递归可枚举语言言精选ppt1型文法型文法n特点：产生式的形式为特点：产生式的形式为其中其中| |=|=| |, |, 但但S S 除外，且除外，且S S不不得出现于任何产生式的右部得出现于任何产生式的右部n1型文法又称为上下文有关文法型文法又称为上下文有关文法n另一种定义形式另一种定义形式: A A n该文法所描述的语言又称上下文有关语言该文法所描述的语言又称上下文有关语言精选ppt2型文法型文法n特点：该文法的产生式满足：特点：该文法的产生式满足：A AA A为非终结符
53、，为非终结符， 为终结符和非终结符组成为终结符和非终结符组成的符号串，可以是空串的符号串，可以是空串n该文法又称为上下文无关文法该文法又称为上下文无关文法n该文法所描述的语言又称为上下文无关语言该文法所描述的语言又称为上下文无关语言 精选ppt3型文法型文法n特点：该文法的产生式满足：特点：该文法的产生式满足：A AB B 或或 A AB B A A为非终结符，为非终结符， 为终结符组成的符号串，可以是为终结符组成的符号串，可以是空串空串n该文法又称为右线性文法，或左线性文法，通称该文法又称为右线性文法，或左线性文法，通称正规文法正规文法n该文法所描述的语言又称为正规语言该文法所描述的语言又称
54、为正规语言精选ppt四种文法的比较四种文法的比较产生式形产生式形式式文法名称文法名称定义的语言定义的语言描述能描述能力力包含关系包含关系0型文法型文法短语文法短语文法递归可枚举语递归可枚举语言言最强最强1型文法型文法| | |=|0 , n0 精选ppt例例2 2 文法文法GNGN为：为： ND|ND ND|ND D0|1|2|3|4|5|6|7|8|9 D0|1|2|3|4|5|6|7|8|9 GN GN的语言是什么？的语言是什么？解：解：N N ND ND NDD. NDD. NDDDD.D NDDDD.D D.D D.D 所以所以GNGN的语言是允许的语言是允许0 0开头的非负整数。开头
55、的非负整数。 精选ppt例例3 3 为只包含数字、加号和减号的表达式，为只包含数字、加号和减号的表达式，例如例如9-29-25 5，3-13-1，等构造一个文法。，等构造一个文法。 解：解： GS: GS: S S+D|S-D|D S S+D|S-D|D D 0|1|2|3|4|5|6|7|8|9 D 0|1|2|3|4|5|6|7|8|9 精选ppt例例2 2 文法文法GNGN为：为： ND|ND ND|ND D0|1|2|3|4|5|6|7|8|9 D0|1|2|3|4|5|6|7|8|9 GN GN的语言是什么？的语言是什么？解：解：N N ND ND NDD. NDD. NDDDD.D
56、 NDDDD.D D.D D.D 所以所以GNGN的语言是允许的语言是允许0 0开头的非负整数。开头的非负整数。 精选ppt 解：偶数的组成和特点：可以是一位偶数，例如解：偶数的组成和特点：可以是一位偶数，例如2，4，6，8，可以是多位偶数，首位不能为，可以是多位偶数，首位不能为0，末位只能是，末位只能是0，2，4，6，8，中间为任意，中间为任意 G(Z): FA|CNDN NE|E| E 0|CD 0|AC A|B B 1|3|5|7|9 A 2|4|6|8例例4 试构造文法，该文法可以生成所有不试构造文法，该文法可以生成所有不能以能以0开头的偶数。开头的偶数。精选ppt 解：奇数的组成和特
57、点：可以是一位奇数：例如解：奇数的组成和特点：可以是一位奇数：例如1 1，3 3，5 5，7 7，9 9，可以是多位奇数：首位不能为，可以是多位奇数：首位不能为0 0，末位只能是，末位只能是1 1，3 3，5 5，7 7，9 9 ，中间为任意。，中间为任意。例例5 5 试构造文法，该文法可以生成所有不能试构造文法，该文法可以生成所有不能以以0 0开头的奇数。开头的奇数。 G(Z): G(Z): F FB|CNBB|CNB N N NE|E| NE|E| E E 0|C 0|C C C A|B A|B B B 1|3|5|7|9 1|3|5|7|9 A A 2|4|6|8 2|4|6|8精选pp
58、t 解：奇数的组成和特点：可以是一位奇数：例如解：奇数的组成和特点：可以是一位奇数：例如1 1，3 3，5 5，7 7，9 9，可以是多位奇数：首位不能为，可以是多位奇数：首位不能为0 0，末位只能是，末位只能是1 1，3 3，5 5，7 7，9 9 ，中间为任意。，中间为任意。例例5 5 试构造文法，该文法可以生成所有不能试构造文法，该文法可以生成所有不能以以0 0开头的奇数。开头的奇数。 G(Z): G(Z): F FB|CNBB|CNB N N NE|E| NE|E| E E 0|C 0|C C C A|B A|B B B 1|3|5|7|9 1|3|5|7|9 A A 2|4|6|8
59、2|4|6|8精选ppt例例7 7 证明下述文法证明下述文法GG表达式表达式 是二义的。是二义的。 a|(a|()|)| +|-|*|/ +|-|*|/ 解：可为句子解：可为句子a+a*aa+a*a构造两个不同的最右推导构造两个不同的最右推导: : 最右推导最右推导1 1： 表达式表达式 表达式运算符表达式表达式运算符表达式 表达式表达式 运算符运算符a a 表达式表达式*a *a 表达式运算符表达式表达式运算符表达式*a *a 表达式运算符表达式运算符a*a a*a 表达式表达式+a*a +a*a a+a*a a+a*a 精选ppt例例7 7 证明下述文法证明下述文法GG表达式表达式 是二义
60、的。是二义的。 a|(a|()|)| +|-|*|/ +|-|*|/ 解：可为句子解：可为句子a+a*aa+a*a构造两个不同的最右推导构造两个不同的最右推导: : 最右推导最右推导2 2：表达式表达式 表达式运算符表达式表达式运算符表达式 表达式运算符表达式运算符表达式表达式运算符表达式运算符表达式 表达式运算符表达式运算符表达式运算符表达式运算符a a 表达式运算符表达式表达式运算符表达式*a *a 表达式运算符表达式运算符a*a a*a 表达式表达式+a*a +a*a a+a*a a+a*a 精选ppt例例9 9 考虑下面上下文无关文法：考虑下面上下文无关文法： SSS*|SS+|a S
61、SS*|SS+|a (1)(1)表明通过此文法如何生成串表明通过此文法如何生成串aa+a*aa+a*，并为该串构造语，并为该串构造语法树。法树。 (2)GS(2)GS的语言是什么？的语言是什么？ 解：解： (1) (1)此文法生成串此文法生成串aa+a*aa+a*的最右推导如下的最右推导如下 S S SS* SS* SS* SS* Sa* Sa* SS+a* SS+a* Sa+a* Sa+a* aa+a* aa+a* (2)(2)该文法生成的语言是：该文法生成的语言是：* *和和+ +的后缀表达式，即逆波兰的后缀表达式，即逆波兰式式 精选ppt例例10 10 文法文法SS(S)S| SS(S)
62、S| (1) (1)生成的语言是什么？生成的语言是什么？ (2) (2)该文法是二义的吗？说明理由。该文法是二义的吗？说明理由。 解：解： ( () )嵌套的括号嵌套的括号 ( () )是二义的，因为对于（）（）可以构造两棵不是二义的，因为对于（）（）可以构造两棵不同的语法树。同的语法树。 精选ppt例例11 11 给出生成下述语言的上下文无关文法：给出生成下述语言的上下文无关文法： （1 1）aan nb bn na am mb bm m|n|n，m=0 m=0 （2 2）11n n0 0m m1 1m m0 0n n|n|n，m=0 m=0 （3 3）WWa aW Wr r|W|W属于属于
63、0|1*0|1*，W Wr r表示表示W Wa a的逆的逆 解：解： （）（）SAA SAA AaAb| AaAb|（）（）S1S0|A S1S0|A A0A1| A0A1|（）（）S0S0|1S1|0|1| S0S0|1S1|0|1| 精选ppt例例12 12 给出生成下述语言的三型文法：给出生成下述语言的三型文法： (1)a (1)an n|n=0 |n=0 (2)a (2)an nb bm m|n,m=1 |n,m=1 (3)a (3)an nb bm mc ck k|n,m,k=0 |n,m,k=0 解：解：(1)SaS| (1)SaS| (2) SaA (2) SaA AaA|B AaA|B BbB|b BbB|b (3) AaA|B (3) AaA|B BbB|C BbB|C CcC| CcC| 精选ppt精选ppt精选ppt精选ppt句型句型精选ppt精选ppt作业作业n课本课本P36P36：6 6、7 7精选ppt
