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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,编译原理,华东师大计算机科学技术系,2008年,Principles of Compiler,9/13/2024,1,课程目的、学习方法和基本要求,性质,专业基础课程，是计算机科学技术的基础,前导课程,离散数学、程序设计语言、数据结构、操作系统,目的,编译程序是计算机系统的基本系统软件，本课程主要介绍设计、实现编译程序时所涉及的基本原理、基本方法和基本技术。通过本课程的学习和上机实践使学生掌握构造高级程序设计语言编译程序的基本原理、结构、设计与实现技术，培养学生了解和掌握编译原理的基本原理及典型技术并具备相当的应用能力。,9/13/2024,2,课程目的、学习方法和基本要求,知识,形式语言与形式语言处理、自动机理论、形式描述方法、程序自动生成方法、数据流和控制分析方法,方法,系统性：前后的连接、融会贯通，避免孤立化,实践性：可实现的系统软件，理论与实践相结合,多样性：实现技术多样、表示形式多样,基本性：举一反三，在掌握多种方法、算法和表 示形式的同时正确把握基本性,9/13/2024,3,课程目的、学习方法和基本要求,本专业人员4种基本的专业能力,计算思维能力,算法的设计与分析能力,程序设计和实现能力,计算机软硬件系统的认知、分析、设计与应用能力,计算思维能力,逻辑思维能力和抽象思维能力,构造模型对问题进行形式化描述,理解和处理形式模型,9/13/2024,4,课程目的、学习方法和基本要求,主要特点,抽象和形式化、理论证明和构造性,前半部分（词法、语法分析）,实现技术、形式化,后半部分（语义分析、代码优化、生成）,希望,“知其然，不知其所以然”,“知其所以然”,9/13/2024,5,教材及主要参考书目,教材,胡伦骏等 编译原理电子工业出版社 2005年,参考书目,侯文永、张冬茉,编译原理,电子工业出版社,2002,年,杨宗源,编译原理习题精选分析与解答,清华大学出版社,2003,徐国定 杨宗源,编译程序构造,华东师范大学出版社,1989.10,Kenneth C. Loudon Compiler Construction: Principles and Practice,Pws,Publishing Company 1997,Alfred V.,Aho,Ravi,Sethi,Jeffrey D.,Ullman,Compilers Principles, Techniques, and Tools Addison-Wesley, Reading, Mass, 1986,Charles N. Fischer Richard J. LeBlanc, Jr. Crafting A Compiler The Benjamin/Cummings Publishing Company 1988,Dick,Grune, Henri E Bal,Ceriel,J H,Jacobs,Koen,G,Langendoen, Modern Compiler Design John Wiley & Sons, Ltd, 2000,9/13/2024,6,第一章 编译概述,1.1,语言处理与编译程序,1.1.1 程序设计语言的引入是解决人机对话鸿沟的一个里程碑,语言处理程序,自然语言,数学概念,与符号,程序设计语言,机器指令,人类的“计算”思维,形式表示方法,计算机的“计算”方式,9/13/2024,7,语言处理与编译程序,1.1.2 程序设计语言分类,程序设计语言是遵守一定规范的、描述“计算”（,Computing,）过程的形式语言。一般可以划分,：,低级语言,低级语言是面向机器的语言，它是为特定的计算机系统设计的语言。如：机器指令、汇编语言是低级语言。,高级语言,高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示。如：,FORTRAN,、,Pascal,、,C,、,JAVA,等等高级语言,。,其他语言,如：控制命令语言、查询语言、脚本语言等。,9/13/2024,8,语言处理与编译程序,1.1.3 语言处理程序,翻译程序,(Translator),翻译程序是一种语言处理程序，它将输入的用程序设计语言（源语言）书写的程序（源程序）转换为等价的用另一种语言书（目标语言）写的程序（目标程序）。,若源语言是汇编语言，目标语言是机器语言，称这种翻译程序为,汇编程序,。,若源语言是高级语言，目标语言是低级语言，称这种翻译程序为,编译程序,。,若源语言是高级语言，目标语言是另一种高级语言，称这种翻译程序为,转换程序,。,9/13/2024,9,语言处理与编译程序,解释程序（,Interpreter,）,解释程序是一种语言处理程序，它对源程序逐个语句地进行分析，并根据每个语句的含义执行语句指定的功能。,编译程序（翻译程序）,与解释程序主要的不同是：编译程序将先生成目标程序，再执行目标程序，而解释程序不生成目标程序，边翻译、边执行。形象地说，这类似于自然语言中的“笔译”与“口译”。,翻译与解释相结合的方法是一种不错的方法,：即先将源程序翻译为中间语言表示的代码，然后再解释执行。例如，JAVA语言的源程序翻译为一种称为Bytecode的中间代码，再通过JAVA虚拟机解释执行。,9/13/2024,10,语言处理与编译程序,编译程序的一个实例,FACOM M-340的C语言编译器,程序名,意义,功能,CV,替换程序,、$等字符的替换,CPP,预处理程序,#include、#define等的处理,CSA,词法、语法、语义分析程序,生成中间代码,CCG,代码生成程序,生成汇编指令,ASM,汇编程序,生成二进制机器指令,LINK,连接装配程序,生成可执行程序,9/13/2024,11,语言处理与编译程序,相关说明,CV,、,CPP,与语言、机器相关，,ASM,、,LINK,与机器相关，而,CSA,、,CSG,组成了编译程序的主体。,称,CSA,为编译器的前端独立于目标语言，称,CSG,为编译器的后端面向目标语言。,遍,在编译过程中，扫描一遍源程序（输入文件），经处理形成一个输出文件，称为一遍。,合理地决定“遍数”，可提高效率（时,/,空）,LINK,程序,linker,：,连接程序：,多个不同的目标文件 一个 可执行文件,loader,：,装配程序：相对地址 绝对地址,9/13/2024,12,语言处理与编译程序,编译器所在的集成环境,编辑器（Editor),调试器（Debugger),描述器（Profiler),项目管理器（Project Manager)等,9/13/2024,13,编译程序概貌,1.2 编译过程和编译程序的基本结构,抽象地看：,源程序（S）,编译程序（C,）,目标程序（T）,出错信息（E）,9/13/2024,14,这是一个逻辑模型,独立于具体的语言和机器,9/13/2024,15,以赋值语句 pos:=init+rate*60 为例来了解编译的全过程,词法分析,(Lexical Analysis),功能：,a) 扫描源程序的字符串，识别出意义独立的最小的词法单位单词（Token）。,b) 删除注解、空格、回车及与输入介质有关的符号。,c) 报告词法错误。,如上述赋值语句经过词法分析后输出为如下单词：,(ID,pos) (OP,:=) (ID,init) (OP,+) (ID,rate) (OP,*) (CONST,60),9/13/2024,16,语法分析,(Syntax Analysis),功能：对输入的单词串，按程序设计语言的语法规则，检查源程序句法正确性。,例如某语言关于赋值语句的语法规则是：,赋值语句是：,ID:=EXP,ID,、,CONST,是,EXP,若,EXP1,和,EXP2,是,EXP,，则,EXP1+EXP2,、,EXP1*EXP2,、,(EXP1),是,EXP,。,可以通过自顶向下或自底向上的句法分析方法，建立分析树（又称,句法树、推导树）进行句法分析。,9/13/2024,17,对此例，分析树为：,9/13/2024,18,语义分析,(Semantic Analysis),功能：检查语义的正确性，完成语义解释及必要的转换。,例如：此例中各变量的数据类型是,float,，由于,rate,与,60,的类型不同就应该进行转换，即将,60,转换为,60.0,。,中间代码生成,（,Intermediate Code Generation,）,功能：将单词串转换为等价的中间代码串。,常见的中间代码有：四元组、三元组、,逆波兰（后缀）表示等。,上例中的赋值语句可翻译为（四元组形式）：,(float， ，60，t1) (*，ID.rate，t1，t2),(+，ID.init，t2，t3) (:=,t3, ,ID.pos),其中,t1，t2，t3,是临时变量、,ID.x,是,x,在符号表中的位置。,9/13/2024,19,代码优化,(Code Optimization),功能：以提高目标代码运行的时/空间效率为目的 的对中间代码进行等价变换。,常见的方法有：删除无用赋值和多余运算、常量合并、运算强度削弱、代码外提、复写传播等等。,此例中的中间代码通过优化可为：,(*，ID.rate，60.0，t1) (+，ID.init，t1，t2),(:=，t2， ，ID.pos),代码生成 （Code Generation）,功能：将中间代码串转换为汇编代码或机器指令。,9/13/2024,20,代码生成,此例中优化后的中间代码可生成如下的汇编代码：,LOAD R0, d,rate,(R3),LOAD R1, d,60.0,(R3),MULT R0, R1,LOAD R0, d,init,(R3),ADD R0, R1,STORE R1, d,pos,(R3),其中,R3,是基地址寄存器，,d,x,是,x,的位移（相对于,R3,的内容）。,9/13/2024,21,出错处理,(Error Handle),功能：显示出错的位置、性质，限制出错的影响，为尽可能多地发现错误做些恢复工作。,符号表管理,(Symbol-Table Management),功能：管理源程序中各种数据对象及其各种属性，提供包括生成、查询、更新等各种功能。,9/13/2024,22,编译程序的生成方法,1.3 编译程序的生成方法,1.3.1 手工生成,完全由人采用低级语言开发编译程序，工作量很大。,1.3.2 自动生成,利用自动生成工具开发编译程序。如：,LEX 词法分析程序的自动生成程序,YACC、LLgen 语法分析程序的自动生成程序,GAG、CGSS 代码生成程序的自动生成程序,9/13/2024,23,1.3.3 其他编译模式,前面讨论的编译模式称为“完全编译”。,其他编译模式有：,交互式编译,允许通过交互方式处理源程序中的错误，及时改错。允许部分或逐步测试。,增量编译,允许在修改了部分程序结构后仅对该修改部分重新编译，而不一定对整个程序进行编译。,问题：如何实现？,9/13/2024,24,