编译原理刘善梅第1章绪论2

1、编译原理2自我介绍自我介绍n姓名：刘善梅姓名：刘善梅nqq qq ： 3068353030683530n办公室：逸夫楼办公室：逸夫楼c427c427n 邮箱：邮箱： 3课程介绍课程介绍n两门独立的课程：理论（两门独立的课程：理论（4848学时）学时） 实验（实验（1616学时）学时）n考试成绩组成考试成绩组成 理论：理论：平时作业和考勤占平时作业和考勤占20%20%，期末结业，期末结业考试占考试占80%80%； 实验：实验：根据实验报告和程序源代码评分，根据实验报告和程序源代码评分，实验报告占实验报告占40%, 40%, 程序源代码占程序源代码占60%60%。n课程特点：课程特点：难！难！4开

2、课目的：开课目的：介绍设计与构造程序设计语言介绍设计与构造程序设计语言编译程序编译程序的的原理与方法原理与方法源程序源程序编译编译程序程序目标程序目标程序连接连接可执行程序可执行程序预备知识：预备知识：形式语言与自动机、形式语言与自动机、两门以上的高两门以上的高级程序设计语级程序设计语言言汇编语言汇编语言数据结构等数据结构等how?5教学要求教学要求 通过课程的学习和实验的完成，通过课程的学习和实验的完成， 应该应该清楚的理解一个编译程序是如何工作的；清楚的理解一个编译程序是如何工作的； 如果在以后遇到了任何一个程序设计语言，如果在以后遇到了任何一个程序设计语言，应该应该知道如何实现这个语言的

