编译原理 第二章

2/5/2023温故知新翻译程序：它是一个程序，能把一种语言程序转换成另一种语言程序，且二者在逻辑上是等价的。这两种语言分别称为源语言和目标语言。编译程序：一种翻译程序，它的源语言是“高级语言”（C,Java,Pascal），目标语言是“低级语言”(汇编语言，机器语言)12/5/2023中国科大温故知新编译前端编译后端编译前端：与源语言有关，与目标机无关词法分析器语法分析器语义分析与中间代码生成器源程序优化器目标代码生成器目标代码表格管理出错处理单词符号语法单位中间代码中间代码编译后端：与源语言无关，与目标机有关2第二章高级语言及其语法描述本章内容简介本章描述程序设计语言的基本结构和主要共同特征并介绍程序设计语言主要语句的文法描述与形式定义。

与机器语言或汇编语言比较，高级语言的优点：较接近于数学语言和工程语言，比较直观、自然和易于理解;便于验证其正确性，易于改错;编写效率高;易于移植.2.1程序语言的定义任何语言实现的基础是语言定义语言的定义决定了该语言具有什么样的语言功能、什么样的程序结构、什么样的数据结构以及具体的使用形式等细节问题。对于语言用户来说：语言定义就是一本用户手册。对于编译程序设计者来说：语言定义就是具体实现的理论依据。对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。语义是描述了语言的含义语用则是从使用的角度去描述语言。例如赋值语句s＝2*3.1416*r*(r+h)的非形式化的描述为：语法：赋值语句由一个变量，后随一个赋值号“＝”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。2.1.1语法语言的语法是指这样一组规则，用它可产生一个程序。规则：词法规则语法规则词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法2.1.2语义语义：一组规则，用它可以定义一个程序的意义。程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。程序的层次结构程序|子程序或分程序、过程、函数|语句|表达式|数据引用算符函数调用程序语言每个组成成分的逻辑和实现意义

抽象的逻辑的意义数学意义计算机实现的意义具体实现2.2高级语言的一般特性

高级语言的分类

强制式语言(ImperativeLanguge)也称过程式语言：命令驱动，面向语句FORTRAN、C、Pascal，Ada应用式语言（ApplicativeLanguage）：注重程序所表示的功能，而不是具体语句的执行LISP、ML2.2高级语言的一般特性

2.2.1高级语言的分类

基于规则的语言（Rule-basedLanguage）：检查一定的条件，当它满足值，则执行适当的动作Prolog面向对象语言（Object-OrientedLanguage）：封装性、继承性和多态性Smalltalk，C++，Java2.2.2程序结构FORTRAN一个程序由一个主程序段和若干辅程序段组成。辅程序段可以是子程序、函数段或数据块。每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。模块结构，没有嵌套和递归各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。主程序PROGRAM… …end辅程序1SUBROUTINE… …end辅程序2FUNCTION… …endPASCALPASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。一个PASCAL过程：过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end2/5/2023中国科大2.2高级语言的一般特性2.2.2程序结构–JavaclassCar{intcolor_number;intdoor_number;intspeed;Push_break(){…}Add_oil(){…}}classTrash_CarextendsCar{doubleamount;Fill_trash(){…}}封装、继承、多态(2)public、protected、private202.2.3数据类型与操作一个数据类型通常包括以下三种要素：用于区别这种类型数据对象的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作2.2.3数据类型与操作一．初等数据类型数值类型：整型、实型、复数、双精度，运算：+，-，*，/等逻辑类型：布尔运算：∨，∧，┑字符类型：符号处理指针类型：值指向另外一些数据标识符与名字标识符：以字母开头的，由字母数字组成的字符串。标识符与名字两者有本质区别：标识符是语法概念名字有确切的意义和属性标识符与名字名字：值：单元中的内容属性：类型和作用域名字的性质的说明方式：由说明语句来明确规定的隐含说明：FORTRAN以I,J,K,…N为首的名字代表整型，否则为实型。动态确定：走到哪里，是什么，算什么2/5/2023中国科大2.2高级语言的一般特性1、数组数组：同一类型数据所组成的某种n维矩形结构下标：沿着某一维的距离数组元素：由数组名连同各维的下标值命名确定数组、可变数组intarray[3];

inta=array[2];intsize=3;//或用户输入的数int*array=newint[size];

inta=array[2];Delete[]array;确定数组可变数组252/5/2023中国科大2.2高级语言的一般特性1、数组数组存储方式：按行存放、按列存放数组元素地址计算：数据结构1A[2][3]={{1,2,3},{4,5,6}}23456123456按行存放142536按列存放26内情向量把数组的有关信息记录在一个“内情向量”中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型。对于确定数组来说，内情向量可登记在符号表中；

