第1章编译程序基本概念

《第1章编译程序基本概念》由会员分享，可在线阅读，更多相关《第1章编译程序基本概念（20页珍藏版）》请在金锄头文库上搜索。

1、编译程序的设计原理与实现编译程序的设计原理与实现如何让计算机如何让计算机认识认识、理解、理解和和执行执行高级程序设计语言？高级程序设计语言？自我介绍自我介绍课件课件课件课件: :compiler_compiler_ password:2008happy password:2008happy 网易网盘网易网盘网易网盘网易网盘-我的文档我的文档我的文档我的文档EmailEmail：刘洪娟：刘洪娟：刘洪娟：刘洪娟：办公室：办公室：办公室：办公室：综合楼综合楼综合楼综合楼303303办公电话：办公电话：办公电话：办公电话：8368083183680831 教材与参考书教材与参考书l教材：教材： 胡伦骏

2、等：胡伦骏等：编译原理编译原理（第（第2版），电子工版），电子工业出版社业出版社 。l参考书：参考书：美美 Alfred V.Aho, Ravi Sethi Jeffrey, D. Ullman著著. 李建中，姜守旭译：李建中，姜守旭译：编译原理编译原理，机械工业出，机械工业出版社，版社，2003-1。美美 Kenneth C.Louden著，冯博琴等译：著，冯博琴等译：编译原编译原理及实践理及实践，机械工业出版社，机械工业出版社，2002-2。陈火旺等：陈火旺等：程序设计语言编译原理程序设计语言编译原理（第（第3版）版）， 国防工业出版社，国防工业出版社，2003-2。课程的学时分配课程的学

3、时分配（4040学时）学时）课程内容课程内容 教学教学上机上机第第1章章 编译程序基本概念程序基本概念2第第2章章 形式形式语言基言基础4第第3章章 自自动机基机基础4第第4章章 词法分析法分析24第第5章章 语法分析法分析6第第6章章 中中间代代码生成生成64第第7章章 符号表符号表组织2第第8章章 优化化2第第9章章 目目标代代码生成生成4合计合计328计计算算机机系系统统硬件硬件软件软件组成组成原理原理电子技术电子技术体系体系结构结构数字逻辑电路数字逻辑电路电路原理电路原理大学物理大学物理计算机网络计算机网络接口与通讯技术接口与通讯技术通讯概论通讯概论安全与保密安全与保密程序设程序设计语

4、言计语言汇编语言汇编语言高级语言高级语言编译原理编译原理计算理论计算理论C、C、JAVA、PB、VB系统系统软件软件操作系统操作系统DOS、Windows 、UNIX数据库数据库Access、Sybase 、Oracle数据结构数据结构人工智能人工智能应用应用软件软件开发开发软件工程软件工程算法设计与分析算法设计与分析本课程在计算机系统中的地位本课程在计算机系统中的地位 课程的名称、地位和特点课程的名称、地位和特点课程名称：课程名称：编译理论编译理论、编译原理编译原理、编译结构编译结构、编译技编译技术和编译方法等。术和编译方法等。课程地位：课程地位：编译程序（系统）和操作系统一起构成了编译程序

5、（系统）和操作系统一起构成了计算机中两大计算机中两大系统软件系统软件；一个是计算机资源的操纵者；一个是计算机资源的操纵者；而另一个是计算机软件资源的开拓者。而另一个是计算机软件资源的开拓者。课程特点课程特点: : 知识性知识性 形式语言和自动机作为本课程的两大理论基础形式语言和自动机作为本课程的两大理论基础并具有典型的应用技术并具有典型的应用技术; ; 系统性系统性 从词法、语法、语义直到目标生成，构成了语从词法、语法、语义直到目标生成，构成了语言翻译的完整体系言翻译的完整体系; ; 趣味性趣味性 关于语言处理的一些经典算法和实现技术，可关于语言处理的一些经典算法和实现技术，可以享受获取软件设

6、计方法的乐趣。以享受获取软件设计方法的乐趣。 应用性应用性 编译技术可广泛应用于文本编辑、排版系统、编译技术可广泛应用于文本编辑、排版系统、模式识别以及机器翻译等各个领域。模式识别以及机器翻译等各个领域。第第1 1章章 编译程序基本概念编译程序基本概念内容提要内容提要 1.1 1.1 什么是编译程序什么是编译程序? ? 1.2 1.2 编译程序逻辑结构编译程序逻辑结构 1.3 1.3 编译程序实现机制编译程序实现机制 1.4 1.4 编译程序的生成方法编译程序的生成方法 1.5 1.5 编译过程实例分析编译过程实例分析 . .计算机中语言的翻译程序体系计算机中语言的翻译程序体系解解 释释 程程

