研究生院第一

1、1编译程序高级教程编译程序高级教程Compilers: An Advanced Course冯晓兵冯晓兵E-mail: 中国科学院计算技术研究所中国科学院计算技术研究所计算机体系结构国家重点实验室计算机体系结构国家重点实验室编译与编程实验室编译与编程实验室2 复杂的系统工程复杂的系统工程：现代高性能并行计算机在体系设计中采用了多层次并行、多级分布存储等复杂结构，加大了开发高质量并行软件的难度。影响先进计算机性能的三个主要因素是：算法、编译程序和硬件体系结构，必须体系结构、硬件、系统软件/编程环境及算法、应用等领域有机结合、合理分配复杂性,才能获得高计算性能。 3 课程内容课程内容：本课程介绍了

2、编译程序的基本构造原理和基本实现技术，主要内容包括形式语言基础知识、词法分析、语法分析及语法制导翻译、流分析、程序优化、代码生成等编译理论和技术。课程目标课程目标：现代芯片体系结构的设计和适应这种体系结构的高性能编译程序的设计，在过去20年里，都取得了巨大的进展，但是还存在大量挑战性问题。本课程将介绍当代编译系统普遍使用的成熟技术，并简要介绍部分当前的研究热点问题。促进算法、编译程序和体系结构领域研究人员的沟通与合作，使大家具备从事研发工作的高级编译专业基础。 4参考书：1.主要参考书： Alfred V. Aho, Ravi Sethi, Jeffery D. Ullman, Compile

3、rs Principles, Techniques and Tools, Addison-Wesley, 19852.参考书：1)陈火旺等：程序设计语言编译原理（第三版），国防工业出版社，2000年2)吕映芝、张素琴、蒋维杜：编译原理；清华大学出版社 19983)杜淑敏、王永宁：编译程序设计原理；北京大学出版社 19864)陈意云编著：编译原理和技术（第二版，中国科学技术大学出版社，1997）5)张幸儿：计算机编译原理，科学出版社，1999年5考核方式：1.习题2.课堂开卷考试6第第1 1章章 编译概论编译概论编译的概念编译的概念编译的阶段编译的阶段编译程序的结构编译程序的结构与编译相关的程序

4、与编译相关的程序自举和移植自举和移植7编译的概念（编译的概念（1 1）编译：从面向人的编译：从面向人的源语言源语言表示的算法到面向硬表示的算法到面向硬件的件的目标语言目标语言表示的算法的一个表示的算法的一个等价变换等价变换等价变换：是指功能的等价性等价变换：是指功能的等价性一般程序设计语言的定义包括以下三个方面：一般程序设计语言的定义包括以下三个方面：v语法：指程序的构造规则，目前已较好地形式化语法：指程序的构造规则，目前已较好地形式化v语义：指按语法规则构成的各个语法成分的含义语义：指按语法规则构成的各个语法成分的含义，作了一些形式化的探索，作了一些形式化的探索v语用：表示程序与使用者间的关

5、系，语用：表示程序与使用者间的关系，一般地，变换要求满足程序的语义的等价性一般地，变换要求满足程序的语义的等价性8编译的概念（编译的概念（2 2）通常通常源语言编写的程序是编译器的输入，用户用于编源语言编写的程序是编译器的输入，用户用于编程的通常是某种高级语言，如程的通常是某种高级语言，如C C、FortranFortran等等目标语言是指目标计算机的目标代码，有时也称目标语言是指目标计算机的目标代码，有时也称为机器代码，编译器的输出是目标语言的程序为机器代码，编译器的输出是目标语言的程序但随着编译应用的发展，编译器的输出也可以但随着编译应用的发展，编译器的输出也可以是高级语言的程序（如串行程

6、序的并行编译），是高级语言的程序（如串行程序的并行编译），而编译器的输入也可以是某种机器代码（如二进而编译器的输入也可以是某种机器代码（如二进制翻译、动态优化器等）制翻译、动态优化器等）编译只是一个对程序进行静态优化的过程吗？编译只是一个对程序进行静态优化的过程吗？编译不仅可以在静态时刻完成，也可以在动态时编译不仅可以在静态时刻完成，也可以在动态时刻进行，甚至可以实行动静态信息的交互刻进行，甚至可以实行动静态信息的交互编译器处理的语言以及编译器的实现语言对编编译器处理的语言以及编译器的实现语言对编译器有重要的影响译器有重要的影响9编译的阶段（编译的阶段（1 1）人进行进行汉英翻译的过程：信、达

