编译原理---第1章

1、编译原理国家精品课程国家精品课程学时与参考教材学时与参考教材v学时：学时：44+1244+12学时学时v教材教材蒋宗礼，姜守旭，编译原理，高等教育出版社，国蒋宗礼，姜守旭，编译原理，高等教育出版社，国家家“十一五十一五”规划教材，规划教材，20102010年年2 2月月v参考书参考书1. 1.陈火旺等，程序设计语言编译原理（第陈火旺等，程序设计语言编译原理（第3 3版），国防版），国防工业出版社，工业出版社，2003.8.2003.8.印刷印刷2.2.Alfred Aho ect.Alfred Aho ect.， 编译原理，赵建华等译，机械工编译原理，赵建华等译，机械工业出版社，业出版社，20

2、09.12009.1. .3.3. Alfred Aho ect. Alfred Aho ect.，编译原理，李建中等译，机械工，编译原理，李建中等译，机械工业出版社，业出版社，2003.8.(2003.8.(原版原版- -邮电出版社邮电出版社) )4.4.Kenneth C. LoudenKenneth C. Louden，编译原理及实践，冯博琴等译，编译原理及实践，冯博琴等译，机械工业机械工业出版社，出版社，2001.2.2001.2.印刷印刷编译原理国家精品课程国家精品课程v 参考教材参考教材( (续续) )：6.6. 金成植，编译程序构造原理和实现技术，高等金成植，编译程序构造原理和实

3、现技术，高等教育出版社，教育出版社，2000.7.200. 高仲仪等，编译技术，西北工业大学出版社，高仲仪等，编译技术，西北工业大学出版社，1985.91985.98.8. 何炎祥等，编译原理，华中理工大学出版社，何炎祥等，编译原理，华中理工大学出版社，2000.10. 2000.10. 9.9. P.M.P.M.刘易斯，编译程序设计理论，科学出版社，刘易斯，编译程序设计理论，科学出版社，1984.5.1984.5.2学时与参考教材学时与参考教材编译原理国家精品课程国家精品课程课程网站课程网站3教学教学目的目的是一门是一门非常好非常好的课程的课程18个方面个方面助你成长助你成长编

4、译原理国家精品课程国家精品课程课程网站课程网站v路径：进入北工大主页路径：进入北工大主页http:/http:/，进入，进入“教育在教育在线线”，再进入，再进入“精品课程精品课程”，继续进入，继续进入“编译原理编译原理”4全程录像讲稿全程录像讲稿（最新）、有（最新）、有关资料关资料编译原理国家精品课程国家精品课程主要内容主要内容q 编译系统及其设计概述编译系统及其设计概述( (总体结构总体结构、设计方法；、设计方法；3 3) )q 语言与文法语言与文法( (文法、推导、归约、分类、分析树；文法、推导、归约、分类、分析树；5 5) )q 词法分析词法分析( (词法分析、正规式与正规文法、词法分析

5、、正规式与正规文法、DFADFA状态转移图；状态转移图；6 6) )q 语法分析语法分析( (自顶向下自顶向下：LL(1)LL(1)、递归子程序；、递归子程序；自底向上自底向上：算符优先、：算符优先、LRLR；1313) )q 语义分析语义分析( (属性文法、各种语句的属性文法、各种语句的语法制导翻译语法制导翻译；1010) )q 运行环境运行环境( (存储分配、存储分配、过程调用过程调用、符号表管理；、符号表管理；3 3) )q 代码优化与代码生成代码优化与代码生成( (基本块与流图、局部优化、驯化优化、基本块与流图、局部优化、驯化优化、代码生成；代码生成；2 2) )q 总结总结(2)(2

6、)编译原理国家精品课程国家精品课程实验安排（另行通知）实验安排（另行通知）v11 11周周1212周（周（5 5月月11 11日日5 5月月2020日）日） 星期二星期二1212节、星期四节、星期四5656节节v1313周周1414周（周（5 5月月2020日日6 6月月1 1日）日） 星期二星期二1212节可以验收节可以验收v基本要求：实现词法分析、语法分析基本要求：实现词法分析、语法分析 选作：语义分析、选作：语义分析、LRLR分析表自动生成、系统分析表自动生成、系统v1616周（周（6 6月月1515日）日） 星期二星期二1212节总结节总结编译原理国家精品课程国家精品课程成绩评定成绩评

