编译程序引言1

《编译程序引言1》由会员分享，可在线阅读，更多相关《编译程序引言1（40页珍藏版）》请在金锄头文库上搜索。

1、编 译 原 理2011.12011.11课程简介先行课程： (PASCAL)、离散数学、 汇编语言、数据结构编译原理课程应用领域编译原理课程应用领域编译器的设计编译器的设计一般的软件设计一般的软件设计例如：例如：例如：例如：v文本编辑器、信息检索系统、文本编辑器、信息检索系统、文本编辑器、信息检索系统、文本编辑器、信息检索系统、模式识别器模式识别器模式识别器模式识别器v排版、绘图系统排版、绘图系统排版、绘图系统排版、绘图系统v程序验证器程序验证器程序验证器程序验证器21、程序设计语言编译程序程序设计语言编译程序 陈火旺等陈火旺等 国防工业出版社（第三版）国防工业出版社（第三版）2、编译原理 吕

2、映芝 清华大学出版社 3、编译原理及实践，Kenneth C. Louden， 冯博琴译，机械工业出版社主要参考资料主要参考资料3系统地了解程序设计语言编译程序的构造原理及其具体实现的方法；培养利用计算机语言处理技术进行系统分析和软件设计的能力。 为什么要学习编译原理，为什么要学习编译原理，学习的目的是什么？学习的目的是什么？4课程考核方法课程考核方法主要采用闭卷考试的形式；同时，作业完成情况和上机实践的结果占一定的比例。 考试成绩 = 闭卷考试+ 考勤和作业完成 情况 + 上机5联系方式E-mail: Tel: 作业可通过班长（或课程代表）提交。如有什么建议和问题，课后可E-mail或电话联

3、系。6编译原理编译原理第一章第一章 引论引论第二章第二章 高级语言及其语法描述高级语言及其语法描述第三章第三章 词法分析词法分析第四章第四章 语法分析语法分析自上向下分析自上向下分析第五章第五章 语法分析语法分析自下向上分析自下向上分析第六章第六章 属性文法与语法制导翻译属性文法与语法制导翻译第七章第七章 语义分析和中间代码生成语义分析和中间代码生成第八章第八章 符号表符号表第九章第九章 运行时存储空间组织运行时存储空间组织第十章第十章 优化优化第十一章第十一章 目标代码生成目标代码生成第十二章第十二章 并行编译基础并行编译基础7第一章第一章 引论引论1.1 1.1 什么叫编译程序什么叫编译程

4、序1.2 1.2 编译过程概述编译过程概述1.3 1.3 编译程序的结构编译程序的结构1.4 1.4 编译程序与程序设计环境编译程序与程序设计环境1.5 1.5 编译程序的生成编译程序的生成8知知 识识 结结 构构9过程式语言过程式语言 Fortran,Pascal,C函数式语言函数式语言 Lisp逻辑式语言逻辑式语言 Prolog对象式语言对象式语言 C+汇编语言汇编语言机器语言机器语言第一章第一章 引论引论1.1 1.1 什么叫编译程序什么叫编译程序. . 程序设计语言程序设计语言程序设程序设程序设程序设计语言计语言计语言计语言 高级语言高级语言低级语言：面向机器的语言低级语言：面向机器的

5、语言10编译程序编译程序: :是指这样的程序，它能够把某是指这样的程序，它能够把某种语言的程序转换成另一种语言的程序，种语言的程序转换成另一种语言的程序，而后者与前者在逻辑上是等价的。如果而后者与前者在逻辑上是等价的。如果源语言是诸如源语言是诸如FORTRANFORTRAN、PascalPascal、C C、AdaAda、SmalltalkSmalltalk或或JavaJava这样的这样的“高级语高级语言言”，而目标语言如汇编语言之类的，而目标语言如汇编语言之类的“低级语言低级语言”这样的翻译程序则称之为编这样的翻译程序则称之为编译程序。译程序。112 2. .在计算机上如何执行一个高级在计算

6、机上如何执行一个高级语言程序？语言程序？1）把高级语言程序翻译成机器语言程序；2）运行所得的机器语言程序求得计算结果。高级语言源程序的执行通常分两个阶段:计算机只能识别由0和1组成的二进制指令。12源程序(高级语言)编译程序计算机目标程序(机器语言)编译阶段初始数据目标程序计算机运行系统计算结果运行阶段13. . 翻译和解释程序翻译和解释程序(1)(1)翻译和编译程序翻译和编译程序编译编译：如果一个翻译程序的源语言源语言源语言源语言是某种高级语言，其目标语目标语目标语目标语言言言言是相对于某一计算机的汇编语言或机器语言，则称这种翻译程序为编译程序（或称为编译器）。翻译翻译：是指在计算机中放置一

7、个能由计算机直接执行的翻译程序，它以某一种程序设计语言（源语言）所编写的程序（源程序源程序源程序源程序）作为翻译或转换的对象，当计算机执行翻译程序时，就将它转换成与之等价的另一种语言（目标语言）的程序（目标程序目标程序目标程序目标程序）。输入输入输出输出14(2) (2) (2) (2) 编译和解释程序编译和解释程序编译和解释程序编译和解释程序目标目标目标目标程序程序程序程序源源源源程程程程序序序序编编编编译译译译程程程程序序序序初始数据初始数据初始数据初始数据计计计计算算算算结结结结果果果果源程序源程序源程序源程序解解解解释释释释程程程程序序序序初始数据初始数据初始数据初始数据计计计计算算算