7、、雅的翻人进行进行汉英翻译的过程：信、达、雅的翻译目标译目标识别句子中的一个个单词识别句子中的一个个单词分析句子的语法结构分析句子的语法结构根据语义进行初步翻译根据语义进行初步翻译对译文进行修饰对译文进行修饰写出最后的译文写出最后的译文10一个中英翻译的例子一个中英翻译的例子If you do not leave me, I will stand by your side until the life ends.你如果不离开我，我就和你同归于尽。你如果不离开我，我就和你同归于尽。 （四级水平）（四级水平） 你若不离不弃，我必生死相依。你若不离不弃，我必生死相依。 （六级水平）（六级水平） 问世

8、间情为何物？直教人生死相许。问世间情为何物？直教人生死相许。 （八级水平）（八级水平） 山无棱，天地合，乃敢与君绝。山无棱，天地合，乃敢与君绝。 （专家水平）（专家水平） 你在或不在，爱就在那里，不增不减。你在或不在，爱就在那里，不增不减。 （圣者水平）（圣者水平） 11编译的阶段（编译的阶段（2 2）编译是一个类似的过程，一般一个编译器不仅编译是一个类似的过程，一般一个编译器不仅要将源程序翻译为等价的可以执行的目标程序要将源程序翻译为等价的可以执行的目标程序，还要对程序进行优化。因此一个编译器包括，还要对程序进行优化。因此一个编译器包括以下几个阶段：以下几个阶段：词法分析程序（词法分析程序（

9、scanner）：）：将源程序的字符流将源程序的字符流组成记号流组成记号流记号表示逻辑上有内聚力的字符序列记号表示逻辑上有内聚力的字符序列形成记号的字符序列称为该记号的单词形成记号的字符序列称为该记号的单词赋值语句：赋值语句：a index = 4 + 2词法分析后形成词法分析后形成8个单词：标识符个单词：标识符a、左括号左括号、标、标识符识符index、右括号右括号、赋值号、赋值号=、数字、数字4、加号、加号+、数字数字2词法分析同时完成一些可行的操作，如填符号表词法分析同时完成一些可行的操作，如填符号表12编译的阶段（编译的阶段（3 3）语法分析程序（语法分析程序（parser）：）：语法

10、分析语法分析syntax analysis将记号流按语言的语法结构层次分组，得到语法将记号流按语言的语法结构层次分组，得到语法短语短语语法分析得到分析树或语法树语法分析得到分析树或语法树分析树：内部节点由其表示的结构名标出，而叶分析树：内部节点由其表示的结构名标出，而叶子节点表示输入的记号流子节点表示输入的记号流13编译的阶段（编译的阶段（4 4）赋值语句表达式表达式=下标表达式加法表达式表达式表达式表达式+表达式标标识识符符a标标识识符符index数数字字4数数字字214编译的阶段（编译的阶段（5 5）语法树：是分析树中所含信息的浓缩，也可以称语法树：是分析树中所含信息的浓缩，也可以称为抽象

11、语法树（为抽象语法树（AST），），算符作为内部节点出现算符作为内部节点出现赋值语句下标表达式加法表达式标标识识符符a标标识识符符index数数字字4数数字字215编译的阶段（编译的阶段（6 6）语义分析程序（语义分析程序（semantic analyzer）：）：检查程序检查程序的语义正确性的语义正确性程序的语义决定了程序的运行程序的语义决定了程序的运行程序设计语言中存在在执行前可以确定而不易被程序设计语言中存在在执行前可以确定而不易被语法表示的特征，这些特征称为静态语义，这也语法表示的特征，这些特征称为静态语义，这也是语义分析的内容是语义分析的内容一般，典型的静态语义包括声明和类型检查等一

12、般，典型的静态语义包括声明和类型检查等由语义分析程序计算得到的额外信息（如数据类由语义分析程序计算得到的额外信息（如数据类型）等作为属性（型）等作为属性（attribute），），填加到填加到AST中中16编译的阶段（编译的阶段（7 7）赋值语句下标表达式整形加法表达式整形标标识识符符a整形数组标标识识符符index整形数数字字4整形数数字字2整形17编译的阶段（编译的阶段（8 8）源程序优化程序（源程序优化程序（source code optimizer）：）：代代码的改进只依赖于源代码码的改进只依赖于源代码各个编译器由于接受的源语言、目标语言的不同各个编译器由于接受的源语言、目标语言的不同

