编译原理与技术 2018/11/30 《编译原理与技术》讲义

第一章 引论 什么是编译程序？ 翻译程序、解释程序和汇编程序 编译程序的组成结构 编译程序的生成 相关话题 2018/11/30 《编译原理与技术》讲义

语言翻译过程 算法描述，求某整数n的阶乘fact(n), n≥0 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) 2018/11/30 《编译原理与技术》讲义

语言翻译过程 高级程序设计语言描述，（如C语言） int fact( int n ) { if (n<= 0) return 1; else return ( n*fact(n-1)); } 2018/11/30 《编译原理与技术》讲义

语言翻译过程 输入命令 cc foo.c c 程序 foo.c 库函数或其它object文件 Ansi C compiler cc Object file Linker/连接程序 a.out/可执行程序 2018/11/30 《编译原理与技术》讲义

语言翻译过程 a.out/可执行程序 loader/装入程序 输入数据 计算机 计算结果 2018/11/30 《编译原理与技术》讲义

语言翻译过程 为何不设计直接运行高级语言的机器？ 机器本身的指令系统（二进制） 语言本身扩展 2018/11/30 《编译原理与技术》讲义

什么是编译程序？ 源程序 S （高级语言） 编译程序 C 目标程序 T （机器语言） 目标程序 T 运行系统 计算机 初始数据 计算结果 2018/11/30 《编译原理与技术》讲义

什么是编译程序？ 源语言（程序）到目标语言（程序）的映射转换或者翻译过程 系列转换（翻译）过程 源语言S T1 … Tn 目标语言T 中间语言 2018/11/30 《编译原理与技术》讲义

解释程序与汇编程序 均属于翻译程序 源程序 S 初始数据 Interpreter/解释程序 计算结果 汇编程序 S’ 汇编语言 assembler/汇编程序 目标程序 T 2018/11/30 《编译原理与技术》讲义

C函数fact的汇编语言形式 .file "foo.c" .text pushl %eax .globl fact call fact .type fact,@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 movl 8(%ebp), %eax decl %eax pushl %eax call fact addl $16, %esp imull 8(%ebp), %eax movl %eax, -4(%ebp) .L1: movl -4(%ebp), %eax leave ret .Lfe1: .size fact,.Lfe1-fact .ident "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5)" 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 词法分析阶段 语法分析阶段 语义分析、中间代码生成 优化阶段 目标代码生成 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 program 前端 front end 与源语言有关 scanner parser semantics 后端 back end 与目标机相关 middle end optimizer code generator 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 例子，hoo.c： main() { float position, initial, rate; } 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 词法分析阶段－scanner 字符流 －> 记号流 position = initial + rate * 60 字符流 scanner id1 = id2 + id3 * 60 记号流 标识符 赋值运算符 标识符 加运算符 标识符 乘运算符 整型常量 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 语法分析阶段－parser 记号流 －> 分析树（语法树） id1 = id2 + id3 * 60 记号流 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 语义分析 语义树－带有语义信息的分析树（语法树） = id1 + id2 * id3 60 进行类型转换 int  float 60 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 中间代码生成 形式多样 － 三地址码，p-code等 t1 := int_to_float( 60 ) t2 := id3 * t1 t3 := id2 + t2 id1 := t3 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 代码优化 得到“优化”后的中间代码；也可以在最后的代码生成阶段实施“优化” t1 := rate * 60.0 // 直接用浮点数60.0 position := initial + t1 // 去除多余的 // 临时变量 较优化前，减少2条中间代码 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 代码生成 与目标机器有密切联系，如指令选择，寄存器的使用等。 movf rate, R1 mulf #60.0, R1 movf initial, R2 addf R2, R1 movf R1, position 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 符号表管理 名称 类型 … position float initial rate 编译程序中使用的符号表 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 出错处理 程序错误分类 出错处理的目标与方法 1) if ( n <= 0 return 1; // missing “)” 2) if ( n <= 0 ) return 1 // missing “;” else return ( n * fact(n-1) ); 2018/11/30 《编译原理与技术》讲义

编译程序的组成结构 scanner parser 符号表管理 出错处理 semantics optimizer code generator 2018/11/30 《编译原理与技术》讲义

编译程序生成 手工编写 耗时，“效率”问题。 自动生成 各个阶段基本上有相应的自动生成工具，如 lex、yacc。 自展（bootstrapping) 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的自展/自编译 T型图 目标语言T S T 源语言S I 编译程序的实现语言I 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的自展/自编译 我们的目标是在机器A（目标语言）上，用语言A（实现语言）构造高级语言L（源语言）的编译程序。 L A 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的自展/自编译 Step1: 我们可以考虑源语言L的子集语言S, S L。在机器A（目标语言）上，用语言A（实现语言）构造语言S的编译程序。 S A A 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的自展/自编译 Step2: 在机器A（目标语言）上，用语言S（实现语言）构造语言L的编译程序。 L A S 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的自展/自编译 Step3: L A S L A A S A A 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的移植/交叉编译 考虑将A机器上语言L的编译实现移植到机器B上，即我们的目标是： L B B 2018/11/30 《编译原理与技术》讲义

编译程序生成 编译程序的移植/交叉编译 我们已有的编译程序是： L A A 2018/11/30 《编译原理与技术》讲义

得到机器A上（实现语言）语言L到语言B的编译程序 编译程序生成 编译程序的移植/交叉编译 Step1: L B L L B A L A A 得到机器A上（实现语言）语言L到语言B的编译程序 用语言L编写的语言L到语言B的编译程序 借助已有的A机器上语言L的编译程序 2018/11/30 《编译原理与技术》讲义

得到机器B上（实现语言）语言L到语言B的编译程序 编译程序生成 编译程序的移植/交叉编译 Step2: L B L L B B L B A 用语言L编写的语言L到语言B的编译程序 得到机器B上（实现语言）语言L到语言B的编译程序 新的A机器上语言L到语言B的编译程序 2018/11/30 《编译原理与技术》讲义

编译程序相关的软件 预处理程序－preprocessor 汇编程序－assembler 解释程序－interpreter 宏替换－macro 包含文件展开－include files 汇编程序－assembler 两趟扫描 解释程序－interpreter 连接程序－linker 装入程序－loader 重定位 2018/11/30 《编译原理与技术》讲义

编译程序相关的软件 调试程序－debugger 描述程序－profiler cc 编译器中 –g 选项；与-O的关系 性能分析 2018/11/30 《编译原理与技术》讲义