第二章--高级程序设计语言.ppt

第二章高级语言及其语法描述,任何语言实现的基础是语言的定义。在定义方面，编译程序研制者与一般用户有所不同用户关心语言如何使用开发人员关心语言的定义。他们对哪些构造允许出现更感兴趣。即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它。程序语言主要由语法和语义两方面定义。,2.1程序语言的定义,第二章高级语言及其语法描述,2.1.1语法,所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合适的程序。这些规则一部分称为词法规则，另一部分能称为语法规则（或产生规则）。,第二章高级语言及其语法描述,几个概念,a.一个语言只是用一个有限字符集作为字母表；b.词法规则是指单词符号的形成规则。单词符号一般包括：各类型的常数、标识符、基本字、算符和界符等。C.语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位或语法范畴），换言之，语法规则是语法单位的形成规则。一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等。,第二章高级语言及其语法描述,对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。语义是指这样的一组规则，使用它可以定义一个程序的意义。我们采用的方法为：属性文法和基于属性文法的语法制导翻译方法。,2.1.2语义,第二章高级语言及其语法描述,程序语言的基本功能是描述数据和对数据的运算。所谓程序，从本质上来说是描述一定数据的处理过程。,程序,第二章高级语言及其语法描述,程序设计语言的定义,建立在有限字母集之上的一个符号系统有一定的语法和语义规则语法规则：词法规则和语法规则语义规则：描述语法单位的功能和含义程序设计语言的功能是描述数据和对数据的运算,第二章高级语言及其语法描述,2.2高级语言的一般特性,2.2.1高级语言分类2.2.2程序结构2.2.3数据类型与操作2.2.4语句与控制结构,第二章高级语言及其语法描述,2.2.1高级语言分类,从不同的角度看，对高级程序设计语言有不同的分类方法。如果我们从语言范型分类，当今的大多数程序设计语言可划分为四类。一、强制式语言强制式语言也称过程式语言。其特点是命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个浯句的执行引起若干存储单元中的值的改变。这种语言的语法形式通常具有如下形式：语句1；语句2；语句n；许多广为使用的语言，如FORTRAN、C、Pascal，等等，属于这类语言。,第二章高级语言及其语法描述,2.2.1高级语言分类,二、应用式语言与强制式语言不同的是，应用式语言更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。这种语言通常的语法形式是：函数n(函数2(函数1(数据)因此，这种语言也称函数式语言。LISP和ML属于这种语言。,第二章高级语言及其语法描述,2.2.1高级语言分类,三、基于规则的语言基于规则的语言程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。最有代表性的基于规则语言是Prolog，它也称逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。这类语言的语法形式通常为：条件1动作l条件2动作2条件n动作3,第二章高级语言及其语法描述,2.2.1高级语言分类,四、面向对象语言面向对象语言如今已成为最流行、最重要的语言。它主要的特征是支持封装性、继承性和多态性等。把复杂的数据和用于这些数据的操作封装在一起，构成对象；对简单对象进行扩充、继承简单对象的特性，从而设计出复杂的对象。通过对象的构造可以使面向对象程序获得强制式语言的有效性，通过作用于规定数据的函数的构造可以获得应用式语言的灵活性和可靠性。,第二章高级语言及其语法描述,2.2.2程序结构,不同程序语言都有各自的程序结构C语言程序可以包含多个函数Pascal支持过程的嵌套定义程序结构的不同，决定了符号表构造方法的不同,第二章高级语言及其语法描述,Pascal是一个允许子程序嵌套定义的语言,programmainprocedureP1;procedureP11;beginend;beginend;procedureP2;beginend;beginend,第二章高级语言及其语法描述,程序设计语言支持特定的数据类型与操作。一个数据类型通常包括以下三种要素：a.用于区别这种类型的数据对象的属性b.这种类型的数据对象可以具有的值c.可以作用于这种类型数据对象的操作,2.2.3数据类型与操作,第二章高级语言及其语法描述,一.初等数据类型（基本数据类型）,常见的初等数据类型有：a.数值数据b.逻辑数据c.字符数据d.指针类型,不同的数据类型占存储空间不同，表示的数的范围也不相同,第二章高级语言及其语法描述,名字和标识符,标识符：无意义的符号串名字：可以看成是代表一个抽象的存储单元名字的值：名字所代表的单元的内容则认为是此名字的值。名字的属性：一个名字的属性包括类型和作用域。标识符、名字与存储空间的关系:同一标识符可以表示不同的名字；同一名字可以表示不同的存储空间；同一存储空间可以有多个名字,第二章高级语言及其语法描述,二.构造数据类型,a.数组特点：一个数组是由同一类型数据所组成的某种n维矩形结构。每个元素占相同的存储空间下标：沿着每一维的距离称为一个下标。数组元素的命名：数组名+下标确定数组与可变数组：在编译时数组所需的存储空间是否确定数组元素的存储与地址的计算内情向量表：数据类型，数组的维数，下标的变化范围，首地址,设计符号表的构造方法，需要在符号表中存储更多的信息，并需要定义不同的属性文法以便对其语义进行描述,第二章高级语言及其语法描述,b.记录从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构。记录结构是许多程序语言的一类重要的数据结构。,第二章高级语言及其语法描述,Pascal语言采用下面形式定义记录：CARD:recordNAME:array120ofchar;AGE:integer;MARRIED:booleanend;,structNodechardata；inta;intmark;；,第二章高级语言及其语法描述,多种基本数据类型组成的新的数据类型记录分量的访问：记录名.分量名记录的存放：连续存放记录的长度：每个分量的长度之和记录分量地址的计算：首地址+各分量相对于首地址的偏移（offset）,特点：,第二章高级语言及其语法描述,如：就CARD而言，NAME,AGE,MARRIED的相对数OFFSET分别为0、20、24。于是，假定CARD的首地址为a，那么，CARD.NAME地址为aCARD.AGE地址为a+20CARD.MARRIED地址为a+24,第二章高级语言及其语法描述,2.2.4语句与控制结构,表达式数值、关系、逻辑、字符串语句赋值语句控制语句（无条件、条件、循环、过程调用、返回）说明句简单句和复合句,第二章高级语言及其语法描述,一.表达式组成：运算量（亦称操作数，即数据引用或函数调用）和算符组成的。表示形式:前缀式：+a*bc中缀式：a+b*c后缀式：abc*+,第二章高级语言及其语法描述,表达式中的算符,算符的优先级和结合性乘幂（*或）一元负（-）乘、除（*，/，）加、减（+，-）关系符（,=)非（，not,或.NOT.)与（，SaS|a,第二章高级语言及其语法描述,例2.4构造一个文法G4使L(G4)=anb|n1解;SaS|ab,第二章高级语言及其语法描述,例2.5构造一个文法G5使L(G5)=anbm|n1,m1解;SABAaA|aBbB|b,第二章高级语言及其语法描述,例2.6构造一个文法G6使L(G6)=anbn|n0解;SaSb|,第二章高级语言及其语法描述,例2.7：已知语言L=anbbn|n1,写出产生L的文法。解：GS:SaAbAaAb|b如果写成GS:SaSb|b可不可以？,第二章高级语言及其语法描述,例2.8：试构造生成语言L=anbnci|n0,i1的文法解：G(Z):ZABAaAb|BcB|c,第二章高级语言及其语法描述,例2.9：已知语言L=x|xa,b,c*,且x的排列是对称的（aabcbaa,aabbaa,等)写出该语言的文法。解：G(Z)：ZaZa|bZb|cZc|a|b|c|,第二章高级语言及其语法描述,最左（右）推导,最左推导或最右推导：所谓最左推导是指：任何一步都是对中的最左非终结符进行替换的。同样，可定义最右推导。最右推导又称为规范推导。,第二章高级语言及其语法描述,例如：对于文法：EE+E|E*E|(E)|(2.1)符号串（i*i+i)的一个最左推导过程如下：E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i),最左（右）推导,第二章高级语言及其语法描述,课堂作业：,第二章高级语言及其语法描述,语法分析树：简称语法树。用来表示推导过程。,2.3.2语法分析树与二义性,第二章高级语言及其语法描述,语法树示例,例如对于文法EE+E|E*E|(E)|,关于（i*i+i)的推导形成语法树如图,第二章高级语言及其语法描述,语法树的构造：语法树的根结点由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生了下一代新结点。每个新结点和其父亲结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结点自左至右排列起来就是一个句型。,2.3.2语法分析树与二义性,第二章高级语言及其语法描述,语法树的不唯一性,一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有唯一的一个最左（最右)推导呢？,第二章高级语言及其语法描述,语法树的不唯一性,EE+E|E*E|(E)|,关于（i*i+i)的推导E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i),第二章高级语言及其语法描述,EE+E|E*E|(E)|,关于（i*i+i)的语法树,第二章高级语言及其语法描述,文法的二义性,二义文法:如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，则这个文法是法是二义的。,第二章高级语言及其语法描述,文法二义性的几个问题,文法二义不等于语言二义文法的二义性问题是不可判定的文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导文法二义性的消除：给每个产生式定义优先级,第二章高级语言及其语法描述,消除文法二义性示例,一个二义文法E-E+EE-E*EE-(E)E-i,二义原因分析没有定义运算符优先级和结合性消除方法定义优先级和结合性给每个候选式定义一个优先级引入新的非终结符，建立新的产生式,第二章高级语言及其语法描述,一个二义文法EE+EEE*EE(E)Ei,一个无二义文法ET|E+TTF|T*FF(E)Fi,第二章高级语言及其语法描述,上下文无关文法的几点限制,（1）文法中不含任何下面形式的产生式：PP因为这种产生式除了产生二义性外没有任何用处。（2）每个非终结符P必须有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号出发，存在推导S*P.另一方面意味着，必须存在终结符串VT*,使得P+；也就是，对于P不存在永不终结的回路。,第二章高级语言及其语法描述,形式语言分类,乔姆斯基把文法分为四种类型0型1型2型3型0型强于1型，1型强于2型，2型强于3型。这几种文法的差别在于对产生式施加不同的限制。,第二章高级语言及其语法描述,0型文法,G=(VT,VN,S,P)是一个0型文法，如果它的每个产生式是这样的结构(VNVT)*且至少有一个非终结符，而(VNVT)*。0型文法也称短语文法0型文法的描述能力相当于图灵机该文法所描述的语言称为0型语言，或者称递归可枚举语言,第二章高级语言及其语法描述,1型文法,特点：产生式的形式为其中|0,第二章高级语言及其语法描述,解：偶数的组成和特点：可以是一位偶数，例如2，4，6，8，可以是多位偶数，首位不能为0，末位只能是0，2，4，6，8，中间为任意G(Z):FA|CNDNNE|E|E0|CD0|ACA|BB|1|3|5|7|9A2|4|6|8,例2.11试构造文法，该文法可以生成所有不能以0开头的偶数。,第二章高级语言及其语法描述,解：奇数的组成和特点：可以是一位奇数：例如1，3，5，7，9，可以是多位奇数：首位不能为0，末位只能是1，3，5，7，9，中间为任意。G(Z):D1|3|5|7|9|BDB1|2|3|4|5|6|7|8|9|B0,例2.12:试构造文法，该文法可以生成所有不能以0开头的奇数。,G(Z):FB|CNBNNE|E|E0|CCA|BB1|3|5|7|9A2|4|6|8,第二章高级语言及其语法描述,ABC,C,C,BCD,第二章高级语言及其语法描述,ABCD,ABC,D,B,BCD,BD,第二章高级语言及其语法描述,CD,C,第二章高级语言及其语法描述,句型,A,B,+,*,(