高级程序设计语言

高级程序设计语言任何语言实现的基础是语言的定义。在定义方面，编译程序研制者与一般用户有所不同用户关心语言如何使用开发人员关心语言的定义。他们对哪些构造允许出现更感兴趣。即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它。程序语言主要由语法和语义两方面定义。2.1程序语言的定义第2页,共96页，2024年2月25日，星期天2.1.1语法所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合适的程序。这些规则一部分称为词法规则，另一部分能称为语法规则（或产生规则）。第3页,共96页，2024年2月25日，星期天几个概念a.一个语言只是用一个有限字符集作为字母表；b.词法规则是指单词符号的形成规则。单词符号一般包括：各类型的常数、标识符、基本字、算符和界符等。C.语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位或语法范畴），换言之，语法规则是语法单位的形成规则。一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等。第4页,共96页，2024年2月25日，星期天

对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。语义是指这样的一组规则，使用它可以定义一个程序的意义。我们采用的方法为：属性文法和基于属性文法的语法制导翻译方法。2.1.2语义第5页,共96页，2024年2月25日，星期天

程序语言的基本功能是描述数据和对数据的运算。所谓程序，从本质上来说是描述一定数据的处理过程。程序子程序或分程序语句表达式算符函数调用数据引用程序第6页,共96页，2024年2月25日，星期天程序设计语言的定义建立在有限字母集之上的一个符号系统有一定的语法和语义规则语法规则：词法规则和语法规则语义规则：描述语法单位的功能和含义程序设计语言的功能是描述数据和对数据的运算第7页,共96页，2024年2月25日，星期天2.2高级语言的一般特性2.2.1高级语言分类2.2.2程序结构2.2.3数据类型与操作2.2.4语句与控制结构第8页,共96页，2024年2月25日，星期天2.2.1高级语言分类从不同的角度看，对高级程序设计语言有不同的分类方法。如果我们从语言范型分类，当今的大多数程序设计语言可划分为四类。

一、强制式语言强制式语言也称过程式语言。其特点是命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个浯句的执行引起若干存储单元中的值的改变。这种语言的语法形式通常具有如下形式：语句1；语句2；语句n；许多广为使用的语言，如FORTRAN、C、Pascal，等等，属于这类语言。第9页,共96页，2024年2月25日，星期天2.2.1高级语言分类

二、应用式语言与强制式语言不同的是，应用式语言更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。这种语言通常的语法形式是：函数n(…函数2(函数1(数据))…)因此，这种语言也称函数式语言。LISP和ML属于这种语言。第10页,共96页，2024年2月25日，星期天2.2.1高级语言分类三、基于规则的语言基于规则的语言程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。最有代表性的基于规则语言是Prolog，它也称逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。这类语言的语法形式通常为：条件1→动作l

条件2→动作2

条件n→动作3第11页,共96页，2024年2月25日，星期天2.2.1高级语言分类四、面向对象语言面向对象语言如今已成为最流行、最重要的语言。它主要的特征是支持封装性、继承性和多态性等。把复杂的数据和用于这些数据的操作封装在一起，构成对象；对简单对象进行扩充、继承简单对象的特性，从而设计出复杂的对象。通过对象的构造可以使面向对象程序获得强制式语言的有效性，通过作用于规定数据的函数的构造可以获得应用式语言的灵活性和可靠性。第12页,共96页，2024年2月25日，星期天2.2.2程序结构不同程序语言都有各自的程序结构C语言程序可以包含多个函数Pascal支持过程的嵌套定义程序结构的不同，决定了符号表构造方法的不同第13页,共96页，2024年2月25日，星期天Pascal是一个允许子程序嵌套定义的语言

programmain

…procedureP1;…procedureP11;…begin…end;begin…end;procedureP2;…begin…end;begin…end第14页,共96页，2024年2月25日，星期天程序设计语言支持特定的数据类型与操作。一个数据类型通常包括以下三种要素：a.用于区别这种类型的数据对象的属性b.这种类型的数据对象可以具有的值c.可以作用于这种类型数据对象的操作2.2.3数据类型与操作第15页,共96页，2024年2月25日，星期天一.初等数据类型（基本数据类型）常见的初等数据类型有：

a.数值数据

b.逻辑数据

c.字符数据

