编译原理第二章

1、编编 译译 原原 理理 （第二版）（第二版）郑郑 洪洪 编著编著2第第2章章 程程 序序 语语 言言高高 级级 语语 言言1中中 间间 语语 言言232.1 高高 级级 语语 言言v 2.1.1 高级语言的分类高级语言的分类 1过程式语言过程式语言 过程式语言以语句为核心，命令驱动。过程式语言设计的程序以语过程式语言以语句为核心，命令驱动。过程式语言设计的程序以语句为最小执行单位，程序由一系列的语句组成。句为最小执行单位，程序由一系列的语句组成。 这种语言设计的程序通常具有如下形式：这种语言设计的程序通常具有如下形式：语句语句1;语句语句2;语句语句n; 2面向对象语言面向对象语言 面向对象语

2、言（面向对象语言（Object-Oriented Language）是如今使用最广、）是如今使用最广、最为重要的语言。它的主要特征是支持封装性、继承性和多态性；最为重要的语言。它的主要特征是支持封装性、继承性和多态性；把复杂的特性和用于这些数据的操作装在一起，构成对象；对简单把复杂的特性和用于这些数据的操作装在一起，构成对象；对简单对象进行扩充，继承简单对象的特性，从而设计出复杂的对象。对象进行扩充，继承简单对象的特性，从而设计出复杂的对象。4 3应用式语言应用式语言 将已知的函数作为新开发函数的参数，利用函数的嵌套与递归使得将已知的函数作为新开发函数的参数，利用函数的嵌套与递归使得程序的功能

3、由简单变为复杂，最终满足程序设计的要求。程序的功能由简单变为复杂，最终满足程序设计的要求。 这种语言的结构形式是：这种语言的结构形式是：函数函数n（函数函数2（函数（函数1（数据）（数据） 4基于规则的语言基于规则的语言 基于规则的语言以判断基于规则的语言以判断选择语句为基本执行单位。其程序的执行选择语句为基本执行单位。其程序的执行过程是：检查一定的条件，当它满足时选择适当的操作。最有代表过程是：检查一定的条件，当它满足时选择适当的操作。最有代表性的基于规则语言是性的基于规则语言是PROLOG。 其程序结构形式为：其程序结构形式为：条件条件1动作动作1条件条件2动作动作2条件条件n动作动作n5

4、v 2.1.2 数据类型及其操作数据类型及其操作 （1）数值数据：数值数据包括整数、实数、复数以及这些类型的双长（或多倍长）精度数。对数值类型的数据可描述为算术运算集合。 （2）逻辑数据：很多语言有专门用于布尔代数的数据类型，即逻辑型数据类型。有的语言甚至还有位串型数据。对逻辑数据可实施逻辑运算（and、or、not等）。 （3）字符数据：有些语言可以处理字符或字符串。字符数据类型用来承载字符或字符串。对字符数据的操作有很多，包括判断、转换以及对字符串的各种加工。 （4）指针类型：指针类型的数据不是用来描述客观事物的，它的作用是为运算提供数据的地址。6v 常见的结构型数据类型有以下几种：常见的

5、结构型数据类型有以下几种： 1数组 一个数组是由同一类型数据组成的有序的集合。数组下标与数组元一个数组是由同一类型数据组成的有序的集合。数组下标与数组元素的存储地址密切相关，二者呈线性关系。因此数组元素也称为下素的存储地址密切相关，二者呈线性关系。因此数组元素也称为下标变量。标变量。N维数组的每个元素有维数组的每个元素有N个下标。由个下标。由N个下标决定数组元素个下标决定数组元素的存储位置。的存储位置。 2记录 记录是由不同类型数据所组成的集合。记录结构中每个元素所占有记录是由不同类型数据所组成的集合。记录结构中每个元素所占有的存储空间可能互不相同，记录的元素称为分量。的存储空间可能互不相同，

6、记录的元素称为分量。 例如，例如，C语言采用下面的形式定义记录：语言采用下面的形式定义记录：struct student char name8; int studclass; float math; 7 结构分量是通过名字而不是像数组元素那样通过下标访问的。结构分量的名字是所谓复合名字，例如“结构名.分量名”。结构分量的使用与基本数据结构定义的变量相同，如下述3个赋值语句： =LIMING student.studclass=3 student.math=95.4 每个分量的存储地址由记录结构的首地址与相应分量的偏移地址相加而成。记录结构的每个分量（域）所占用的存储字节

