编译原理清华大学导论

《编译原理清华大学导论》由会员分享，可在线阅读，更多相关《编译原理清华大学导论（48页珍藏版）》请在金锄头文库上搜索。

1、课程简介,总学时： 72学时 4.5学分 课堂教学： 52学时 ； 课内实验： 8学时 课内实践： 12学时 主讲：林泓,课程内容,介绍编译器构造的一般原理和基本实现方法 理论知识：形式语言和自动机理论、语法制导翻译的定义和属性文法等 形式化描述技术 对编译原理和技术的宏观理解，注意力无需分散到枝节算法，无需偏向于某种源语言或目标机器,学习的意义,对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。 大多数程序员同时是简单语言的设计者，有助于提高对这

2、些语言的设计水平。 在软件逆向工程、软件的设计方法、程序理解和软件安全等方面有着广泛的应用。,课程要求,讲课进展较快，平时要复习并加深理解。 作业较多，要求独立完成。 实验和课内实践，每次验收检查。 学期总评成绩 = 考试成绩60% + 平时成绩40% 平时成绩40% = 作业实验考勤30% + 课内实践10%,编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应用于编译程序的设计，也广泛应用于一般软件的设计和实现。本课程是计算机类专业的一门重要的核心专业课。 先修课程： 高级程序设计语言、汇编语言、 离散数学、数据结构 学习要求：不旷课，上课认真听讲，课上保持安静； 课

3、后即时复习，认真完成作业； 实验课内实践程序独立设计及实现 。,学习目标,通过本课程的学习，旨在使同学们掌握程序设计语言的形式化描述和编译的基本理论、原理和技术，并对编译程序有较为具体的认识。使同学们能运用所学过的基本知识、着手开发系统程序，为今后的工作（理论研究和技术开发）打下基础。 具体为： （1）掌握编译程序基本结构及构造的基本原理和技术； （2）掌握文法、形式语言及自动机的基本概念和在编译程序构造中的应用； （3）掌握典型的几种语法分析方法的基本原理和实现方法； （4）掌握语法制导方法在语义分析中的应用和中间代码生成方法； （5）掌握存储分配的基本思想和实现方法； （6）掌握代码优化及

4、代码生成的方法。,学习向导,编译原理课程是理论性较强的课程。其特点是概念多、内容抽象。尤其是文法、形式语言及自动机的概念是计算机专业的理论学习和研究的基础。掌握这些基本理论、原理和技术，对于培养同学们对事物的抽象能力以及分析问题和解决问题的能力大有帮助。 编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言的翻译方法起到不可替代的作用。同时编译原理课程也是实践性很强的课程，要求同学们在基本掌握了编译理论和技术的基础上，综合应用先修课程及本课程的知识，完成课程的实验和课程设计。,参考资料,教材： 1编译原理（第三版） 主编：王生原、董渊、张素琴、吕映芝 出版

5、社：清华大学出版社 出版时间：2015年 参考书： 1编译原理 主编：何炎祥 出版社：华中理工大学出版社 出版时间：2010年10月 2程序设计语言编译原理（第3版） 主编：陈火旺、刘春林、谭庆平、赵克佳、刘越 出版社：国防工业出版社 出版时间：20012年8月 3编译原理技术与工具（英文版） Compilers:Principles,Techniques,and Tools 主编：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 出版社：人民邮电出版社 出版时间：2002年2月,参考资料,4编译原理与技术（第二版） 主编：陈意云 出版社：中国科学技术大学出版社

6、 出版时间：2002年1月 5编译程序构造原理和实现技术 主编：金成植 出版社：高等教育出版社 出版时间：2002年7月 6编译原理及编译程序构造 主编：高仲仪、金茂忠 出版社：北京航空航天大学出版社 出版时间：2001年3月 7编译原理(第2版) 主编：蒋立源, 康慕宁 出版社：西北工业大学出版社 出版时间：1999年4月 8编译原理 主编：张幸儿 出版社：科学出版社 出版时间：1999年4月,第1章 引论,本章主要内容： 什么是编译程序 编译过程和编译程序的结构 为什么要学习编译程序,本章的重点： 本章没有难以理解的内容,主要是对编译程序的功能和结构做一综合描述,1.1 什么叫编译程序,使

7、用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现代计算机系统一般都含有不止一个的高级语言编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。 要在计算机上执行用高级语言（或汇编语言）编写的程序，必须通过特定的途径来进行，也就是要通过翻译程序把用高级语言（或汇编语言）编写的程序翻译成为机器语言构成的程序，计算机才能执行。 在计算机上执行一个高级语言程序一般要分为两步： 第一步，用一个编译程序把高级语言翻译成机器语言程序； 第二步，运行所得的机器语言程序求得计算结果。,（1）翻译程序（Translator）,通常所说的翻译程序是指这样的一

