编译原理1编译引论

1、 第一章第一章 引论引论一一 什么是编译程序？什么是编译程序？ 计算机经过几十年的发展，计算机经过几十年的发展， 在程序设计语言方面在程序设计语言方面,已经从已经从低级语言发展到高级语言低级语言发展到高级语言;然而然而,计算机内部的本质只能识别计算机内部的本质只能识别 0 , 1 代码序列（机器语言）代码序列（机器语言）,而对高级语言甚至符号语言仍然一窍而对高级语言甚至符号语言仍然一窍不通。不通。 因此用高级语言编写的程序因此用高级语言编写的程序,必须先翻译为机器语言，必须先翻译为机器语言，才能被计算机理解执行。才能被计算机理解执行。 第一个完成这种翻译任务的编译程序为第一个完成这种翻译任务的

2、编译程序为FORTRAN编译程编译程序序,是上世纪五十年代，由是上世纪五十年代，由1977年的图灵奖得主约翰年的图灵奖得主约翰 巴克斯巴克斯(John Warner Backus)设计的，同时巴克斯也是最广泛流行的设计的，同时巴克斯也是最广泛流行的元语言元语言BNF范式的发明人。范式的发明人。第一节、编译程序概述第一节、编译程序概述关于关于FORTRAN的一个小故事：的一个小故事： 关于关于FORTRAN的发明，其中还有一个小插曲，当时冯诺伊曼正的发明，其中还有一个小插曲，当时冯诺伊曼正在担任在担任IBM公司顾问，每周一次公司顾问，每周一次“升堂升堂”审查公司的各种新科研计审查公司的各种新科研

3、计划。他当时看到了划。他当时看到了FORTRAN的想法，丝毫没有兴奋之感，反而这的想法，丝毫没有兴奋之感，反而这样问样问Backus：“为什么除了机器语言之外，你还想弄点别的呢？为什么除了机器语言之外，你还想弄点别的呢？”。有趣的是，冯诺伊曼此后还一直坚持这种观点，他在普林斯顿的学有趣的是，冯诺伊曼此后还一直坚持这种观点，他在普林斯顿的学生生Donald Gillies回忆说，为了不像大家那样手工将程序汇编为二进回忆说，为了不像大家那样手工将程序汇编为二进制代码，他曾经开发了一个汇编程序，冯诺伊曼发现后非常生气，制代码，他曾经开发了一个汇编程序，冯诺伊曼发现后非常生气，说：说：“这是在浪费宝贵

4、的科学计算设备来干琐碎的杂事！这是在浪费宝贵的科学计算设备来干琐碎的杂事！”定义定义:设源语言为设源语言为L1,目标语言为目标语言为L2, 翻译程序翻译程序是一个程序是一个程序,它能将它能将L1转换为逻辑上等价的转换为逻辑上等价的L2。 若若 L1 为高级语言，为高级语言，L2 为低级语言或机器语言，称这种为低级语言或机器语言，称这种 翻译程序为翻译程序为编译程序编译程序。 若若 L1 为低级语言，为低级语言，L2 为机器语言，称这种翻译程序为为机器语言，称这种翻译程序为 汇编程序。汇编程序。 解释程序解释程序是指逐条翻译是指逐条翻译 L1的语句，并立即执行翻译出的的语句，并立即执行翻译出的

5、目标代码序列。目标代码序列。 编译原理编译原理 就是介绍编译程序的一般规律及设计方法的一门课程。就是介绍编译程序的一般规律及设计方法的一门课程。高级语言程序高级语言程序机器语言程序机器语言程序翻译为翻译为二二 编译过程概述编译过程概述 编译程序从接受源程序到输出目标代码的整个过程，可编译程序从接受源程序到输出目标代码的整个过程，可逻辑的分为逻辑的分为 5 5 个阶段：个阶段：词词 法法 分分 析析语语 法法 分分 析析 中间代码生成中间代码生成 代代 码码 优优 化化 目标代码生成目标代码生成 1） 词法分析：把源程序作为字符串进行扫描词法分析：把源程序作为字符串进行扫描 ，根据单词词，根据单