对于可变数组，内情向量的信息在编译时无法全部知道，只有到运行阶段才能全部确定下来，存贮分配也要等到运行时方能进行2记录逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。 record{charNAME[20]; integerAGE; boolMARRIED; }CARD[1000]访问：复合名CARD[k].NAME存储：连续存放域的地址计算：相对于记录结构起点的相对数OFFSET。3字符串、表格、栈字符串：符号处理、公式处理表格：本质上是一种记录结构线性表：一组顺序化的记录结构栈：一种线性表，后进先出，POP,PUSH三抽象数据类型一个抽象数据类型包括：数据对象的一个集合；作用于这些数据对象的抽象运算的集合；这种类型对象的封装，即，除了使用类型中所定义的运算外，用户不能对这些对象进行操作。程序设计语言对抽象数据类型的支持Ada语言通过程序包（package）提供了数据封装的支持Smalltalk、C++和Java语言则通过类（Class）对抽象数据类型提供支持。2.2.4语句与控制结构一．表达式表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。形式：中缀、前缀、后缀X*Y-AP↑表达式形成规则(1)变量（包括下标变量）、常数是表达式(2)若E1、E2为表达式，θ为二元运算符，则E1θE2是表达式(3)若E是表达式，θ为一元运算符，则θE或Eθ是表达式(4)若E是表达式，则（E）是表达式5、a、5+a、-a、(a+5)、2+(4+a)-(-5)都是表达式2/5/20232.2高级语言的一般特性表达式的结合性和优先集与数学习惯类似不同的语言，这两种性质各有差异FORTRAN结合性优先集X–Y-Z等于(X–Y)-Z左结合X–Y+Z等于(X-Y)+Z左结合X**Y**Z等于X**(Y**Z)右结合332/5/2023中国科大2.2高级语言的一般特性表达式的结合性和优先集与数学习惯类似不同的语言，这两种性质各有差异FORTRAN结合性优先集乘幂**或↑一元负-乘、除*，/，÷加、减+，-关系符<,=,>,<=,<>,>=非﹁，not或.NOT.与∧，&，and或.AND.或∨，|，or或.OR.隐含imp或等值≡，～或epui342/5/2023中国科大2.2高级语言的一般特性例：令+、*和↑代表加、乘和乘幂，按照如下的非标准优先集和结合性的约定（1）优先顺序（从高至低）为+、*和↑（2）同级优先采用左结合计算1+1*2↑2*1↑2的值

1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256352/5/2023中国科大2.2高级语言的一般特性2.2.4语句和控制结构二、语句从功能上说，语句大体可分执行性语句和说明性语句。从形式上说，语句还可分为简单句、复合句和分程序等。36二．语句赋值语句：A:=B名字左值：该名字代表的那个单元（地址）称为该名字的左值。(所代表的存贮单元的地址)右值：一个名字的值称为该名字的右值。(所代表的存贮单元的内容)控制语句：无条件转移语句

gotoL条件语句

ifBthenSifB

thenS1elseS2循环语句

whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS过程调用语句

callP(X1,X2,...,Xn)返回语句

return(E)说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。简单句和复合句简单句：不包含其他语句成分的基本句复合句：句中有句的语句复习：高级语言的一般特性

高级语言的分类

程序结构数据类型与操作初等数据类型数据结构抽象数据类型语句与控制结构2/5/2023中国科大作业P35页，第3、4题422.3程序语言的语法描述为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。字母表字母表：元素的非空有穷集例如，∑={a,b,c}根据字母表的定义，Σ是字母表，它由a、b、c三个元素组成。注意：

(1)字母表中至少包含一个元素。

(2)字母表中的元素,可以是字母、数字或其他符号。例如，∑‘={0,1}是一个字母表，由0、1两个元素组成。字母表中的元素称为符号或称为字符。例如，前述例子中2.符号（字符）a、b、c是字母表Σ中的符号；0、1是字母表Σ'中的符号。例如，设有字母表∑={a,b,c}符号的有穷序列称为符号串。符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。则有符号串a，b，ab，ba，cba，

abc…

3.符号串（字）说明：符号串中符号的顺序很重要ab和ba是字母表Σ上的两个不同符号串。不包含任何符号的符号串被称为是空符号串。用ε表示2/5/20232.3程序语言的语法描述符号串的长度串中符号的个数为符号串的长度。若x=ab是符号串，则|x|表示符号串的长度。|x|=2。注意：|ε|=049字符串的连接：设X是个字符串，Y是个字符串，则XY就是字符串的连接。例如设X＝ABC，Y＝10A则XY＝ABC10A，YX＝10AABC。对于任意一个字符串X，都有εx＝xε＝x。注意在U≠V下，UV≠VU，即不满足交换率(UV)W=U(VW)，即满足结合率2、集合乘积

设A和B是符号串的集合,则A和B的乘积定义为：

AB={xy|x∈A,y∈B}集合的乘积是满足于x∈A,y∈B的所有符号串xy所构成的集合。例如：设A={a,b},B={c,d}则AB={ac,ad,bc,bd}由于对任意的符号串x，总有

x=x=x所以,对任意集合A,我们有:{}A=A{}=A特别指出的是，是符号串,不是集合，而{}表示由空符号串所组成的集合,但这样的集合不是空集合Φ={}。3.符号串的幂运算设x是符号串,则x的幂运算定