d.指针类型不同的数据类型占存储空间不同，表示的数的范围也不相同第16页,共96页，2024年2月25日，星期天名字和标识符标识符：无意义的符号串名字：可以看成是代表一个抽象的存储单元名字的值：名字所代表的单元的内容则认为是此名字的值。名字的属性：一个名字的属性包括类型和作用域。标识符、名字与存储空间的关系:同一标识符可以表示不同的名字；同一名字可以表示不同的存储空间；同一存储空间可以有多个名字第17页,共96页，2024年2月25日，星期天二.构造数据类型

a.数组特点：一个数组是由同一类型数据所组成的某种n维矩形结构。每个元素占相同的存储空间下标：沿着每一维的距离称为一个下标。数组元素的命名：数组名+下标确定数组与可变数组：在编译时数组所需的存储空间是否确定数组元素的存储与地址的计算内情向量表：数据类型，数组的维数，下标的变化范围，首地址设计符号表的构造方法，需要在符号表中存储更多的信息，并需要定义不同的属性文法以便对其语义进行描述第18页,共96页，2024年2月25日，星期天b.记录从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构。记录结构是许多程序语言的一类重要的数据结构。第19页,共96页，2024年2月25日，星期天Pascal语言采用下面形式定义记录：CARD:recordNAME:array[1…20]ofchar;AGE:integer;MARRIED:booleanend;structNode{ chardata； inta; intmark;}；第20页,共96页，2024年2月25日，星期天多种基本数据类型组成的新的数据类型记录分量的访问：记录名.分量名记录的存放：连续存放记录的长度：每个分量的长度之和记录分量地址的计算：首地址+各分量相对于首地址的偏移（offset）特点：第21页,共96页，2024年2月25日，星期天如：就CARD而言，NAME,AGE,MARRIED的相对数OFFSET分别为0、20、24。于是，假定CARD的首地址为a，那么，

CARD.NAME地址为aCARD.AGE地址为a+20CARD.MARRIED地址为a+24

第22页,共96页，2024年2月25日，星期天2.2.4语句与控制结构表达式数值、关系、逻辑、字符串语句赋值语句控制语句（无条件、条件、循环、过程调用、返回）

说明句简单句和复合句第23页,共96页，2024年2月25日，星期天一.表达式组成：运算量（亦称操作数，即数据引用或函数调用）和算符组成的。表示形式:

前缀式：+a*bc

中缀式：a+b*c

后缀式：abc*+第24页,共96页，2024年2月25日，星期天表达式中的算符算符的优先级和结合性乘幂（**或↑）一元负（-）乘、除（*，/，÷）加、减（+，-）关系符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)与（∧，&,and或.AND.)或（∨，∣，or或.OR.)消除文法的二义性第25页,共96页，2024年2月25日，星期天算符的代数性质作用：（交换率、结合率和分配率）常常可用来优化目标程序的质量。但是必须注意两点：代数性质引用到什么程度视具体语言的不同而不同。如在ALGOL中把A*B+C*D处理成C*D+A*B,则至少是对ALGOL不够忠实。数学上成立的代数性质在计算机上未必完全成立。如：(A+B)+C=A+(B+C)在计算机上并不普遍成立。决定了在优化的过程中应采取的优化策略第26页,共96页，2024年2月25日，星期天二.语句从功能上说语句大体可分执行性语句和说明性语句，说明性语句旨在定义不同数据类型的变量或运算。执行性语句旨在描述程序的动作。对不同的语句，编译器的处理方式不同。执行性语句又可分赋值语句、控制语句和输入/输出语句.从形式上说，语句还可分为简单句、复合句和分程序等。根据属性文法的定义进行处理第27页,共96页，2024年2月25日，星期天2.3程序语言的语法描述对于高级程序语言及编译程序而言，语言的语法定义是非常重要的。本节将介绍语法结构的形式描述问题。第28页,共96页，2024年2月25日，星期天字母表：由若干元素组成的有限非空集合，用

表示，它的每个元素称为一个符号。符号串：由中的符号所构成的有穷序列。符号串的前缀和后缀及子串：设x是一个符号串，将x的尾（前）部删掉几个字符后形成的符号串，称为x的前（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串。与文法定义相关的几个概念和术语：第29页,共96页，2024年2月25日，星期天空串（字）：不包含符号的序列称为空串（字）

，记为

。用

