编译原理--引论（三）

构建一个编译器的相关科学

• 编译器必须接受所有遵循语言规范的源程序
• 源程序的集合是无穷的
• 编译一个源程序的过程中，编译器所做的任何翻译工作不能改变被编译源程序所编译的全部程序

编译器设计和实现中的建模

• 编译器研究的是有关如何设计正确的数学模型和选择正确算法的研究
• 设计和选择时，考虑到对通用性及功能的要求与简单性及有效性之间的平衡

代码优化的科学

• 在编译器设计中，术语"优化"是指编译器为了生成比浅显直观的代码更加高效的代码而做的工作
• “优化”这个词并不恰当，因为没有办法保证一个编译器生成的代码比完成相同任务的任何其他代码更快，或至少一样快

编译器优化必须满足下面的设计目标

• 优化必须是正确的，也就是说，不能改变被编译程序的含义
• 优化必须能够改善很多程序的性能
• 优化所需时间必须保持在合理的范围内
• 所需要的工程方面的工作必须是可管理的

设计目标

• 对正确性
• 的强调是无论如何不会过分的
• 编译器应该有效提高很多输入程序的性能，性能意味着程序执行的速度，尽可能降低生成代码的大小，同时节约能耗
• 编译时间保持在较短范围内，支持快速的开发和调试周期，当机器变得越来越快，这个要求会越来越容易达到
• 编译器是一个复杂的系统，我们必须使系统保持简单以保证编译器的设计和维护费用是可管理的

编译技术的应用

• 编译器设计不只是关于编译器的

高级程序设计语言的实现

• 一个高级程序设计语言定义了一个编程抽象，程序员使用这个语言表达算法，而编译器必须把这个程序翻译成目标语言
• 用高级程序设计语言编程比较容易，但是比较低效，目标程序运行较慢
• 低级程序设计语言的程序员能够更多控制一个计算过程，可以产生更加高效的代码
• 低级语言难编写，可移植性差，容易出错，难以维护

面向对象思想（Java）

• 特性的继承
• 不可访问的对象分配在栈里而不是堆里面
• 垃圾回收
• 可移植，可移动
• 程序以Java字节码方式分发，这些字节码要么被解释执行，要么被动态编译为本地代码
• 动态编译中，尽可能降低编译时间是很重要的
• 编译时间也是运行开销的一部分

针对计算机体系结构的优化

• 并行（parallelism）和内存层次结构（memory hierachy）
• 并行可以出现在多个层次上，指令层次上，多个运算可以被同时执行；在处理器层次上，同一个应用的多个不同线程在不同的处理器上运行
• 内存层次结构是应对下述局限性的方法：我们可以制造非常快的内存或非常大的内存，无法制造非常大又非常快的内存

并行性

• 所有的现代微处理器都采用了指令级并行性
• 硬件动态地检测顺序指令流之间的依赖关系，在可能的时候并行发出指令
• 机器包含一个硬件调度器，该调度器可以改变指令的顺序以提高程序的并行性
• 不管硬件是否对指令进行重新排序，编译器可以重新安排指令，使得指令级并行更加有效

内存层次结构

• 一个内存层次结构由几层具有不同速度和大小的存储器组成
• 离处理器最近的层速度最快但是容量最小
• 如果一个程序大部分内存访问都能由层次中结构中最快的层满足，程序的平均内存访问时间就会降低
• 并行性和内存层次结构的存在都会提高一个机器的潜在性能
• 内存层次结构可以在所有的机器中找到，层次结构中相邻层次间的存取速度会有两到三个数量级上的差异
• 系统性能经常受到内存子系统（而不是处理器的性能）的性能的限制
• 虽然优化处理器的执行，人们更多地强调如何使得内存层次结构更加高效
• 高效使用寄存器可能是优化一个程序时要处理地最重要的问题

新计算机体系结构的设计

• 决定一个计算机系统性能的不是它的原始速度，还包括编译器能够以何种程度利用其特征
• RISC（Reduced Instruction Set Computer），精简指令集计算机，在此之前CISC（Complex Instruction Set Computer），复杂指令集计算机
• 编译器优化经常能够消除复杂指令之间的冗余，把指令削减为少量较简单的运算
• 专用体系结构

程序翻译

二进制翻译

• 编译器技术可以用于把一个机器的二进制代码翻译成另一个机器的二进制代码，使得可以在一个机器上运行原本为另一个指令集翻译的程序

硬件合成

• 硬件设计通常在寄存器传输层（Register Transger Level，RTL）上描述
• 在这个层，变量代表寄存器，表达式代表组合逻辑
• 硬件合成工具把RTL描述自动翻译成为门电路，而门电路再被翻译成为晶体管，最后生成一个物理布局

数据查询解释器

编译然后模拟

• 模拟器的输入通常包括设计描述和某次特定模拟运行的具体输入参数
• 模拟可能会非常昂贵，编译的模拟运行可以比基于解释器的方法快几个数量级

软件生产率工具

类型检查

• 类型检查是一种有效的，且被充分研究的技术，它可以被用于捕捉程序中的不一致性，检测一些错误
• 可以用来捕捉某种安全漏洞，其中攻击者可以向程序提供一个字符串或者其他数据，这些数据没有被谨慎使用
• 一个用户提供的字符串可以被加上一个"危险"的标号
• 如果没有检查这个字符串是否满足特定的格式，那么它仍然是"危险"的
• 如果该类型字符串能够在某个程序点上影响的代码的控制流，存在一个潜在的安全漏洞

边界检查

• 较低级的语言编程更加容易犯错
• 很多系统中的安全漏洞都是因为C语言编写的程序中缓冲区溢出造成的，C语言没有数组边界检查，必须由用户保证数组的访问没有超出边界
• 如果程序用一种包含了自动区间检查的安全的语言编写，这个问题就不会发生
• 用来消除程序中的冗余区间检查的数据流分析技术也可以用来定位缓冲区溢出错误
• 最大区别在于，没能消除某个区间检查仅仅会导致很小的额外运行时刻开销，没有指出一个潜在的缓冲区溢出错误却可能危及系统的安全性

内存管理工具

• 垃圾回收机制是在效率和易编程及软件可靠性之间进行折衷处理的另一个极好的例子
• 自动的内存管理消除了所有的内存管理错误（内存泄漏）