1、本章内容,一. 什么叫编译程序 二. 编译过程概述 三. 编译程序的结构 四. 编译程序生成 五. 课程学习指导,1 引论,一. 什么叫编译程序,编译程序是系统软件中资格最老的成员之一,编译理论和技术近30年来发展十分迅速、成熟,1.编译程序历史,现已形成一套较为系统化的编译理论和技术,一. 什么叫编译程序,2.编译理论与其他课程关系,编译理论,自动机和形式语言,离散数学,数据结构,操作系统,素材,基础,控制对象,一. 什么叫编译程序,编译理论 的许多想法和技术可用于一般软件的设计：,3.编译理论的应用,一. 什么叫编译程序,翻译程序（Translator）是一种程序，其输入是某种语言的一系列
2、语句，而其输出则是另一种语言的一系列语句。,4.翻译程序,源语言程序,目标语言程序,Translator,输入,输出,一. 什么叫编译程序,编译程序（Compiler）是一种程序。它把用高级语言写的源程序作为数据接收，经过翻译转换，产生面向机器的代码作为输出。这当中代码还可能要由汇编程序或装配程序作进一步加工，得出目标程序，交给计算机执行。,5.编译程序,高级语言源程序,面向机器代码,Compiler,目标程序代码,汇编 装配,一. 什么叫编译程序,6.翻译与编译比较,源语言程序,目标语言程序,转变为,高级语言源程序,面向机器代码,编译为,这种变换程序称为翻译程序,编译程序 有一些限制 （针对
3、输入、输出）,这种变换程序称为编译程序,二. 编译过程概述,1.编译过程的组成,编译过程,词法分析,语法分析,中间代码生成,代码优化,目标代码生成,源程序,单词符号,中间代码,语法单位,目标代码,中间代码（优化后）,源程序,目标代码,二. 编译过程概述,2.词法分析,任务,所做转换,依据,构词规则,主要理论基础,自动机理论,源程序字符串,单词符号,输入源程序；扫描、分解字符串，识别出一个个单词（定义符、标识符、运算符、界符、常数）,二. 编译过程概述,2.词法分析,示例,FOR K := 1 TO 100 M := I + 10 * K N := J + 10 * KNEXT K,TO,NEX
4、T,FOR,K,N,M,I,J,K,K,K,:=,100,:=,:=,1,10,10,+,*,*,+,定义符,标识符,分界符,运算符,常数,二. 编译过程概述,3.语法分析,任务,所做转换,依据,语法规则,主要理论基础,上下文无关文法,单词符号,语法单位（语法范畴）,在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。,二. 编译过程概述,3.语法分析,示例,TO,NEXT,FOR,K,N,M,I,J,K,K,K,:=,100,:=,:=,1,10,10,+,*,*,+,变量、常数及其运算结果均是表达式,表达式,
5、表达式,表达式,表达式,表达式,表达式,赋值句的形式为“变量：表达式”,赋值句,赋值句,多个赋值句可构成语句块,语句块,表达式可作为循环的初值和终值,初值,终值,简单数值变量可作为循环的控制变量,控制变量,控制变量,此时可以看出上述结果符合循环语句的语法定义，故语法分析成功完成,二. 编译过程概述,4.中间代码生成,任务,所做转换,依据,语义规则,主要理论基础,属性文法,语法范畴,中间代码,对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。,二. 编译过程概述,4.中间代码生成,示例,TO,NEXT,FOR,K,N,M,I,J,K,K,K,:=,100,:=,:=,
6、1,10,10,+,*,*,+,(1) ( :=, 1, , K ),(2) ( j,100, K, ),(3) ( *, 10, K, T1 ),(8) ( j, , , (2),(7) ( +, K, 1, K ),(4) ( +, I, T1, M ),(9) ( ),(9),(5) ( *, 10, K, T2 ),(6) ( +, J, T2, N ),T1,T2,(1) K := 1,(2) if 100K goto (9),(3) T1 := 10 * K,(8) goto (2),(7) K := K + 1,(4) M := I + T1,(9),(5) T2 := 10 *
7、 K,(6) N := J + T2,循环语句,出口语句,循环块,STEP 1,生成四元式,将四元式重写为另一种形式的中间代码,(1) ( :=, 1, , K ),(2) ( j,100, K, (9),(3) ( *, 10, K, T1 ),(8) ( j, , , (2),(7) ( +, K, 1, K ),(4) ( +, I, T1, M ),(9) ( ),(5) ( *, 10, K, T2 ),(6) ( +, J, T2, N ),循环语句和出口语句 彼此相连地被定义,包括循环语句开始到有同一控制变量的第一个出口语句的那些语句的自然序列称为一循环块,块嵌套不可交叉，嵌套块
8、控制变量不可同名,不正确,正确嵌套,缺省的 STEP = STEP 1,二. 编译过程概述,5.代码优化,任务,所做转换,依据,程序等价变换规则,主要理论基础,数据流方程,中间代码,中间代码（优化后）,对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码。,二. 编译过程概述,5.代码优化,示例,(1) K := 1,(2) if 100K goto (9),(3) T1 := 10 * K,(8) goto (2),(7) K := K + 1,(4) M := I + T1,(9),(5) T2 := 10 * K,(6) N := J + T2,(3)
9、K := 1,(4) if 100K goto (9),(8) goto (4),(7) K := K + 1,(9),(3) T1 := 10 * K,(4) M := I + T1,(1) M := I,(5) M := M + 10,(5) T2 := 10 * K,(6) N := J + T2,(2) N := J,(6) N := N + 10,(1) K := 1,(2) if 100K goto (9),(8) goto (2),(7) K := K + 1,(9),二. 编译过程概述,6.目标代码生成,任务,所做转换,依据,硬件体系结构、指令系统,中间代码,目标代码,将中间代
10、码变换成特定机器上的低级语言代码,目标代码形式,绝对指令、可重定位指令、汇编指令,二. 编译过程概述,6.目标代码生成,LD R1, I,L2: ST R1, M,LD R2, J,ST R2, N,LD R0, 1,L1: CMP 100, R0,J L2,ADD R1, 10,ADD R2, 10,ADD R0, 1,J L1,示例,(8) goto (4),(7) K := K + 1,(1) M := I,(9),(6) N := N + 10,(3) K := 1,(2) N := J,(5) M := M + 10,(4) if 100K goto (9),(9),(8) goto
11、 (4),(7) K := K + 1,(1) M := I,(6) N := N + 10,(3) K := 1,(2) N := J,(4) if 100K goto (9),(5) M := M + 10,三.编译程序 的结构,1.编译程序总框,表格管理,词法分析,语法分析,中间代码生成,代码优化,目标代码生成,源程序,单词符号,中间代码,语法单位,目标代码,中间代码,出错处理,三. 编译程序的结构,2.表格与表格管理,编译各阶段均须维持表格并进行表格管理,建表的技术支持是数据结构,表格的分类、结构、处理方法决定于语言及机器，还有优化措施,三. 编译程序的结构,2.表格与表格管理,编译程
12、序涉及的表格有：,符号名表,常量名、变量名、数组名、过程名、 性质、 引用、定义,常数表,标号表,入口名表,过程引用表,各种类型常数的值,标号的定义和引用情况,过程的入口名和入口位置,外部过程的名字、引用位置,循环表,等价名表,公用链表,格式表,中间代码表,三. 编译程序的结构,3.出错处理,一个好的编译程序应该：,全 最大限度发现错误,准 准确指出错误的性质和发生地点,局部化 将错误的影响限制在尽可能小的范围内,若能自动校正错误则更好，但其代价非常高,三. 编译程序的结构,3.出错处理,源程序中的错误通常分为 ：,语法错误 不符合语法（或词法）规则的错误,语义错误 不符合语义规则的错误,单词
13、拼写错误、括号不匹配 .,说明错误、作用域错误、类型不匹配 .,三.编译程序 的结构,4.遍,遍 是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。,词法分析,语法分析,中间代码生成,代码优化,目标代码生成,一遍语法分析器处于核心地位,一遍 局部优化,一遍,一遍 全局优化,三. 编译程序的结构,5.编译前端与后端,词法分析,语法分析,中间代码生成,代码优化,目标代码生成,编译前端主要由与源语言有关但与目标机无关的那些部分组成,编译后端包括编译程序中与目标机有关的那些部分,四. 编译程序生成,以往 编译程序的构造大多采用机器语言或汇编语言,现在 编译程
14、序的构造越来越多采用高级语言,1.编译程序的构造工具,有时为了充分发挥效率或满足不同需求，仍然采用 机器语言或汇编语言构造编译程序（或其核心部分）,四. 编译程序生成,2. T型图,S表示源语言,T表示目标语言,I表示编译程序的实现语言,四. 编译程序生成,3. 用高级语言L1构造编译程序,已有用A机器代码实现的高级语言L1的编译程序,可用高级语言L1编写另一个高级语言L2的编译程序,将写好的语言L2的编译程序用L1的编译程序编译后就可得到用A机器代码实现的L2编译程序,四. 编译程序生成,4. 编译程序的移植,已有A机器上的高级 语言L编译程序（1）,用L编写能在B机器上运行的L的编译程序（
15、2）,将(2)用(1)编译，得到A机器上运行的产生B代码的L的编译程序（3）,再将(2)用(3)编译，即可得到B机器上运行的产生B代码的L的编译程序（4）,至此，将A机器上的L的编译程序(1)移植为B机器上的L的编译程序（4）,四. 编译程序生成,5. 自编译方式,先对语言的核心部分构造一个小小的编译程序（可用低级语言实现）,再以它为工具构造能编译更多语言成分的较大编译程序,如此不断扩展，最后形成整个编译程序（滚雪球）,四. 编译程序生成,6. 构造工具,构造编译程序的工具称为编译程序-编译程序、编译程序产生器或翻译程序书写系统,自动产生扫描器 LEX FLEX,自动产生语法分析器 YACC
16、BISON,五. 课程学习指导,原理课程：基础性、科学性、普适性,优点：揭示科学本质、长期受用的知识,缺点：抽象，连贯性差，学时矛盾大,1. 课程性质,五. 课程学习指导,2. 学习目的,加深理解计算概念，提高素质,为主流语言写编译器,写专业编译器机会很多,为应用提供思路、技术,五. 课程学习指导,3. 如何学好,学好“四大原理”课程，是计算机专业学生必要条件,上课：准时到，认真听，注意记,课后：认真完成作业、实验,方法：编译是个大系统，要反复琢磨进国家级精品课程网站，获取更多信息,程序设计语言 编译原理（第二版） 陈火旺等 国防工业出版社 第0章,编译原理和技术（第二版） 陈意云 中国科学技术大学出版社 第1章,参考文献,Compilers :principles, techniques, and tools（2001）, Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. 第1章 第2章,参考文献,Crafting a Compiler with C（1991）, Charles N. Fischer, Richard J. LeBlanc Jr. 第1章 第2章,现代编译程序设计 冯博琴等译 第1章,