6、词词法，识别出所有单词，过滤无用符，并检查是否为合法的单法，识别出所有单词，过滤无用符，并检查是否为合法的单词。词。 单词一般分为如下几种：单词一般分为如下几种： 基本字，标识符，常数，算符，界符基本字，标识符，常数，算符，界符 例如：例如： if n=1 then f:=1 else f:=n*f(n); 该程序经过语法分析该程序经过语法分析,得到如下单词序列得到如下单词序列:ifn=1thenf:=1 elsef:=n*f(n);过滤掉回车换行过滤掉回车换行,空格空格,注释等注释等2) 语法分析语法分析: 根据语言的语法规则根据语言的语法规则,从单词符号串中识别出从单词符号串中识别出各种语

7、法单位各种语法单位 ,进行句子分析进行句子分析,并检查整个输入字串是否为合并检查整个输入字串是否为合法的程序法的程序; 重要的语法单位有重要的语法单位有: 程序程序,子程序子程序,语句语句,短语短语,表达式等表达式等例如例如: program add;var a,b:real;begin read(a,b);write (a+b);end.程序程序首部首部说明段说明段执行部执行部program程序名及参数程序名及参数var说明语句说明语句add变量名表变量名表变量类型变量类型a,brealbegin多语句多语句endread(a,b)write(a+b)3) 中间代码生成中间代码生成:根据语义

8、规则根据语义规则,把各种语法单位翻译成中间把各种语法单位翻译成中间代码序列代码序列. 中间代码有三种中间代码有三种: 四元式四元式,三元式三元式,逆波兰式逆波兰式. 中间代码的特点中间代码的特点:结构简单结构简单,语义明确语义明确,易于理解及优化易于理解及优化. 四元式可表示为四元式可表示为: (操作符操作符,操作数操作数1,操作数操作数2,结果结果)例如例如: 语句语句 Z:=(x+0.4)*Y/W; 翻译后得到右面翻译后得到右面 的四元式序列的四元式序列: 四元式序列四元式序列(+ , x, 0.4, T1)(* , T1, Y, T2)(/ , T2, w, T3)(:= , T3, ,

9、 Z)从示例可看出从示例可看出:每条四元式只进行一次最基本的操作每条四元式只进行一次最基本的操作.4) 代码优化：对产生的中间代码序列进行加工变换，使变换代码优化：对产生的中间代码序列进行加工变换，使变换后的代码更为高效后的代码更为高效 （时间，空间上）。（时间，空间上）。 优化主要有：优化主要有： 循环优化，公共表达式提取，强度削弱等。循环优化，公共表达式提取，强度削弱等。5) 目标代码生成：把中间代码程序翻译为机器指令或汇编指目标代码生成：把中间代码程序翻译为机器指令或汇编指令程序。令程序。 这一部分的处理，与计算机硬件及操作系统密切相关。这一部分的处理，与计算机硬件及操作系统密切相关。

10、如寄存器数目，机器指令功能及指令条数；操作系统的如寄存器数目，机器指令功能及指令条数；操作系统的 BIOS，内存管理，文件管理等。内存管理，文件管理等。三三 编译程序的结构编译程序的结构 编译程序可以划分为如下几个基本模块：编译程序可以划分为如下几个基本模块：词法分析器词法分析器语法分析器语法分析器中间代码生成中间代码生成中间代码优化中间代码优化目标代码生成目标代码生成源程序源程序单词符号单词符号语法单位语法单位四元式四元式四元式四元式目标程序目标程序 表表格格管管理理 错错误误处处理理编译程序总框编译程序总框表格管理表格管理:对各种表格进行管理对各种表格进行管理,包括表格的构造、查找、修改、

11、包括表格的构造、查找、修改、 删除、插入删除、插入 等；等； 编译程序中，表格的种类较多，最主要的有如下几种：编译程序中，表格的种类较多，最主要的有如下几种： 符号表，常量表，标号表，子程序名表，四元式表等符号表，常量表，标号表，子程序名表，四元式表等。 表格由若干结构相同的表格项组成，表格项由二元式表示：表格由若干结构相同的表格项组成，表格项由二元式表示：项名项名 信息信息表格项表格项表格表格项名项名 1 信息信息项名项名 2 信息信息项名项名 n 信息信息4设计编译程序设计编译程序 编译程序的设计方式可以分为两类：编译程序的设计方式可以分为两类：方式方式人工设计人工设计自动生成自动生成低级