*表示上的所有符号串的全体，空字也包括在其中。如：若={a,b}则*={,a,b,aa,ab,bb,aaa,…}。表示不含人何元素的空集{}。这里要注意、{}和{}的区别。与文法定义相关的几个概念和术语：第30页,共96页，2024年2月25日，星期天符号串及符号串集合的运算符号串的连接运算：设x和y是两个符号串，如果将y直接拼接在x之后，称这种操作为符号串的连接,记作：x.y符号串的方幂：一个符号串与其自身的n-1的任意连接称为符号串的n次幂，记作：xnxn=xn-1.x=x.xn-1特别地:x0=

第31页,共96页，2024年2月25日，星期天符号串及符号串集合的运算字符串集合的和(等价于集合的并运算)：设A、B是两个符号串的集合，则将集合A、B的和记为A+B或A∪B,定义为：A∪B={w|wA或wB}符号串集合的连接：*的子集U和V中的（连接）积定义为:UV={∣U&V}

即集合UV中的符号串是由U和V的符号串连接而成的。注意，一般UVVU，但（UV)W=U(VW).第32页,共96页，2024年2月25日，星期天令X1=“abc”,X2=“def”表示、术语举例|X1||abc|=3ε|ε|=0X1.X2“abc”“def”=“abcdef”X1n

“abc”3=“abcabcabc”X1的前缀“abc”的前缀可以是：ε，a，ab,abcX1的后缀“abc”的前缀可以是：ε，c，bc,abcX1的子串“abc”的子串可以是：ε，a，b,c,…X1的真前缀“abc”的真前缀可以是：a，abX1的真后缀？X1的真子串？X1的子序列“abdf”是“abcdef”的一个子序列（X1中去掉若干个不一定连续的字符后形成的字符串）第33页,共96页，2024年2月25日，星期天符号串集合V自身的n次（连接）积记为：

Vn=VV…V=Vn-1V

=VVn-1(n个V)规定V0={}.V的闭包：令：V*=V0∪V1∪V2∪…

称V*是V的闭包。V的正则包（正闭包，正则闭包）：记V+=VV*,称V+是V的正则包，即V+

=V1∪V2∪V3∪…。第34页,共96页，2024年2月25日，星期天一个例子有一个字母表：A={a,b,c}A0={ε}A1=？A2=？A3=？A*=？

A+=?第35页,共96页，2024年2月25日，星期天

文法是描述语言的语法结构的形式规则（即语法规则）。所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位)是完全独立于这种范畴可能出现的环境的。特点：独立性缺点：不能用来描述自然语言，但对于程序语言基本上够用，所以以后凡“文法”一词，若无特殊说明，均指上下文无关文法2.3.1上下文无关文法第36页,共96页，2024年2月25日，星期天引例例子：对于英文句子：Hegavemeabook.是由如下语法规则产生的：第37页,共96页，2024年2月25日，星期天由语法规则“推导”出句子的过程第38页,共96页，2024年2月25日，星期天“推导”过程对应的语法分析树第39页,共96页，2024年2月25日，星期天上下文无关文法的定义一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。形式上定义一个上下文无关文法Ｇ是一个四元式（ＶＴ，ＶＮ，Ｓ，P）第40页,共96页，2024年2月25日，星期天上下文无关文法的形式定义形式上定义一个上下文无关文法Ｇ是一个四元式（ＶＴ，ＶＮ，Ｓ，P）其中ＶＴ是一个非空有限集，它的每一个元素称为终结符号；ＶＮ是一个非空有限集，它的每一个元素称为非终结符号，ＶＴ∩ＶＮ＝；Ｓ是一个非终结符号，称为开始符号；P是一个产生式（有限）集合，每个产生式形式是A→

，其中，A∈ＶＮ，

∈（ＶＴ∪ＶＮ）＊开始符号S至少必须在某一产生式的左部出现一次。第41页,共96页，2024年2月25日，星期天上下文无关文法的定义所谓终结符号乃是组成语言的基本符号，“终结”含义在于是具有独立意义的最小语法单位，即不能再分解了的语法单位，如，He，book，如程序语言中的基本字，标识符，常数，算符和界符等.如：{*,+,a,b,c,(,),<,>,+,-}终结符号一般用小写字母表示第42页,共96页，2024年2月25日，星期天上下文无关文法所谓非终结符号（也称语法变量）用来代表语法范畴。如“算术表达式”、“布尔表达式”、“过程”等。一个非终结符代表一个一定的语法概念。因此非终结符是一个类（或集合）记号，而不是个体记号。非终结符号一般用大写字母表示如：{E，T，F}第43页,共96页，2024年2月25日，星期天开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴。例：E上下文无关文法第44页,共96页，2024年2月25日，星期天产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。一个产生式的形式是A→α其中箭头左边的A是一个非终结符，称为产生式的左部符号；箭头右边的α是终结符号或与非终结符号组成的一符号串，称为产生式的右部，或称候选式。上下文无关文法第45页,共96页，2024年2月25日，星期天文法简写约定只写出产生式集合；第一个产生式的左部符号约定为文法的开始符号所有产生式中的大写字母组成文法的非终结符号集；小写字母组成文法的终结符号集；第46页,共96页，2024年2月25日，星期天产生式实例变量是一个算术表达式；若E1和E2是算术表达式，E1+E2是算术表达式E1*E2是算术表达式(E1)是算术表达式

