《编译原理实践及应用》编译原理概述省公开课金奖全国赛课一等奖微课获奖课件

编译原理实践及应用----清华大学出版社11/50教材及主要参考资料教材：编译原理实践及应用，黄贤英，清华大学出版社主要参考资料：(1)编译原理，陈火旺，国防工业出版社程序设计语言编译方法，肖军模，大连理工大学出版社编译原理，张素琴，吕映芝，清华大学出版社编译原理，alfredV.Aho等著，李建中等译，人民邮电出版社22/50考核方法平时成绩、作业完成：10%要求上课不迟到早退,不旷课,有事请假,记好笔记要求用大作业本,不能交单张纸,独立完成试验：30%要求程序可运行,并有相关设计和使用说明期末考试：60%闭卷形式33/50C语言程序voidmain(){intx,y,z;x=3;y=2;z=x+y;}内存地址内存内容单元名字………………200H3x：局部变量201H2y：局部变量202H5z：局部变量…………汇编语言程序……movax,3movx,axmovax,2movy,axmovax,xmovbx,yaddax,bxmovz,ax......300302304306308……序言44/50为何要学习编译原理？1、有利于深刻了解和正确使用程序设计语言，加深对高级语言程序执行过程了解2、有利于加深对整个计算机系统了解。3、设计开发编译程序软件技术一样能够用于其它软件设计开发。4、伴随微处理器技术飞速发展，处理器性能在很大程度上取决于编译器质量、编译技术成为计算机关键技术，地位变得越来越主要。55/50《编译原理》课程在计算机科学中主要地位(1)学习编程最初是学习一门高级语言，C或Pascal，掌握编写一些简单程序方法；(2)学习数据结构，建立“算法”概念，对编程有更深入了解。碰到问题时候，能够寻找对应数据结构模型，设计适当算法来处理问题；(3)学习汇编语言，这门课程是我们真正深入了解计算机内部工作第一门课程。经过学习了解汇编语言怎样变为机器语言，怎样对应于一条指令；(4)计算机组成原理课程学习使我们了解到计算机硬件组成，以及机器指令程序怎样在计算机中运行过程。(5)编译原理课程帮助我们了解高级语言程序转换成机器指令程序过程。能够帮助我们更深刻地了解高级语言程序运行内部机制。66/50《编译原理》课程在计算机科学中地位高级语言程序设计离散数学数据结构编译原理操作系统系统软件应用软件软件工程信息系统电子商务汇编语言计算机组成原理77/50学习本课程目标和任务加深对编程语言设计和实现了解，对和编程语言相关理论有所了解，对宏观上把握编程语言来说，起一个奠基作用，提升本身编程能力掌握编译程序基本结构，掌握惯用编译技术和方法，将编译原理理论和方法应用于普通软件设计中培养团体协作能力88/50本课程特点(1)本课程理论性很强，学习时需要很强逻辑思维能力(2)包括算法复杂，要深入地了解这些算法很困难(3)整个编译程序结构方法非常精妙，就像一部走时准确时钟，很多齿轮、部件协调地运转，以驱动指针准确地旋转；编译程序也是如此，一边扫描源程序，一边经过各个部件运算，准确地输出为目口号言。(4)编译原理课程各个部分之间独立性很强，包含词法分析、语法分析、存放组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析和语法分析是其中重点，语法分析也是难点，需要掌握比较复杂算法逻辑；其它部分相对来说知识性更强一些。各部分之间方法也相互独立，在学习时，便于逐一击破。(5)考试考查内容相对来说是很稳定，绝大多数题目标解法都非常机械。99/50学习方法(1)尽可能地掌握编译原理思想，要站得高一点，尽可能了解算法思想，而不是背固定算法。应该尽力了解为何要这么做，逐步在头脑中建立起编译器整体概念，而不是零零碎散一些算法。(2)很多题目标解法比较固定，要熟练掌握对应详细方法。(3)多做习题,对于编译这么学科，题目标规模很大，步骤繁多，而且前面步骤一旦犯错，后面都错。(4)要扎扎实实地切记主要算法，配合大量习题进行练习，到达拿到题目就能够动手做地步。(5)一边学习，一边总结，关键是找差异：同一问题能够用各种方法来求解，不一样方法适合用于不一样文法，对文法限制和要求，对应表格结构、使用等，各个方面差异都要关注。(6)亲自动手实现书上一些算法,完成试验指导书上给出一个简单编译程序，或者编译程序一部分，这么能更灵活地掌握编译程序结构精华。