13、，优化的目标不同等，采用的优化手段也是不同，优化的目标不同等，采用的优化手段也是不同的。的。在编译时刻完成可以静态完成的操作，是优化的在编译时刻完成可以静态完成的操作，是优化的一个典型手段一个典型手段赋值语句下标表达式整形标标识识符符a整形数组标标识识符符index整形数数字字6整形18编译的阶段（编译的阶段（9 9）代码生成器（代码生成器（code generator）：）：生成目标代码生成目标代码目标机器的特性成为主要影响因素目标机器的特性成为主要影响因素指令选择、寄存器分配、数据表示形式等指令选择、寄存器分配、数据表示形式等MOVR0 , index/ index的值的值=R0MULR0

14、 , 2MOVR1 , &a/ a的首地址的首地址=R1ADDR1 , R0/ 计算计算aindex的地址的地址MOV*R1 , 6/ 赋值赋值19编译的阶段（编译的阶段（1010）目标代码优化器（目标代码优化器（target code optimizer）：）：改进改进目标代码目标代码选择编址模式提高性能选择编址模式提高性能将速度慢的指令换为速度快的指令将速度慢的指令换为速度快的指令删除多余的代码删除多余的代码寄存器优化寄存器优化软流水等软流水等MOVR0 , index/ index的值的值=R0SHLR0/ R0*2MOV&aR0 , 6/ 赋值赋值20编译的阶段（编译的

15、阶段（1111）中间代码的生成可以被认为是一个独立的阶段，中间代码的生成可以被认为是一个独立的阶段，但其工作可以在三个分析阶段逐步完成，因此我但其工作可以在三个分析阶段逐步完成，因此我们不把它单独出来们不把它单独出来编译器与上述各阶段：通常编译器通常包含上述编译器与上述各阶段：通常编译器通常包含上述几个阶段几个阶段但不同的编译器由于要求的不同，因此上述各个但不同的编译器由于要求的不同，因此上述各个阶段不是一定要出现的阶段不是一定要出现的在不同的编译器中，上述各个阶段的结构细节差在不同的编译器中，上述各个阶段的结构细节差异很大异很大各个阶段间存在着先后的次序关系，但不是绝对各个阶段间存在着先后的

16、次序关系，但不是绝对的，如词法分析程序通常作为语法分析程序的一的，如词法分析程序通常作为语法分析程序的一个过程调用，每次返回一个记号供语法分析使用个过程调用，每次返回一个记号供语法分析使用21编译的主要数据结构（编译的主要数据结构（1 1）编译器与其使用的数据结构间存在着密切的交编译器与其使用的数据结构间存在着密切的交互关系互关系主要数据结构如下：主要数据结构如下：记号记号(token)记号集可以用枚举数据表示，有时还要记录记号记号集可以用枚举数据表示，有时还要记录记号代表的字符串的相关信息，如名字、数值等代表的字符串的相关信息，如名字、数值等对于多数语言，一次生成一个记号即可推动编译对于多数

17、语言，一次生成一个记号即可推动编译器的工作，但对器的工作，但对FORTRAN等语言，可能要多个等语言，可能要多个记号：记号：DO 10 I = 5 ， 1022编译的主要数据结构（编译的主要数据结构（2 2）语法树语法树(syntax tree)：由分析程序生成，由于对象语言等的不同，各个由分析程序生成，由于对象语言等的不同，各个节点的内容是不同的节点的内容是不同的语法树的各个节点由于表示的对象的不同，因此语法树的各个节点由于表示的对象的不同，因此数据内容也是不同的数据内容也是不同的既可以是动态分配，也可以是静态数组实现，还既可以是动态分配，也可以是静态数组实现，还可以用存储池实现可以用存储池

