编译原理第一章PPT教材.ppt

8/6/2019,编译原理,1,编译原理 The Principles of Compilers,8/6/2019,编译原理,2,课程基本信息,课时： 48（163/周） 成绩评定： 1、平时成绩：40%或30%：包括作业，含习题；出勤；课堂表现。 2、期末考试成绩：60%或70%,8/6/2019,编译原理,3,课程的性质及意义,课程性质： 技术基础 课程意义： “编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到。” Alfred V. Aho /aho/,8/6/2019,编译原理,4,2019/8/6,4,课程目的和基本要求 （附录）,知识： 掌握编译器的总体结构、各个组成部分的任务、各个阶段的工作原理、所要解决的问题及其采用的方法和技术。 能力： 掌握程序变换基本概念、问题描述和处理方法，增强理论结合实际能力；使学生在系统级上认识算法和系统的设计，培养系统能力.,8/6/2019,编译原理,5,2019/8/6,5,主要内容,1. 引论 2. 词法分析 3. 语法分析： 4. 语法制导翻译 5. 类型检查 6. 运行时的存储组织 7. 中间代码生成 8. 目标代码生成 9. 代码优化技术介绍,正规表达式(RE)； 有限自动机(FA：DFA与NFA); RE FA； 词法分析器及其生成器。,语言与文法；自顶向下的语法分析(LL(k)文法)， 自底向上的语法分析(LR(k)文法) 。,文法的综合属性与继承属性； 属性的计算与L属性； 属性的自下而上和自上向下的计算 。,类型与类型语言； 类型检查； 多态函数 函数与算符的重载 。,局部存储的分配； 全局栈式存储分配； 非局部名字的访问 参数传递 。,几种常用中间代码； 赋值语句及数组元素的地址计算； 布尔表达式和控制流的翻译 。,代码生成器设计中的问题； 目标机器的指令集与指令代价； 基本块和流图； 代码的生成 。,独立于机器的优化； 优化的主要类型； 数据流分析介绍； 流图中的循环 。,8/6/2019,编译原理,6,第1章 引论 Introduction,8/6/2019,编译原理,7,2019/8/6,7,计算机的语言,母语：机器语言(Machine Language)：用 0、1代码表示的机器指令系统。 汇编语言(Assemble Language)：用助记符表示的指令系统，以及伪指令和伪指令和符号地址。汇编语言又称为低级语言(Low Level Language)。 高级语言(High Level Language)：用人工语言设计的程序设计语言，其表示方法更接近于待解问题的表示方法，例如：C、FORTRAN、PASCAL、C+、JAVA、SQL、等。,8/6/2019,编译原理,8,计算机不能没有的翻译,因为机器的母语是二进制的指令集，所以要让机器懂得低级语言和高级语言就必须要有翻译者。 这样的翻译者称其为翻译程序。 担任低级程序设计语言翻译工作的程序称为汇编程序。 担任高级程序设计语言翻译工作的程序称为编译程序。,8/6/2019,编译原理,9,程序设计语言的翻译,翻译程序(Translator)： 将某一种语言描述的程序(源程序，Source Program)翻译成等价的另一种语言描述的程序(目标程序，Object Program)的程序。,翻译程序,源程序,目标程序,(*.C / *.PAS),(*.OBJ / *.EXE),8/6/2019,编译原理,10,程序设计语言的翻译,编译程序(Compiler) 将源程序完整地转换成机器语言程序或汇编语言程序，然后再处理、执行的翻译程序。 高级语言程序汇编/机器语言程序,源程序,目标程序,编译程序,8/6/2019,编译原理,11,系统支撑(System Support),编译系统 = 编译器 + 运行系统,源程序,编译器,目标程序,连接程序,运行时 的函数库,用户定义的 目标代码模块,可执行代码,8/6/2019,编译原理,12,1、识别出句子中的一个个单字； 2、分析句子语法结构； 3、初步翻译句子的含意； 4、译文修饰； 5、写出最后译文。,自然语言的翻译：,1、词法分析； 2、语法分析； 3、语义分析与中间代码生成； 4、优化； 5、目标代码生成。,程序设计语言的翻译：,语言的翻译过程,8/6/2019,编译原理,13,2019/8/6,13,编译程序的组织,前端(Front End ) 与源语言有关、与目标机无关的部分： 词法分析、语法分析、语义分析、中间代码生成、与机器无关的代码优化 后端(Back End) 与目标机有关的部分： 与机器有关的代码优化、目标代码生成,8/6/2019,编译原理,14,编译程序的前端,词法分析器,语法分析器,中间代码生成器,脱离机器优化器,表 格 管 理,出 错 处 理,语义分析器,8/6/2019,编译原理,15,编译程序的后端,编译程序在逻辑上被分成了七个阶段(Phrase)。 也可以将编译程序分为：分析、综合和管理三个部分。,目标代码生成器,表格管理,出错处理,依赖机器优化器,8/6/2019,编译原理,16,编译器技术的应用,高级语言的实现。 高级编程语言易于编程，但程序运行较慢。 低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护。 流行编程语言的大多数演变都是朝着提高抽象级别的方向。 每一轮编程语言新特征的出现都刺激编译器优化的新研究。,8/6/2019,编译原理,17,编译器技术的应用,针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要。 并行化： 重新整理指令，使得指令级并行更有效； 自动生成并行代码，使之运行于多处理器。 内存分层： 编译器优化历来集中在优化处理器执行上，但是现在更强调要使内存分层更有效。,8/6/2019,编译原理,18,编译器技术的应用,新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码。 在现代计算机体系结构研究中，在处理器设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构的特征。 编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机(RISC)的发明。,8/6/2019,编译原理,19,编译器技术的应用,程序翻译： 二进制翻译： 翻译技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码。 数据库查询解释器： 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令。,8/6/2