7、定v考试必备条件考试必备条件 必须按照要求完成指定的必须按照要求完成指定的习题习题 必须通过必须通过实验系统实验系统的验收的验收v成绩成绩 平时平时20%20% 期末期末80%80%编译原理国家精品课程国家精品课程教学目的教学目的计算学科是一个宽泛的学科计算学科是一个宽泛的学科8用户用户多层虚拟系统多层虚拟系统 基本计算基本计算机系统机系统开发利用开发利用工程实现工程实现计算机理计算机理呈现呈现抽象、理论、设计抽象、理论、设计三种学科形态三种学科形态性能越来越好性能越来越好使用越来越方便使用越来越方便编译原理国家精品课程国家精品课程教学目的教学目的计算学科的定义计算学科的定义 关键：由计算机自

8、动完成关键：由计算机自动完成/ /实现自动计算实现自动计算v 对对信息描述和变换算法信息描述和变换算法的系统研究，主的系统研究，主要包括它们的理论、分析、效率、实现和应要包括它们的理论、分析、效率、实现和应用用v 计算学科的根本问题是计算学科的根本问题是什么能什么能且如何且如何被被有效地自动计算有效地自动计算v 讨论问题求解的讨论问题求解的“能行性能行性”编译原理国家精品课程国家精品课程教学目的教学目的计算学科各有分工计算学科各有分工10科学科学工程工程技术技术什么能够被有效地什么能够被有效地自动计算自动计算如何方便有效地利如何方便有效地利用系统进行计算用系统进行计算如何低成本、高效如何低成本

9、、高效地实现自动计算地实现自动计算：发现规律：发现规律：构建系统：构建系统：实现服务：实现服务计算学科计算学科涉及涉及编译原理国家精品课程国家精品课程教学目的教学目的学科基本特征学科基本特征11形式化、抽象、逻辑形式化、抽象、逻辑思维方式思维方式描述手段描述手段符号、符号变换符号、符号变换表达形式表达形式 求解途径求解途径本学科的本学科的基本教育原理基本教育原理抽象第一抽象第一程序的非物理特性程序的非物理特性编译原理国家精品课程国家精品课程教学目的教学目的计算学科本科生专业能力构成计算学科本科生专业能力构成编译原理的授课涉及上述四种能力的培养编译原理的授课涉及上述四种能力的培养12计算思维计算

10、思维算法设计算法设计程序实现程序实现系统开发系统开发公共基础系列公共基础系列基础理论系列基础理论系列程序与算法系列程序与算法系列软件系统系列软件系统系列 ( (系统级系统级的的再认识再认识与与再提高再提高) )硬件技术系列硬件技术系列实践系列实践系列学科基础能力学科基础能力工程型工程型应用型应用型科学型科学型编译原理国家精品课程国家精品课程教学目的教学目的编译原理编译原理是一门非常好的课程是一门非常好的课程vAlfred V.Aho：编写编译器的原理和技术具：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术

11、都学家的研究生涯中，本书中的原理和技术都会反复用到会反复用到v涉及的是一个比较适当的抽象层面上的数涉及的是一个比较适当的抽象层面上的数据变换（既抽象，又实际）据变换（既抽象，又实际）v既有一些具体的表示和变换算法；又是针既有一些具体的表示和变换算法；又是针对一类问题的求解（自动计算的具体体现）对一类问题的求解（自动计算的具体体现）编译原理国家精品课程国家精品课程教学目的教学目的编译原理编译原理是一门非常好的课程是一门非常好的课程v一个相当规模的、逻辑结构清晰系统的设一个相当规模的、逻辑结构清晰系统的设计（含总体结构）计（含总体结构）v“自顶向下自顶向下”和和“自底向上自底向上”的系统设计的系统

