《[所有分类]编译原理-第一章》由会员分享，可在线阅读，更多相关《[所有分类]编译原理-第一章（43页珍藏版）》请在金锄头文库上搜索。
1、编译原理 第一章 引论,王金伟 计算机与信息工程学院 天津师范大学,TJNU-COCIE-WJW,2,2018/9/27,编译原理,课程类别：专业必修课 适用专业：计算机科学与技术、计算机软件 总 学 时：51（平均每周3学时） 总 学 分：3 先修课：C语言、数据结构、离散数学 各班选一位同学担任课代表（收发作业） 考核方法 平时30% (考勤、课后作业、上机作业） 期末70% (闭卷考试）,TJNU-COCIE-WJW,3,2018/9/27,主要内容,编译程序的基本构造原理和基本实现技术 形式语言基础知识 词法分析 语法分析 语法制导翻译 程序优化 代码生成,TJNU-COCIE-WJW
2、,4,2018/9/27,主要章节,第1章引论 第2章高级语言的定义和一般特征 第3章词法分析 第4章语法分析自上而下分析 第5章语法分析自下而上分析 第6章属性文法和语法制导翻译 第7章语义分析和中间代码生成 第8章符号表 第9章运行时存储空间组织 第10章优化 第11章目标代码生成,TJNU-COCIE-WJW,5,2018/9/27,教材和参考书,1. 教材： 陈火旺等：程序设计语言编译原理（第三版），国防工业出版社，2000年 2. 参考书： 编译原理和技术（第二版，陈意云编著，中国科学技术大学出版社，1997） 吕映芝、张素琴、蒋维杜：编译原理；清华大学出版社 1998 杜淑敏、王永
3、宁：编译程序设计原理；北京大学出版社 1986,TJNU-COCIE-WJW,6,2018/9/27,第一章 引论,1.1 什么叫编译程序 1.2 编译过程概述 1.3 编译程序的结构 1.4 编译程序与程序设计环境 1.5 编译程序的生成 1.6 学习“编译原理”课的注意事项,TJNU-COCIE-WJW,7,2018/9/27,1.1 什么叫编译程序,多数用户用高级语言（C，C+，Pascal）编写程序，以实现他们所需要的应用 但目前的计算机执行的是非常低级的语言：机器语言。 问题：高级语言写出的程序最终是怎样在计算机上执行的呢？ 答案：编译程序,TJNU-COCIE-WJW,8,2018
4、/9/27,1. 现实例子,一、编译程序的概念,英文书,中文书,翻译,TJNU-COCIE-WJW,9,2018/9/27,2. 翻译程序 能够把某一种语言程序转换成另一种语言程序，并且，后者与前者在逻辑上是等价的。,源语言程序,目标语言程序,翻译 程序,Main() int i,j; ,PROCEDURE MAIN; Var I,J:Integer; Begin End ,输入,输出,c程序,pascal程序,TJNU-COCIE-WJW,10,2018/9/27,3. 编译程序 是翻译程序的一种 特点：目标语言比源语言低级,源语言程序,目标语言程序,翻译 程序,. int a,b,c; a
5、 = 1; b = 2; c = a + b; , Mov a, 1 Mov b, 2 Add c, a, b ,输入,输出,c程序,汇编语言程序,编译 程序,TJNU-COCIE-WJW,11,2018/9/27,4. 解释程序 特点：以源语言程序作为输入，但不产生目标语言程序，而是边解释边执行,源语言程序,. public class student public static void main(String args) StringBuffer string= new StringBuffer10; . ,输入,执行,JAVA程序,解 释 程 序,JVM （JAVA虚拟机）,输入,编
6、译 程 序,字节流,输入,JAVA字节流,javac （JAVA编译器）,TJNU-COCIE-WJW,12,2018/9/27,按编译目的不同分类： 1.诊断编译程序 专门用于帮助程序开发和调试的编译程序 2.优化编译程序 着重于提高目标代码运行效率的编译程序,二、编译程序的分类,TJNU-COCIE-WJW,13,2018/9/27,按编译目标不同分类： 目标机：运行编译程序所产生目标代码的计算机 宿主机：运行编译程序的计算机 1.交叉编译程序 产生不同于其宿主机的机器代码 2.可变目标编译程序 不需重写编译程序中与机器代码无关的部分就能改变目标机,二、编译程序的分类（续）,TJNU-CO
7、CIE-WJW,14,2018/9/27,1.机器语言 计算机能够直接执行的机器指令系统 例如某种计算机的指令为 1011011000000000 加法操作 1011010100000000 减法操作 2.汇编语言 用一些助记符号来表示机器指令 例如A+B LD R A ADD R B,三、几个概念,TJNU-COCIE-WJW,15,2018/9/27,3.高级语言 其语法和结构类似于自然语言，容易记忆和书写 例如C语言，Java等 4.源语言 把被翻译（或编译）的语言称为源语言 5.目标语言 把翻译（或编译）之后得到的语言称为目标语言 6.源程序 用源语言编写的程序 7.目标程序 用目标语
8、言编写的程序,TJNU-COCIE-WJW,16,2018/9/27,1.2 编译过程概述,过程复杂，可与自然语言翻译作类比,翻译自然语言 识别句子中的单词 分析句子的语法结构 进行初步翻译 对译文进行修饰 写出最后的译文,编译程序 词法分析 语法分析 语义分析与中间代码生成 中间代码优化 目标代码成成,TJNU-COCIE-WJW,17,2018/9/27,任务：输入源程序，根据词法规则，对构源程序的字符串进行扫描和分解，识别出一个个单词符号 单词符号是程序语言的基本成分 例：A = B * C 由5个单词构成：A，等号，B，乘号，C for I:=1 to 100 do 单词符号：for,
9、 I, :=, 1, to, 100, do 实现方法： 构造词法分析程序（扫描器）,一、词法分析阶段,TJNU-COCIE-WJW,18,2018/9/27,任务： 在词法分析的基础上，根据语言的语法规则把识别出的单词符号串，分解成各类语法单位（语法范畴，如表达式、语句、程序段、过程、函数、程序等），以确定整个输入串是否构成语法上正确的“程序”。 例：A = B * C B * C是表达式， A = B * C是赋值语句 实现方法： 构造语法分析程序（语法分析器）,二、语法分析阶段,TJNU-COCIE-WJW,19,2018/9/27,任务： 对语法分析所识别出的各类语法范畴，分析其含义，
10、并进行初步翻译（产生中间代码） 静态语义检查：变量是否定义、类型是否正确等 进行中间代码翻译 例：C语言中，变量需要在使用前声明 实现方法： 构造语义分析程序,三、语义分析和中间代码生成阶段,TJNU-COCIE-WJW,20,2018/9/27,中间代码： 是一种含义明确，便于记忆的记号系统，独立于硬件，与机器指令在形式上有所接近，容易替换成机器指令。 表示形式： 后缀式：表示表达式，把运算量（操作数）写在前面，把运算符写在后面（后缀） 例：A+B 写成 AB+,TJNU-COCIE-WJW,21,2018/9/27,三元式： 算符 第一操作对象 第二操作对象 表示二地址指令： 四元式： 算
11、符 第一操作对象 第二操作对象 结果 表示三地址指令：,TJNU-COCIE-WJW,22,2018/9/27,任务： 对中间代码进行等价变换，使生成目标代码更高效。 例： 实现方法： 构造代码优化程序,优化,for k:=1 to 100 do begin M:=i+10*k N:=j+10*k end,递归加法 M:=i N:=j for k:=1 to 100 do begin M:=M+10 N:=N+10 end,四、代码优化阶段,TJNU-COCIE-WJW,23,2018/9/27,任务： 把中间代码变换成特定机器上的低级语言代码。 目标代码：机器语言代码、汇编语言代码 例：AB
12、+ LD R A ADD R B 实现方法： 构造生成目标代码程序,五、目标代码生成阶段,TJNU-COCIE-WJW,24,2018/9/27,1.3 编译程序的结构,由上述5个阶段的实现程序组成,TJNU-COCIE-WJW,25,2018/9/27,源程序,语义分析和中间代码生成器,语法分析器,词法分析器,代码优化器,目标代码生成器,目标程序,表 格 管 理,出 错 处 理,( 字符串),单词符号,语法单位,中间代码,中间代码,一、编译程序总框架,TJNU-COCIE-WJW,26,2018/9/27,编译程序在工作过程中需要建立一系列表格，以登记源程序中所提供的或在编译过程中所产生的一
13、些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息。 例 符号表 用来登记源程序中出现的每个名字以及名字的属性（常量名、变量名（什么类型）、过程名）,二、表格管理,TJNU-COCIE-WJW,27,2018/9/27,在翻译各阶段把原程序错误性质和地点通知用户。 语法错误：源程序中不符合语法（词法）规则的错误 例如：拼写错误，括号不匹配，非法字符等 语义错误：源程序中不符合语义规则的错误 例如：说明错误，作用域错误，类型不一致等,三、出错处理,TJNU-COCIE-WJW,28,2018/9/27,前端： 主要由与源语言有关但与目标语言无关的那些部分组成 例如：词法分析
14、、语法分析、中间代码产生、（代码优化） 后端： 由与目标机有关的那些部分组成，不依赖于源语言而仅仅依赖于中间语言。 例如：（代码优化）、目标代码生成等,四、编译前端和后端,TJNU-COCIE-WJW,29,2018/9/27,源程序,语义分析和中间代码生成器,语法分析器,词法分析器,代码优化器,目标代码生成器,目标程序,( 字符串),单词符号,语法单位,中间代码,中间代码,四、编译前端和后端（续1）,前端,后端,TJNU-COCIE-WJW,30,2018/9/27,四、编译前端和后端（续2）,C语言 编译器 前端,中间代码,C语言 编译器 后端 （X86）,C语言 编译器 后端 （ARM）
15、,中间代码,X86代码,ARM代码,TJNU-COCIE-WJW,31,2018/9/27,1.4 编译程序与程序设计环境,程序开发过程 程序设计环境,编辑 程序,编译 程序,链接 程序,库代码,源 代码,目标 代码,可执行 代码,UE VI等,Link ld等,Windbg gdb等,调试 程序,Masm as等,程序设计环境,TJNU-COCIE-WJW,32,2018/9/27,1.4 编译程序与程序设计环境（续）,传统的程序设计环境 编辑、编译、链接、调试各自独立 集成化的程序设计环境（IDE） Turbo C Visual C+ PowerBuilder J Builder 等等,T
16、JNU-COCIE-WJW,33,2018/9/27,1.5 编译程序的生成,早期用机器或汇编语言 现在用高级语言编写,TJNU-COCIE-WJW,34,2018/9/27,1.直接编写 机器语言、汇编语言、高级语言 2.自举的方法 先对语言的核心部分用机器语言编写 核心部分：程序语言的三个支柱：条件、循环、调用返回 然后以此为基础，再编写更多的语言成分 3.移植的方法 将一个已有的A机器上的编译器移植到B机器上,一、编译程序的构造方法,TJNU-COCIE-WJW,35,2018/9/27,二、 T形图,描述源语言S、目标语言T和编译程序实现语言I间的关系,TJNU-COCIE-WJW,36,2018/9/27,三、 T形图的组合方式,1.将第一个T形图的输出作为第二个T形图的输入 已有将语言A编译为语言B的编译器和将语言B到语言C的编译器，用上述方法得到A到C的编译器,TJNU-COCIE-WJW,37,2018/9/27,
