《编译原理绪论》ppt课件

《《编译原理绪论》ppt课件》由会员分享，可在线阅读，更多相关《《编译原理绪论》ppt课件（34页珍藏版）》请在金锄头文库上搜索。

1、第 1 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦 办公地址：信息学院403 联系电话：18392451815 电子邮箱：,联系方式,教材和参考书,关于编译原理 1 编译原理理论概述 2 学习目标 3 学习方法 重点掌握 1 翻译、解释、编译的区别和联系 2 编译过程分为哪些步骤,本讲目标,第一章 绪论,1.1 程序设计语言和编译程序 1.2 编译程序的历史及发展(自学) 1.3 编译过程和编译程序结构 1.4 编译程序的开发 1.5 构造编译程序所应具备的知识内容,计算机的指令系统 计算机所能执行的每一种操作称为一条指令，计算机能够执行的全部指令集合就是该计算机的指令系统。 指

2、令格式：操作码 操作地址码 PC的指令规模一般是300500条。 可执行程序就是不同指令的反复组合。,1.1 程序设计语言和编译程序,算术运算、逻辑运算、存数、取数、转移等。,指出该条指令涉及的操作数的地址。,低级语言 机器语言 二进制形式的指令序列称为某计算机的机器语言，也是计算机唯一能够直接识别并执行的语言。 汇编语言 用助记符代替机器语言的二进制指令，所生成的语言就是汇编语言。 例如用“MOV”代替“0001”，用“ADD”代替“0011”，,1.1 程序设计语言和编译程序,低级语言 举例：计算“b = a+2” 显然，汇编语言比机器语言有了长足的进步。但仍存在以下缺点： 严重依赖目标机

3、器； 不易开发、调试； 和自然语言存在鸿沟，可读性差。,1.1 程序设计语言和编译程序,MOV a，R1 ADD #2，R1 MOV R1，b,0001 01 00 00000000 0011 01 10 00000010 0010 01 00 00000100,汇编语言,机器语言,高级语言的发展,1.1 程序设计语言和编译程序,高级语言 高级语言已经从具体机器中抽象出来，摆脱了依赖具体机器的问题。 高级语言虽然更符合人类的思维习惯，但高级语言程序也必须翻译(编译)成最终能够直接执行的机器语言程序。而且，这个难度比汇编过程大大增加。,1.1 程序设计语言和编译程序,从1966年至今，所有颁布的

4、图灵奖中，有三分之一的奖项颁布给了对高级程序设计语言和编译理论有杰出贡献的科学家。,程序设计语言的转换 翻译 是指将某种语言的源程序，在不改变语义的条件下，转换成另一种语言程序目标语言程序 编译 专指由高级语言程序一次性转换成低级语言程序，类似于全文翻译 解释 接受某高级语言的一个语句输入，进行解释并控制计算机执行，得到这个语句的执行结果后，等待下一个语句的解释执行，执行过程中并不产生目标程序。类似于口译,1.1 程序设计语言和编译程序,不同高级语言程序的执行类型： 编译型（本课程只关注编译型） C、C+、Pascal、Delphi等：生成目标程序。 解释型 BASIC、Unix的shell、

5、网络浏览器（将HTML及Javascript等脚本程序解释执行）等； 特殊型 即时编译：Java：先翻译成较低级的字节码程序，然后编译为机器语言程序。,1.1 程序设计语言和编译程序,在翻译的过程中，必须始终遵循的原则是：在逻辑上等价。,编译型高级语言程序的阶段： 高级语言程序的执行通常分为两个阶段：编译阶段和运行阶段。 编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序（如C语言下的exe） 编译： 运行：初始数据 + 目标程序 + 运行系统 计算结果,1.1 程序设计语言和编译程序,高级语言程序的执行分为三个阶段的情况：编译阶段、汇