3、多数机制；知道如何实现这个语言的多数机制； 应应具有一定的使用编译构造工具开发编译程序的具有一定的使用编译构造工具开发编译程序的经验；经验； 会会将所学的常用技术和算法应用于类似的软件的将所学的常用技术和算法应用于类似的软件的设计和实现中。设计和实现中。理论课内容简介：理论课内容简介：第一章：绪论 第二章：编译基础(形式语言 、有穷自动机等）第三章：词法分析 第四章：语法分析第五章：语法制导翻译和中间代码生成第七章：程序运行时的存贮分配问题第八章：代码优化第九章：目标代码生成 第六章：符号表实验课内容简介：实验课内容简介：第一次课：词法分析 （4学时）第二次课：语法分析 （4学时）第三次课：词

4、义分析、代码生成 （4学时）第四次课：小型c语言编译器设计（4学时）详细实验内容请见实验要求和实验指导书8教材：教材：编译原理编译原理（第（第2版），张素琴、吕映芝、蒋维杜、戴桂版），张素琴、吕映芝、蒋维杜、戴桂 兰，清华大学出版社兰，清华大学出版社 2004参考书：参考书：教材及主要参考书教材及主要参考书 compilers: principles, technigues, and tools alfred v.aho, ravi sethi, jeffrey d.ullman, addison-wesley,1986. 译著版：机械工业出版社，译著版：机械工业出版社，2003，李建中，姜守

5、旭译。，李建中，姜守旭译。(龙书）龙书） 中文名：编译原理技术和工具中文名：编译原理技术和工具 modern compiler implementation in java modern compiler implementation in c andrew w.appel，人民邮电出版社影印，人民邮电出版社影印，2005 （虎书）（虎书） 中文名：现代编译原理中文名：现代编译原理 advanced compiler design and implementation steven s. muchnick, 1997. 机械工业出版社影印机械工业出版社影印，2003 （鲸书）（鲸书） 中文名：

6、高级编译器设计与实现中文名：高级编译器设计与实现内地内地 陈火旺（国防科大版）陈火旺（国防科大版） 陈意云（中国科技大学版）陈意云（中国科技大学版） 王生原等（人民邮电版）王生原等（人民邮电版） 王生原等（清华大学第三版）王生原等（清华大学第三版） 主要参考书主要参考书10第一章绪论第一章绪论n编译器就是一个编译器就是一个程序程序，它，它读入读入用某种语言用某种语言编写的源程序，并编写的源程序，并翻译翻译成一个成一个与之等价与之等价的的另一种语言编写的源程序。另一种语言编写的源程序。编译器编译器源程序源程序目标程序目标程序错误信息错误信息fortran、pascal、java、 c .另一种程

7、序另一种程序设计语言、设计语言、汇编语汇编语言、机言、机器语言器语言1.1什么是编译程序什么是编译程序什么是编译程序什么是编译程序 编译程序编译程序通常通常是是从较高级语言的程序翻译从较高级语言的程序翻译 至较低级语言的程序至较低级语言的程序，如，如c 代码汇编代码a c compilerc+ 代码汇编代码a c+ compilerc+ 代码c代码another c+ compilerjava 代码bytecode代码a java compiler121.2编译过程概述编译过程概述编译程序的工作，从输入源程序开始，到输出目编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻

8、译有很多相似之处。标程序结束，与自然语言之间的翻译有很多相似之处。 一段英文翻译成中文，一段英文翻译成中文，需经下列步骤：需经下列步骤：识别出句子中的单词识别出句子中的单词分析句子的语法结构分析句子的语法结构根据句子的含义进行初步分析根据句子的含义进行初步分析对译文进行修饰对译文进行修饰写出最后的译文写出最后的译文编译程序编译程序词法分析词法分析代码优化代码优化语法分析语法分析语义分析及中语义分析及中间代码生成间代码生成目标代码生成目标代码生成构成编译程构成编译程序各个阶段序各个阶段i am a teacher.13编译器的各个阶段：编译器的各个阶段：编译器是分编译器是分阶段执行的。阶段执行的

9、。每个阶段将源程每个阶段将源程序从一种表示转序从一种表示转换成另一种表示换成另一种表示源程序源程序词法分析器词法分析器错错误误处处理理器器符符号号管管理理表表语法分析器语法分析器语义分析器语义分析器中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器编译的各编译的各个阶段个阶段14各分析阶段各分析阶段随着编译器各个阶段的进展，源程序的内部表示不随着编译器各个阶段的进展，源程序的内部表示不断地发生变化。断地发生变化。以以a=b+c *d为例为例1。词法分析。词法分析读入源程序读入源程序完成的任务：完成的任务：识别出单词：识别出单词： a、=、b、+、c 、 *、 d并用记号方式表

10、示识别出的单词并用记号方式表示识别出的单词关键字、标识关键字、标识符、常数、算符、常数、算符和界符符和界符例：例：25表示表示a、b、c、d；36：；：；2：；：；31：*记号表示逻辑记号表示逻辑上相关的字符上相关的字符序列，常用整序列，常用整数来表示数来表示上述单词表示为：上述单词表示为：(25,a),(36,=),(25,b),(32,+),(25,c),(31,*),(25,d)n程序文本程序文本if x = y then z := 1 else z := 2; 经词法分析，变成一个个单词经词法分析，变成一个个单词nif, x, =, y, then, z, :=, 1, else, z

11、, :=, 2, ;n语言的单词符号是由语言的单词符号是由词法规则词法规则所确定的。所确定的。词法词法规则规则规定了字母表中哪样的字符串是一个单词规定了字母表中哪样的字符串是一个单词符号。符号。又例，又例， 从左至右扫描字符流的源程序从左至右扫描字符流的源程序、分解构成源、分解构成源程序的字符串，程序的字符串，识别出识别出(拼拼)一个个的一个个的单词单词（符号）（符号） 单词符号是语言中具有独立意义的最基本单词符号是语言中具有独立意义的最基本结构。多数程序语言中，结构。多数程序语言中，单词单词符号一般符号一般包括包括 各类型的各类型的常数、保留字、标识符常数、保留字、标识符、运算符、界符、运算

12、符、界符等等。等等。 词法分析词法分析第一步识别单词第一步识别单词position := initial + rate * 60;单词类型单词类型单词值单词值 标识符标识符1(id1) position 算符算符(赋值赋值) := 标识符标识符2(id2) initial 算符算符(加加) + 标识符标识符3(id3) rate 算符算符(乘乘) * 整数整数 60 分号分号 ；词法分析词法分析18语法分析语法分析在词法分析的基础上，根据语言的语法规则，在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位把单词符号串组成各类语法单位.具体的说，语法分析是在单词流的基础上建立具体

13、的说，语法分析是在单词流的基础上建立一个层次结构一个层次结构-建立语法树建立语法树赋值语句赋值语句标识符标识符=表达式表达式 id1表达式表达式标识符标识符 id2 +表达式表达式表达式表达式*标识符标识符 id3表达式表达式 整数整数 60语法分析语法分析 举例举例id1 := id2 + id3 * 60 ;（pascal）语法规则）语法规则 :=“:=” :=“+” :=“*” :=“(”“)” := := := 赋值语句赋值语句标识符标识符表达式表达式表达式表达式+表达式表达式表达式表达式标识符标识符整数整数标识符标识符:=表达式表达式*id1:=id2+id3*60:=+60*id1

14、id2id322语义分析阶段语义分析阶段语义分析利用语法分析阶段确定的层次结构来识别语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息表达式和语句中的操作信息及类型信息= + a b*c dtemp1=c*dtemp2=b+temp1 temp1 temp2a=temp2语义分析语义分析n 句子的结构理解了，句子的结构理解了，扑捉它的扑捉它的“含义含义” 如：杰克说杰瑞把他的作业落在了家里。如：杰克说杰瑞把他的作业落在了家里。 “他的他的”是谁的？是谁的？ 又：杰克说杰克把他的作业落在了家里。又：杰克说杰克把他的作业落在了家里。 几个杰克？几个杰克？n杰克把她的作业

15、落在了家里。杰克把她的作业落在了家里。（杰克是男生）（杰克是男生）“杰克杰克”和和“她的她的”不一致。不一致。 “杰克杰克”和和“他的他的”才匹配才匹配语义分析语义分析25中间代码生成阶段中间代码生成阶段本阶段将产生源程序的一个显式中间表示本阶段将产生源程序的一个显式中间表示这种中间表示可以看成是某种抽象的程这种中间表示可以看成是某种抽象的程序，通常是与平台无关的序，通常是与平台无关的其重要性质：其重要性质：1.易于产生易于产生2.易于翻译成目标程序易于翻译成目标程序下面是用下面是用三地址码三地址码（四元式）（四元式）表示的例子：表示的例子：temp1=c*dtemp2=b+temp1a=te

16、mp2（* , c , d , tempt1) (+ , b, tempt1 , tempt2) (= , tempt2 , , a)id1:= id2 + id3 * 60(1)(inttoreal, 60, ,t1)(2)(*,id3,t1,t2)(3)(+,id2,t2,t3)(4)(:=,t3,id1)27代码优化阶段代码优化阶段对代码进行变换对代码进行变换以使得编译产生的目标代码更高效以使得编译产生的目标代码更高效（执行速度更快）（执行速度更快）。对上面中间代码进行优化处理后，产生如对上面中间代码进行优化处理后，产生如下的代码：下的代码：temp1=c*da=b+temp1temp1

17、=c*dtemp2=b+temp1a=temp2如下程序 语法分析结果j = 2 * i + 1;if (j = n) j = 2 * i + 3;return aj;t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto l0t4 = 2 * it5 = t4 + 3j = t5l0: t6 = ajreturn t6t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto l0t4 = 2 * it5 = t4 + 3j = t5l0: t6 = ajreturn t6t1 = 2 * ij = t1 + 1t3 = j

18、 nif t3 goto l0 j = t1 + 3l0: t6 = ajreturn t6代码优化代码优化代码优化代码优化id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3 t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360.0 t1) ( 2）（）（ + id2 t1id1)31代码生成阶段代码生成阶段生成目标机机器代码或汇编代码生成目标机机器代码或汇编代码(*,id360.0 t1)(+,id2t1id1)movf id3,r2mulf #60.0,r2movf id2,r1addf r2