8、个程序，它能够把某一种语言程序（称为源语言程序或源程序）转换成另一种语言程序（称为目标语言程序或目标程序），而后者与前者在逻辑上是等价的。,翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。,（2）. 汇编程序（Assembler）,如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。,（3）. 编译程序（Compiler）,如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。,（4）. 解释程序（Interpreter）,这是另外一种类型的翻译程序，在翻译过程它按照高

9、级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。,根据不同的用途，编译程序可进一步分类: （1）诊断编译程序（Diagnostic Compiler）： 专门用于帮助程序开发和调试的编译程序。 （2）优化编译程序（Optimizing Compiler）： 着重于提高目标代码效率的编译程序。 （3）交叉编译程序(Cross Compiler)： 如果一个编译程序产生不同于其宿主机的机器代码。 （4）可变目标编译程序（Retargetable Compiler）： 不需

10、重写编译程序中与机器无关的部分就能改变目标机。 宿主机（host machine）：运行编译程序的计算机。 目标机(object machine) ：运行编译程序所产生目标代码的计算机。,1.2 编译过程概述,编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。 一段英文翻译为中文时，通常需经下列步骤： （1）识别出句子中的一个个单词； （2）分析句子的语法结构； （3）根据句子的含义进行初步翻译； （4）对译文进行修饰； （5）写出最后的译文。 类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。,第一阶

11、段: 词法分析 （Lexical analysis）,词法分析的任务： 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。 保留字（begin、end、if、for、while等）、 标识符（x1、s等变量名）、 常数(3.14、100等)、 算符（+、-、and、or等）、 界符（标点符号、左右括号等）。,例如，对于Pascal的循环语句： for I：1 to 100 do 词法分析的结果是识别出如下的单词符号： 保留字 for 标识符 I 赋值号： ：= 整常数 1 保留字 to 整常数 100 保留字 do,单词符号是语言的基本组成成分，是人们理解和编写程序的基本要素

12、。识别和理解这些要素无疑也是翻译的基础。 如同将英文翻译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。 在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的有效工具是正规式和有限自动机。,第二阶段，语法分析(Syntax Analysis),语法分析的任务是： 在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子”（“语句”）、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。,语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。 词法分析

13、是一种线性分析，而语法分析是一种层次结构分析。例如，在很多语言中，符号串 z：=X十0.618*Y 代表一个“赋值语句”，而其中的 X0.618*Y代表一个“算术表达式”。因而，语法分析的任务就是识别 X0.618*Y为算术表达式，同时，识别上述整个符号串属于赋值语句这个范畴。,第三阶段，语义分析与中间代码产生(Semantic Analysis and Intermediate Generator),此阶段的任务是： 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。,中间代码是一种独立于具体硬件的记号系统。 常用的中间代码：三地址码，四元式，三元式、间接三元式、

14、逆波兰式，树形表示等。 所谓“中间代码”是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。,四元式的形式是： （ 算符 左操作数 右操作数 结果） 它的意义是：对“左、右操作数”进行某种运算（由“算符”指明），把运算所得的值作为“结果”保留下来。 例如 赋值语句 Z：（X0.418）*YW 翻译为四元式序列： 序号 算符 左操作数 右操作数 结果 1 十 X 0.418 T1 2 * T1 Y T2 3 T2 W Z,第四阶段，优化 (Optimization),优化的任务: 对

15、产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。,优化的主要方面有： 公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于“并行运算”，还可以对代码进行并行化处理。 优化所依循的原则: 程序的等价变换规则。,例如，有程序片断 for K:1 to 100 do begin M:=I+10*K N:=J+10*K end,其中间代码为：,转换成如下的等价代码：,优化后目标程序的执行效率提高很多。因为，对于前者，在循环中需做300次加法和200乘法；对于后者，在循环中只需做300次加法。,第五阶段，目标代码生成(Code Generation),这一阶段的任务是： 把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。,例 （*, id3, 10.0, t1） （+, id2, , t1, id1 ） 目标代码： （1）MOV id3, R2 （2）MUL #10.0, R2 （3）MOV id2, R1 （4）ADD R1, R2 （5）MOV R1, id1,上述编译过程的五个阶段是一种典型的分法。 事实上，并非所有编译程序都分成这五阶段。 有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，