1010/50引论第一章1111/50本章要求主要内容：各种翻译程序概念，编译过程和阶段划分，编译程序组成和结构，编译程序结构方法重点掌握：编译程序工作基本过程及其各阶段基本任务，编译程序总框。1212/501.1程序设计语言与翻译程序机器语言(machinelanguage)C70600000002汇编语言(assemblerlanguage)

MOVX,2高级语言(high-levellanguage)

X=2为何要使用编译程序？1313/50机器语言(machinelanguage)C70600000002汇编语言(assemblerlanguage)

MOVX,2高级语言(high-levellanguage)

X=2为何要使用编译程序？1414/50计算机中语言层次和转换关系1515/50高级语言语言处理程序操作系统汇编语言编译程序所处层次计算机硬件C编译程序C语言Basic解释程序Basic语言Fortran编译程序Fortran语言............1616/50什么叫编译程序翻译程序：能够将某种语言写程序转换成另一个语言程序，而且后者与前者在逻辑上是等价。编译程序：将高级程序设计语言程序翻译成逻辑上等价低级语言(汇编语言,机器语言)程序翻译程序。解释程序：将高级程序设计语言写源程序作为输入，边解释边执行源程序本身，而不产生目标程序翻译程序。1717/50编译程序功效编译程序源程序目标程序计算机运行输入数据结果1818/50解释程序功效解释程序源程序输入数据结果1919/50对编译程序一些说明编译程序实质上是一个翻译程序，要注意等价变换本课程任务就是讲解在这个转换过程中所包括到一些理论和方法，最终，使用这些理论和方法，自己编写一个小编译器转换是一个总体功效，要抓住总体结构，逐层细分，写编译器时要表达软件工程中软件设计标准，自顶向下，逐层分解。编译器要完成转换任务相当复杂，实现编译器时必须分步骤分阶段实现。分阶段实现好处是能够简化程序设计，当然也能够不分阶段实现。2020/50编译程序分类诊疗编译程序优化编译程序可变目标编译程序交叉编译程序2121/50与编译程序相关程序编辑器(editor)预处理器(Preprocessor)将源程序聚集到一起，宏展开等汇编程序(assembler)连接程序(linker)连接系统函数与系统资源装入程序(loader)重定位(relocation)Debugger,Profiler,ProjectManager2222/50编译原理是讨论编译程序设计基本理论、基本概念、基本方法什么是编译原理2323/501.2编译过程概述1、逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成

每个阶段把源程序从一个表示变换成另一个表示词法分析语法分析语义分析与中间代码生成代码优化目标代码生成2424/50按照词法分析、语法分析、语义分析等这种方式来划分阶段原因是：每个阶段复杂程度不一样，所依据理论基础不一样，实现时采取方法也不一样。主要是方便了解和实现。划分阶段依据是什么？每个阶段所实现功效相对独立。2525/50第一阶段：词法分析任务:从左到右扫描源程序，识别出每个单词附加任务：a、滤掉空格b、识别单词单词符号是语言基本组成成份词法分析工作主要依据语言词法规则，描述词法规则有效工具是正规式和有限自动机。单词种类：（1）标识符（2）关键字（char、int、if、else、switch、while、for等）（3）运算符（即运算符号+、－、*、/、&等）（4）界符（常见有；，：（）等）（5）常数

2626/50beginresult:=5＋B*C＋B*Cend;单词类型内部形式begin关键字$beginresult标识符id1:=界符:=5常数int1+算符+B标识符id1*算符*C标识符id2+算符+B标识符id2*算符*C标识符id3end关键字$end;界符;例:2727/50第二阶段：语法分析任务:在词法分析基础上，依据语言语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表示式)。确定整个输入串是否组成语法上正确程序。依据规则判定：赋值语句：标识符：＝表示式

表示式：标识符、常数是表示式

表示式运算也是表示式例：识别符号串id1:=int1+id2*id3+id2*id3（即result:=5＋B*C＋B*C）是一个赋值语句，而int1+id2*id3+id2*id3（5＋B*C＋B*C）是一个表示式2828/50语法分析所依据是语言语法规则，表示语法规则工具是上下文无关文法,用下推自动机实现。id1:=int1+id2*id3+id2*id3注意树形式！！2929/50第三阶段：语义分析和中间代码生成任务：对语法分析所识别出各类语法范围分析其含义，进行初步翻译(翻译成中间代码)。静态语义审查变量定义类型匹配类型转换例：C:=A*B(检验C与Ａ、Ｂ类型)中间代码翻译

中间代码有各种形式，如：

四元式:(运算符，运算对象1，运算对象2，结果)3030/50例：对赋值语句：id1:=int1+id2*id3+id2*id3

