编译原理第二章.ppt

《编译原理第二章.ppt》由会员分享，可在线阅读，更多相关《编译原理第二章.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、数据）（数据）4基于基于规则的的语言言基于基于规则的的语言以判断言以判断选择语句句为基本基本执行行单位。其程序的位。其程序的执行行过程是：程是：检查一定的条件，当它一定的条件，当它满足足时选择适当的操作。最有代表适当的操作。最有代表性的基于性的基于规则语言是言是PROLOG。其程序其程序结构形式构形式为：条件条件1动作作1条件条件2动作作2条件条件n动作作nv2.1.2 数据数据类型及其操作型及其操作（1）数值数据：数值数据包括整数、实数、复数以及这些类型的双长（或多倍长）精度数。对数值类型的数据可描述为算术运算集合。（2）逻辑数据：很多语言有专门用于布尔代数的数据类型，即逻辑型数据类型。有的

4、语言甚至还有位串型数据。对逻辑数据可实施逻辑运算（and、or、not等）。（3）字符数据：有些语言可以处理字符或字符串。字符数据类型用来承载字符或字符串。对字符数据的操作有很多，包括判断、转换以及对字符串的各种加工。（4）指针类型：指针类型的数据不是用来描述客观事物的，它的作用是为运算提供数据的地址。v常常见的的结构型数据构型数据类型有以下几种：型有以下几种：1数组一个数一个数组是由同一是由同一类型数据型数据组成的有序的集合。数成的有序的集合。数组下下标与数与数组元元素的存素的存储地址密切相关，二者呈地址密切相关，二者呈线性关系。因此数性关系。因此数组元素也称元素也称为下下标变量。量。N维数

5、数组的每个元素有的每个元素有N个下个下标。由。由N个下个下标决定数决定数组元素元素的存的存储位置。位置。2记录记录是由不同是由不同类型数据所型数据所组成的集合。成的集合。记录结构中每个元素所占有构中每个元素所占有的存的存储空空间可能互不相同，可能互不相同，记录的元素称的元素称为分量。分量。例如，例如，C语言采用下面的形式定言采用下面的形式定义记录：struct student char name8;int studclass;float math;结构分量是通过名字而不是像数组元素那样通过下标访问的。结构分量的名字是所谓复合名字，例如“结构名.分量名”。结构分量的使用与基本数据结构定义的变量相

6、同，如下述3个赋值语句：student.name=LIMINGstudent.studclass=3student.math=95.4每个分量的存储地址由记录结构的首地址与相应分量的偏移地址相加而成。记录结构的每个分量（域）所占用的存储字节数称为该域的长度。通过累加分量的长度可计算出各分量的偏移量。student.name占占8个字个字节，student.studclass占占2个字个字节，student.math占占4个字个字节，可，可计算三者算三者对应的偏移量的偏移量为0、8、10，若，若student记录结构在构在运行运行时被分配一个基址被分配一个基址a，则其各分量的地址其各分量的地址为

7、：student.name:astudent.studclass:a+8student.math:a+103字符串、表格和队列不同的不同的语言根据不同的需要会拓展出一些言根据不同的需要会拓展出一些实用数据用数据类型。型。有越来越多的有越来越多的语言把字符串作言把字符串作为一种基本的数据一种基本的数据类型，串的型，串的长度不度不加限制。加限制。这种数据种数据类型型给各种各种处理文字理文字语言的程序言的程序带来很多便利。来很多便利。v2.1.3 语句与表达式句与表达式1语句每当用每当用户创建了一个名称，就要用建了一个名称，就要用说明明语句来句来说明明这个名称所指个名称所指对象的意象的意义，是一种，

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

9、切智能行为的基础。条件语句if E then Sif E then S else 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 L2表达式表达式由运算对象和算符组成，对于多数程序语言来说，表达式的形式规则如下：（1）变量（包括下标变量）是表达式。（2）若E1、E2为表达式，是一个二元算符，则E1E2是表达式。表达式一般采用中缀形式。（3）若E是表达式，为一元算符，则E或E是表达式。（4）若E是表达式，则（E）是表

10、达式。一般程序设计语言中算术算符和逻辑算符的优先顺序：乘幂 （*或）一元负 （-）乘、除 （*，/，）加减 （+，-）关系符 （，=，=）非 （，not或NOT）与 （，&，and或AND）或 （，|，or或OR）等值 （，或equi）v2.1.4 程序的程序的结构构1FORTRAN一个一个FORTRAN程序由一个主程序和若干个（可以是程序由一个主程序和若干个（可以是0个）个）辅程序段程序段组成。成。PROGRAM MAINENDSUBROUTINE SUB1ENDSUBROUTINE SUBnEND辅程序段可以是函数、过程或数据块。每个程序段由一系列说明语句和执行语句组成，各段可以独立编译，

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

12、新说明过的那个X。4JavaJava很重要的概念是类（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()2.2 中中 间 语 言言v2.2.1 逆波逆波兰表示法表示法逆波兰表示表达式 高级语言表示表达式 ab*a*b ab*c+a*b+c abcd

13、/+*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）若高）若高级语言中的表达式言中的表达式为（E），），则逆波逆波兰表示式表示式为去掉括号去掉括号的的E，E为E的逆波的逆波

14、兰表示式。表示式。若把逆波兰表达式视为一个字符串，则计算逆波兰式的算法为：（1）读入字串左端的一个字。入字串左端的一个字。（2）如果）如果读入空字，入空字，计算算结束。束。（3）如果）如果读入一个操作数，将操作数推入一个操作数，将操作数推进栈，转（1）。）。（4）如果）如果读入一个一元操作符，取入一个一元操作符，取栈顶一个操作数与一元操作符一个操作数与一元操作符进行运算，并将运算行运算，并将运算结果推果推进栈，转（1）。）。（5）如果）如果读入一个二元操作符，取入一个二元操作符，取栈顶两个操作数与二元操作符两个操作数与二元操作符进行运算，并将运算行运算，并将运算结果推果推进栈，转（1）。）。v

15、【例【例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读操作符+，计算3+20823将计算结果23进栈923读入空，计算结束v2.2.2 三地址代三地址代码三地址代码是由下面一般形式的语句构成的序列。x:=y op z其中x、y、z是变量名或编译时产生的临时变量名

16、；y、z还可以是常数；op代表某种操作符。这种中间语言的特点有两个。（1）非常接近）非常接近汇编语言形式，包括言形式，包括汇编语言中最基本的操作。言中最基本的操作。（2）每个）每个语句中句中赋值号的右号的右边只有一个操作符，使得句子意只有一个操作符，使得句子意义最最小且不可分。小且不可分。三地址代码的具体实现常以记录的形式表示，通常有3种表示方法：四元式、三元式、间接三元式。四元式的一般形式四元式的一般形式为：操作符操作数1操作数2运算结果三地址码 四元式x:=A (:=，A，x)x:=op A (op，A，x)x:=A op B (op，A，B，x)对于转移类语句，上述四元式记录的内涵要做适

17、当的修改：例如，下面的三地址码转移类语句用四元式表示为：三地址码 四元式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条件运算量2转移目标v【例【例2.2】考】考虑如下如下语句：句：while ab do if cd then x:=y+z else x:=y-z翻翻译成四元式成四元式为：（1）(J,a,b,(3)（2）(JP,(11)（3）(J,c,d,(5)（4）(JP,(8)（5）(+,y,z,T1)（6）(:=,T1,x)（7）(JP,(1)（8）(-,y,z,T2)（9）(:=,T2,x)（10）(JP,(1)（11）