《编译原理与技术》讲义编译原理与技术

1、2022/7/12编译原理与技术讲义 1编译原理与技术2022/7/12编译原理与技术讲义 2第一章 引论什么是编译程序？翻译程序、解释程序和汇编程序编译程序的组成结构编译程序的生成相关话题2022/7/12编译原理与技术讲义 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)2022/7/12编译原理与技术讲义 4语言翻译过程高级程序设计语言描述，（如C语言）int fact( int

2、 n )if (n 记号流 position = initial + rate * 60 字符流scanner id1 = id2 + id3 * 60 记号流 标识符 赋值运算符 标识符 加运算符 标识符 乘运算符 整型常量2022/7/12编译原理与技术讲义 16编译程序的组成结构语法分析阶段parser记号流 分析树（语法树） id1 = id2 + id3 * 60 记号流 parser=id1id2+*id360语法树2022/7/12编译原理与技术讲义 17编译程序的组成结构语义分析语义树带有语义信息的分析树（语法树）id1id2+*id360=int float进行类型转换202

3、2/7/12编译原理与技术讲义 18编译程序的组成结构中间代码生成形式多样 三地址码，p-code等t1 := int_to_float( 60 )t2 := id3 * t1t3 := id2 + t2id1 := t32022/7/12编译原理与技术讲义 19编译程序的组成结构代码优化得到“优化”后的中间代码；也可以在最后的代码生成阶段实施“优化”t1 := rate * 60.0 / 直接用浮点数60.0position := initial + t1 / 去除多余的/ 临时变量较优化前，减少2条中间代码2022/7/12编译原理与技术讲义 20编译程序的组成结构代码生成与目标机器有密切

4、联系，如指令选择，寄存器的使用等。movf rate, R1mulf #60.0, R1movf initial, R2addf R2, R1movf R1, position2022/7/12编译原理与技术讲义 21编译程序的组成结构符号表管理名称类型positionfloatinitialfloatratefloat编译程序中使用的符号表2022/7/12编译原理与技术讲义 22编译程序的组成结构出错处理程序错误分类出错处理的目标与方法1) if ( n = 0 return 1; / missing “)”2) if ( n = 0 ) return 1 / missing “;” el

5、se return ( n * fact(n-1) );2022/7/12编译原理与技术讲义 23编译程序的组成结构semanticsparserscanneroptimizercode generator符号表管理出错处理2022/7/12编译原理与技术讲义 24编译程序生成手工编写耗时，“效率”问题。自动生成 各个阶段基本上有相应的自动生成工具，如 lex、yacc。自展（bootstrapping)2022/7/12编译原理与技术讲义 25编译程序生成编译程序的自展/自编译T型图S T I源语言S目标语言T编译程序的实现语言I2022/7/12编译原理与技术讲义 26编译程序生成编译程序

6、的自展/自编译 我们的目标是在机器A（目标语言）上，用语言A（实现语言）构造高级语言L（源语言）的编译程序。L A A2022/7/12编译原理与技术讲义 27编译程序生成编译程序的自展/自编译 Step1: 我们可以考虑源语言L的子集语言S, S L。在机器A（目标语言）上，用语言A（实现语言）构造语言S的编译程序。S A A2022/7/12编译原理与技术讲义 28编译程序生成编译程序的自展/自编译 Step2: 在机器A（目标语言）上，用语言S（实现语言）构造语言L的编译程序。L A S2022/7/12编译原理与技术讲义 29编译程序生成编译程序的自展/自编译 Step3: L A S

7、S A AL A A2022/7/12编译原理与技术讲义 30编译程序生成编译程序的移植/交叉编译考虑将A机器上语言L的编译实现移植到机器B上，即我们的目标是：L B B2022/7/12编译原理与技术讲义 31编译程序生成编译程序的移植/交叉编译我们已有的编译程序是：L A A2022/7/12编译原理与技术讲义 32编译程序生成编译程序的移植/交叉编译Step1:L B LL A AL B A用语言L编写的语言L到语言B的编译程序借助已有的A机器上语言L的编译程序得到机器A上（实现语言）语言L到语言B的编译程序2022/7/12编译原理与技术讲义 33编译程序生成编译程序的移植/交叉编译Step2:L B LL B AL B B用语言L编写的语言L到语言B的编译程序新的A机器上语言L到语言B的编译程序得到机器B上（实现语言）语言L到语言B的编译程序2022/7/12编译原理与技术讲义 34编译程序相关的软件预处理程序preprocessor宏替换macro包含文件展开include files汇编程序assembler