编译原理-计算机科学技术系.ppt

2019/12/2,华东师大信息学院计算机科学技术系,1,编译原理,华东师大计算机科学技术系杨宗源2008年,PrinciplesofCompiler,2019/12/2,华东师大信息学院计算机科学技术系,2,课程目的、学习方法和基本要求,性质专业基础课程，是计算机科学技术的基础前导课程离散数学、程序设计语言、数据结构、操作系统目的编译程序是计算机系统的基本系统软件，本课程主要介绍设计、实现编译程序时所涉及的基本原理、基本方法和基本技术。通过本课程的学习和上机实践使学生掌握构造高级程序设计语言编译程序的基本原理、结构、设计与实现技术，培养学生了解和掌握编译原理的基本原理及典型技术并具备相当的应用能力。,2019/12/2,华东师大信息学院计算机科学技术系,3,课程目的、学习方法和基本要求,知识形式语言与形式语言处理、自动机理论、形式描述方法、程序自动生成方法、数据流和控制分析方法方法系统性：前后的连接、融会贯通，避免孤立化实践性：可实现的系统软件，理论与实践相结合多样性：实现技术多样、表示形式多样基本性：举一反三，在掌握多种方法、算法和表示形式的同时正确把握基本性,2019/12/2,华东师大信息学院计算机科学技术系,4,课程目的、学习方法和基本要求,本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型,2019/12/2,华东师大信息学院计算机科学技术系,5,课程目的、学习方法和基本要求,主要特点抽象和形式化、理论证明和构造性前半部分（词法、语法分析）实现技术、形式化后半部分（语义分析、代码优化、生成）希望,2019/12/2,华东师大信息学院计算机科学技术系,6,教材及主要参考书目,教材胡伦骏等编译原理电子工业出版社2005年参考书目侯文永、张冬茉编译原理电子工业出版社2002年杨宗源编译原理习题精选分析与解答清华大学出版社2003徐国定杨宗源编译程序构造华东师范大学出版社1989.10KennethC.LoudonCompilerConstruction:PrinciplesandPracticePwsPublishingCompany1997AlfredV.AhoRaviSethiJeffreyD.UllmanCompilersPrinciples,Techniques,andToolsAddison-Wesley,Reading,Mass,1986CharlesN.FischerRichardJ.LeBlanc,Jr.CraftingACompilerTheBenjamin/CummingsPublishingCompany1988DickGrune,HenriEBal,CerielJHJacobs,KoenGLangendoen,ModernCompilerDesignJohnWiley&Sons,Ltd,2000,2019/12/2,华东师大信息学院计算机科学技术系,7,第一章编译概述,1.1语言处理与编译程序1.1.1程序设计语言的引入是解决人机对话鸿沟的一个里程碑,2019/12/2,华东师大信息学院计算机科学技术系,8,语言处理与编译程序,1.1.2程序设计语言分类程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。一般可以划分：低级语言低级语言是面向机器的语言，它是为特定的计算机系统设计的语言。如：机器指令、汇编语言是低级语言。高级语言高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示。如：FORTRAN、Pascal、C、JAVA等等高级语言。其他语言如：控制命令语言、查询语言、脚本语言等。,2019/12/2,华东师大信息学院计算机科学技术系,9,语言处理与编译程序,1.1.3语言处理程序翻译程序(Translator)翻译程序是一种语言处理程序，它将输入的用程序设计语言（源语言）书写的程序（源程序）转换为等价的用另一种语言书（目标语言）写的程序（目标程序）。若源语言是汇编语言，目标语言是机器语言，称这种翻译程序为汇编程序。若源语言是高级语言，目标语言是低级语言，称这种翻译程序为编译程序。若源语言是高级语言，目标语言是另一种高级语言，称这种翻译程序为转换程序。,2019/12/2,华东师大信息学院计算机科学技术系,10,语言处理与编译程序,解释程序（Interpreter）解释程序是一种语言处理程序，它对源程序逐个语句地进行分析，并根据每个语句的含义执行语句指定的功能。编译程序（翻译程序）与解释程序主要的不同是：编译程序将先生成目标程序，再执行目标程序，而解释程序不生成目标程序，边翻译、边执行。形象地说，这类似于自然语言中的“笔译”与“口译”。翻译与解释相结合的方法是一种不错的方法：即先将源程序翻译为中间语言表示的代码，然后再解释执行。例如，JAVA语言的源程序翻译为一种称为Bytecode的中间代码，再通过JAVA虚拟机解释执行。,2019/12/2,华东师大信息学院计算机科学技术系,11,语言处理与编译程序,编译程序的一个实例FACOMM-340的C语言编译器,2019/12/2,华东师大信息学院计算机科学技术系,12,语言处理与编译程序,相关说明CV、CPP与语言、机器相关，ASM、LINK与机器相关，而CSA、CSG组成了编译程序的主体。称CSA为编译器的前端独立于目标语言，称CSG为编译器的后端面向目标语言。遍在编译过程中，扫描一遍源程序（输入文件），经处理形成一个输出文件，称为一遍。合理地决定“遍数”，可提高效率（时/空）LINK程序linker：连接程序：多个不同的目标文件一个可执行文件loader：装配程序：相对地址绝对地址,2019/12/2,华东师大信息学院计算机科学技术系,13,语言处理与编译程序,编译器所在的集成环境编辑器（Editor)调试器（Debugger)描述器（Profiler)项目管理器（ProjectManager)等,2019/12/2,华东师大信息学院计算机科学技术系,14,编译程序概貌,1.2编译过程和编译程序的基本结构抽象地看：,2019/12/2,华东师大信息学院计算机科学技术系,15,这是一个逻辑模型,独立于具体的语言和机器,2019/12/2,华东师大信息学院计算机科学技术系,16,以赋值语句pos:=init+rate*60为例来了解编译的全过程词法分析(LexicalAnalysis)功能：a)扫描源程序的字符串，识别出意义独立的最小的词法单位单词（Token）。b)删除注解、空格、回车及与输入介质有关的符号。c)报告词法错误。如上述赋值语句经过词法分析后输出为如下单词：(ID,pos)(OP,:=)(ID,init)(OP,+)(ID,rate)(OP,*)(CONST,60),2019/12/2,华东师大信息学院计算机科学技术系,17,语法分析(SyntaxAnalysis)功能：对输入的单词串，按程序设计语言的语法规则，检查源程序句法正确性。例如某语言关于赋值语句的语法规则是：赋值语句是：ID:=EXPID、CONST是EXP若EXP1和EXP2是EXP，则EXP1+EXP2、EXP1*EXP2、(EXP1)是EXP。可以通过自顶向下或自底向上的句法分析方法，建立分析树（又称句法树、推导树）进行句法分析。,2019/12/2,华东师大信息学院计算机科学技术系,18,对此例，分析树为：,2019/12/2,华东师大信息学院计算机科学技术系,19,语义分析(SemanticAnalysis)功能：检查语义的正确性，完成语义解释及必要的转换。例如：此例中各变量的数据类型是float，由于rate与60的类型不同就应该进行转换，即将60转换为60.0。中间代码生成（IntermediateCodeGeneration）功能：将单词串转换为等价的中间代码串。常见的中间代码有：四元组、三元组、逆波兰（后缀）表示等。上例中的赋值语句可翻译为（四元组形式）：(float，60，t1)(*，ID.rate，t1，t2)(+，ID.init，t2，t3)(:=,t3,ID.pos)其中t1，t2，t3是临时变量、ID.x是x在符号表中的位置。,2019/12/2,华东师大信息学院计算机科学技术系,20,代码优化(CodeOptimization)功能：以提高目标代码运行的时/空间效率为目的的对中间代码进行等价变换。常见的方法有：删除无用赋值和多余运算、常量合并、运算强度削弱、代码外提、复写传播等等。此例中的中间代码通过优化可为：(*，ID.rate，60.0，t1)(+，ID.init，t1，t2)(:=，t2，ID.pos)代码生成（CodeGeneration）功能：将中间代码串转换为汇编代码或机器指令。,2019/12/2,华东师大信息学院计算机科学技术系,21,代码生成,此例中优化后的中间代码可生成如下的汇编代码：LOADR0,drate(R3)LOADR1,d60.0(R3)MULTR0,R1LOADR0,dinit(R3)ADDR0,R1STORER1,dpos(R3)其中R3是基地址寄存器，dx是x的位移（相对于R3的内容）。,2019/12/2,华东师大信息学院计算机科学技术系,22,出错处理(ErrorHandle)功能：显示出错的位置、性质，限制出错的影响，为尽可能多地发现错误做些恢复工作。符号表管理(Symbol-TableManagement)功能：管理源程序中各种数据对象及其各种属性，提供包括生成、查询、更新等各种功能。,2019/12/2,华东师大信息学院计算机科学技术系,23,编译程序的生成方法,1.3编译程序的生成方法1.3.1手工生成完全由人采用低级语言开发编译程序，工作量很大。1.3.2自动生成利用自动生成工具开发编译程序。如：