第二章第二章 高级语言及其语法描述高级语言及其语法描述n程序设计语言的语法n程序设计语言的语义n程序设计语言的特点n程序设计语言的语法描述第二章 高级语言及其语法描述n任何语言实现的基础是语言的定义。n在定义方面，编译程序研制者与一般用 户有所不同u用户关心语言如何使用u开发人员关心文法的定义。他们对哪些 构造允许出现更感兴趣。即使一时不能看出某种 构造的实际应用，或者判断实现该结构会导致严 重的困难，但仍必须严格根据语言的定义实现它 。n程序语言主要由语法和语义两方面定义 。2.1 程序语言的定义第二章 高级语言及其语法描述2.1.1 语法u所谓一个语言的语法是指这样的一组规 则，用它可以形成和产生一个合适的程序 。u这些规则一部分称为词法规则，另一部 分能称为语法规则（或产生规则）。第二章 高级语言及其语法描述几个概念a.一个语言只是用一个有限字符集作为字母表； b.词法规则是指单词符号的形成规则。单词符号 一般包括：各类型的常数、标识符、基本字、算 符和界符等。 C.语言的语法规则规定了如何从单词符号形成更 大的结构（即语法单位或语法范畴），换言之， 语法规则是语法单位的形成规则。一般程序语言 的语法单位有：表达式、语句、分程序、函数、 过程和程序等。第二章 高级语言及其语法描述n对于一个语言来说，不仅要给出它的词 法、语法规则，而且要定义它的单词符号 和语法单位的意义。这就是语义问题。n语义是指这样的一组规则，使用它可 以定义一个程序的意义。n我们采用的方法为：属性文法和基于属 性文法的语法制导翻译方法。2.1.2 语义第二章 高级语言及其语法描述n程序语言的基 本功能是描述数 据和对数据的运 算。所谓程序， 从本质上来说是 描述一定数据的 处理过程。程序子程序或分程序语句表达式算符函数调用数据引用程序第二章 高级语言及其语法描述程序设计语言的定义n建立在有限字母集之上的一个符号系统n有一定的语法和语义规则n语法规则：词法规则和语法规则n语义规则：描述语法单位的功能和含义n程序设计语言的功能是描述数据和对数 据的运算第二章 高级语言及其语法描述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(20 世纪 50 年代末由 麻省理工学院为研究人工智能而开发的)和ML(20世纪70年代,由 爱丁堡大学开发的一个通用的函数式编程语言)属于这种语言。第二章 高级语言及其语法描述2.2.1 高级语言分类三、基于规则的语言基于规则的语言程序的执行过程是：检查一 定的条件，当它满足值，则执行适当的动作。 最有代表性的基于规则语言是Prolog，它也称 逻辑程序设计语言，因为它的基本允许条件是 谓词逻辑表达式。这类语言的语法形式通常为 ：条件1动作l条件2动作2条件n动作3第二章 高级语言及其语法描述2.2.1 高级语言分类四、面向对象语言面向对象语言如今已成为最流行、最重要的 语言。它主要的特征是支持封装性、继承性和 多态性等。把复杂的数据和用于这些数据的操 作封装在一起，构成对象；对简单对象进行扩 充、继承简单对象的特性，从而设计出复杂的 对象。通过对象的构造可以使面向对象程序获 得强制式语言的有效性，通过作用于规定数据 的函数的构造可以获得应用式语言的灵活性和 可靠性。第二章 高级语言及其语法描述2.2.2 程序结构n不同程序语言都有各自的程序结构nC语言程序可以包含多个函数nPascal 支持过程的嵌套定义n程序结构的不同，决定了符号表构造 方法的不同第二章 高级语言及其语法描述Pascal 是一个允许子程序嵌套定义的语言program mainprocedure P1;procedure P11;begin end;beginend;procedure P2;beginend;beginend 第二章 高级语言及其语法描述程序设计语言支持特定的数据类型与操作。一个数据类型通常包括以下三种要素：na.用于区别这种类型的数据对象的属性nb.这种类型的数据对象可以具有的值nc.可以作用于这种类型数据对象的操作2.2.3 数据类型与操作第二章 高级语言及其语法描述一.初等数据类型（基本数据类型）常见的初等数据类型有： a.数值数据b.逻辑数据 c.字符数据 d.指针类型不同的数据类型占 存储空间不同，表 示的数的范围也不 相同第二章 高级语言及其语法描述名字和标识符n标识符：无意义的符号串 n名字：可以看成是代表一个抽象的存储单元n名字的值：名字所代表的单元的内容则认为是 此名字的值。n名字的属性： 一个名字的属性包括类型和作用 域。n标识符、名字与存储空间的关系:同一标识符 可以表示不同的名字；同一名字可以表示不同的 存储空间；同一存储空间可以有多个名字第二章 高级语言及其语法描述二.构造数据类型a. 数组n特点：一个数组是由同一类型数据所组成的某 种n维矩形结构。每个元素占相同的存储空间n下标：沿着每一维的距离称为一个下标。n数组元素的命名：数组名+下标n确定数组与可变数组：在编译时数组所需的存 储空间是否确定n数组元素的存储与地址的计算n内情向量表：数据类型，数组的维数，下标的 变化范围，首地址设计符号表的构造 方法，需要在符号 表中存储更多的信 息，并需要定义不 同的属性文法以便 对其语义进行描述第二章 高级语言及其语法描述b.记录从逻辑上说，记录结构是由已知类型 的数据组合起来的一种结构。记录结构是许多程序语言的一类重要 的数据结构。第二章 高级语言及其语法描述Pascal语言采用下面形式定义记录：CARD: recordNAME: array120 of char;AGE:integer;MARRIED:booleanend;第二章 高级语言及其语法描述n多种基本数据类型组成的新的数据类型n记录分量的访问：记录名.分量名n记录的存放：连续存放n记录的长度：每个分量的长度之和n记录分量地址的计算：首地址+各分量相 对于首地址的偏移（offset）特点：第二章 高级语言及其语法描述如：就CARD而言，NAME,AGE,MARRIED 的相 对数OFFSET分别为0、20、24。于是，假定 CARD的首地址为a，那么，CARD.NAME 地址为 aCARD.AGE 地址为 a+20CARD.MARRIED 地址为 a+24第二章 高级语言及其语法描述2.2.4 语句与控制结构n表达式数值、关系、逻辑、字符串n语句赋值语句控制语句（无条件、条件、循环、过程调用、返回）说明句简单句和复合句第二章 高级语言及其语法描述一.表达式组成：运算量（亦称操作数，即数据引用或函数 调用）和算符组成的。 表示形式: 前缀式： +a*bc 中缀式：a+b*c 后缀式：abc*+第二章 高级语言及其语法描述表达式中的算符算符的优先级和结合性 乘幂 （ * 或 ） 一元负 （ - ） 乘、除 （ * ， /， ） 加、减 （ + ， - ） 关系符 （ , , = ) 非 （ ， not, 或 .NOT. ) 与 （， &, and 或 .AND. ) 或 （ ， or 或 .OR . )消除文法的二 义性第二章 高级语言及其语法描述算符的代数性质n作用：（交换率、结合率和分配率）常 常可用来优化目标程序的质量。但是必须 注意两点：n代数性质引用到什么程度视具体语言的 不同而不同。如在ALGOL中把nA*B+C*D 处理成C*D+A*B, 则至少是对 ALGOL不够忠实。n数学上成立的代数性质在计算机上未必 完全成立。如：(A+B)+C=A+(B+C)在计算机 上并不普遍成立。决定了在优化的 过程中应采取的 优化策略第二章 高级语言及其语法描述二.语句n从功能上说语句大体可分执行性语句和说明性语句，说明性语句旨在定义不同数据类型的变量或运算。n执行性语句旨在描述程序的动作。n对不同的语句，编译器的处理方式不同。n执行性语句又可分赋值语句、控制语句和输入/输出语句.n从形式上说，语句还可分为简单句、复合句和分程序等。根据属性文法的定义 进行处理第二章 高级语言及其语法描述2.3 程序语言的语法描述n对于高级程序语言及编译程序而言 ，语言的语法定义是非常重要的。n本节将介绍语法结构的形式描述问 题。第二章 高级语言及其语法描述n字母表：由若干元素组成的有限非空集合，用表示，它的每个元素称为一个符号。n符号串： 由中的符号所构成的有穷序列。n符号串的前缀和后缀及子串：设x是一个符号串，将x的尾（前）部删掉几个字符后形成的符号串，称为x的前（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串。与文法定义相关的几个概念和术语：第二章 高级语言及其语法描述n空串（字）：不包含符号的序列称为空串（字） ，记为。n用*表示上的所有符号串的全体，空字也包括在其中。如：若=a,b则*=,a,b,aa,ab,bb,aaa,。表示不含人何元素的空集。这里要注意、和的区别。与文法定义相关的几个概念和术语：第二章 高级语言及其语法描述符号串及符号串集合的运算n符号串的连接运算：设x和y是两个符号串，如果将y直接拼接在x之后，称这种操作为符号串的连接,记作： x.yn符号串的方幂：一个符号串与其自身的n-1的任意连接称为符号串的n次幂，记作：xn xn = xn-1.x=x.xn-1n特别地:x0= 第二章 高级语言及其语法描述应应用举举例表示、术语 令X1=“abc”, X2=“def”|X1| |abc|= 3 |= 0 X1.X2 “abc”“def”=“abcdef” Xn “abc”3 =“abcabcabc”X1的前缀 “abc”的前缀可以是：，a，ab, abcX1的后缀“abc”的后缀可以是：，c，bc, abc X1的子串 “abc”的子串可以是： ，a，b, c, ab, bc ，abc X1的真前缀“abc”的真前缀可以是：a，abX1的真后缀c，bc X1的真子串a，b, c, ab, bc 第二章 高级语言及其语法描述符号串及符号串集合的运算n字符串集合的和(等价于集合的并运算)：设A、B是两个符号串的集合，则将集合A、B的和记为A+B或AB,定义为：AB=w|wA或wBn符号串集合的连接：*的子集U和V中的（连接）积定义为:UV=U & V 即集合UV中的符号串是由U和V的符号串连接而成的。注意，一般UVVU，但（UV)W=U(VW).第二章 高级语言及其语法描述n符号串集合V自身的n次（连接）积记为：Vn = V VV =Vn-1V =VVn-1 (n个V)规定 V0 = .nV的闭包：令： V* = V0 V1 V2