8、算结结结结果果果果15解释程序和编译程序的区别解释程序和编译程序的区别解释程序和编译程序的根本区别根本区别：是否生成目标代码16l口译解释程序l笔译编译程序解释程序和编译程序的区别解释程序和编译程序的区别优点：直观易懂，结构简单， 易于实现人机对话。缺点：效率低。解释程序的优缺点解释程序的优缺点17编译程序的分类编译程序的分类诊断型编译程序: 用于帮助程序开发和调试的编译程序。优化型编译程序： 着重于提高目标代码效率的编译程序。交叉型编译程序可变目标型编译程序18编译技术的发展编译技术的发展第一个编译程序出现在20世纪50年代早期，主要是将算术公式翻译成机器代码。20世纪60年代起，出现自编译

9、技术。还在不断发展之中，目前已经形成一套比较成熟的系统化的理论和方法。191.1. 编译过程概述编译过程概述翻译外文资料与编译源程序进行类比20 编译程序的工作过程指从输入源程序开始到输出目标程序为止的整个过程。一般可划分为五个阶段：词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成。 1)词法分析词法分析 词法分析的任务是输入源程序, 对构成源程序的字符串进行扫描和分解，识别出一个个单词符号, 并将识别出的单词用统一长度的标准形式表示。词法分析过程就是将源程序中的字符串字符串变换成单词串单词串的过程。21 在词法分析阶段工作所依循的是语言的词法规则。描述词法规则的有效工具是正

10、规式和有限自动机。int fun() int i,sum; sum=0; for(i=0;i=100;i+) sum+=i; return sum; 关键字：关键字：intint for return for return 标识符：标识符：i sumi sum 常量：常量：0 1000 100 运算符：运算符：= = + += = + += 界限符：界限符：; ( ) ,; ( ) , 222)语法分析语法分析 语法分析的任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（语法范畴），如“短语”、“句子”、 “子句”、“程序段”等。 语法规则通常用上下文无关文法描述。2

11、3int fun() -函数定义语句 int i,sum; -变量定义语句 sum=0; -赋值语句 for(i=0;i=100;i+) - for语句 sum+=i; -赋值语句 return sum; -返回语句243)语义分析与中间代码的产生语义分析与中间代码的产生 这一阶段通常包括两方面的工作：首先对各种语法范畴进行静态语义检查，如果正确则进行另一方面的工作，即进行中间代码的翻译。 该阶段遵循的是语言的语义规则语义规则。 通常使用属性文法描述语义规则。 所谓“中间代码”是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。 中间代码除四元式外，还有三元式、间接三元式、逆波兰记号、

12、树形表示等。254）优化 优化的任务在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高效（省时间和空间）的代码 优化所依循的原则是程序的等价变换规则。其方法有：公共子表达式的提取、循环优化、删除无用代码等。265）目标代码生成 这一阶段的任务：把中间代码（或经优化处理后）变换成特定机器上的低级语言代码。它有赖于硬件系统结构和机器指令含义。 如何充分利用寄存器、合理选择指令以生成尽可能短且有效的目标代码等都与目标机器硬件结构有关。271）编译程序的功能和组织结构表表 处处 理理词法分析器源源程程序序目目标标程程序序错错 误误 处处 理理语法分析器语义分析目标代码生成前 端后 端代码优化器

13、中间代码生成1.3 1.3 编译程序的结构编译程序的结构282）表格与表格管理）表格与表格管理 用于记录源程序的各种信息以及编译过程中的各种状况，以便后续阶段使用。 与编译前三阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表等。 注：在编译过程中，随着源程序的不断被改造，编译的各阶段常常需要不同的表格，编译过程的绝大多数时间是花在查表、造表和更新表格的事务上。在大多数的编译程序中，表格专门由表格管理程序来处理。293）出错处理）出错处理 出错处理程序的任务包括检查错误、报告出错信息、排错、恢复编译工作。错误类型: 语法错误:在词法分析和语法分析阶段检测 出来。 语义错误：一般

14、在语义分析阶段检测。 30编译程序的前端前端： 与源语言有关，而与目标机无关的编译程序编译程序的后端后端： 与目标机有关，而与源语言无关的编译程序遍（趟）遍（趟）：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序。宿主机宿主机：运行编译程序的计算机称为宿主机。目标机目标机：运行编译程序所产生的目标代码的计算机成为目标机。4）相关概念）相关概念311.4 1.4 编译程序与程序设计环境编译程序与程序设计环境 编译程序无疑是实现高级语言的一个最重要的工具。但支持程序设计人员进行程序设计开发通常还需要其它一些工具：如编辑程序、连接程序、调试程序等。编译程序与

15、这些程序设计工具一起构成所谓的程序设计环境。 在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、程序分析等工具直接依赖于编译程序所产生的结果，而其它工具的构造也常常要用到编译的原理、方法和技术。32图1.2 Ada程序设计环境 331.5 1.5 编译程序的生成编译程序的生成1 1 常用的方法（根据语言来分）常用的方法（根据语言来分）1）直接用机器语言编写编译程序2）用汇编语言编写编译程序注：编译程序核心部分常用汇编语言编写3）用高级语言编写编译程序注：这是普遍采用的方法2 2 常用的方法（根据实现途径来分）常用的方法（根据实现途径来分）1）自编译2）编译工具:LEX(词法分析)与YACC(用于自动产生LALR分析表)3）移植（同种语言的编译程序在不同类型的机器之间移植）343移植S为源语言，T为目标语言，I为编译程序实现语言35用L1语言实现L2语言的编译程序36移植：利用A机器上已有的高级语言L编写一个能够 在B机器上运行的高级语言L的编译程序。37 设计和实现一个编译程序，必须精通设计和实现一个编译程序，必须精通:源 语 言目标语言编译方法4 4 编译程序的编译程序的设计实现设计实现385 5 经典的编译程序经典的编译程序Pascal编译程序C编译程序Fortran 编译程序39谢 谢40