第一章 编译器概述

1、编 译 原 理,夏 斌 ,关于编译原理课程,内容 编译原理是介绍如何将高级程序设计语言变换成计算机硬件所能识别的机器语言，以便计算机进行处理。 介绍编译系统的工作原理 介绍编译系统的构造方法,先行课程：高等数学、 (PASCAL)、离散数学、 汇编语言、数据结构,编译原理课程应用领域 编译器的设计 一般的软件设计,例如： 文本编辑器、信息检索系统、模式识别器 打字程序、绘图系统 优化程序,本课程的地位,是计算机专业的学生必修的一门主干课 是本学科研究生入学考试的课程之一 是软件技术基础,学习方法,1、认真听课，认真理解书中的基本概念、基 本原理与基本算法 2、认真做作业 3、在看书时或理解例题

2、时，一定要画出相应 的细节变化过程，通过画图来加深理解 4、在理解的基础上记忆 5、理论结合实践,编译原理 吕映芝 清华大学出版社,编译原理 技术与工具 人民邮电出版社,Compiler Construction Principle and Pratice 编译原理及实践 Kenneth C.Louden 机械工业出版社,参 考 书 籍 参 考 书 籍,Compilers Principles,Techniques,and Tools 龙书,第一章 引论,本章内容： 什么是编译程序 编译程序各阶段的主要功能,在计算机上如何执行一个高级语言程序？ 把高级语言程序翻译成机器语言程序 运行所得的机器

3、语言程序求得计算结果 翻译器：能够将一种语言转换成另一种语言的软件，而且后者与前者在逻辑上是等价的。 源语言 目标语言,编译 专指由高级语言转换为低级语言 解释 接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。,编译和解释的区别：,特点： 1编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译 2解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。 基本功能：二者相同 所采用的技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。,英译汉与

4、编译的比较,1.识别出句子中的一个个单词 2.分析句子的语法结构 3.分析句子的语义 4.初步翻译 5.译文修饰 6.写出最后译文,1.词法分析 2.语法分析 3.语义分析 4.中间代码生成 5.优化 6.目标代码生成,1.1 词法分析,任务 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。 单词 是高级语言中有实在意义的最小语法单位，它由字符构成。,识别右边程序中的单词 基本字：Void , int , float 标识符: a, b, c, d, x, y, jisuan 常数 : 50 算符 : +,*,= 界限符: ; , ( ),Void jisuan() int

5、 y,c,d; float x,a,b; x=a+b*50; y=（c+d）*(x+b）; ,词法分析依照词法规则，识别出正确的单词，转换成统一规格，备用。 转换 对基本字、运算符、界限符的转换 标识符的转换 常数的转换 转换完成后的格式：（单词种别，单词符号的 属性值） 二元式表示 （单词种别，单词符号的属性值） 描述词法规则的有效工具是正规式和有限自动机。,1.2 语法分析,任务：根据语言的语法规则，把单词流组成各类语法单位，如：短语、句子、过程、程序 语法规则：语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。 语法规则通常用上下文无关文法描述。,表达式的语法特征 任何一个

6、标识符都是表达式； 任何一个数都是表达式； 如果e1和e2都是表达式，那么 e1 + e2 e1 * e2 (e1) 也都是表达式,position := initial + rate * 60;,语法分析有两种方法： 推导(Derive)和规约(Reduce) 语法分析过程也可以用一棵倒着的树来表示，这棵树叫做分析树,赋值语句,标识符 （position）,整数 (60),1.3 语义分析,任务：检查程序的语义正确性，以保证程序各部分能有意义的结合在一起，为以后的代码生成阶段收集类型信息 语义分析阶段的重要工作：类型检查,position := initial + rate * 60;,1.

7、4 中间代码生成,任务：根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。 中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统 中间代码形式 逆波兰式、 四元式、三元式,position := initial + rate * 60;,1.5 代码优化,任务：对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。 原则：等价变换 主要方面：公共子表达式的提取、合并已知量、删除无用语句、循环优化等。,例.,For (k=1;k=100;k+) m=i+10*k; n=j+10*k; ,1.6 目标代码生成,任务：把经过优化的中

8、间代码转化成特定 机器上的低级语言代码 目标代码的形式 绝对指令代码:可立即执行的目标代码。 汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。,temp1 := id3 * 60.0 id1 := id2 * temp1,1.7 符号表管理,表格作用：用来记录源程序的各种信息以及编译过程中的各种状况。 与编译前四阶段有关的表格有： 符号表、常数表、标号表、分程序入口表、中间代码表等。 符号表：用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。,1.8 错误诊断和报告,任务：如果源程序有错误，编译程序应设法发现错误，并报告给用户。 完成：由专门的出错处理程序来完成 错误类型: 语法错误:在词法分析和语法分析阶段检测出来。 语义错误：一般在语义分析阶段检测。,1.9 阶段的分组,编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化 编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成,遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。,