19、,r1movf r1,id1nexample: a in r0, i in r1, n in r2t1 = 2 * ij = t1 + 1t3 = j nif t3 goto l0 j = t1 + 3l0: t6 = ajreturn t6sll r1, 1, r1add r1, 1, jcmp j,r2blt .ll3add r1, 3, j.ll3: ld r0+j, rt retr代码生成代码生成n记录记录源程序中使用的源程序中使用的标识符标识符n收集收集每个标识符的各种每个标识符的各种属性信息属性信息n普通变量：普通变量：类型、作用域、分配存储信息类型、作用域、分配存储信息n函数或过

20、程：函数或过程：参数个数、类型、传递方法参数个数、类型、传递方法 返回值类型返回值类型符号表管理符号表管理(登录，查找）登录，查找）1.3 符号表符号表34符号表管理符号表管理int a,b;float e,fchar ch1,ch2;为什么要先说明为什么要先说明? 定义了变量的类型，也就规定了变量定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的在内存中的存放形式，在其上所能进行的运算运算解决符号地址到存贮地址上的映射解决符号地址到存贮地址上的映射35编译器的一个基本功能是编译器的一个基本功能是记录源程序中使用记录源程序中使用的标识符的标识符并将它们并将它们记载到符号表中记

21、载到符号表中。符号表是一个数据结构。符号表是一个数据结构。 每个标识符在符号表中都有每个标识符在符号表中都有一条记录一条记录名字名字记号记号类型类型种属种属 addrid1(25)id2(25) b a例：例：int a,b;int简变简变 0 4 并并收集与每个标识符相关的各种属收集与每个标识符相关的各种属性信息，性信息，int简变简变36在编译的各个阶段都会发现源程序中的错误，在编译的各个阶段都会发现源程序中的错误，1.4错误检测与报告错误检测与报告为了使编译器能继续运行，以检测出源程序中为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后，必须以合适的方式更多的错误，在检测

22、到错误后，必须以合适的方式进行错误处理。进行错误处理。error37小结：小结：编译器编译器的各个的各个阶段阶段源程序源程序词法分析器词法分析器错错误误处处理理器器符符号号管管理理表表语法分析器语法分析器语义分析器语义分析器中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器38编译的前端和后端编译的前端和后端 前端包括词法分析、语法分析、语前端包括词法分析、语法分析、语义分析，以及相关的错误处理和符号表义分析，以及相关的错误处理和符号表的建立的建立 前端依赖于源程序并在很大程度上前端依赖于源程序并在很大程度上独立于目标机器。独立于目标机器。39 后端主要包括代码优化、代码生成

23、和相后端主要包括代码优化、代码生成和相关错误处理。关错误处理。 后端依赖于目标机器。后端依赖于目标机器。 后端处理对象是由前端产生的结果，即中后端处理对象是由前端产生的结果，即中间代码间代码 前端生成与平台无关的字节码前端生成与平台无关的字节码 后端是由与平台有关的解释器对所生成后端是由与平台有关的解释器对所生成的字节码文件进行解释执行的字节码文件进行解释执行java语言的编译采用的是前端后端方式。语言的编译采用的是前端后端方式。编译程序的组织编译程序的组织 编译程序的遍编译程序的遍（passes / phases）- 对一种代码形式从头到尾扫描一遍对一种代码形式从头到尾扫描一遍- 将一个代码

24、空间变换到另一个代码空间将一个代码空间变换到另一个代码空间- 代码空间代码空间 = 代码代码 + 符号表符号表 + 其他有用信息其他有用信息 编译程序的组织取决于各遍的组织编译程序的组织取决于各遍的组织- 单遍单遍编译程序，编译程序，多遍多遍编译程序编译程序- 多个遍之间有逻辑上的先后关系多个遍之间有逻辑上的先后关系- 多个遍的实现可采用顺序结构或并发结构多个遍的实现可采用顺序结构或并发结构 （后者不常用）（后者不常用）编译程序的组织编译程序的组织 例：一个以语法、语义分析程序为中心的例：一个以语法、语义分析程序为中心的 单遍编译程序单遍编译程序组织组织source programtarget

25、 program语法、语义语法、语义分析程序分析程序词法分词法分析程序析程序代码生代码生成程序成程序编译程序的伙伴程序编译程序的伙伴程序 解释程序解释程序（interpreter）- 不产生目标程序文件不产生目标程序文件- 不区别翻译阶段和执行阶段不区别翻译阶段和执行阶段- 翻译源程序的每条语句后直接执行翻译源程序的每条语句后直接执行- 程序执行期间一直有解释程序守候程序执行期间一直有解释程序守候- 常用于实现虚拟机常用于实现虚拟机 比较比较编译程序和解释程序编译程序和解释程序源程序源程序编译程序编译程序目标程序目标程序输入输入目标程序目标程序输出输出解释程序解释程序输出输出输入输入源程序源程序 预处理程序预处理程序（preprocessor）- 支持宏定义支持宏定义（macro definition） 如c源程序中 #define 行的处理- 支持文件包含支持文件包含（file inclusion） 如c源程序中 #include 行的处理- 支持其他更复杂的源程序扩展信息支持其他更复杂