编译原理1编译引论.ppt

1、编译原理课程,第一章 引论,一 什么是编译程序,计算机经过几十年的发展， 在程序设计语言方面,已经从低级语言发展到高级语言;然而,计算机内部的本质只能识别 0 , 1 代码序列（机器语言）,而对高级语言甚至符号语言仍然一窍不通。 因此用高级语言编写的程序,必须先翻译为机器语言，才能被计算机理解执行。 第一个完成这种翻译任务的编译程序为FORTRAN编译程序,是上世纪五十年代，由1977年的图灵奖得主约翰 巴克斯(John Warner Backus)设计的，同时巴克斯也是最广泛流行的元语言BNF范式的发明人,第一节、编译程序概述,关于FORTRAN的一个小故事,关于FORTRAN的发明，其中还

2、有一个小插曲，当时冯诺伊曼正在担任IBM公司顾问，每周一次“升堂”审查公司的各种新科研计划。他当时看到了FORTRAN的想法，丝毫没有兴奋之感，反而这样问Backus：“为什么除了机器语言之外，你还想弄点别的呢？”。有趣的是，冯诺伊曼此后还一直坚持这种观点，他在普林斯顿的学生Donald Gillies回忆说，为了不像大家那样手工将程序汇编为二进制代码，他曾经开发了一个汇编程序，冯诺伊曼发现后非常生气，说：“这是在浪费宝贵的科学计算设备来干琐碎的杂事,定义:设源语言为L1,目标语言为L2, 翻译程序是一个程序,它能将L1转换为逻辑上等价的L2。 若 L1 为高级语言，L2 为低级语言或机器语言

3、，称这种 翻译程序为编译程序。 若 L1 为低级语言，L2 为机器语言，称这种翻译程序为 汇编程序。 解释程序是指逐条翻译 L1的语句，并立即执行翻译出的 目标代码序列。 编译原理 就是介绍编译程序的一般规律及设计方法的一门课程,高级语言程序,机器语言程序,翻译为,二 编译过程概述 编译程序从接受源程序到输出目标代码的整个过程，可逻辑的分为 5 个阶段： 词 法 分 析 语 法 分 析 中间代码生成 代 码 优 化 目标代码生成 1） 词法分析：把源程序作为字符串进行扫描 ，根据单词词法，识别出所有单词，过滤无用符，并检查是否为合法的单词。 单词一般分为如下几种： 基本字，标识符，常数，算符，

4、界符,例如： if n=1 then f:=1 else f:=n*f(n); 该程序经过语法分析,得到如下单词序列,过滤掉回车换行,空格,注释等,2) 语法分析: 根据语言的语法规则,从单词符号串中识别出各种语法单位 ,进行句子分析,并检查整个输入字串是否为合法的程序; 重要的语法单位有: 程序,子程序,语句,短语,表达式等 例如,program add; var a,b:real; begin read(a,b); write (a+b); end,程序,首部,说明段,执行部,program,程序名及参数,var,说明语句,add,变量名表,变量类型,a,b,real,begin,多语句,