12、设计方法（思想、方法、实现）方法（思想、方法、实现）v结论：计算机专业最恰当、有效的知识载结论：计算机专业最恰当、有效的知识载体之一体之一v编译：掌握编译：掌握“编译原理编译原理”中的基本概念、中的基本概念、基本理论、基本方法，在系统级上再认识程基本理论、基本方法，在系统级上再认识程序和算法，提升计算机问题求解的水平，增序和算法，提升计算机问题求解的水平，增强系统能力，体验实现自动计算的乐趣强系统能力，体验实现自动计算的乐趣 编译原理国家精品课程国家精品课程教学要求教学要求v知识层面知识层面 掌握编译程序掌握编译程序总体结构总体结构系统能力基础系统能力基础 掌握程序变换基本概念、问题描述和处理

13、方法，掌握程序变换基本概念、问题描述和处理方法，学习有关的原理、实现方法和技术，掌握典型学习有关的原理、实现方法和技术，掌握典型方法方法 （自顶向下、自底向上、逐步求精、递归求解，目标驱动，问（自顶向下、自底向上、逐步求精、递归求解，目标驱动，问题分析、问题的抽象与形式化描述，算法设计与实现，系统构建、题分析、问题的抽象与形式化描述，算法设计与实现，系统构建、模块化模块化 ） 增强理论结合实际能力，获得更多的增强理论结合实际能力，获得更多的“顶峰体顶峰体验验” 程序实现程序实现实现能力基础实现能力基础编译原理国家精品课程国家精品课程教学要求教学要求v能力层面能力层面 理论与实践的结合能力：理论

14、指导系统实现理论与实践的结合能力：理论指导系统实现 系统能力：系统能力：在在系统级系统级上认识算法、系统的设计，上认识算法、系统的设计，从宏观到微观、从微观到宏观，从宏观到微观、从微观到宏观，提高把握系统提高把握系统的能力的能力 较大规模程序的设计与实现较大规模程序的设计与实现 形式化描述能力：修养形式化描述能力：修养“问题、形式化描述、问题、形式化描述、计算机化计算机化”问题求解典型过程，推进从问题求解典型过程，推进从“实例实例计算计算”到到“类计算类计算”和和“模型计算模型计算”的跨越的跨越 程序语言：兼顾语言描述方法、设计、应用程序语言：兼顾语言描述方法、设计、应用编译原理国家精品课程国

15、家精品课程学习方法学习方法v学习是一个过程学习是一个过程 上课、读书、复习、做作业、讨论、做实验、自上课、读书、复习、做作业、讨论、做实验、自己编程序、上机调试排错己编程序、上机调试排错是绝对必要的，不是绝对必要的，不可缺的可缺的v上课上课 课堂是本科教育的主要渠道：不要放弃自己经过课堂是本科教育的主要渠道：不要放弃自己经过多年努力争取到的权利多年努力争取到的权利 美国心理学家阿贝尔美国心理学家阿贝尔. .梅拉别思：梅拉别思：信息总效果信息总效果=文字文字27%+27%+音调音调38%+38%+面部表情面部表情35%35%编译原理国家精品课程国家精品课程v复习、做作业、讨论：勤于思考复习、做作

16、业、讨论：勤于思考 博览、多思（学而不思则罔、思而不学则怠；博览、多思（学而不思则罔、思而不学则怠；书由厚到薄、由薄到厚）、常实践书由厚到薄、由薄到厚）、常实践 思考由怀疑和答案组成。思考由怀疑和答案组成。怀疑是智慧的大门怀疑是智慧的大门，知道得越多，就越会发问，而问题就越多。知道得越多，就越会发问，而问题就越多。 发问使人进步发问使人进步学问学问v“轮子轮子”与人类的认识与人类的认识18学习方法学习方法编译原理国家精品课程国家精品课程v理论：使自己理论：使自己“站到巨人的肩膀上站到巨人的肩膀上”，并拥有一，并拥有一个个“智慧的脑智慧的脑” 增加问题求解和探索的主动增加问题求解和探索的主动性性