7、数称为该域的长度。通过累加分量的长度可计算出各分量的偏移量。 占占8个字节，个字节，student.studclass占占2个字节，个字节，student.math占占4个字节，可计算三者对应的偏移量为个字节，可计算三者对应的偏移量为0、8、10，若，若student记录结构在记录结构在运行时被分配一个基址运行时被分配一个基址a，则其各分量的地址为：，则其各分量的地址为：:astudent.studclass:a+8student.math:a+108 3字符串、表格和队列 不同的语言根据不同的需要会拓展出一些实用数据类型。不同的语言根据不同的需

8、要会拓展出一些实用数据类型。 有越来越多的语言把字符串作为一种基本的数据类型，串的长度不有越来越多的语言把字符串作为一种基本的数据类型，串的长度不加限制。这种数据类型给各种处理文字语言的程序带来很多便利。加限制。这种数据类型给各种处理文字语言的程序带来很多便利。v 2.1.3 语句与表达式语句与表达式 1语句 每当用户创建了一个名称，就要用说明语句来说明这个名称所指对每当用户创建了一个名称，就要用说明语句来说明这个名称所指对象的意义，是一种变量、一种操作、还是一个子程序。而执行性语象的意义，是一种变量、一种操作、还是一个子程序。而执行性语句就是描述计算机操作的，其还可分为赋值语句、控制语句、输

9、入句就是描述计算机操作的，其还可分为赋值语句、控制语句、输入/输出语句。输出语句。 （1）说明语句 说明语句的作用在于定义名字的属性，即赋予名字意义，如：说明语句的作用在于定义名字的属性，即赋予名字意义，如：int x; C语言定义整型变量语言定义整型变量9 （2）赋值语句：赋值语句在不同的程序设计语言中可能有不同的语句形式，但实现功能基本相同。 例如：例如：X：=Y PASCAL赋值语句赋值语句 （3）控制语句：计算机程序之所以能够实现各种强大的功能，原因是有了控制语句。控制语句的核心操作就是：判断选择，这是一切智能行为的基础。 条件语句if E then Sif E then S else

10、 S1 循环语句while(E) B do S repeat S until Bfor I:=E1 step E2 until E3 do S过程调用语句call p(x1,x2,xn)返回语句return(E)无条件转移语句goto L10 2表达式 表达式由运算对象和算符组成，对于多数程序语言来说，表达式的形式规则如下： （1）变量（包括下标变量）是表达式。 （2）若E1、E2为表达式，是一个二元算符，则E1E2是表达式。表达式一般采用中缀形式。 （3）若E是表达式，为一元算符，则E或E是表达式。 （4）若E是表达式，则（E）是表达式。 一般程序设计语言中算术算符和逻辑算符的优先顺序：乘幂

11、 （*或）一元负 （-）乘、除 （*，/，）加减 （+，-）关系符 （，=，=）非 （，not或NOT）与 （ ，&，and或AND）或 （ ，|，or或OR）等值 （，或equi）11v 2.1.4 程序的结构程序的结构 1FORTRAN 一个一个FORTRAN程序由一个主程序和若干个（可以是程序由一个主程序和若干个（可以是0个）辅程序段组成。个）辅程序段组成。 PROGRAM MAIN END SUBROUTINE SUB1 END SUBROUTINE SUBn END 辅程序段可以是函数、过程或数据块。每个程序段由一系列说明语句和执行语句组成，各段可以独立编译，这对于模块设计特

12、别合适。12 2C语言 一般由一个主函数和若干个（可以是一般由一个主函数和若干个（可以是0个）函数组成。个）函数组成。 C语言的程序结构如下：语言的程序结构如下：main() type function1 (参数表) type functionn （参数表） 3PASCAL PASCAL语言的特点是允许子程序嵌套定义，一个PASCAL程序可以看作是由操作系统调用的一个子程序，而子程序中又可以定义别的子程序。 （1）一个子程序B1中说明的名字X只在B1中有效。 （2）如果B2是B1的一个内层子程序，且B2中对X没有新的说明，则原来的名字在B2中仍然有效。如果B2对X重新作了说明，那么B2中对X的