7、序序 图图1.1 计算机语言的层次体系计算机语言的层次体系高级语言高级语言1 1编编译译程程序序2 2反汇编程序反汇编程序汇编程序汇编程序 汇编语言汇编语言机器语言机器语言反编译程序反编译程序转换程序转换程序 高级语言高级语言2 2编译程序编译程序1 11.1 什么是编译程序？什么是编译程序？ 编译程序编译程序(compiler)是一种是一种翻译程序翻译程序，它，它特指把某种特指把某种高级程序设计语言高级程序设计语言翻译成与之等价翻译成与之等价的具体计算机上的的具体计算机上的低级程序设计语言低级程序设计语言。编译程序的执行过程编译程序的执行过程两个阶段：两个阶段： 源语言源语言编译程序编译程序

8、目标语言目标语言数据数据 结果结果运行程序运行程序编译阶段编译阶段运行阶段运行阶段图图1.2 编译程序的执行过程编译程序的执行过程 什么是什么是解释程序解释程序? ? 解释程序解释程序(interpreter)也是一种也是一种翻译程序翻译程序，它将源语言书写的源程序作为输入，它将源语言书写的源程序作为输入，解释一句后解释一句后就提交计算机执行一句就提交计算机执行一句，并不形成目标程序。，并不形成目标程序。 编译程序编译程序与与解释程序解释程序的主要区别的主要区别: : 数据数据 结果结果解释程序解释程序 图图1.3 解释程序的执行过程解释程序的执行过程 源语句源语句(1) (1) 前者前者前者

9、前者有有有有目标程序目标程序目标程序目标程序而后者而后者而后者而后者无无无无目标程序目标程序目标程序目标程序； (2) (2) 前者前者前者前者运行运行运行运行效率高效率高效率高效率高而后者而后者而后者而后者便于便于便于便于人机对话人机对话人机对话人机对话。1.2 编译程序逻辑结构编译程序逻辑结构词法词法分析分析语法语法分析分析语义语义分析分析目目标标代码代码生成生成源源语语言言目目标标语语言言错错 误误 处处 理理 程程 序序符符 号号 表表 管管 理理 程程 序序图图1.4 编译程序总体结构编译程序总体结构优化优化处理处理编译程序的编译程序的五个阶段：五个阶段： 编译程序执行过程编译程序执

10、行过程词法词法分析分析语法语法分析分析语义语义分析分析目目标标代码代码生成生成源源语语言言目目标标语语言言错错 误误 处处 理理 程程 序序符符 号号 表表 管管 理理 程程 序序 图图1.5 编译程序执行过程图解编译程序执行过程图解优化优化处理处理单词串单词串TOKEN语法树语法树语义树语义树优化优化语义树语义树前前 端端后后 端端 编译程序编译程序与与外文翻译外文翻译的类比：的类比： 词法分析词法分析词法分析词法分析 - - - - 识别识别识别识别单词单词单词单词, , , ,确认词类确认词类确认词类确认词类; ; ; ; 语法分析语法分析语法分析语法分析 - - - - 识别识别识别识

11、别短语短语短语短语和和和和句型句型句型句型的的的的 语法属性语法属性语法属性语法属性； 语义分析语义分析语义分析语义分析 - - - - 确认单词、短语和句型的确认单词、短语和句型的确认单词、短语和句型的确认单词、短语和句型的 语义特征语义特征语义特征语义特征； 代码优化代码优化代码优化代码优化 - - - - 修辞修辞修辞修辞、文本、文本、文本、文本编辑编辑编辑编辑； 代码生成代码生成代码生成代码生成 - - - - 生成生成生成生成译文译文译文译文。 I wish you success!1.3 编译程序的实现机制编译程序的实现机制遍：编译程序对源程序或等价程序从头至尾 扫描的次数。 根根