5、end,read(a,b,write(a+b,3) 中间代码生成:根据语义规则,把各种语法单位翻译成中间代码序列. 中间代码有三种: 四元式,三元式,逆波兰式. 中间代码的特点:结构简单,语义明确,易于理解及优化. 四元式可表示为: (操作符,操作数1,操作数2,结果,例如: 语句 Z:=(x+0.4)*Y/W; 翻译后得到右面 的四元式序列,四元式序列 (+ , x, 0.4, T1) (* , T1, Y, T2) (/ , T2, w, T3) (:= , T3, , Z,从示例可看出:每条四元式只进行一次最基本的操作,4) 代码优化：对产生的中间代码序列进行加工变换，使变换后的代码更为

6、高效 （时间，空间上）。 优化主要有： 循环优化，公共表达式提取，强度削弱等。 5) 目标代码生成：把中间代码程序翻译为机器指令或汇编指令程序。 这一部分的处理，与计算机硬件及操作系统密切相关。 如寄存器数目，机器指令功能及指令条数；操作系统的 BIOS，内存管理，文件管理等。 三 编译程序的结构 编译程序可以划分为如下几个基本模块,表格管理:对各种表格进行管理,包括表格的构造、查找、修改、 删除、插入 等； 编译程序中，表格的种类较多，最主要的有如下几种： 符号表，常量表，标号表，子程序名表，四元式表等。 表格由若干结构相同的表格项组成，表格项由二元式表示,项名 信息,表格项,表格,项名 1

7、 信息,项名 2 信息,项名 n 信息,设计编译程序 编译程序的设计方式可以分为两类,第二节、高级语言概述,一 什么是程序设计语言 程序设计语言是一符号系统，由语法和语义两方面所定义。 语法：是一组规则，规定了语言的形式结构，包括单词结构， 句子结构，程序结构等。 语法=词法规则+句法规则 词法规则：规定了形成单词的规则；如常数，标识符， 基本字，算符等。 句法规则：规定了由单词构造更大语法单位的规则； 如表达式，短语，语句，程序等,语义：也是一组规则，规定了各语法单位的确切含义。 例如：A=B，可解释为：A赋值为B；（C语言） 也可以解释为 ：A等于B （P语言） 这完全由语义规则所确定。

8、二 数据类型 各种语言都提供了一些最基本的数据类型,称为初等数据类型，这些数据类型的特征是数据的单一性；还提供了由初等数据类型构造复杂结构类型的手段。 1）初等数据类型,数值类型：（整数，实数）可进行算术运算和比较运算； 逻辑类型：可进行逻辑运算； 字符类型：可进行比较远算及字符串操作； 指针类型：指向另一变量的地址,这些因素中,在编译时能确定的部分,用一个数组内情向量表来记录, 以便计算数组元素地址使用。换句话说：当编译程序扫描到数组说明语句时，就把数组的各确定部分登记到内情向量表中。 内情向量表组织如下,记录分量表,因此，name i 在记录中的地址为： addr=a+offset i a

9、 为记录的第一个分量的地址,6 循环控制语句 while do ; for := to do ; repeat ;. until 7 子程序调用 函数调用一般出现在表达式中,形式如下: (实际参数) 过程调用一般作为语句,形式如下: (实际参数,8 输入输出语句 read(); write(); 9 简单句和复合句 简单句是指不包含其它语句的基本语句, 复合句是指句中有句. 例如: V:=E,goto L ,read(a,b) 等都是简单句; if B then S else S, while B do S 等都是复合句,五 子程序参数传递 当调用一个子程序时,首先应将所需的数据传递给子程序,

10、 传递方式主要有三种: 传值,传地址,传名 设有如下函数: function distence(x1,y1,x2,y2):real; begin distence:=sqrt(x2-x1)*2+(y2-y1)*2) end; x1,y1,x2,y2 称为形式参数 设主程序调用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 称为实际参数,1传值 调用程序把实际参数的值传递到形式参数的空间中,这种方式,子程序一般不改变实际参数的值,这种方式,子程序间接访问主程序实际参数的值,改变了实际参数的值,3传名 传名是一种宏替换,直接在调用处产生一个子程序副本,并且 用实际

11、参数名替代形式参数名. 设主程序调用如下: d:=distence(a1,b1,a2,b2); 相当于在此处产生一段程序: d:=sqrt(a2-a1)*2+(b2-b1)*2,六 存储分配 程序运行时,必须分配相应的存储空间. 这些空间包括: 变量空间,常量空间,临时空间,连接单元 等.有的空间在编译时就能确定其大小,而有的空间必须在程序运行时才能确定.根据这一特性,把空间分配分为两种: 静态存储分配 动态存储分配 1 静态存储分配 若在编译时能完全确定程序所需空间大小,并能确定每个数据项的地址,就可在编译时分配所需空间,这种分配方法称为静态存储分配. 若一个语言无递归调用,无可变数据项,则可静态地确定各数据项的空间大小和地址. Fortran语言满足这种定义,2 动态存储分配 是指在程序运行时才能确定存储空间和地址的一种分配方法.适用于允许递归和可变数据项的语言,如pascal 和 c 语言. 一般采用堆栈动态地分配空间, 当调用子程序时,就在堆栈中为该子程序分配所需空间;而子程序运行结束后,就释放该子程序空间