18、实现符号表符号表(symbol table)：记录标识符相关的信息，如函数、变量、常量、记录标识符相关的信息，如函数、变量、常量、数据类型等数据类型等编译器的全程都有应用编译器的全程都有应用操作的效率必须重视，杂凑表是一种主要的构造操作的效率必须重视，杂凑表是一种主要的构造方式方式23编译的主要数据结构（编译的主要数据结构（3 3）常数表常数表(literal table)：存放程序中出现的常量和字符串存放程序中出现的常量和字符串允许重复使用，无须删除允许重复使用，无须删除目标代码也要使用目标代码也要使用中间代码中间代码(intermediate code)：三元式是一种简单的表示三元式是一种

19、简单的表示编译器出于各方面的考虑，中间代码可以很复杂编译器出于各方面的考虑，中间代码可以很复杂，也可以分成多层，一般称为中间表示，也可以分成多层，一般称为中间表示(intermediate representation)临时文件临时文件(temporary file)：存储局限存储局限分别编译分别编译24编译的结构（编译的结构（1 1）源代码源代码词法分析词法分析语法分析语法分析语义分析语义分析源代码优源代码优化化代码生成代码生成目标代码目标代码优化优化目标代码目标代码记号记号语法树语法树带注释的语法树带注释的语法树中间代码中间代码目标代码目标代码符号表等符号表等错误处理错误处理25编译的结构

20、（编译的结构（2 2）分析与综合分析与综合分析源程序以计算其特性的操作称为分析，如词分析源程序以计算其特性的操作称为分析，如词法分析、语法分析和语义分析等法分析、语法分析和语义分析等生成翻译代码时所涉及到的操作称为综合，如代生成翻译代码时所涉及到的操作称为综合，如代码生成码生成优化过程中，既有分析，也有综合优化过程中，既有分析，也有综合前端与后端前端与后端前端依赖源语言，后端依赖目标语言前端依赖源语言，后端依赖目标语言编译器移植的考虑编译器移植的考虑26编译的结构（编译的结构（3 3）遍遍(pass)：对源程序或中间表示的一次扫描，同时作相应的对源程序或中间表示的一次扫描，同时作相应的处理，称

21、为一遍处理，称为一遍只要语言没有特殊限制，编译器可以在一只要语言没有特殊限制，编译器可以在一“遍遍”完成，但目标代码不是很好完成，但目标代码不是很好可以根据需要，将多个编译的阶段合成一遍完成可以根据需要，将多个编译的阶段合成一遍完成，如将词法分析、语法分析、语义分析和中间代，如将词法分析、语法分析、语义分析和中间代码的生成组成一遍完成，各个阶段穿插进行码的生成组成一遍完成，各个阶段穿插进行由于优化阶段的工作复杂，优化技术繁多，所以由于优化阶段的工作复杂，优化技术繁多，所以优化阶段可能分解成多遍完成优化阶段可能分解成多遍完成27编译的结构（编译的结构（4 4）出错处理：出错处理：编译器的各个阶段

22、都可能发现错误编译器的各个阶段都可能发现错误错误处理包括错误的报告和错误的恢复错误处理包括错误的报告和错误的恢复一次编译应尽可能找到完全的错误，并准确报告一次编译应尽可能找到完全的错误，并准确报告错误的种类和位置，只报告一个错误不是一种好错误的种类和位置，只报告一个错误不是一种好的方法的方法编译器的前三个分析阶段可以发现大部分错误编译器的前三个分析阶段可以发现大部分错误静态可检测的错误由静态编译报告，但有些语言静态可检测的错误由静态编译报告，但有些语言要求检查动态时刻的错误，编译器要生成代码完要求检查动态时刻的错误，编译器要生成代码完成上述功能，如异常处理的机制成上述功能，如异常处理的机制28

23、编译相关的程序（编译相关的程序（1 1）伙伴程序：与编译器协作最终实现目标程序的伙伴程序：与编译器协作最终实现目标程序的执行执行预处理器预处理器(preprocessor)：编译器之前的处理程序编译器之前的处理程序注释的删除注释的删除宏处理宏处理文件的包含文件的包含语言扩充，如语言扩充，如SQL的数据库操作的数据库操作29编译相关的程序（编译相关的程序（2 2）汇编器汇编器(assembler)：生成可重定位的机器码生成可重定位的机器码连接器连接器(linker)：将不同的目标文件合成一个可将不同的目标文件合成一个可执行的文件执行的文件外部量外部量/全局量的处理全局量的处理装入程序装入程序(l

24、oader)：将可重定位的代码读入内存将可重定位的代码读入内存，形成可执行的程序，形成可执行的程序可重定位地址的确定化可重定位地址的确定化解释程序：同编译一样对高级语言程序翻译执解释程序：同编译一样对高级语言程序翻译执行行在源程序运行的同时对程序进行翻译和优化在源程序运行的同时对程序进行翻译和优化对源程序逐句进行分析、执行（模拟）对源程序逐句进行分析、执行（模拟）仍然可能生成某种简单的中间代码仍然可能生成某种简单的中间代码编译是在静态时刻完成源程序到目标代码的翻译编译是在静态时刻完成源程序到目标代码的翻译30编译相关的程序（编译相关的程序（3 3）结构编辑器：结构编辑器：可以对输入进行一些分析