12、根根据据据据语语语语言言言言和和和和环环环环境境境境的的的的不不不不同同同同，编编编编译译译译程程程程序序序序实实实实现现现现时时时时是是是是把把把把图图图图 1.4 1.4 中中中中的各阶段划分成若干遍；典型的情况是的各阶段划分成若干遍；典型的情况是的各阶段划分成若干遍；典型的情况是的各阶段划分成若干遍；典型的情况是两遍的编译程序：两遍的编译程序：两遍的编译程序：两遍的编译程序： 第一遍第一遍第一遍第一遍: : 词法分析、语法分析和语义分析；词法分析、语法分析和语义分析；词法分析、语法分析和语义分析；词法分析、语法分析和语义分析； 第二遍第二遍第二遍第二遍: : 中间代码优化和目标代码生成。

13、中间代码优化和目标代码生成。中间代码优化和目标代码生成。中间代码优化和目标代码生成。 每遍中的各阶段的工作是每遍中的各阶段的工作是每遍中的各阶段的工作是每遍中的各阶段的工作是穿插进行穿插进行穿插进行穿插进行的，例如：的，例如：的，例如：的，例如： 使使使使语语语语法法法法分分分分析析析析器器器器处处处处于于于于核核核核心心心心位位位位置置置置。当当当当语语语语法法法法分分分分析析析析需需需需要要要要下下下下一一一一个个个个单单单单词词词词时时时时，就就就就调调调调用用用用词词词词法法法法分分分分析析析析器器器器，识识识识别别别别一一一一个个个个单单单单词词词词；一一一一旦旦旦旦识识识识别别别别

14、出出出出一一一一个个个个语语语语法法法法单单单单位位位位，就就就就调调调调用用用用语语语语义义义义分分分分析析析析器器器器，完完完完成成成成语语语语义义义义分分分分析析析析并并并并产产产产生生生生中中中中间间间间代代代代码。码。码。码。1.4 编译程序的生成方法编译程序的生成方法编译程序的生成方法：编译程序的生成方法： 利用已有的编译器利用已有的编译器 自编译方式自编译方式 移植方式：重写编译器代码的后端移植方式：重写编译器代码的后端自动生成编译程序：自动生成编译程序： 词法分析程序生成器词法分析程序生成器LEX 语法分析程序生成器语法分析程序生成器YACC 编译程序生成器编译程序生成器 输入

15、：词法规则、语法规则和语义解释输入：词法规则、语法规则和语义解释三个语言：源语言、目标语言和实现语言。三个语言：源语言、目标语言和实现语言。1.5 编译过程实例分析编译过程实例分析例：例：C程序片段程序片段 :1. 词法分析词法分析：识别单词并分类识别单词并分类 int a,b; . . . b = a + 2 * 5;v 编译过程如下：编译过程如下： 关键字关键字 (k) - (k) - intint 标识符标识符 (i) - a(i) - a，b b 常常 数数 (c) - 2(c) - 2，5 5 界界 符符 (p) - , ; = + (p) - , ; = + * 单词单词类码类码

16、图 1.6 赋值语句 b=a+2*5 的语法树 例： b = a + 2 * 5 的分析过程如下所示： （ 生成的结果是一棵语法树 ) = = b b + + * * a25 2. 语法分析：语法分析：组词成句及语法错误检查组词成句及语法错误检查算术表达式的算术表达式的层次结构层次结构3. 语义分析：语义分析：分析各种语法成分的分析各种语法成分的语义特征语义特征int a,b;. . .b=a+2*5;l构建构建标识符标识符的语义辞典的语义辞典-符号表：符号表：l构造语句的语义树构造语句的语义树-中间语言；中间语言； b 的值 a 的值 数据区数据区 v i b v i a 地址种类 类型 名

17、字符号表符号表= =b b+ +a a* *2 25 5如如如如: : : : b = a+2*5b = a+2*5(1) ( * 2 5 t1 )(2) ( + a t1 t2 )(3) ( = t2 _ b )或或4. 优化优化：提高目标程序的质量：提高目标程序的质量= =b b+ +a a* *2 25 5(1) ( * 2 5 t1 )(2) ( + a t1 t2 )(3) ( = t2 _ b )经经常数合并常数合并，可分别获得优化后的中间代码如下图所示：，可分别获得优化后的中间代码如下图所示：(1) ( + a 10 t2 )(2) ( = t2 _ b )例例例例: b = a+2*5: b = a+2*5 = =b b+ +a a10105. 目标代码生成目标代码生成上例可生成目标代码：上例可生成目标代码：(1) ( + a 10 t2 )(2) ( = t2 _ b ) LD R,10 ADD R, a ST R, bR 为寄存器为寄存器三条指令分别为：三条指令分别为：取取、加加 和和 存存 。