17、v实践：用智慧的脑，练就一双灵巧的手，开创一实践：用智慧的脑，练就一双灵巧的手，开创一个新世界个新世界希望创新性实践希望创新性实践v在理论指导下实践，在理论指导下实践，强化理论与实践相结合能力强化理论与实践相结合能力的培养的培养v读书：强化基础读书：强化基础 在独立思考之前，必须先有基础知识。所谓在独立思考之前，必须先有基础知识。所谓“获得获得基础知识基础知识”并不是形式上读过某门课程，而是将学并不是形式上读过某门课程，而是将学过的东西过的东西真正弄懂真正弄懂19学习方法学习方法编译原理国家精品课程国家精品课程学习方法学习方法v加强实践加强实践“听过的会忘记，听过的会忘记，看过的能记得，看过的

18、能记得，做过的才理解做过的才理解”20提高实践能力提高实践能力教了什么教了什么学到什么学到什么会做什么会做什么编译原理国家精品课程国家精品课程学习方法学习方法v辅导答疑辅导答疑 教师是最宝贵的资源教师是最宝贵的资源 自己要思考，以追求最大收获：习题、问题自己要思考，以追求最大收获：习题、问题v应对困难应对困难 不畏惧困难不畏惧困难 从教训到经验从教训到经验亲身体验亲身体验 要实践（作业、实验），加深理解，探讨开拓要实践（作业、实验），加深理解，探讨开拓编译原理国家精品课程国家精品课程学生的体会学生的体会v向我们展示了一个原先未曾接触过的世界。我向我们展示了一个原先未曾接触过的世界。我越来越坚信

19、在编译这个领域里，包含了越来越坚信在编译这个领域里，包含了太多前太多前人的智慧人的智慧v课中不时的小问题，让我们去课中不时的小问题，让我们去自由思考自由思考v问题不断被解决的同时，又有一个个新的问题问题不断被解决的同时，又有一个个新的问题提了出来，问题的出现恰恰是上一个方案的不提了出来，问题的出现恰恰是上一个方案的不足，这个逐渐递进，逐渐解决问题的过程好像足，这个逐渐递进，逐渐解决问题的过程好像踏着前人研究编译理论的路线，踏着前人研究编译理论的路线，不断感觉大师不断感觉大师们遇到的问题、解决问题的思路们遇到的问题、解决问题的思路编译原理国家精品课程国家精品课程学生的体会学生的体会v开阔思路，建

20、立严谨的思考方法开阔思路，建立严谨的思考方法, ,潜移默化地培养潜移默化地培养形式化描述能力和抽象思维能力形式化描述能力和抽象思维能力, , 建立和完善建立和完善系系统观和全局观统观和全局观v带给我的不只是理论知识，更重要的是带给我的不只是理论知识，更重要的是自动计自动计算算的思路的思路, ,感到了一种感到了一种“自动计算自动计算”的快乐的快乐v这门课不仅让我对编译器有了一个比较理性的认这门课不仅让我对编译器有了一个比较理性的认识与了解，让我提高了自己的编程能力，还让我识与了解，让我提高了自己的编程能力，还让我再次体会到了计算机学科的一些基本思想，再次再次体会到了计算机学科的一些基本思想，再次

21、感受到了人类的伟大感受到了人类的伟大在于在于抽象的公理系统以抽象的公理系统以及算法的巧妙及算法的巧妙编译原理国家精品课程国家精品课程第第1 1章章 引论引论v1.1 1.1 计算机语言的发展计算机语言的发展v1.2 1.2 翻译系统翻译系统v1.3 1.3 编译系统的功能分析编译系统的功能分析v1.4 1.4 编译程序总体结构编译程序总体结构v1.5 1.5 编译程序的生成编译程序的生成v1.6 1.6 编译技术的应用编译技术的应用编译原理国家精品课程国家精品课程1.1 计算机语言的发展计算机语言的发展v机器语言机器语言(Machine Language)(Machine Language)

