编译原理课件汇总

编译原理主讲：闫健恩Email：yanjianen(@)yahoo.com.cn写在课程之前木桶原理：一个木桶由许多块木板组成，如果组成木桶的这些木板长短不一，那么这个木桶的最大容量不取决于长的木板，而取决于最短的那块木板。蝴蝶效应：1963年12月，洛伦兹（Lorenz）在华盛顿的美国科学促进会的一次讲演中提出：一只蝴蝶在巴西扇动翅膀，有可能会在美国的德克萨斯引起一场龙卷风。他的演讲和结论给人们留下了极其深刻的印象。马太效应：“马太福音”第二十五章由这么几句话：“凡有的，还要加给他叫他多余；没有的，连他所有的也要夺过来。”。1968年，美国科学史研究者罗伯特·莫顿（RobertK.Merton）提出这个术语用以概括一种社会心理现象：“相对于那些不知名的研究者，声名显赫的科学家通常得到更多的声望即使他们的成就是相似的，同样地，在同一个项目上，声誉通常给予那些已经出名的研究者，例如，一个奖项几乎总是授予最资深的研究者，即使所有工作都是一个研究生完成的。”学时与参考教材学时：44+16学时参考教材：1、AlfredAhoect.《编译原理》，赵建华等译，机械工业出版社，2009.10.2、KennethC.Louden，《编译原理及实践》，冯博琴等译，机械工业出版社，2001.2.3、金成植，《编译程序构造原理和实现技术》，高等教育出版社，2000.7.4、陈火旺等，《程序设计语言编译原理》，国防工业出版社，2003.8.印刷学时与参考教材5、何炎祥等，《编译原理》，华中理工大学出版社，2000.10.6、蒋立源，《编译原理》，西北工业大学出版社，2000.7.7、肖军模，《程序设计语言编译方法》，大连理工大学出版社，2000.88、蒋宗礼等，《形式语言与自动机理论》，清华大学出版社，2003.1.主要内容编译系统及其设计概述（总体结构、设计方法）语言与文法（文法、推导、归约、分类、分析树）词法分析（词法分析、正规式与正规文法、DFA的状态转移图）语法分析（自顶向下：LL(1)、递归子程序；自底向上：LR）语义分析（属性文法、各种语句的语法制导翻译）运行环境（存储分配、过程调用、符号表管理）代码优化（基本块的优化、循环优化等）代码生成（目标机器模型、基本块和流图、寄存器分配、基本块的DAG表示、从DAG生成目标代码）教学目的——《编译原理》是一门非常好的课程AlfredV.Aho：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到涉及的是一个比较适当的抽象层面上的数据变换（既抽象，又实际）一些具体的表示和变换算法“自顶向下的方法”和“自底向上的方法”系统设计方法（思想、方法、实现全方位讨论）一个相当规模的系统的设计（含总体结构）计算机专业最为恰当、有效的知识载体之一教学要求掌握编译程序总体结构在系统级上认识算法、系统的设计具有把握系统的能力学习有关的原理、实现方法和技术，了解计算学科的基本方法、思想掌握典型方法。“在每一个计算机科技工作者的职业生涯中，这些原理和技术都被反复用到。”兼顾语言的描述方法、设计、应用——形式化能形式化就能自动化进一步培养“计算机思维能力”软件系统的非物理性质学习成果__以学生为中心理解和掌握编译过程各个阶段的工作原理理解标准编译器各个组成部分的任务熟悉编译过程各阶段所要解决的问题及其采用的方法和技术应用一些标准的技术解决编译器构造过程中所产生的相关问题理解编译器在生成代码时如何充分利用特定处理器的特征第1章引论1.1计算机语言的发展1.2翻译系统1.3编译系统的功能分析1.4编译程序总体结构1.5编译程序的生成1.6编译技术的应用1.1计算机语言的发展机器语言(MachineLanguage)与汇编语言(AssembleLanguage)0、1代码与助记符：更接近于计算机硬件指令系统的工作高级语言(HighLevelLanguage)其表示方法更接近于待解问题的表示方法定义数据、描述运算、控制流程、传输数据如：C、FORTRAN、PASCAL、C++、JAVA、SQL(数据定义、数据操作)命令语言(CommandLanguage)控制系统的工作——以功能封装为特征如UNIX上的shell1.2翻译系统翻译程序(Translator)将某一种语言描述的程序(源程序——SourceProgram)翻译成等价的另一种语言描述的程序(目标程序——ObjectProgram)的程序。翻译程序源程序目标程序(*.C/*.PAS)(*.OBJ/*.EXE)1.2翻译系统解释程序(Interpreter)口译与笔译（单句提交与整篇提交）源程序输入数据计算结果解释程序1.2翻译系统编译程序(Compiler)高级语言程序→汇编/机器语言程序源程序目标程序编译程序1.2编译系统SPCompilerS-SourceO-ObjectOPP-ProgramInputRSRS-RunSys.Output编译系统(CompilingSystem)编译系统=编译程序+运行系统支撑环境、运行库等1.2翻译系统其它：诊断编译程序（DiagnosticCompiler)优化编译程序（OptimizingCompiler)交叉编译程序（CrossCompiler)可变目标编译程序（RetargetableCompiler)并行编译程序（ParallelizingCompiler）汇编程序(Assembler)、交叉汇编程序(CrossAssembler)、反汇编程序（Disassembler)1.2翻译系统—汇总MLMLPAssemblerDisassemblerALALPTranslatorCompilerDataHLHLPInterpreterResultM-MachineL-LangugeP-ProgramA-AssembleH-HighLevel1.3编译系统的功能分析程序分析词法、语法、语义分析综合语句的翻译、代码生成标识符处理：左值与右值的绑定(binding)变量：存储单元函数：目标代码序列1.4编译程序总体结构目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码中间代码目标代码语法单位单词符号词法分析器源程序1.词法分析例：main(){printf(“hello”);}结果IDNmain‘(’‘)’‘{’IDNprintf‘(’STRhello‘)’‘;’‘}’1、词法分析词法分析由词法分析器完成(LexicalAnalyzer)，词法分析器又叫做扫描器(Scanner)词法分析器从左到右扫描源程序——发现一个字符串，则将该字符串转换成单词(记号—Token)串；同时要：查词法错误，进行标识符登记——符号表管理。输入：字符串输出：(种别码，属性值)——序对属性值——token的机内表示2、语法分析语法分析由语法分析器(SyntaxAnalyzer)完成，语法分析器又叫Parser。功能：Parser实现“组词成句”将词组成各类语法成分：表达式、因子、项，语句，子程序…构造分析树指出语法错误指导翻译输入：Token序列输出：语法成分2.语法分析res=fact*(term1+term2);*；赋值语句表达式=）（fact表达式res表达式表达式表达式表达式+term1term23.语义分析功能：分析由语法分析器识别出的语法单位的语义获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址4.中间代码生成中间代码(intermediateCode)例:id1+id2*id3后缀表示(逆波兰Anti-PolishNotation)id1id2id3*+前缀表示(波兰PolishNotation)+id1*id2id3四元式表示(三地址码)1(*,id1,id2,T1)2(+,id3,T1,T2)三元式表示1(*,id2,id3)2(+,id1,(1))EE+EidE*Eidid语法树4.中间代码生成中间代码的特点简单规范与机器无关易于优化与转换三地址码的另一种表示形式T1=id2*id3T2=id1*T1其它类型的语句例：printf(“hello”)x:=s（赋值）paramx（参数）callf（函数调用）注释s是hello的地址f是函数printf的地址对中间代码的优化处理:对代码进行等价变换以求提高执行效率——提高运行速度和节省存储空间与机器无关的优化与机器有关的优化5.代码优化与机器无关的优化局部优化常量合并：常数运算在编译期间完成，如8+9*4公共子表达式的提取:基本块内循环优化强度削减用较快的操作代替较慢的操作代码外提将循环不变计算移出循环与机器有关的优化寄存器的利用将常用量放入寄存器，以减少访问内存的次数体系结构MIMD、SIMD、SPMD、向量机、流水机存储策略根据算法访存的要求安排：Cache、并行存储体系——减少访问冲突任务划分按运行的算法及体系结构，划分子任务(MPMD)6.目标代码生成（CodeGenerator）将中间代码转换成目标机上的机器指令代码或汇编代码确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组）制定从中间代码到目标代码的翻译策略或算法目标代码的形式具有绝对地址的机器指令汇编语言形式的目标程序模块结构的机器指令（需要链接程序）7、表格管理管理各种符号表（常数、标号、变量、过程、结构……），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种查、填表技术8、错误处理进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化）词法：拼写……语法：语句结构、表达式结构……语义：类型不匹配……编译系统词法分析语法分析语义分析中间代码代码优化目标代码错误处理符号表源程序目标程序分析综合模块分类分析：词法分析、语法分析、语义分析、中间代码生成综合：代码优化、目标代码生成辅助：符号表管理、出错处理8项功能对应8个模块词法分析器语法分析器语义分析器中间代码生成器代码优化器代码生成器position:=initial+rate*60id1:=id2+id3*60:=+*id1id2id360:=+*id1id2id360inttorealtemp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2+temp1MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1符号表position…initial…rate…1234例一个语句的翻译9编译的遍（Pass）根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。如：首遍构造语法树，二遍处理中间表示，增加信息等。遍可以和阶段相对应，也可无关单遍代码不太有效10、编译的前端与后端前端与源语言有关、与目标机无关的部分词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化后端与目标机有关的部分与机器有关的代码优化、目标代码生成1.5编译程序的生成设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。如何实现编译器？直接用可运行的代码编制——太费力！自举-使用语言提供的功能来编译该语言自身。“第一个编译器是怎样被编译的？”问题：直接在一个机上实现C语言编译器，还有别的技术么？解决：