1.检验result、Ｂ、C是否定义、类型2.生成中间代码(运算符，运算对象1，运算对象2，结果)

(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T4,_,id1)id1:=int1+id2*id3+id2*id33131/50第四阶段：代码优化任务：对已产生中间代码进行加工变换，使生成目标代码更为高效(时间和空间)。优化方法包含：公共子表示式提取、循环优化、删除无用代码等。代码优化依据是程序等价变换规则。序号四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(*,id2,id3,T3)4(+,T2,T3,T4)5(:=,T4,_,id1)序号四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)3232/50第五阶段：目标代码生成任务：把中间代码(或经优化中间代码)变换成特定机器上低级语言代码。依赖于机器硬件系统结构和机器指令含义目标代码能够是：绝对指令代码、可重定位指令代码、汇编指令代码序号四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)（1）movAX,id2（2）mulAX,id3（3）movBX,AX（4）addAX,int1（5）addAX,BX（6）movid1,AX3333/501.2编译程序结构

由左图能够看出，词法分析是实现编译器基础，语法分析是实现编译器关键。所以按照这个次序来实现编译器每一步实现都依赖于一定理论基础。数学，尤其是离散数学是程序设计方法学理论基础3434/501.2编译阶段组合几个概念遍：对源程序或源程序中间结果从头到尾扫描一次，并作相关加工处理，生成新中间结果或目标程序。编译前端：主要指与源语言相关，与目口号言无关部分，通常包含词法分析、语法分析、语义分析和中间代码生成，与机器无关部分代码优化编译后端：指与目标机器相关部分。如与机器相关优化、目标代码生成3535/50编译阶段组合3636/50为何生成中间代码3737/501.2编译程序结构(续)

(1)记号(token)当扫描程序将字符搜集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型值来表示源程序记号集。编译程序中主要数据结构:3838/50编译程序中主要数据结构(2)语法树（syntaxtree）假如分析程序确实生成了语法树，它结构通常为基于指针标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点单个变量保留。结构中每一个节点都是一个统计，它域表示由分析程序和之后语义分析程序搜集信息。3939/50(3)符号表（symboltable）这个数据结构中信息与标识符相关：函数、变量、常量以及数据类型。符号表几乎与编译器全部阶段交互：扫描程序、分析程序或将标识符输入到表格中语义分析程序；语义分析程序将增加数据类型和其它信息；优化阶段和代码生成阶段也将利用由符号表提供信息选出恰当代码。因为对符号表访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管能够使用各种树结构，但杂凑表却是到达这一要求标准数据结构。有时在一个列表或栈中可使用若干个表格。编译程序中主要数据结构:4040/50(4)常数表（literaltable）常数表功效是存放在程序中用到常量和字符串，所以快速插入和查找在常数表中也十分主要。不过，在其中却无需删除，这是因为它数据全程应用于程序而且常量或字符串在该表中只出现一次。编译程序中主要数据结构:4141/50(5)中间代码（intermediatecode）依据中间代码类型（比如三元式代码）和优化类型，该代码能够是文本串数组、暂时文本文件或是结构连接列表。对于进行复杂优化编译器，应尤其注意选择允许简单重组表示。编译程序中主要数据结构:4242/50(6)暂时文件（temporaryfile）计算机过去一直未能在编译器时将整个程序保留在存放器中。这一问题已经经过使用暂时文件来保留翻译时中间步骤结果或经过“慌忙地”编译（也就是只保留源程序早期部分足够信息用以处理翻译）处理了。编译程序中主要数据结构:4343/501.3编译程序结构结构编译程序要掌握以下几方面内容：源语言：了解其结构和含义目口号言：必须清楚硬件系统结构和指令格式等编译方法4444/501.3编译程序结构普通实现编译程序方法有：1.直接用机器语言编写编译程序2.用汇编语言编写编译程序注：编译程序关键部分惯用汇编语言编写3.用高级语言编写编译程序注：这是普遍采取方法4.自编译5.用编译工具自动生成:LEX(词法分析)与YACC(用于自动产生LALR分析表)6.移植（同种语言编译程序在不一样类型机器之间移植）4545/50本书组成及编译程序框架4646/501.4编译技术发展1954年至1957年间，FORTRAN语言及其编译器开发。花了18个人年。几乎与此同时，NoamChomsky开始研究语言文法(grammar，结构规则)难易程度以及识别它们所需算法来为语言分类。在60年代和70年代进行分析问题(parsingproblem，用于限定上下文无关语言识别有效算法)研究。有穷自动机(finiteautomata)和正规式(re