12、语言低级语言高级语言高级语言自动生成扫描器自动生成扫描器自动生成分析器自动生成分析器自动生成编译程序自动生成编译程序第二节、高级语言概述第二节、高级语言概述一一 什么是程序设计语言什么是程序设计语言 程序设计语言是一符号系统，由程序设计语言是一符号系统，由语法语法和和语义语义两方面所定义。两方面所定义。语法：语法：是一组规则，规定了语言的形式结构，包括单词结构，是一组规则，规定了语言的形式结构，包括单词结构， 句子结构，程序结构等。句子结构，程序结构等。 语法语法=词法规则词法规则+句法规则句法规则 词法规则词法规则：规定了形成单词的规则；如常数，标识符，：规定了形成单词的规则；如常数，标识符

13、， 基本字，算符等。基本字，算符等。 句法规则句法规则：规定了由单词构造更大语法单位的规则；：规定了由单词构造更大语法单位的规则； 如表达式，短语，语句，程序等。如表达式，短语，语句，程序等。语义：语义：也是一组规则，规定了各语法单位的确切含义。也是一组规则，规定了各语法单位的确切含义。 例如：例如：A=B，可解释为：可解释为：A赋值为赋值为B；（；（C语言）语言） 也可以解释为也可以解释为 ：A等于等于B （P语言）语言） 这完全由语义规则所确定。这完全由语义规则所确定。二二 数据类型数据类型 各种语言都提供了一些最基本的数据类型各种语言都提供了一些最基本的数据类型,称为初等数据称为初等数据

14、类型，这些数据类型的特征是数据的单一性；还提供了由初等类型，这些数据类型的特征是数据的单一性；还提供了由初等数据类型构造复杂结构类型的手段。数据类型构造复杂结构类型的手段。1）初等数据类型）初等数据类型数值类型：（整数，实数）可进行算术运算和比较运算；数值类型：（整数，实数）可进行算术运算和比较运算；逻辑类型：可进行逻辑运算；逻辑类型：可进行逻辑运算；字符类型：可进行比较远算及字符串操作；字符类型：可进行比较远算及字符串操作；指针类型：指向另一变量的地址。指针类型：指向另一变量的地址。2）结构类型）结构类型-数组数组 数组是由同一类型数据所组成的多维结构，数组元素是多数组是由同一类型数据所组成

15、的多维结构，数组元素是多维空间的一个点，代表了一个存储空间。数组的存储，是通过维空间的一个点，代表了一个存储空间。数组的存储，是通过按行或按列方式，把每个数组元素存放在一个连续的存储空间按行或按列方式，把每个数组元素存放在一个连续的存储空间中。中。设数组类型为设数组类型为 A:arrayL1 .u1,L2 . u2,.Ln . un of elemtype, 数组元素为数组元素为 Ai1,i2,.in, di=ui -Li+1则该元素的地址可按如下公式计算则该元素的地址可按如下公式计算: addr= a + (i1 - L1)*d2d3d4.dn + (i2 - L2)* d3d4.dn +

16、(in-1 - Ln-1)* dn + (in - Ln ) *elemlengthaddr=a -c +v c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.dn + ( Ln-1)* dn + ( Ln ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlengthv = (.(i1d2+i2)d3+i3)d4+i4).) dn + in *elemlength C是常量是常量,在编译时可以计算出在编译时可以计算出;V是可变部分是可变部分,只能在程序只能在程序运行时才能计算出。运行时才能计算出。 从上可知：计

17、算数组元素地址涉及到如下几个因素：从上可知：计算数组元素地址涉及到如下几个因素： a c L1.Ln d1.dn elemlength i1.in 这些因素中这些因素中,在编译时能确定的部分在编译时能确定的部分,用一个数组用一个数组内情向量内情向量表表来记录来记录, 以便计算数组元素地址使用。换句话说：当编译程以便计算数组元素地址使用。换句话说：当编译程序扫描到数组说明语句时，就把数组的各确定部分登记到内情序扫描到数组说明语句时，就把数组的各确定部分登记到内情向量表中。向量表中。 内情向量表组织如下：内情向量表组织如下：L1 u1 d1 L2 u2 d2 Ln un dn a c n elem