25、可以对输入进行一些分析调试程序：调试程序：源程序信息的获得源程序信息的获得断点的管理断点的管理优化代码的调试优化代码的调试静态检查器：静态检查器：程序的分析程序的分析性能预测性能预测动态监测程序：程序动态行为的监测和分析动态监测程序：程序动态行为的监测和分析31编译相关的程序（编译相关的程序（4 4）程序开发环境：程序开发环境：便于程序的开发便于程序的开发几类特殊的编译程序：几类特殊的编译程序：高级语言间的转换工具高级语言间的转换工具并行编译程序并行编译程序二进制翻译程序二进制翻译程序动态优化工具动态优化工具32编译程序的自举与移植（编译程序的自举与移植（1 1）T形图：形图：描述源语言描述源

26、语言S、目标语言目标语言T和编译程序实现语言和编译程序实现语言I间间的关系的关系T形图的组合方式：形图的组合方式：将第一个将第一个T形图的输出作为第二个形图的输出作为第二个T形图的输入形图的输入已有将语言已有将语言A编译为语言编译为语言B的编译器和将语言的编译器和将语言B到语到语言言C的编译器，用上述方法得到得到的编译器，用上述方法得到得到A到到C的编译器的编译器 S T I A B I B C I A C I=33编译程序的自举与移植（编译程序的自举与移植（2 2）编译器实现语言的变换编译器实现语言的变换例如我们用例如我们用C语言开发了一个将语言开发了一个将FORTRAN语言语言程序编译为程

27、序编译为JAVA程序的编译器程序的编译器FOR2J，如果我如果我们已经有一个将们已经有一个将C语言编译为语言编译为X86代码的编译器，代码的编译器，利用上述的方式可以得到一个在利用上述的方式可以得到一个在X86机器上执行机器上执行的的FOR2J编译器编译器 A B I I K M A B K=34编译程序的自举与移植（编译程序的自举与移植（3 3）编译器的自举编译器的自举(bootstrapping)的开发方式的开发方式没有高级语言可以用来写编译器，怎么办？没有高级语言可以用来写编译器，怎么办？用汇编语言开发一个完整的编译器？太繁琐用汇编语言开发一个完整的编译器？太繁琐用自举的方式：用自举的方

28、式：v首先用汇编语言开发一个实现源语言一个子集的首先用汇编语言开发一个实现源语言一个子集的编译器，这个编译器只要正确即可编译器，这个编译器只要正确即可v用这个子集语言开发语言全集的编译器用这个子集语言开发语言全集的编译器v上述过程可以重复多次，直至得到性能良好的、上述过程可以重复多次，直至得到性能良好的、正确的对语言全集有效的编译器正确的对语言全集有效的编译器 A M A A M M A M M=35编译程序的自举与移植（编译程序的自举与移植（4 4）编译器的移植的开发方式编译器的移植的开发方式以以PC机为工具开发机为工具开发MIPS芯片的芯片的C语言编译器语言编译器PC机上已有机上已有C语言编译器语言编译器用用C语言在语言在PC机上开发一个产生机上开发一个产生MIPS代码的代码的C编编译器译器C1将将C1在在PC机上编译，得到机上编译，得到PC机上运行的交叉编机上运行的交叉编译器译器用交叉编译器在用交叉编译器在PC机上对机上对C1重新编译，得到在重新编译，得到在MIPS上运行的上运行的C语言编译器语言编译器36编译程序的自举与移植（编译程序的自举与移植（5 5） C M CC P P C M P=PC上的C语言编译器交叉编译器 C M CC M P C M M=交叉编译器MIPS上的C语言