第1章-引论

课程简介总学时：56学时3.5学分课堂教学：48学时；实验：8学时课程设计：一周1学分主讲：林泓课程内容介绍编译器构造的一般原理和基本实现方法介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法等强调形式化描述技术强调对编译原理和技术的宏观理解，注意力无需分散到枝节算法，无需偏向于某种源语言或目标机器学习的意义对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。在软件逆向工程、软件的设计方法、程序理解和软件安全等方面有着广泛的应用。课程要求讲课进展较快，平时要复习并加深理解。作业较多，要求独立完成。上机实验，每次检查。学期总评=考试成绩占70%，平时成绩占30%编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应用于编译程序的设计，也广泛应用于一般软件的设计和实现。本课程是计算机类专业的一门重要的核心专业课。先修课程：高级程序设计语言、汇编语言、离散数学、数据结构学习要求：不旷课，上课认真听讲，课上保持安静；课后即时复习，认真完成作业。学习目标通过本课程的学习，旨在使同学们掌握程序设计语言的形式化描述和编译的基本理论、原理和技术，并对编译程序有较为具体的认识。使同学们能运用所学过的基本知识、着手开发系统程序，为今后的工作（理论研究和技术开发）打下基础。具体为：（1）掌握编译程序基本结构及构造的基本原理和技术；（2）掌握文法、形式语言及自动机的基本概念和在编译程序构造中的应用；（3）掌握典型的几种语法分析方法的基本原理和实现方法；（4）掌握语法制导方法在语义分析中的应用和中间代码生成方法；（5）掌握存储分配的基本思想和实现方法；（6）掌握代码优化及代码生成的方法。学习向导《编译原理》课程是理论性较强的课程。其特点是概念多、内容抽象。尤其是文法、形式语言及自动机的概念是计算机专业的理论学习和研究的基础。掌握这些基本理论、原理和技术，对于培养同学们对事物的抽象能力以及分析问题和解决问题的能力大有帮助。编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言的翻译方法起到不可替代的作用。同时《编译原理》课程也是实践性很强的课程，要求同学们在基本掌握了编译理论和技术的基础上，综合应用先修课程及本课程的知识，完成课程的实验和课程设计。参考资料教材：[1]《编译原理》主编：张素琴、吕映芝、蒋维杜出版社：清华大学出版社出版时间：2005年2月参考书：[1]《编译原理》主编：何炎祥出版社：华中理工大学出版社出版时间：2000年10月[2]《程序设计语言编译原理（第3版）》主编：陈火旺、刘春林、谭庆平、赵克佳、刘越出版社：国防工业出版社出版时间：2001年8月[3]《编译原理技术与工具（英文版）》Compilers:Principles,Techniques,andTools主编：AlfredV.Aho,RaviSethi,JeffreyD.Ullman出版社：人民邮电出版社出版时间：2002年2月参考资料[4]《编译原理与技术》（第二版）主编：陈意云出版社：中国科学技术大学出版社出版时间：2002年1月[5]《编译程序构造原理和实现技术》主编：金成植出版社：高等教育出版社出版时间：2002年7月[6]《编译原理及编译程序构造》主编：高仲仪、金茂忠出版社：北京航空航天大学出版社出版时间：2001年3月[7]《编译原理(第2版)》主编：蒋立源,康慕宁出版社：西北工业大学出版社出版时间：1999年4月[8]《编译原理》主编：张幸儿出版社：科学出版社出版时间：1999年4月第1章引论本章主要内容：什么是编译程序编译过程和编译程序的结构为什么要学习编译程序本章的重点：本章没有难以理解的内容,主要是对编译程序的功能和结构做一综合描述§1.1什么叫编译程序使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现代计算机系统一般都含有不止一个的高级语言编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。要在计算机上执行用高级语言（或汇编语言）编写的程序，必须通过特定的途径来进行，也就是要通过翻译程序把用高级语言（或汇编语言）编写的程序翻译成为机器语言构成的程序，计算机才能执行。在计算机上执行一个高级语言程序一般要分为两步：第一步，用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。（1）．翻译程序（Translator）通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序（称为源语言程序或源程序）转换成另一种语言程序（称为目标语言程序或目标程序），而后者与前者在逻辑上是等价的。源程序（sourceprogram）翻译程序目标程序(targetprogram)输入输出图1.1翻译程序翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。（2）.汇编程序（Assembler）如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。源程序（汇编语言）翻译程序（汇编程序）目标程序（机器语言）输入输出图1.2汇编程序（3）.编译程序（Compiler）如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。源程序（高级语言）翻译程序（编译程序）目标程序（低级语言）图1.3编译程序输入输出（4）.解释程序（Interpreter）这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。源程序（高级语言）翻译程序（解释程序）计算结果输入输出图1.4解释程序初始数据根据不同的用途，编译程序可进一步分类:（1）诊断编译程序（DiagnosticCompiler）：专门用于帮助程序开发和调试的编译程序。（2）优化编译程序（OptimizingCompiler）：着重于提高目标代码效率的编译程序。（3）交叉编译程序(CrossCompiler)：如果一个编译程序产生不同于其宿主机的机器代码。（4）可变目标编译程序（RetargetableCompiler）：不需重写编译程序中与机器无关的部分就能改变目标机。宿主机：运行编译程序的计算机。目标机：运行编译程序所产生目标代码的计算机。§1.2编译过程概述编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一段英文翻译为中文时，通常需经下列步骤：（1）识别出句子中的一个个单词；（2）分析句子的语法结构；（3）根据句子的含义进行初步翻译；（4）对译文进行修饰；（5）写出最后的译文。类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。第一阶段:词法分析（Lexicalanalysis）词法分析的任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。保留字（begin、end、if、for、while等）、标识符（x1、s等变量名）、常数(3.14、100等)、算符（+、-、and、or等）、界符（标点符号、左右括号等）。例如，对于Pascal的循环语句：forI：＝1to100do词法分析的结果是识别出如下的单词符号：保留字for标识符I赋值号：：=整常数1保留字to整常数100保留字do单词符号是语言的基本组成成分，是人们理解和编写程序的基本要素。识别和理解这些要素无疑也是翻译的基础。如同将英文翻译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的有效工具是正规式和有限自动机。第二阶段，语法分析(SyntaxAnalysis)语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子”（“语句”）、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。词法分析是一种线性分析，而语法分析是一种层次结构分析。例如，在很多语言中，符号串z：=X十0.618*Y代表一个“赋值语句”，而其中的X＋0.618*Y代表一个“算术表达式”。因而，语法分析的任务就是识别X＋0.618*Y为算术表达式，同时，识别上述整个符号串属于赋值语句这个范畴。第三阶段，语义分析与中间代码产生(SemanticAnalysisandIntermediateGenerator)此阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。中间代码是一种独立于具体硬件的记号系统。常用的中间代码：三地址码，四元式，三元式、间接三元式、逆波兰式，树形表示等。所谓“中间代码”是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。四元式的形式是：（算符左操作数右操作数结果）它的意义是：对“左、右操作数”进行某种运算（由“算符”指明），把运算所得的值作为“结果”保留下来。例如赋值语句Z：＝（X＋0.418）*Y／W翻译为四元式序列：序号算符左操作数右操作数结果1十X0.418T12*T1YT23／T2WZ第四阶段，优化(Optimization)优化的任务:在于对前段产生的中间代码进行加工变换，以期在最后分段能产生出更为高效（省时间和空间）的目标代码。优化的主要方面有：公共子表达式构提取、循环优化、删除无用代码等等。有时，为了便于“并行运算”，还可以对代码进行并厅化处理。优化所依循的原则:程序的等价变换规则。例如，如果我们有程序片断forK:＝1to100dobeginM:=I+10*KN:=J+10*Kend其中间代码为：序号OPARG1ARG2RESULT注解（1）（2）（3）（4）（5）（6）（7）（8）（9）:=j*+*++j110010I10JKKKT1KT21K（9）T1MT2NK（2）K：＝1若100＜K转至第(9)个四元式T1:二10*K;T1为临时变量M:＝I＋T1T2:＝10*k;T2为临时变量N:＝J十T2K:＝K十1转至第（2）个四元式转换成如下的等价代码：序号OPARG1ARG2RESUL注解（1）（2）（3）（4）（5）（6）（7）（8）（9）：=：=：=j+++jIJ1100MNKK10101MNK（9）MNK（4）M：＝IN：＝JK：＝lif（100＜k）goto（9）M：＝M＋10N：＝N十10K：＝K＋lgoto（4）优化后目标程序的执行效率提高很多。因为，对于前者，在循环中需做300次加法和200乘法；对于后者，在循环中只需做300次加法。第五阶段，目标代码生成(CodeGeneration)这一阶段的任务是：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。例（*,id3,10.0,t1）（+,id2,,t1,id1）目标代码：（1）MOVid3,R2（2）MUL#10.0,R2（3）MOVid2,R1（4）ADDR1,R2（5）MOVR1,id1上述编译过程的五个阶段是一种典型的分法。事实上，并非所有编译程序都分成这五阶段。有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。有些最简单的编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序的工作过程大致都像上面所说的那