18、length 3）结构类型）结构类型- 记录记录 是由多种类型的数据组合起来的一种数据结构。是由多种类型的数据组合起来的一种数据结构。Pascal 语语言中，可如下定义一种记录类型言中，可如下定义一种记录类型type = record :; :; :; end; 域名即记录分量域名即记录分量,域的类型可以是简单数据类型域的类型可以是简单数据类型,也可以是已也可以是已经定义过的数据类型。经定义过的数据类型。 可采用分量顺序方式可采用分量顺序方式,分配记录的地址空间。由于每个域类分配记录的地址空间。由于每个域类型及空间大小都可能不同型及空间大小都可能不同,因此因此,只能通过表映射方式计算各个域只能

19、通过表映射方式计算各个域在记录中的地址。在记录中的地址。记录分量表：记录分量表：域名域名 相对位移相对位移 域类型域类型name1 offset1 type1name2 offset2 type2 namen offsetn typen因此，因此，name i 在记录中的地址为：在记录中的地址为：addr=a+offset ia 为记录的第一个分量的地址；为记录的第一个分量的地址；三三 表达式表达式 表达式是由算符和运算量组成表达式是由算符和运算量组成,可递规定义如下可递规定义如下: 1 变量变量,常量常量,函数为表达式函数为表达式 E; 2 若若 E1,E2为表达式为表达式,则则: E1 o

20、p E2, op E, (E) 为表达式。为表达式。 算符间存在如下优先顺序：算符间存在如下优先顺序： 乘幂（乘幂（*） 负号负号 （） 乘除（乘除（* /） 加减（加减（+ -） 关系符（关系符（ = = 类型定义段类型定义段 type = set of ; = array of ; = record end;2 变量说明段变量说明段var :;:;:;3 函数及过程定义函数及过程定义 function (参数说明参数说明):; ; procedure (参数说明参数说明) ; ;4 赋值句赋值句 := ; 左边变量取其地址左边变量取其地址,右边表达式取其值右边表达式取其值.5 分支语句分支

21、语句 if then else ; case of :; : else : end; goto ;6 循环控制语句循环控制语句 while do ; for := to do ; repeat ;. until 7 子程序调用子程序调用 函数调用一般出现在表达式中函数调用一般出现在表达式中,形式如下形式如下: (实际参数实际参数) 过程调用一般作为语句过程调用一般作为语句,形式如下形式如下: (实际参数实际参数);8 输入输出语句输入输出语句 read(); write();9 简单句和复合句简单句和复合句 简单句简单句是指不包含其它语句的基本语句是指不包含其它语句的基本语句, 复合句复合句是

22、指句中有句是指句中有句.例如例如: V:=E,goto L ,read(a,b) 等都是简单句等都是简单句; if B then S else S, while B do S 等都是复合句等都是复合句.五五 子程序参数传递子程序参数传递 当调用一个子程序时当调用一个子程序时,首先应将所需的数据传递给子程序首先应将所需的数据传递给子程序,传递方式主要有三种传递方式主要有三种: 传值传值,传地址传地址,传名传名 设有如下函数设有如下函数: function distence(x1,y1,x2,y2):real; begin distence:=sqrt(x2-x1)*2+(y2-y1)*2) en

23、d; x1,y1,x2,y2 称为形式参数称为形式参数 设主程序调用如下设主程序调用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 称为实际参数称为实际参数.1传值传值 调用程序把实际参数的调用程序把实际参数的值值传递到形式参数的空间中传递到形式参数的空间中.1145x1y1x2y21145a1b1a2b2主程序空间主程序空间子程序空间子程序空间这种方式这种方式,子程序一般不改变实际参数的值子程序一般不改变实际参数的值.2传地址传地址 调用程序把实际参数的调用程序把实际参数的地址地址传递到形式参数的空间中传递到形式参数的空间中. addr(a1) addr(b

24、1) addr(a2) addr(b2)x1y1x2y21145a1b1a2b2主程序空间主程序空间子程序空间子程序空间 这种方式这种方式,子程序间接访问主程序实际参数的值子程序间接访问主程序实际参数的值,改变了改变了实际参数的值实际参数的值.3传名传名 传名是一种传名是一种宏替换宏替换,直接在调用处产生一个子程序副本直接在调用处产生一个子程序副本,并且并且用实际参数名替代形式参数名用实际参数名替代形式参数名. 设主程序调用如下设主程序调用如下: d:=distence(a1,b1,a2,b2);相当于在此处产生一段程序相当于在此处产生一段程序: d:=sqrt(a2-a1)*2+(b2-b1)*2);六六 存储分配存储分配 程序运行时程序运行时,