13、任何引用都是指重新说明过的那个X。13 4Java Java很重要的概念是类（Class）及继承（Heritanced）。Java同时支持多态性（Polymorphism）和动态绑定（Dynamic Binding）等特性。class Car int calor-number; int door-number; int speed; push-break() Add oil() class Trash-Car extends Car double amount; fill-trash() 142.2 中中 间间 语语 言言v 2.2.1 逆波兰表示法逆波兰表示法逆波兰表示表达式 高级语言表示表

14、达式 ab* a*b ab*c+ a*b+c abcd/+* a*(b+c/d) ab*cd*+ a*b+c*d 高级语言表达式E的逆波兰表示法可这样定义： （1）若）若E是高级语言中的一个变量或常数，则是高级语言中的一个变量或常数，则E的逆波兰表示式仍的逆波兰表示式仍是是E。 （2）若高级语言中的表达式为）若高级语言中的表达式为E1 op E2，其中，其中，op是一个二元算是一个二元算符，符，E1、E2也是表达式，则逆波兰式表示为也是表达式，则逆波兰式表示为E1 E2 op，其中，其中，E1是是E1的逆波兰式，的逆波兰式，E2是是E2的逆波兰式。的逆波兰式。 （3）若高级语言中的表达式为（）

15、若高级语言中的表达式为（E），则逆波兰表示式为去掉括号），则逆波兰表示式为去掉括号的的E，E为为E的逆波兰表示式。的逆波兰表示式。15 若把逆波兰表达式视为一个字符串，则计算逆波兰式的算法为： （1）读入字串左端的一个字。）读入字串左端的一个字。 （2）如果读入空字，计算结束。）如果读入空字，计算结束。 （3）如果读入一个操作数，将操作数推进栈，转（）如果读入一个操作数，将操作数推进栈，转（1）。）。 （4）如果读入一个一元操作符，取栈顶一个操作数与一元操作符）如果读入一个一元操作符，取栈顶一个操作数与一元操作符进行运算，并将运算结果推进栈，转（进行运算，并将运算结果推进栈，转（1）。）。 （

16、5）如果读入一个二元操作符，取栈顶两个操作数与二元操作符）如果读入一个二元操作符，取栈顶两个操作数与二元操作符进行运算，并将运算结果推进栈，转（进行运算，并将运算结果推进栈，转（1）。）。16v 【例【例2.1】有以下用高级语言所编写的表达式：】有以下用高级语言所编写的表达式：3+5*4转换为逆波兰表达式为：354*+ 计算逆波兰表达式计算逆波兰表达式354*+的过程的过程步 骤 序 号栈计 算待处理字符串说 明1354*+初始状态2354*+读操作数3，进栈33 54*+读操作数5，进栈43 5 4*+读操作数4，进栈535*4+读操作符*，计算5*463 20+将计算结果20进栈73+20

17、读操作符+，计算3+20823将计算结果23进栈923读入空，计算结束17v 2.2.2 三地址代码三地址代码 三地址代码是由下面一般形式的语句构成的序列。x:=y op z其中x、y、z是变量名或编译时产生的临时变量名；y、z还可以是常数；op代表某种操作符。这种中间语言的特点有两个。 （1）非常接近汇编语言形式，包括汇编语言中最基本的操作。）非常接近汇编语言形式，包括汇编语言中最基本的操作。 （2）每个语句中赋值号的右边只有一个操作符，使得句子意义最）每个语句中赋值号的右边只有一个操作符，使得句子意义最小且不可分。小且不可分。 三地址代码的具体实现常以记录的形式表示，通常有3种表示方法：四

18、元式、三元式、间接三元式。 四元式的一般形式为：四元式的一般形式为：操作符操作数1操作数2运算结果18三地址码 四元式x:=A (:=， A， ， x)x:=op A (op， A， ， x) x:=A op B (op， A，B， x)对于转移类语句，上述四元式记录的内涵要做适当的修改： 例如，下面的三地址码转移类语句用四元式表示为： 三地址码 四元式goto L (JP， ， ， L)if a relop b goto L (Jrelop， a， b， L)if a goto L (J， a， ， L)call p, n (call， n， ， p)return y (RET， y， ， )转移方式条件运算量1条