E→i

Ｅ→Ｅ＋ＥＥ→Ｅ＊Ｅ

Ｅ→（Ｅ）第47页,共96页，2024年2月25日，星期天关于产生式可能用多个产生式对一个非终结符进行定义

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）定义产生式，可以采用递归的形式直接递归间接递归第48页,共96页，2024年2月25日，星期天利用语法规则进行分析的方法推导——对于当前符号串中的非终结符，用对应的产生式的右部去替换之。构造语法树——文法的开始符号作为根结点，每推导一步，将非终结符作为父结点，对应的产生式的右部作为其孩子结点。第49页,共96页，2024年2月25日，星期天用文法定义语言采用推导的方法：利用产生式，对非终结符进行替换、展开

E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）第50页,共96页，2024年2月25日，星期天推导与直接推导直接推导：仅当A—>γ是一个产生式，有αAβ

αγβ该推导称为直接推导（直接导出）推导的描述形式：

：任意次推导：至少一次推导*+第51页,共96页，2024年2月25日，星期天句型与句子假定G是一个文法，S是它的开始符号。如果S(表示从S出发，经0步或若干步可推出），则称是一个句型。若是仅含终结符号的句型，则称是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G).L(G)={|S

，∈VT*}

*+第52页,共96页，2024年2月25日，星期天句型与句子例如：终结符号串（i*i+i)是文法

E→E+E|E*E|(E)|ｉ(2.1)

的一个句子。从开始符号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)等是文法的句型。第53页,共96页，2024年2月25日，星期天例2.1考虑一个文法G1:S→bAA→aA|a它定义了一个什么语言呢？从开始符S出发，我们可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以写为：L(G1)={ban|n≥1}第54页,共96页，2024年2月25日，星期天例2.2设有文法GS→P|aPPbP→ba|bQaQ→ab

求语言L(G).

解：

L(G)={ba,baba,abab,ababab…}第55页,共96页，2024年2月25日，星期天例2.3构造一个文法G3使

L(G3)={an|n≥1}

解;S→aS|a第56页,共96页，2024年2月25日，星期天例2.4构造一个文法G4使

L(G4)={anb|n≥1}

解;S→aS|ab第57页,共96页，2024年2月25日，星期天例2.5构造一个文法G5使

L(G5)={anbm|n≥1,m≥1}

解;S→AB A→aA|a B→bB|b第58页,共96页，2024年2月25日，星期天例2.6构造一个文法G6使

L(G6)={anbn|n≥0}

解;S→aSb|

第59页,共96页，2024年2月25日，星期天

例2.7：已知语言L={anbbn|n1},写出产生L的文法。[解]：

G[S]:SaAbAaAb|b如果写成

G[S]:SaSb|b

可不可以？第60页,共96页，2024年2月25日，星期天例2.8：试构造生成语言L={anbnci|n

0,i1}的文法解：G(Z):ZABAaAb|BcB|c第61页,共96页，2024年2月25日，星期天

例2.9：已知语言L={x|x{a,b,c}*,且x的排列是对称的（aabcbaa,aabbaa,等)写出该语言的文法。解：G(Z)：

ZaZa|bZb|cZc|a|b|c|第62页,共96页，2024年2月25日，星期天最左（右）推导最左推导或最右推导：所谓最左推导是指：任何一步都是对中的最左非终结符进行替换的。同样，可定义最右推导。最右推导又称为规范推导。第63页,共96页，2024年2月25日，星期天例如：对于文法：

E→E+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)

最左（右）推导第64页,共96页，2024年2月25日，星期天课堂作业：第65页,共96页，2024年2月25日，星期天语法分析树：简称语法树。用来表示推导过程。2.3.2语法分析树与二义性第66页,共96页，2024年2月25日，星期天语法树示例

