Part1编译原理-引论(天津大学).pptVIP

编译原理 编译原理引论 授课：胡静 教材及参考书 教材： 《程序设计语言编译原理（第3版）》，国防工业出版社，陈火旺等编著 主要参考资料 编译原理（Compilers Principles, Techniques, and Tools）出版社：机械工业出版社 《编译原理》，清华大学出版社，吕映芝、张素琴、蒋维杜编著 《编译器工程》——《Design a Compiler》，机械工业出版社，Keith D.Cooper、Linda Torczon著；冯速译 相关课程 课程基础 数据结构 计算机原理和汇编语言 高级程序设计语言 后续课程 编译技术 第一章 概论 编译的起源：程序设计语言的发展 基本概念 编译过程和编译程序的构造 程序设计语言的发展 基本概念 低级语言（Low level Language) 字位码、机器语言、汇编语言 特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错 高级语言 Fortran 、Pascal、C 语言等 特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。 基本概念 基本概念 源程序的编译和运行 源程序的解释运行 源程序的编译-解释运行 编译器和解释器 编译器和解释器的比较 相同点（执行相同的任务）: 检查输入程序并确定这个程序是否一个有效程序 建立一个内部模型来刻画输入程序的结构和含义 决定在执行期间值的存放位置 不同点（执行的行为不同）： 编译器以一个可执行程序的描述作为输入，以另一个等价的可执行程序的描述作为输出。 解释器以一个可执行程序的描述作为输入，以执行这一可执行程序描述的结果作为输出。 举例 典型的编译器：gcc, javac 非典型的编译器： latex (document compiler) : Transforms a LaTeX document into DVI printing commands Input information = document (not program) 解释器： f2c : Fortran-to-C translator (both high-level) latex2html : LaTeX-to-HTML (both documents) 我们为什么需要编译器 编写、调试、维护和理解用装配语言(assemble language)编写的程序是很困难的 自从第一个编译器出现之后，软件产品的数量有了巨大的增加。 但是仍然有一些情况需要用装配语言编写 例如，访问某些底层的机器资源（设备驱动） 这些代码规模一般较小，还是需要编译器去处理其他的应用 编译器构造法的研究目的 好的编译器是计算机科学的缩影 包含大量的技术：贪婪算法（寄存器分配）、启发式有哪些信誉好的足球投注网站技术（列表调度）、图形算法（死码消除）、动态规划（指令筛选）、有穷自动机和下推自动机（扫描和语法分析）、不动点算法（数据流分析） 处理复杂的问题：动态分配、同步、命名、局部化、存储器分层管理、管道调度 提供完整的解决方案：有机的结合算法、软件体系结构和软件工程的各种理论，对棘手问题给出综合性的解答方案。 什么是编译器 什么是编译程序 源代码 符合人类阅读习惯 符合人类语法定义 使用被命名的结构，例如变量和过程 装配语言机器代码 符合硬件需求 包含机器指令，使用寄存器和没有命名的内存地址 对人类来说很难理解 例子：输出的装配代码 没有优化的代码 编译器的基本原则 编译器是工程对象，是具有独特目标的大型软件系统，两个设计原则必须遵守 不违背原义 编译器必须保持被编译程序的含义不变 这一原则是编译器设计者与编译器用户之间的契约的核心 实用性原则 编译器必须用某种明确的方式改进输入程序 例如代码优化等对输入程序的改进 有效的转换 目标：产生和源代码描述相同计算的机器代码 这种转换是唯一的嘛？ 有没有“完美的转换”（速度快，代码量小） 编译器优化=找到更好的转换 转换的正确性 产生的代码必须精确的执行和源代码相同的计算 正确性很重要 用不正确的编译器调试程序很难…… 和开发的成本、安全性密切相关 编译原理这门课程讲述的就是可以保证转换安全性的技术。 如何转换 转换是一个很复杂的过程 源程序语言和目标程序语言是截然不同的 我们需要结构化这个转换过程 定义中间阶段 每个阶段完成特定的功能 一个简单的编译器的结构 简单的前端结构 Analogy（ctd） 前端可以通过类比于人类理解自然语言的过程进行解释 词法分析 自然语言：He wrote the program 单词： ‘he’ ‘wrote’ ‘the’ ‘program’ 编程语言：if (b==0) a=b token: ‘if’ ‘(’ ‘b’ ‘= = ’ ‘0’ ‘)’ ‘a’ ‘=