6、编阶段和运行阶段。,1.1 程序设计语言和编译程序,思考：解释和编译的主要区别是什么？,机器语言的诞生 例：C7 06 0000 0002 （将数字2移到地址0000) 汇编语言和汇编程序的诞生 例： MOV X,2 (功能和上式类似,其中X的值赋值为0） 第一个高级语言FORTRAN及其编译器的诞生（1957，IBM） Chomsky研究了语言和文法的数学理论 0型、1型、2型、3型 编译程序的自动生成研究 YACC、JavaCC:语法分析器自动生成工具,1.2 编译程序的历史及发展（里程碑意义的事件）,联系实际，想想自然语言的翻译 Let me show you! 翻译成中文的五个阶段：

7、词法分析：识别出句子中的一个个单词 语法分析：分析句子的语法结构，是否符合英语语法 语义分析：对正确的英文句子分析其含义，并用汉语表示 优化：根据上下文的关系以及汉语的表达习惯对中文句子做修饰工作 输出全部中文,1.3 编译过程和编译程序结构,高级语言程序的编译过程 输入：源程序，输出：目标程序 五个阶段： 词法分析 语法分析 语义分析和中间代码生成 中间代码优化 目标代码生成,1.3 编译过程和编译程序结构,1.3.1 词法分析 任务：将源程序中的字符串变换成单词符号流 例如，如下的C语言程序： 通过词法分析得到如下单词符号： 关键字：float 标识符：position initial r

8、ate 常数： 60 运算符：+ * 界符： , ; =,1.3 编译过程和编译程序结构,float position, initial, rate; position = initial + rate * 60;,词法分析所遵循的是语言的构词规则,1.3.2 语法分析 任务：根据语法规则，从单词符号串中识别出各种语法单位（如表达式、说明、程序段等），并检查语法结构的正确性。 “position = initial + rate * 60; ” 包含哪些语法单位？ 被定义为： = 被定义为： + 被定义为： * 被定义为： | ,1.3 编译过程和编译程序结构,语法分析遵循语言的语法规则，通常

9、使用上下文无关文法,1.3.2 语法分析 “position = initial + rate * 60” 的语法树：,1.3 编译过程和编译程序结构,标识符,position,initial,标识符,rate,常数,60,1.3.3 语义分析和中间代码生成 任务：1、对每种语法单位（范畴）进行静态语义审查 (验证语法结构合法的程序是否真正有意义) 2、在语义检查正确的情况下进行中间代码的翻译 中间代码是介于高级语言语句和低级语言的指令之间的一种独立于具体硬件的记号系统，既有一定抽象，又与低级语言指令十分接近，因此转换成目标代码比较容易 中间代码的常用表示形式：四元式、三元式、间接三元式和逆波

10、兰记号等（将在第四章介绍）,1.3 编译过程和编译程序结构,把语法单位翻译成中间代码遵循语言的语义规则,1.3.3 语义分析和中间代码生成 “position = initial + rate * 60”所转换的四元式：,1.3 编译过程和编译程序结构,（*，rate, 60, t1 ）,（+，initial, t1, t2 ）,（=，t2, _ , position）,（操作符，操作数1, 操作数2 , 执行结果 ）,1.3.4 中间代码优化 任务：是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效(节省时间和空间)的目标代码 优化遵循等价变换规则 手段：删除冗余运算、删除无用赋值

11、、合并已知量、循环优化等 “position = initial + rate * 60”,1.3 编译过程和编译程序结构,（+，initial, t1, position）,1.3.5 目标代码生成 任务：是把中间代码(或经优化处理之后)变换成特定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作 因为目标语言的关系，该阶段的工作非常依赖硬件系统 本学期不作为教学要求,1.3 编译过程和编译程序结构,编译程序结构示意图,1.3 编译过程和编译程序结构,注意：一个编译过程可分为一遍、两遍或多遍完成，每一遍完成所规定的任务。 例如，第一遍只完成词法分析的任务，第二遍完成语法分析和语义加工工作

12、并生成中间代码，第三遍再实现代码优化和目标代码生成。 但是多遍会导致编译效率的降低。,1.3.6 表格管理和出错处理 表格管理 编译程序过程中要记录变量名（存储分配、类型、作用域等） 如果是函数名（参数数量、类型，参数的传递方式、返回值类型等） 常量表、分程序入口表以及中间代码表等 编译程序的各个阶段需要构造、查找、更新变量和函数的信息,表格管理耗费了编译过程的绝大部分时间 因此，编译程序中必须有一个管理各种表格的程序,1.3 编译过程和编译程序结构,1.3.6 表格管理和出错处理 出错处理 完整的编译程序应该能够定位和跟踪错误 能够捕获到各种词法、语法、语义错误，并定位错误的类型及出错位置

13、此外，为了尽可能多地发现错误，应在发现错误后还能继续编译下去，以便发现更多的错误,1.3 编译过程和编译程序结构,1.4.1 开发编译程序的要求 开发人员要熟悉源程序语言 源程序语言的语法和语义有全面深入的理解 对目标机器的环境有深入的研究 确定编译程序的开发方案及方法 开发步骤（熟悉编译原理理论） 软件开发功底，保证编译程序的可读性与扩展性 选择合适的编程语言 一般选择Pascal、C、Java和Ada等高级语言,1.4 编译程序的开发,1.4.2 编译程序的开发技术 自编译 用某种高级语言书写自己的编译程序 交叉编译 针对B机器，在A机上编写一个编译程序，使得B机器上的源代码可以被编译成目

14、标程序 自展 用机器语言或汇编语言实现简单的L0语言，用L0编写自身的扩充语言L1的编译程序，再用L1扩充L2 移植 修改基于A机器的编译程序，使得能够在B机器上顺利执行,1.4 编译程序的开发,1.4.3 编译程序的自动生成 有没有一种软件，可以自动生成高效的编译程序？ 输入： 源语言（如C语言）的语法：包括关键字、标识符的定义，各种语法结构等 输出：编译程序 当有一段源程序作为该编译程序的输入时，可以得到目标代码 现有的编译程序自动生成系统：JavaCC,Lex,YACC等 我们需要做的是尽可能提供完备、正确的语法描述和机器语言的描述,1.4 编译程序的开发,要在一台机器上为某种源语言构造

15、一个编译程序，需要掌握下述三方面的内容： 深刻理解源语言的语法结构(自学理解),如： for循环的终值问题 参数传递的顺序问题 对目标机器的硬件和指令系统有深刻的了解 主要针对于要产生目标代码的情况 熟练掌握编译方法 编译程序中各个环节相互联系 表达式 条件表达式 for、switch、while的实现顺序,1.5 构造编译程序所应具备的知识,掌握编译的理论基础和形式化系统 词法分析 语法分析 语义分析和中间代码生成 掌握编译程序的开发过程（5次实验） JavaCC：一种eclipse插件。通过该插件，可以很方便地定义一种编程语言的文法，从而自动生成编译程序。,2 学习目标,1、认真听课，理解基本概念、原理和算法 2、章节环环相扣，前面的理论是后面学习的基础，因此做好复习，切忌遗留问题 3、看懂书中的例题，多做课后习题(准备一个作业本) 4、理论联系实践,3 学习方法,本章小结 掌握编译程序与高级程序设计语言的关系 掌握编译分为哪几个阶段 了解各个阶段完成的主要功能,