例如对于文法E→E+E|E*E|(E)|ｉ,

关于（i*i+i)的推导形成语法树如图第67页,共96页，2024年2月25日，星期天语法树的构造：语法树的根结点由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生了下一代新结点。每个新结点和其父亲结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结点自左至右排列起来就是一个句型。2.3.2语法分析树与二义性第68页,共96页，2024年2月25日，星期天语法树的不唯一性一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有唯一的一个最左（最右)推导呢？

第69页,共96页，2024年2月25日，星期天语法树的不唯一性E→E+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)第70页,共96页，2024年2月25日，星期天

E→E+E|E*E|(E)|ｉ,关于（i*i+i)的语法树第71页,共96页，2024年2月25日，星期天文法的二义性二义文法:如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，则这个文法是法是二义的。第72页,共96页，2024年2月25日，星期天文法二义性的几个问题文法二义不等于语言二义文法的二义性问题是不可判定的文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导文法二义性的消除：给每个产生式定义优先级第73页,共96页，2024年2月25日，星期天消除文法二义性示例一个二义文法E--->E+EE--->E*EE--->(E)E--->i二义原因分析没有定义运算符优先级和结合性消除方法定义优先级和结合性给每个候选式定义一个优先级引入新的非终结符，建立新的产生式第74页,共96页，2024年2月25日，星期天一个二义文法E——>E+EE——>E*EE——>(E)E——>i一个无二义文法E——>T|E+TT——>F|T*FF——>(E)F——>i第75页,共96页，2024年2月25日，星期天上下文无关文法的几点限制（1）文法中不含任何下面形式的产生式：P→P因为这种产生式除了产生二义性外没有任何用处。（2）每个非终结符P必须有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号出发，存在推导S

*P.

另一方面意味着，必须存在终结符串

VT*,使得P

+

；也就是，对于P不存在永不终结的回路。第76页,共96页，2024年2月25日，星期天形式语言分类

乔姆斯基把文法分为四种类型0型1型2型3型

0型强于1型，1型强于2型，2型强于3型。这几种文法的差别在于对产生式施加不同的限制。第77页,共96页，2024年2月25日，星期天0型文法G=(VT,VN,S,P)是一个0型文法，如果它的每个产生式是这样的结构

(VN∪VT)*

且至少有一个非终结符，而(VN∪VT)*。0型文法也称短语文法0型文法的描述能力相当于图灵机该文法所描述的语言称为0型语言，或者称递归可枚举语言第78页,共96页，2024年2月25日，星期天1型文法特点：产生式的形式为

其中||<=||；但Sε除外，且S不得出现于任何产生式的右部1型文法又称为上下文有关文法另一种定义形式:Aγ该文法所描述的语言又称上下文有关语言第79页,共96页，2024年2月25日，星期天2型文法特点：该文法的产生式满足：A A为非终结符，为终结符和非终结符组成的符号串，可以是空串该文法又称为上下文无关文法该文法所描述的语言又称为上下文无关语言

第80页,共96页，2024年2月25日，星期天3型文法特点：该文法的产生式满足：AB或ABA、B为非终结符，为终结符组成的符号串，可以是空串该文法又称为右线性文法，或左线性文法，通称正规文法该文法所描述的语言又称为正规语言第81页,共96页，2024年2月25日，星期天四种文法的关系第82页,共96页，2024年2月25日，星期天四种文法的比较产生式形式文法名称定义的语言描述能力包含关系0型文法

短语文法递归可枚举语言最强1型文法

||<=||上下文有关文法上下文有关语言次之又是0型文法2型文法A上下文无关文法上下文无关语言次之又是0，1文法3型文法ABAB正规文法正规语言最弱又是0，1，2型文法第83页,共96页，2024年2月25日，星期天内容回顾关于文法描述的几个重要概念字母表，字符串，空串，等等字符串的连接，字符串集合的连接，字符串的幂，字符串集合的幂上下文无关文法G=(VT,VN,S,P)产生式的特点，产生式的形式推导、最左（右）推导，语法树句型与句子文法的二义性形式语言分类第84页,共96页，2024年2月25日，星期天

例2.10已知文法G=({A,B,C},{a,b,c},A,P)其中产生式P由以下组成：

AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa

问：此文法是那种文法？他所描述的语言有何特点？第85页,共96页，2024年2月25日，星期天[解]：由于A为开始符。由于Aa