《Part1编译原理-引论(天津大学)》由会员分享，可在线阅读，更多相关《Part1编译原理-引论(天津大学)（38页珍藏版）》请在金锄头文库上搜索。
1、编译原理引论授课：胡静*2004年12月28日1编译原理教材及参考书 教材： 程序设计语言编译原理（第3版），国防工业出版社， 陈火旺等编著 主要参考资料 编译原理（Compilers Principles, Techniques, and Tools） 出版社：机械工业出版社 编译原理，清华大学出版社，吕映芝、张素琴、蒋维 杜编著 编译器工程Design a Compiler，机械工业出 版社，Keith D.Cooper、Linda Torczon著；冯速译Date2编译原理相关课程 课程基础 数据结构 计算机原理和汇编语言 高级程序设计语言 后续课程 编译技术Date3编译原理第一章 概
2、论 编译的起源：程序设计语言的发展 基本概念 编译过程和编译程序的构造Date4编译原理程序设计语言的发展Date5编译原理基本概念 低级语言（Low level Language) 字位码、机器语言、汇编语言 特点：与特定的机器有关，功效高，但使用复杂、繁琐、费 时、易出错 高级语言 Fortran 、Pascal、C 语言等 特点：不依赖具体机器，移植性好、对用户要求低、易使用 、易维护等。 Date6编译原理基本概念Date7编译原理基本概念Date8编译原理源程序的编译和运行Date9编译原理源程序的解释运行Date10编译原理源程序的编译-解释运行Date11编译原理编译器和解释器
3、编译器和解释器的比较 相同点（执行相同的任务）: 检查输入程序并确定这个程序是否一个有效程序 建立一个内部模型来刻画输入程序的结构和含义 决定在执行期间值的存放位置 不同点（执行的行为不同）： 编译器以一个可执行程序的描述作为输入，以另一个 等价的可执行程序的描述作为输出。 解释器以一个可执行程序的描述作为输入，以执行这 一可执行程序描述的结果作为输出。Date12编译原理举例 典型的编译器：gcc, javac 非典型的编译器： latex (document compiler) : Transforms a LaTeX document into DVI printing commands
4、 Input information = document (not program) 解释器： f2c : Fortran-to-C translator (both high-level) latex2html : LaTeX-to-HTML (both documents)Date13编译原理我们为什么需要编译器 编写、调试、维护和理解用装配语言(assemble language)编写的程序是很困难的 自从第一个编译器出现之后，软件产品的数量有了 巨大的增加。 但是仍然有一些情况需要用装配语言编写 例如，访问某些底层的机器资源（设备驱动） 这些代码规模一般较小，还是需要编译器去处理其
5、他的应用Date14编译原理编译器构造法的研究目的 好的编译器是计算机科学的缩影 包含大量的技术：贪婪算法（寄存器分配）、启发 式搜索技术（列表调度）、图形算法（死码消除） 、动态规划（指令筛选）、有穷自动机和下推自动 机（扫描和语法分析）、不动点算法（数据流分析 ） 处理复杂的问题：动态分配、同步、命名、局部化 、存储器分层管理、管道调度 提供完整的解决方案：有机的结合算法、软件体系 结构和软件工程的各种理论，对棘手问题给出综合 性的解答方案。Date15编译原理什么是编译器 什么是编译程序预处理器编译器汇编器装配连接编辑骨架程序源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标
6、文件库Date16编译原理源代码 符合人类阅读习惯 符合人类语法定义 使用被命名的结构，例如变量和过程Date17编译原理装配语言机器代码 符合硬件需求 包含机器指令，使用寄存器和没有命名的内存地址 对人类来说很难理解Date18编译原理例子：输出的装配代码 没有优化的代码 优化后的代码Date19编译原理编译器的基本原则 编译器是工程对象，是具有独特目标的大型软件系 统，两个设计原则必须遵守 不违背原义 编译器必须保持被编译程序的含义不变 这一原则是编译器设计者与编译器用户之间的契约的 核心 实用性原则 编译器必须用某种明确的方式改进输入程序 例如代码优化等对输入程序的改进Date20编译原
7、理有效的转换 目标：产生和源代码描述相同计算的机器代码 这种转换是唯一的嘛？ 有没有“完美的转换”（速度快，代码量小） 编译器优化=找到更好的转换Date21编译原理转换的正确性 产生的代码必须精确的执行和源代码相同的计算 正确性很重要 用不正确的编译器调试程序很难 和开发的成本、安全性密切相关 编译原理这门课程讲述的就是可以保证转换安全性 的技术。Date22编译原理如何转换 转换是一个很复杂的过程 源程序语言和目标程序语言是截然不同的 我们需要结构化这个转换过程 定义中间阶段 每个阶段完成特定的功能Date23编译原理一个简单的编译器的结构Date24编译原理简单的前端结构Date25编译
8、原理Analogy（ctd） 前端可以通过类比于人类理解自然语言的过程进行 解释 词法分析 自然语言：He wrote the program 单词： he wrote the program 编程语言：if (b=0) a=b token: if ( b = = 0 ) a = b Date26编译原理Analogy（ctd） 语法分析 自然语言 编程语言Date27编译原理Analogy（ctd） 语义分析 自然语言 Hewrotethecomputer nounverbarticlenoun 语法正确，语义错误！ 编程语言 if (b=0) a=foo testassignment 如果
9、a是一个整型变量而foo是一个过程，那么语义分 析就会报错Date28编译原理词法分析 词法分析也叫线性分析和扫描。 从左到右的读构成源程序的字符流，分组为多个记 号。词法分析器position := initial + rate * 60id1 := id2 + id3 * 60Date29编译原理语法分析 语法分析也叫层次分析，把源程序的记号进一步分 组，产生被编译器用于生成代码的语法短语。 程序的语法结构常常需要递归 上下文无关文法是递归规则的一种形式化，可以指 导语法分析 由于词法分析不要求递归，因此我们通常不明确的 界定词法分析和语法分析的界限。也就是说，我们 将词法分析程序当成语法
10、分析程序调用的一个子程 序。Date30编译原理语法分析（续）语法分析器id1 := id2 + id3 * 60id1id3id2:=+*60在本例中，算符优先级 可以通过如下方法定义 ： 1.定义程序语言的语法 规则体现算符的优先级 2.通过某些规则库，例 如算符优先级表格等来 定义算符的优先级Date31编译原理语义分析（续）语义分析器id1id3id2:=+*60id1id3id2:=+*inttoreal60在本例中，几个标识符 都是实数类型，而且源 程序语言允许整数向实 数类型的强制转换Date32编译原理编译器的应用模型（逻辑结构）出错处理语法分析程序语义分析程序目标代码生成程序
11、词法分析程序中间代码生成程序代码优化程序表格管理编译的前端 （Front End） 分析部分 与源语言有关编译的后端 （Back End） 综合部分 与目标语言有关Date33编译原理Date34编译原理Date35编译原理遍（PASS） 遍：对源程序（包括源程序的中间表示形式）从头到尾扫 描一次并作有关的加工处理，生成新的源程序中间形式或 目标程序，通常称之为一遍。上一遍的结果是下一遍的输 入，最后一遍生成目标程序。 遍与基本阶段的区别： 五个基本阶段是将源程序翻译成目标程序在逻辑上要完成的 工作 遍是指完成上述五个基本阶段的工作要经过几次扫描处理Date36编译原理Date37编译原理Thanks for your time!Thanks for your time!Questions & AnswersQuestions & AnswersDate38编译原理
