编译原理课件汇总

编译原理,主讲：闫健恩Email：yanjianen(),写在课程之前,木桶原理：一个木桶由许多块木板组成，如果组成木桶的这些木板长短不一，那么这个木桶的最大容量不取决于长的木板，而取决于最短的那块木板。蝴蝶效应：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.88、蒋宗礼等，形式语言与自动机理论，清华大学出版社，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上的shell,1.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翻译系统汇总,MLMLPAssemblerDisassemblerALALPTranslatorCompilerDataHLHLPInterpreterResult,M-MachineL-LangugeP-ProgramA-AssembleH-HighLevel,1.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,表达式,表达式,表达式,表达式,+,term1,term2,3.语义分析,功能：分析由语法分析器识别出的语法单位的语义获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址,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),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个模块,例一个语句的翻译,9编译的遍（Pass）,根据系统资源的状况、运行目标的要求等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。如：首遍构造语法树，二遍处理中间表示，增加信息等。遍可以和阶段相对应，也可无关单遍代码不太有效,10、编译的前端与后端,前端与源语言有关、与目标机无关的部分词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化后端与目标机有关的部分与机器有关的代码优化、目标代码生成,1.5编译程序的生成,设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。如何实现编译器？直接用可运行的代码编制太费力！自举-使用语言提供的功能来编译该语言自身。“第一个编译器是怎样被编译的？”,问题：直接在一个机上实现C语言编译器，还有别的技术么？解决：用汇编语言实现一个子集的编译程序(P0人)用汇编程序处理该程序,得到(P2:可直接运行)用子集编制语言的编译程序(P3人)用P2编译P3，得到P4,1)编译程序的自展技术,2)利用编译程序自动生成器,词法分析器的自动生成程序,词法规则说明,词法分析程序,(C程序),输入：词法（正规表达式）识别动作（程序段）输出：yylex()函数,语法分析器的自动生成程序,语法规则说明,语法分析程序,(C程序),输入：语法规则（产生式）语义动作（程序段）输出：yyparse()函数,1.6编译技术的应用,把复杂数据看作一条语句数据格式的分析利用词法分析、语法分析方法数据处理的框架基于语法制导的语义处理框架编译技术可以用于各种复杂数据的分析处理,1.6编译技术的应用,语法制导的结构化编辑器程序格式化工具软件测试工具程序理解工具高级语言的翻译工具,例1-1,DOS命令date的输出格式例：9-2-1993、09-03-1993、9-03-93语法datemonth-day-year词法monthDIGITDIGIT|DIGITdayDIGITDIGIT|DIGITyearDIGITDIGIT|DIGIIDIGITDIGITDIGIT,例1-1（续）,语义year(年)、month(月)、day(日)语义约束条件0month.value130day.value32，31，300:返回GT13”OUT(GT,NULL);“=”OUT(GE,NULL);%OUT(intc,char*val),本章总结,词法从组成源程序的字符行中寻找出单词，并给出它们的种别和属性输出二元组序列高级语言的单词组成一个3型语言3型语言可以用RE、RG、FA描述FA的状态转移图，可以被用来指导相应的词法分析器的实现,本章总结,3型语言相应的理论指导人们构造出了高级语言的词法分析器的自动生成器如：Lex,实验报告要求,实验题目实验目的实验内容和要求给出语言的词法规则描述标识符、关键字、整常数、字符常数、浮点常数单界符：，：，双界符：/*，:=，注释出错处理：位置、类型等数据结构设计：符号表、关键字等状态转换图和程序框图测试测试样例输出结果,语法分析,回顾一个语句的翻译,P483附录：Pascal子集的词法和语法,第四章语法分析1,语法分析方法递归子程序法自顶向下预测分析法(LL（1）)算符优先分析法自底向上LR(0)、SLR(1)LR(1)、LALR,TopDown,BottomUp,文法产生语言,自动机识别语言,从根开始，逐步为某语句构造一棵语法树,相反，将一句子归约为开始符号,假定文法是压缩的：即删除了单位产生式和无用产生式。,4.1语法分析的功能,检查由扫描器输出的单词符号序列是否符合该语言的文法句子,分析器的输入：Token序列分析器的输出分析树出错处理:定位、续编译,分析方法自顶向下（递归下降、预测分析)自底向上（算符优先、LR分析器）,4.2自顶向下分析面临的问题与CFG的改造,一、自上而下的分析从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。从树根S开始，构造所给输入符号串的语法树例：G为：SxAyA*|*，输入串：x*y,SxAy,x*y,S,二、存在问题回溯,SxAyx*y,x*y,SxAyx*y匹配成功,x*y,发现不匹配,需要回退,输入串x*ySxAyA*|*,存在回溯的原因,文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。,二、存在问题左递归问题,文法SSay|*与它的句子*ayay,*ayay,S*不对！,SSaySayaySayayaySayayayay,一个无限循环！,二、重要问题左递归问题,例CFG:简单算术表达式的文法（语法）EE+T|E-T|TTT*F|T/F|FF(E)|idNE,T,F,P,FUN,LTid,+,-,*,/,(,)E,三、重要概念回顾,推导:(依据：)最左(Left-most)推导最左分析左句型最左推导对应最右归约最右(Right-most)推导最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）二义性(先天二义性语言、二义性文法),四、消除二义性,例：简单算术表达式的文法二义性文法EE+E|E-E|E*E|E/E|(E)|id非二义性文法EE+T|E-T|TTT*F|T/F|FF(E)|id改造方法：使文法含有更多的信息，引入语法变量,四、消除二义性,再例：If语句SifEthenSSifEthenSelseSSother设执行下列语句前b=0,Ifa0thenifa0thenb=1elseb=-1当a=1时,b=1;当a=-1时，b=-1Ifa0thenifa0thenb=1elseb=-1当a=1时,b=1;当a=-1时，b=0,一个句子有两棵不同的语法树,SSEESSIfa0thenifa0thenb=1elseb=-1SSEESSIfa0thenifa0thenb=1elseb=-1,四、消除二义性,重写文法：引入新的语法变量SU|MUifEthenSUifEthenMelseUMifEthenMelseM|other,每个else与前面最近的没有配对的then配对，即：出现在then和else之间的语句必须是配对的,按照改造后的文法构造的语法树,SUSMEEMMIfa0thenifa0thenb=1elseb=-1,MifEthenMelseM|other,五、消除左递归,无法根据左递归文法进行自顶向下的分析Aa1a2aian直接左递归AA当前变量输入指针(栈顶、最左变量),间接左递归A+A左递归的消除方法将AA|替换为AA和AA,例：表达式文法直接左递归的消除,EE+TTTT*FFF(E)id,ETEE+TE|TFTT*FTF(E)id,例：间接左递归的消除,SAc|cABb|bBSa|a将B的定义代入A产生式得：ASab|ab|b将A的定义代入S产生式得:SSabc|abc|bc|c消除直接左递归：SabcS|bcS|cSSabcS|删除“多余的”产生式：ASab|ab|b和BSa|a结果：SabcS|bcS|cSSabcS|,消除左递归的一般方法,用产生式组A1B|2B|nBB1B|2B|nB|替换产生式组AA1|A2|An|1|2|m其中：B为新变量，相当于A消除左递归的算法见P135的算法4.19为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归,六、解决回溯问题提取左因子,例：if语句的原始文法SifEthenS|ifEthenSelseS|other影响分析:遇到if时难以判断用哪一个产生式进行匹配（推导）存在左因子ifEthenS,左因子提取方法,将形如A1|2|n|1|2|m的规则改写为AA|1|2|m和A1|2|n结果：SifEthenSS|otherS|elseS,七、CFG的使用限制,没有一种方法能够有效地分析所有上下文无关文法存在无法处理的型文法(CFG)每种方法能够处理一部分上下文无关文法每种方法都有适用范围,八、常用文法与分析方法,LL文法和LR文法都是CFG的子集(无二义性)可用不同的文法来描述同一语言对于不同的文法，可用不同的分析方法LL文法递归下降分析法、预测分析法LR文法LR分析法LL文法多用于编译的手工实现LR文法多用于编译的自动生成,4.3自顶向下的分析方法,基本思想寻找输入符号串的最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树,例1：表达式文法G：ETEE+TETFTT*FTF(E)id对于句子：id+id*id，按照最左推导过程，构造分析树,例2：给定文法G：ScAdAab|a对于句子cad，是否为该文法定义语言的句子？,id+id*id最左推导与语法树的生成对应,id,id,id,1、ETE,2、TFT,3、Fid,4、T,5、E+TE,6、TFT,7、Fid,8、T*FT,9、Fid,10、T,11、E,id+id*id的最左推导再现,ETEETEFTETFTidTEFididETid+TEE+TEid+FTETFTid+idTEFidid+id*FTET*FTid+id*idTEFidid+id*idETid+id*idE,候选式的确定与回溯,给定文法ScAdAab|a?句子cad是该文法定义语言的句子SScAdcAdaba产生式(候选式)的选择与回溯(Backtracking)：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式（右部）左端第一个符号相同，则分析程序无法根据当前输入符号选择产生式，只能试探。,无回溯的条件,设A1|2|n是所有的A产生式如果各个i能推导出的首终结符各不相同，则可以构造无回溯的分析。,自顶向下分析希望文法满足的条件,从左到右扫描输入串，寻找它的一个最左推导；对于G的每个非终结符A，当A有多个不同的候选式时，在选择产生某个终结符号时能唯一选定一个。,4.3.1FIRST和FOLLOW集,First集的定义对于(TN)*定义:的首符号集FIRST()=a|*a，aT*,求文法非终结符的FIRST集方法,1)对X为终结符，则FIRST(X)=X；2)对XN，则FIRST(X)：a|XaP；XPFIRST(X)=a|XaP；XP,3)对XN，重复如下过程，直到所有FIRST集不变若XYP，且YN，则FIRST(X)=FIRST(X)(FIRST(Y)-)；若XY1YnP，且Y1.Yi-1*，则对k=1到i-1:FIRST(X)=FIRST(X)(FIRST(Yk)-)；若Y1.Yn*，则FIRST(X)=FIRST(X)。,例表达式文法的语法符号的FIRST集,FIRST(F)=（,idFIRST(T)=FIRST(F)=（,idFIRST(E)=FIRST(T)=（,idFIRST(E)=+，FIRST(T)=*,FIRST(+)=+,FIRST(*)=*FIRST(（)=（FIRST(）)=）FIRST(id)=id,ETEE+TE|TFTT*FT|F(E)|id,求FIRST()的算法,令=X1Xn初值FIRST()=FIRST(X1)-;k=1;循环whileFIRST(Xk)结束处理ifk=na=当前输入符号；ifXT#thenifX=athenifX#then将X弹出,且前移输入指针elseerrorelseifMX,a=Y1Y2Ykthen将X弹出;依次将YkY2Y1压入栈；输出产生式XY1Y2YkelseerroruntilX=#,预测分析法,1）构造文法2）改造文法：消除二义性、消除左递归、提取左因子3）求每个候选式的FIRST集和变量的FOLLOW集4）检查是不是LL(1)文法若不是LL(1),说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”5）构造预测分析表6）实现预测分析器,出错处理问题,对语法变量A，如果MA,a无定义，并且a属于FOLLOW(A)，则增加MA,a为“同步点”(synch)详见教材P145,关键是同步记号的选择,把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合。把高层结构的开始符号加到低层结构的同步记号集合中。把FIRST(A)的终结符加入A的同步记号集合。如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式。如果终结符在栈顶而不能匹配，弹出此终结符。,预测分析中的错误恢复,错误恢复当预测分析器报错时，表示输入的串不是句子。对于使用者而言，希望预测分析器能够进行恢复处理后继续语法分析过程，以便在一次分析中找到更多的语法错误。但是有可能恢复得并不成功，之后找到的语法错误有可能是假的。进行错误恢复时可用的信息：栈里面的符号，待分析的符号两类错误恢复方法：恐慌模式短语层次的恢复,恐慌模式,基本思想语法分析器忽略输入中的一些符号，直到出现由设计者选定的某个同步词法单元；解释：语法分析过程总是试图在输入的前缀中找到和某个非终结符号对应的串；出现错误表明现在已经不可能找到这个非终结符号（程序结构）的串。如果编程错误仅仅局限于这个程序结构，那么我们可以考虑跳过这个程序结构，假装已经找到了这个结构；然后继续进行语法分析处理。同步词法单元就是这个程序结构结束的标志。,同步词法单元的确定,非终结符号A的同步集合的启发式规则FOLLOW(A)的符号加入到非终结符号A的同步集合中这些符号的出现可能表示之前的那些符号是错误的A的串；将高层次的非终结符号对应串的开始符号加入到较低层次的非终结符号的同步集合比如语句的开始符号，if，while等可以作为表达式的同步集合；FIRST(A)中的符号加入到非终级符号A的同步集合。碰到这些符号时，可能意味着前面的符号是多余的符号如果A可以推导出空串，那么把此产生式当作默认值。在匹配时出现错误，可以直接弹出相应的符号；哪些符号需要确定同步集合需要根据特定的应用而定。,恐慌模式的例子（1）,对文法4.28对表达式进行语法分析时，可以直接使用FIRST、FOLLOW作为同步集合。我们为E、T和F设定同步集合；空条目表示忽略输入符号；synch表木表示忽略到同步集合，然后弹出非终结符号；终结符号不匹配时，弹出栈中终结符号；,FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#,恐慌模式的例子（2）,错误输入：）i