22、0 0、1 1代码代码v汇编语言汇编语言(Assemble Language)(Assemble Language) 0 0、1 1代码与代码与助记符助记符：接近计算机硬件指令系统：接近计算机硬件指令系统v高级语言高级语言(High Level Language)(High Level Language) 语句语句定义数据、描述算法（程序）定义数据、描述算法（程序） 如：如：C C、FORTRANFORTRAN、PASCALPASCAL、C+C+、JAVAJAVA、SQL(SQL(数据定义、数据操作数据定义、数据操作) )v命令语言命令语言(Command)(Command) 以以功能封装功能

23、封装为特征为特征编译原理国家精品课程国家精品课程高级语言的分类高级语言的分类v命令式语言命令式语言(Imperative Language) FORTRAN(段结构段结构)、BASIC、Pascal(嵌套结构嵌套结构)、C、COBOL、ALGOLv函数函数( (应用应用) )式语言式语言(Functional Language) LISP、MLv逻辑式逻辑式( (基于规则基于规则) )语言语言(Logical Language) Prologv面向对象语言面向对象语言(Object-Oriented Language) Smalltalk、 Ada(程序包程序包)、 C+ 、J编译原理国家精品

24、课程国家精品课程1.2 1.2 翻译系统翻译系统v翻译程序翻译程序(Translator)将某一种语言描述的程序将某一种语言描述的程序( (源程序源程序Source Program) )翻译成翻译成等价等价的另一种语言描述的程序的另一种语言描述的程序( (目目标程序标程序Object Program) )的程序的程序27翻译程序翻译程序源程序源程序目标程序目标程序(*.C / *.PAS/*.AS)(*.OBJ / *.EXE/*.*)编译原理国家精品课程国家精品课程1.2 1.2 翻译系统翻译系统v解释程序解释程序(Interpreter)(Interpreter)口译与笔译（单句提交与整篇

25、提交）口译与笔译（单句提交与整篇提交）28源程序源程序输入数据输入数据计算结果计算结果编译原理国家精品课程国家精品课程1.2 1.2 翻译系统翻译系统v编译程序编译程序( (CompilerCompiler) )高级语言程序高级语言程序汇编汇编/ /机器语言程序机器语言程序29高级语言高级语言源程序源程序汇编汇编/机器语机器语言言目标程序目标程序编译原理国家精品课程国家精品课程1.2 1.2 翻译系统翻译系统30Compiling SystemSourceProgramCompilerObjectProgramInputRunSystem O编译原理国家精品课程国家精品课程1.2 1.2 翻译

26、系统翻译系统v其它翻译系统其它翻译系统 诊断编译程序（诊断编译程序（Diagnostic Compiler) ) 优化编译程序（优化编译程序（Optimizing Compiler) ) 交叉编译程序交叉编译程序（Cross Compiler) 可变目标编译程序（可变目标编译程序（Retargetable Compiler) ) 并行编译程序（并行编译程序（Parallelizing Compiler） 汇编程序汇编程序( (Assembler) )、交叉汇编程序、交叉汇编程序( (Cross Assembler) )、反汇编程序（、反汇编程序（Disassembler)311.2 1.2 翻

27、译系统翻译系统汇总汇总MLMLPAssemblerDisassemblerAL ALP Compiler DataHLHLPInterpreterResult32M-MachineL-LangugeP-ProgramA-AssembleH-High LevelT编译原理国家精品课程国家精品课程1.3 1.3 编译系统的功能分析编译系统的功能分析v分析分析 词法、语法、语义词法、语法、语义v翻译翻译 语句的翻译、代码生成语句的翻译、代码生成v例如：标识符左值与右值的绑定例如：标识符左值与右值的绑定(binding)(binding) 变量：存储单元；变量：存储单元；名字：值名字：值 函数：目标代

28、码序列；函数：目标代码序列；名字；入口地址名字；入口地址331.4 1.4 编译程序总体结构编译程序总体结构请参阅请参阅P5P5图图1.11.1 编译原理国家精品课程国家精品课程1. 1. 词法分析词法分析v例：例：res=fact res=fact * *(term1+term2);(term1+term2);结果结果IDNres=IDN fact*(IDNterm1 +IDN term2);编译原理国家精品课程国家精品课程1 1、词法分析、词法分析v词法分析器词法分析器 (Lexical Analyzer)(Lexical Analyzer)又叫做扫描器又叫做扫描器(Scanner)(Sc

29、anner)，完成词法分析，完成词法分析v功能功能：词法分析器从左到右扫描源程序（字符：词法分析器从左到右扫描源程序（字符串），并将其转换成单词串），并将其转换成单词( (记号记号Token)Token)串；同串；同时查词法错误，进行标识符登记时查词法错误，进行标识符登记符号表管理符号表管理v输入输入：字符串：字符串 v输出输出：( (种别码，属性值种别码，属性值) )序对序对 属性值属性值tokentoken的机内表示的机内表示v数据结构数据结构？编译原理国家精品课程国家精品课程2. 2. 语法分析语法分析res=factres=fact* *(term1+term2);(term1+ter

30、m2);37关键：让系统关键：让系统知道知道“组成规组成规则则”并按照规并按照规则分析！则分析！编译原理国家精品课程国家精品课程2 2、语法分析、语法分析v语法分析器语法分析器(Syntax Analyzer(Syntax Analyzer，又叫，又叫Parser ) Parser ) 完成语法分析完成语法分析v功能功能：实现：实现“组词成句组词成句”，构造分析树，构造分析树，指出语法错误，指导翻译指出语法错误，指导翻译v输入输入：TokenToken序列序列v输出输出：语法成分：语法成分v数据结构数据结构？编译原理国家精品课程国家精品课程3. 3. 语义分析语义分析v功能功能：分析由语法分析

31、器给出的语法单：分析由语法分析器给出的语法单位的语义位的语义获取标识符的属性：类型、作用域等获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围语义检查：运算的合法性、取值范围等等子程序的静态绑定：代码的相对地址子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址变量的静态绑定：数据的相对地址编译原理国家精品课程国家精品课程4. 4. 中间代码生成中间代码生成v中间代码中间代码(intermediate Code)(intermediate Code) 例例:id:id1 1+id+id2 2* *idid3 340三地址码的另三地址码的另一种表示形式一种表示形式T T1

32、 1=id=id2 2* *idid3 3T T2 2=id=id1 1* *T T1 编译原理国家精品课程国家精品课程波兰表示波兰表示Lukasiewicz1929/1951Lukasiewicz1929/1951年发明年发明v中缀表示中缀表示( (Infix notationInfix notation):(a+):(a+b)b)* *(-c+(-c+d)+d)+e/fe/fv波兰表示（波兰表示（Polish / Prefix / Parenthesis-free / Polish / Prefix / Parenthesis-free / Lukasiewicz notationLuka

33、siewicz notation）也就是前缀表示也就是前缀表示 + +* *+ +a b+a b+c d/efc d/ef 运算顺序从右向左运算顺序从右向左v逆波兰表示逆波兰表示( (Reverse Polish / Suffix / Postfix Reverse Polish / Suffix / Postfix notationnotation) ) 也就是后缀表示也就是后缀表示 a b +a b +c d +c d +* *ef/+ ef/+ 运算顺序从左向右运算顺序从左向右编译原理国家精品课程国家精品课程4. 4. 中间代码生成中间代码生成编译原理国家精品课程国家精品课程4. 4.

34、中间代码生成中间代码生成v中间代码的特点中间代码的特点 简单规范简单规范 机器无关机器无关 易于优化与转换易于优化与转换v输入输入？v输出输出？v数据结构数据结构？编译原理国家精品课程国家精品课程5. 5. 代码优化代码优化v对中间代码的优化处理对中间代码的优化处理: :对代对代码进行等价变换以求提高执行码进行等价变换以求提高执行效率效率提高运行速度和节省提高运行速度和节省存储空间存储空间与机器无关的优化与机器无关的优化与机器有关的优化与机器有关的优化编译原理国家精品课程国家精品课程与机器无关的优化与机器无关的优化v局部优化局部优化 常量合并：常数运算在编译期间完成，如常量合并：常数运算在编译

35、期间完成，如8+98+9* *4 4 公共子表达式的提取公共子表达式的提取: :基本块内基本块内v循环优化循环优化 强度削减强度削减 代码外提代码外提编译原理国家精品课程国家精品课程与机器有关的优化与机器有关的优化v寄存器的利用寄存器的利用 将常用量放入寄存器，以减少访问内存的次数将常用量放入寄存器，以减少访问内存的次数v体系结构体系结构 MIMDMIMD、SIMDSIMD、SPMDSPMD、向量机、流水机、向量机、流水机v存储策略存储策略 根据算法访存的要求安排：根据算法访存的要求安排：CacheCache、并行存储体、并行存储体系系减少访问冲突减少访问冲突v任务划分任务划分 按运行的算法即

36、体系结构，划分子任务按运行的算法即体系结构，划分子任务(MPMD)(MPMD)编译原理国家精品课程国家精品课程6. 6. 目标代码生成目标代码生成v将中间代码转换成目标机上将中间代码转换成目标机上的机器指令代码或汇编代码的机器指令代码或汇编代码编译原理国家精品课程国家精品课程上次课主要内容上次课主要内容v计算机学科：什么能且如何有效地自动计算计算机学科：什么能且如何有效地自动计算 从实例计算走向类计算从实例计算走向类计算v编译是一门好课程编译是一门好课程 掌握掌握“编译原理编译原理”中的基本概念、基本理论、基本方法，中的基本概念、基本理论、基本方法，在系统级上再认识程序和算法，提升计算机问题求

37、解的在系统级上再认识程序和算法，提升计算机问题求解的水平，增强系统能力，体验实现自动计算的乐趣水平，增强系统能力，体验实现自动计算的乐趣v基本概念基本概念 翻译程序、编译程序、解释程序、汇编程序、其他翻译程序、编译程序、解释程序、汇编程序、其他 编译系统：编译程序编译系统：编译程序+运行系统运行系统4849编译程序总体结构编译程序总体结构编译原理国家精品课程国家精品课程7 7、表格管理、表格管理v管理各种符号表（常数、标号、变量、过管理各种符号表（常数、标号、变量、过程、结构程、结构） 查、填（登记、查找）源程序中出现的符号和查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的

38、各个阶段提供编译程序生成的符号，为编译的各个阶段提供信息信息 辅助语法检查、语义检查辅助语法检查、语义检查 完成静态绑定、管理编译过程完成静态绑定、管理编译过程vHashHash表、链表等各种查、填表技术表、链表等各种查、填表技术编译原理国家精品课程国家精品课程8 8、错误处理、错误处理v进行各种错误的检查、报告、纠正，以及进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部相应的续编译处理（如：错误的定位与局部化）化） 词法：拼写、定义、词法：拼写、定义、 语法：语句结构、表达式结构、语法：语句结构、表达式结构、 语义：类型不匹配、语义：类型不匹配、编译原理国家精品课程

39、国家精品课程模块分类模块分类53编译程序编译程序8项功项功能对应能对应8个模块个模块翻译翻译辅助辅助符号表管理符号表管理出错处理出错处理中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成词法分析词法分析语法分析语法分析语义分析语义分析分析分析例例: : 一个语句的翻译一个语句的翻译temp1 := inttoreal(60) temp2 := id3 *temp1temp3 := id2 +temp2id1 := temp3代码优化器代码优化器temp1 := id3 *60.0 id1 := id2 + temp1代码生成器代码生成器MOVF id3, R2MULF #60.0

40、, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1符号表符号表 position initial rate 1 12 23 34 4position:= initial + rate position:= initial + rate * * 60 60词法分析器词法分析器id1=id2+id3*60语法分析器语法分析器语义分析器语义分析器:=+*idid1 1idid2 2idid3 36060inttorealinttoreal:=+*idid1 1idid2 2idid3 36060中间代码生成器中间代码生成器编译原理国家精品课程国家精品课程9 9 编译的遍（

41、编译的遍（PassPass）v根据系统资源的状况、根据系统资源的状况、运行目标的要求运行目标的要求等，等，可以将一个编译程序设可以将一个编译程序设计成多遍扫描的形式，计成多遍扫描的形式，在每一遍扫描中，完成在每一遍扫描中，完成不同的任务不同的任务v遍可以和阶段相对应，遍可以和阶段相对应，也可无关也可无关v单遍代码不太优单遍代码不太优编译原理国家精品课程国家精品课程1010、编译的前端与后端、编译的前端与后端v前端前端 与源语言有关、与目标机无关的部分与源语言有关、与目标机无关的部分 词法分析、语法分析、语义分析与中间代码生词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化成、与机

42、器无关的代码优化v后端后端 与目标机有关的部分与目标机有关的部分 与机器有关的代码优化、目标代码生成与机器有关的代码优化、目标代码生成编译原理国家精品课程国家精品课程1.5 1.5 编译程序的生成编译程序的生成v设计目标设计目标 OPOP 目标程序小，执行速度快目标程序小，执行速度快 CompilerCompiler 编译程序小，执行速度快编译程序小，执行速度快 诊断能力强，可靠性高诊断能力强，可靠性高 可移植性好，可扩充性好可移植性好，可扩充性好v如何实现编译器？直接用可运行的代码编如何实现编译器？直接用可运行的代码编制制太费力！太费力！编译原理国家精品课程国家精品课程 形图形图v表示语言翻

43、译的表示语言翻译的 形图形图581 1）交叉编译）交叉编译(Cross Compiling)/(Cross Compiling)/移植移植 Q1Q1：A A机上有一个机上有一个C C语言编译器，是否可利语言编译器，是否可利用此编译器实现用此编译器实现B B机上的机上的C C语言编译器？语言编译器？条件：条件： 机有机有 语言的编译程序（语言的编译程序（P1)P1)目的：实现目的：实现 机的机的 语言的编译语言的编译(P3)(P3)1. 1. ( (人人) )用语言编制用语言编制B B机的编译程序机的编译程序P0(CP0(C语言语言语语 言言机器机器语言语言机器机器A A机器机器语言语言A A机

44、器机器机器机器2. (2. (机的机的C C编译编译P1)P1)编译编译P0P0，得到在，得到在A A机上可运行的机上可运行的P2(CP2(C59语言语言语言语言机器机器语言语言机器机器A A机器机器语言语言A A机器机器机器机器语言语言A A机器机器机器机器语言语言语言语言机器机器3. (3. (用机的用机的P2)P2)编译编译P0P0，得到在，得到在B B机上可运机上可运行的行的P3(CP3(C语言语言机器机器机器机器编译原理国家精品课程国家精品课程2) 2) 本机编译器利用本机编译器利用vQ2Q2： A A机上有一个机上有一个C C语言编译器，现要实现一个语言编译器，现要实现一个新语言新

45、语言NEWNEW的编译器？能利用交叉编译技术么？的编译器？能利用交叉编译技术么？61语言语言机器机器A A机器机器NEWNEW语言语言A A机器机器A A机器机器NEWNEW语言语言语语 言言A A机器机器v用用C C编写编写NEWNEW的编译，并用的编译，并用C C编译器编译它编译器编译它编译原理国家精品课程国家精品课程3) 3) 编译程序的自展技术编译程序的自展技术vQ3Q3：直接在一个机上实现：直接在一个机上实现C C语言编译器，语言编译器，还有别的技术么？还有别的技术么？v解决解决 用汇编语言实现一个子集的编译程序用汇编语言实现一个子集的编译程序(P0(P0人人) ) 用汇编程序处理该程序用汇编程序处理该程序, ,得到得到P2(P2:P2(P2:可直接运可直接运行行) ) 用子集编制语言的编译程序用子集编制语言的编译程序(P3(P3人人) ) 用用P2P2编译编译P3P3，得到，得到P4P4621. 1. 用汇编语言实现一个用汇编语言实现一个 子集的编译程序子集的编译程序(P0(P0人人) )C C语言子集语言子集汇编语言汇编语言机器语言机器语言2. 2. 用汇编程序用汇编程序(P1)(P1)处理该程序处理该程序, ,得到得到P2(P2:P2(P2:可直接运行可直接运行) )汇编语言汇编语言机器语言机器语言机