编译原理与技术讲义.ppt

1、2020/10/10,编译原理与技术讲义,1,编译原理与技术,2020/10/10,编译原理与技术讲义,2,第一章 引论,什么是编译程序？ 翻译程序、解释程序和汇编程序 编译程序的组成结构 编译程序的生成 相关话题,2020/10/10,编译原理与技术讲义,3,语言翻译过程,算法描述，求某整数n的阶乘fact(n), n0 1 / n = 0 fact(n) = n * fact( n-1 ) / n! = n * (n-1)! 伪语言描述 fact(n) = if n 0 then 1 else n*fact(n-1),2020/10/10,编译原理与技术讲义,4,语言翻译过程,高级程序设计

2、语言描述，（如C语言） int fact( int n ) if (n= 0) return 1; else return ( n*fact(n-1); ,2020/10/10,编译原理与技术讲义,5,语言翻译过程,输入命令 cc foo.c,c 程序 foo.c,Ansi C compiler cc,Object file,Linker/连接程序,a.out/可执行程序,库函数或其它object文件,2020/10/10,编译原理与技术讲义,6,语言翻译过程,a.out/可执行程序,loader/装入程序,计算机,输入数据,计算结果,2020/10/10,编译原理与技术讲义,7,语言翻译过程

3、,为何不设计直接运行高级语言的机器？ 机器本身的指令系统（二进制） 语言本身扩展,2020/10/10,编译原理与技术讲义,8,什么是编译程序？,源程序 S （高级语言）,编译程序 C,目标程序 T （机器语言）,初始数据,计算结果,2020/10/10,编译原理与技术讲义,9,什么是编译程序？,源语言（程序）到目标语言（程序）的映射转换或者翻译过程 系列转换（翻译）过程,源语言S,T1,Tn,目标语言T,中间语言,2020/10/10,编译原理与技术讲义,10,解释程序与汇编程序,均属于翻译程序,2020/10/10,编译原理与技术讲义,11,C函数fact的汇编语言形式,.filefoo.

4、c .text .globl fact .typefact,function fact: pushl%ebp movl%esp, %ebp subl$4, %esp cmpl$0, 8(%ebp) jg.L2 movl$1, -4(%ebp) jmp.L1 .L2: subl$12, %esp movl8(%ebp), %eax decl%eax,pushl%eax callfact addl$16, %esp imull8(%ebp), %eax movl%eax, -4(%ebp) .L1: movl-4(%ebp), %eax leave ret .Lfe1: .sizefact,.Lf

5、e1-fact .identGCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5),2020/10/10,编译原理与技术讲义,12,编译程序的组成结构,词法分析阶段 语法分析阶段 语义分析、中间代码生成 优化阶段 目标代码生成,2020/10/10,编译原理与技术讲义,13,编译程序的组成结构,semantics,parser,scanner,optimizer,code generator,program,前端 front end 与源语言有关,middle end,后端 back end 与目标机相关,2020/10/10,编译原理与技术讲义,1

6、4,编译程序的组成结构,例子，hoo.c： main() float position, initial, rate; position = initial + rate * 60; ,2020/10/10,编译原理与技术讲义,15,编译程序的组成结构,词法分析阶段scanner 字符流 记号流,position = initial + rate * 60 字符流,scanner,id1 = id2 + id3 * 60 记号流,标识符 赋值运算符 标识符 加运算符 标识符 乘运算符 整型常量,2020/10/10,编译原理与技术讲义,16,编译程序的组成结构,语法分析阶段parser 记号流

7、 分析树（语法树）,id1 = id2 + id3 * 60 记号流,parser,=,id1,id2,+,*,id3,60,语法树,2020/10/10,编译原理与技术讲义,17,编译程序的组成结构,语义分析 语义树带有语义信息的分析树（语法树）,id1,id2,+,*,id3,60,=,int float,进行类型转换,2020/10/10,编译原理与技术讲义,18,编译程序的组成结构,中间代码生成 形式多样 三地址码，p-code等 t1 := int_to_float( 60 ) t2 := id3 * t1 t3 := id2 + t2 id1 := t3,2020/10/10,编译

8、原理与技术讲义,19,编译程序的组成结构,代码优化 得到“优化”后的中间代码；也可以在最后的代码生成阶段实施“优化” t1 := rate * 60.0 / 直接用浮点数60.0 position := initial + t1 / 去除多余的 / 临时变量 较优化前，减少2条中间代码,2020/10/10,编译原理与技术讲义,20,编译程序的组成结构,代码生成 与目标机器有密切联系，如指令选择，寄存器的使用等。 movf rate, R1 mulf #60.0, R1 movf initial, R2 addf R2, R1 movf R1, position,2020/10/10,编译原理

9、与技术讲义,21,编译程序的组成结构,符号表管理,编译程序中使用的符号表,2020/10/10,编译原理与技术讲义,22,编译程序的组成结构,出错处理 程序错误分类 出错处理的目标与方法 1) if ( n = 0 return 1; / missing “)” 2) if ( n = 0 ) return 1 / missing “;” else return ( n * fact(n-1) );,2020/10/10,编译原理与技术讲义,23,编译程序的组成结构,semantics,parser,scanner,optimizer,code generator,符号表管理,出错处理,202

10、0/10/10,编译原理与技术讲义,24,编译程序生成,手工编写 耗时，“效率”问题。 自动生成 各个阶段基本上有相应的自动生成工具，如 lex、yacc。 自展（bootstrapping),2020/10/10,编译原理与技术讲义,25,编译程序生成,编译程序的自展/自编译 T型图,源语言S,目标语言T,编译程序的实现语言I,2020/10/10,编译原理与技术讲义,26,编译程序生成,编译程序的自展/自编译 我们的目标是在机器A（目标语言）上，用语言A（实现语言）构造高级语言L（源语言）的编译程序。,2020/10/10,编译原理与技术讲义,27,编译程序生成,编译程序的自展/自编译 S

11、tep1: 我们可以考虑源语言L的子集语言S, S L。在机器A（目标语言）上，用语言A（实现语言）构造语言S的编译程序。,2020/10/10,编译原理与技术讲义,28,编译程序生成,编译程序的自展/自编译 Step2: 在机器A（目标语言）上，用语言S（实现语言）构造语言L的编译程序。,2020/10/10,编译原理与技术讲义,29,编译程序生成,编译程序的自展/自编译 Step3:,2020/10/10,编译原理与技术讲义,30,编译程序生成,编译程序的移植/交叉编译 考虑将A机器上语言L的编译实现移植到机器B上，即我们的目标是：,2020/10/10,编译原理与技术讲义,31,编译程序生成,编译程序的移植/交叉编译 我们已有的编译程序是：,2020/10/10,编译原理与技术讲义,32,编译程序生成,编译程序的移植/交叉编译 Step1:,用语言L编写的语言L到语言B的编译程序,借助已有的A机器上语言L的编译程序,得到机器A上（实现语言）语言L到语言B的编译程序,2020/10/10,编译原理与技术讲义,33,编译程序生成,编译程序的移植/交叉编译 Step2:,用语言L编写的语言L到语言B的编译程序,新的A机器上语言L到语言B的编译程序,得到机器B上（实现语言）语言L到语言B的编译程序,2020/10/10,编译原理与技术讲义,34,编译程序相关的软件,预处理程