编译原理-第一章.ppt

编译原理第一章引论 王金伟计算机与信息工程学院天津师范大学 TJNU COCIE WJW 2 2020 1 25 编译原理 课程类别 专业必修课适用专业 计算机科学与技术 计算机软件总学时 51 平均每周3学时 总学分 3先修课 C语言 数据结构 离散数学各班选一位同学担任课代表 收发作业 考核方法平时30 考勤 课后作业 上机作业 期末70 闭卷考试 TJNU COCIE WJW 3 2020 1 25 主要内容 编译程序的基本构造原理和基本实现技术形式语言基础知识词法分析语法分析语法制导翻译程序优化代码生成 TJNU COCIE WJW 4 2020 1 25 主要章节 第1章 引论第2章 高级语言的定义和一般特征第3章 词法分析第4章 语法分析 自上而下分析第5章 语法分析 自下而上分析第6章 属性文法和语法制导翻译第7章 语义分析和中间代码生成第8章 符号表第9章 运行时存储空间组织第10章 优化第11章 目标代码生成 TJNU COCIE WJW 5 2020 1 25 教材和参考书 1 教材 陈火旺等 程序设计语言编译原理 第三版 国防工业出版社 2000年2 参考书 编译原理和技术 第二版 陈意云编著 中国科学技术大学出版社 1997 吕映芝 张素琴 蒋维杜 编译原理 清华大学出版社1998杜淑敏 王永宁 编译程序设计原理 北京大学出版社1986 TJNU COCIE WJW 6 2020 1 25 第一章引论 1 1什么叫编译程序1 2编译过程概述1 3编译程序的结构1 4编译程序与程序设计环境1 5编译程序的生成1 6学习 编译原理 课的注意事项 TJNU COCIE WJW 7 2020 1 25 1 1什么叫编译程序 多数用户用高级语言 C C Pascal 编写程序 以实现他们所需要的应用但目前的计算机执行的是非常低级的语言 机器语言 问题 高级语言写出的程序最终是怎样在计算机上执行的呢 答案 编译程序 TJNU COCIE WJW 8 2020 1 25 1 现实例子 一 编译程序的概念 英文书 中文书 翻译 TJNU COCIE WJW 9 2020 1 25 2 翻译程序能够把某一种语言程序转换成另一种语言程序 并且 后者与前者在逻辑上是等价的 源语言程序 目标语言程序 翻译程序 Main inti j PROCEDUREMAIN VarI J Integer Begin End 输入 输出 c程序 pascal程序 TJNU COCIE WJW 10 2020 1 25 3 编译程序是翻译程序的一种特点 目标语言比源语言低级 源语言程序 目标语言程序 翻译程序 inta b c a 1 b 2 c a b Mova 1Movb 2Addc a b 输入 输出 c程序 汇编语言程序 编译程序 TJNU COCIE WJW 11 2020 1 25 4 解释程序特点 以源语言程序作为输入 但不产生目标语言程序 而是边解释边执行 源语言程序 publicclassstudent publicstaticvoidmain Stringargs StringBufferstring newStringBuffer 10 输入 执行 JAVA程序 解释程序 JVM JAVA虚拟机 输入 编译程序 字节流 输入 JAVA字节流 javac JAVA编译器 TJNU COCIE WJW 12 2020 1 25 按编译目的不同分类 1 诊断编译程序专门用于帮助程序开发和调试的编译程序2 优化编译程序着重于提高目标代码运行效率的编译程序 二 编译程序的分类 TJNU COCIE WJW 13 2020 1 25 按编译目标不同分类 目标机 运行编译程序所产生目标代码的计算机宿主机 运行编译程序的计算机1 交叉编译程序产生不同于其宿主机的机器代码2 可变目标编译程序不需重写编译程序中与机器代码无关的部分就能改变目标机 二 编译程序的分类 续 TJNU COCIE WJW 14 2020 1 25 1 机器语言计算机能够直接执行的机器指令系统例如某种计算机的指令为1011011000000000加法操作1011010100000000减法操作2 汇编语言用一些助记符号来表示机器指令例如A BLDRAADDRB 三 几个概念 TJNU COCIE WJW 15 2020 1 25 3 高级语言其语法和结构类似于自然语言 容易记忆和书写例如C语言 Java等4 源语言把被翻译 或编译 的语言称为源语言5 目标语言把翻译 或编译 之后得到的语言称为目标语言6 源程序用源语言编写的程序7 目标程序用目标语言编写的程序 TJNU COCIE WJW 16 2020 1 25 1 2编译过程概述 过程复杂 可与自然语言翻译作类比 翻译自然语言识别句子中的单词分析句子的语法结构进行初步翻译对译文进行修饰写出最后的译文 编译程序词法分析语法分析语义分析与中间代码生成中间代码优化目标代码成成 TJNU COCIE WJW 17 2020 1 25 任务 输入源程序 根据词法规则 对构源程序的字符串进行扫描和分解 识别出一个个单词符号单词符号是程序语言的基本成分例 A B C由5个单词构成 A 等号 B 乘号 CforI 1to100do单词符号 for I 1 to 100 do实现方法 构造词法分析程序 扫描器 一 词法分析阶段 TJNU COCIE WJW 18 2020 1 25 任务 在词法分析的基础上 根据语言的语法规则把识别出的单词符号串 分解成各类语法单位 语法范畴 如表达式 语句 程序段 过程 函数 程序等 以确定整个输入串是否构成语法上正确的 程序 例 A B CB C是表达式 A B C是赋值语句实现方法 构造语法分析程序 语法分析器 二 语法分析阶段 TJNU COCIE WJW 19 2020 1 25 任务 对语法分析所识别出的各类语法范畴 分析其含义 并进行初步翻译 产生中间代码 静态语义检查 变量是否定义 类型是否正确等进行中间代码翻译例 C语言中 变量需要在使用前声明实现方法 构造语义分析程序 三 语义分析和中间代码生成阶段 TJNU COCIE WJW 20 2020 1 25 中间代码 是一种含义明确 便于记忆的记号系统 独立于硬件 与机器指令在形式上有所接近 容易替换成机器指令 表示形式 后缀式 表示表达式 把运算量 操作数 写在前面 把运算符写在后面 后缀 例 A B写成AB TJNU COCIE WJW 21 2020 1 25 三元式 算符第一操作对象第二操作对象表示二地址指令 四元式 算符第一操作对象第二操作对象结果表示三地址指令 TJNU COCIE WJW 22 2020 1 25 任务 对中间代码进行等价变换 使生成目标代码更高效 例 实现方法 构造代码优化程序 优化 fork 1to100dobeginM i 10 kN j 10 kend 递归加法M iN jfork 1to100dobeginM M 10N N 10end 四 代码优化阶段 TJNU COCIE WJW 23 2020 1 25 任务 把中间代码变换成特定机器上的低级语言代码 目标代码 机器语言代码 汇编语言代码例 AB LDRAADDRB实现方法 构造生成目标代码程序 五 目标代码生成阶段 TJNU COCIE WJW 24 2020 1 25 1 3编译程序的结构 由上述5个阶段的实现程序组成 TJNU COCIE WJW 25 2020 1 25 源程序 语义分析和中间代码生成器 语法分析器 词法分析器 代码优化器 目标代码生成器 目标程序 表格管理 出错处理 字符串 单词符号 语法单位 中间代码 中间代码 一 编译程序总框架 TJNU COCIE WJW 26 2020 1 25 编译程序在工作过程中需要建立一系列表格 以登记源程序中所提供的或在编译过程中所产生的一些信息 编译各个阶段的工作都涉及到构造 查找 修改或存取有关表格中的信息 例符号表用来登记源程序中出现的每个名字以及名字的属性 常量名 变量名 什么类型 过程名 二 表格管理 TJNU COCIE WJW 27 2020 1 25 在翻译各阶段把原程序错误性质和地点通知用户 语法错误 源程序中不符合语法 词法 规则的错误例如 拼写错误 括号不匹配 非法字符等语义错误 源程序中不符合语义规则的错误例如 说明错误 作用域错误 类型不一致等 三 出错处理 TJNU COCIE WJW 28 2020 1 25 前端 主要由与源语言有关但与目标语言无关的那些部分组成例如 词法分析 语法分析 中间代码产生 代码优化 后端 由与目标机有关的那些部分组成 不依赖于源语言而仅仅依赖于中间语言 例如 代码优化 目标代码生成等 四 编译前端和后端 TJNU COCIE WJW 29 2020 1 25 源程序 语义分析和中间代码生成器 语法分析器 词法分析器 代码优化器 目标代码生成器 目标程序 字符串 单词符号 语法单位 中间代码 中间代码 四 编译前端和后端 续1 前端 后端 TJNU COCIE WJW 30 2020 1 25 四 编译前端和后端 续2 C语言编译器前端 中间代码 C语言编译器后端 X86 C语言编译器后端 ARM 中间代码 X86代码 ARM代码 TJNU COCIE WJW 31 2020 1 25 1 4编译程序与程序设计环境 程序开发过程程序设计环境 编辑程序 编译程序 链接程序 库代码 源代码 目标代码 可执行代码 UEVI等 Linkld等 Windbggdb等 调试程序 Masmas等 程序设计环境 TJNU COCIE WJW 32 2020 1 25 1 4编译程序与程序设计环境 续 传统的程序设计环境编辑 编译 链接 调试各自独立集成化的程序设计环境 IDE TurboCVisualC PowerBuilderJBuilder等等 TJNU COCIE WJW 33 2020 1 25 1 5编译程序的生成 早期用机器或汇编语言现在用高级语言编写 TJNU COCIE WJW 34 2020 1 25 1 直接编写机器语言 汇编语言 高级语言2 自举的方法先对语言的核心部分用机器语言编写核心部分 程序语言的三个支柱 条件 循环 调用返回然后以此为基础 再编写更多的语言成分3 移植的方法将一个已有的A机器上的编译器移植到B机器上 一 编译程序的构造方法 TJNU COCIE WJW 35 2020 1 25 二 T形图 描述源语言S 目标语言T和编译程序实现语言I间的关系 TJNU COCIE WJW 36 2020 1 25 三 T形图的组合方式 1 将第一个T形图的输出作为第二个T形图的输入已有将语言A编译为语言B的编译器和将语言B到语言C的编译器 用上述方法得到A到C的编译器 TJNU COCIE WJW 37 2020 1 25 三 T形图的组合方式 续 2 编译器实现语言的变换例 我们用C语言开发了一个将FORTRAN语言程序编译为JAVA程序的编译器FOR2J 如果我们已经有一个将C语言编译为X86代码的编译器 利用上述的方式可以得到一个在X86机器上执行的FOR2J编译器 编译 TJNU COCIE WJW 38 2020 1 25 四 编译器的自举的开发方式 没有高级语言可以用来写编译器 怎么办 用汇编语言开发一个完整的编译器 太繁琐用自举的方式 首先用汇编语言M开发一个实现源语言A的一个子集A 的编译器 这个编译器只要正确即可用这个子集语言A 开发语言全集的编译器上述过程可以重复多次 直至得到性能良好的 正确的对语言全集有效的编译器 编译 TJNU COCIE WJW 39 2020 1 25 五 编译器的移植的开发方式 以PC机为工具开发M芯片的C语言编译器PC机上已有C语言编译器 把移植到M芯片上用C语言在PC机上开发一个产生M代码的C编译器C1将C1在PC机上编译 得到PC机上运行的交叉编译器C2M用交叉编译器C2M在PC机上对C1重新编译 得到在M芯片上运行的C语言编译器 PC上的C语言编译器 交叉编译器C2M 交叉编译器C2M M上的C语言编译器 C1 C1 TJNU COCIE WJW 40 2020 1 25 1 6学习 编译原理 课的注意事项 1 明确 编译 的任务PTQ从数学角度 把编译程序看成一个映射函