001.编译原理_引论
1.1 语言处理器
一个集成的软件开发环境，其中包括很多种类的语言处理器，比如编译器、解释器、汇编器、连接器、加载器、调试器以及程序概要提取工具。
预处理器（preprocessor）
- 除了编译器外，创建一个可执行的目标程序还需要一些其他程序。一个程序可能被分割成为多个模块，并存放独立的文件中。
- 把源程序聚合在一起的任务由预处理器的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。
编译器（compiler）
一个编译器就是一个程序，他可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。
任务：报告在翻译过程中发现的源程序中的错误。
编译器：源程序→编译器→目标程序
解释器（interpreter）
- 直接利用用户提供的输入执行源程序中制定的操作。
- 解释器：源程序+输入→解释器→输出
- 编译器产生的机器语言目标程序通常要比一个解释器快很多，解释器的错误诊断效果要比编译器好。
Java语言处理器结合了编译和解释的过程，一个Java源程序首先被编译成一个称为字节码（bytecode）的中间表示形式，然后由一个虚拟机对得到的字节码加以解释执行。
为了更快地完成输入到输出的处理，有些被称为即时（just in time）编译器的Java编译在运行中间程序处理输入的前一刻首先把字节码翻译成机器语言，然后再执行程序。
汇编器（assembler）
处理编译器输出的机器语言，生成可重定位的机器代码。
链接器（linker)
大型程序通常被分成多个部分进行编译，因此可重定位的机器代码有必要和可重定位的目标文件以及库文件连接到一起，形成真正在机器上运行的代码。一个文件中的代码可能指向另一个文件中的位置，而链接器能够解决外部内存地址的问题。
一个混合编译器：源程序→翻译器（中间程序）+输入→虚拟机（输出）
加载器（loader）
把所有可执行目标文件放入内存中执行。
一个语言处理系统：源程序→预处理器（经过预处理的源文件）→编译器（目标汇编程序）→汇编器（可重定位机器代码）→链接器/加载器（库文件可重定位对象文件）→目标机器代码
1.2 一个编译器的结构
1.2.1 编译器
把源程序映射为在语义上等价的目标程序，这个映射过程由两部分组成：分析部分和综合部分。
- 分析部分
- 把源程序分解成多个组成要素，并在这些要素上加上语法结构，使用这些结构创建该源程序的一个中间表示。如果检查出语法语义错误，要给提示信息。
- 收集有关源程序的信息，并把信息存放在一个称为符号表（symbol table）的数据结构中。
中间表示和符号表一起传送给综合部分
- 综合部分
根据中间表示和符号表中的信息来构造用户期待的目标程序。
分析部分经常被称为编译器的前端（front end），而综合部分被称为后端（back end）。
编译过程会顺序执行一些步骤，每个步骤把源程序的一种表示方式转换成另一种表示方式，多个步骤可能被组合在一起，而组合在一起的步骤之间的中间表示不需要被明确的构造出来。
存放在整个源程序的信息的符号表可由编译器的各个步骤使用。
有些编译器在前端和后端之间有一个与机器无关的优化步骤，这个优化步骤的目的是在中间表示之上进行转换，以便后端程序能够生成更好的目标程序，优化步骤可被省略。
一个编译器的步骤：
- 字符流
- 词法分析器（符号流）
- 语法分析（语法树）
- 语义分析（语法树）
- 中间代码生成器（中间表示形式）
- 机器无关代码优化器（中间表示形式）
- 代码生成器（目标机器语言）
- 机器相关代码优化器（目标机器语言）
（1）词法分析（lexical analysis）
编译器的第一个步骤，又称扫描。词法分析器读取组成源程序的字符流，并将它们组织称为有意义的词素（lexeme）的序列。对于每个词素，词法分析器产生词法单元（token）作为输出，并传递给语法分析。
词法单元数据结构：< token - name , attribute - value > 。
- token - name：语法分析步骤使用的抽象符号
- attribute - value：符号表中关于这个词法单元的条目，被语义分析和代码生成步骤使用。
position = initial + rate * 60，组合成以下词素，并映射成词法单元，然后将词法单元传递给语法分析阶段。
- position是一个词素，被映射成词法单元
id：标示符（identifier）的抽象符号
1:符号表中position对应的条目
一个标识符对应的符号表条目存放该标识符有关的信息。 - =是一个词素，被映射成词法单元< = >
因为这个词法单元不需要属性值，所以省略了第二个分量。
也可用assign这样的抽象符号作为词法单元的名字 - initial是一个词素，被映射为词法单元
- +是一个词素，被映射为词法单元< + >
- rate是一个词素，被映射为词法单元
- *是一个词素，被映射为词法单元< * >
- 60是一个词素，被影射为词法单元< 60 >
< number , 60 >
上述语句被表示成如下的词法单元序列：
在该表示中，词法单元名=、+和*分别是表示赋值、加法运算符、乘法运算符的抽象符号。
（2）语法分析（syntax analysis）
编译器的第二个步骤称为语法分析（syntax analysis）或解析（parsing）。
语法分析器使用由词法分析器生成的词法单元流的第一个分量来创建树形的中间表示，该中间表示给出了词法单元流的语法结构。
常用的表示方法是语法树（syntax tree），树中的每个内部结点表示一个运算，而该结点的子结点表示该运算的分量。
（3）语义分析（semantic analyzer）
语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时收集类型信息，并将信息放在语法树和符号表中。
语义分析的组成部分包括类型检查（type checking），即检查每个运算符是否具有匹配的运算分量；还有自动类型转换（coercion），比如整数转浮点数等。
（4）中间代码生成
将源代码翻译成目标代码的过程中，编译器可能生成一个或多个中间表示。在源代码的语法分析和语义分析后，编译器会生成一个明确的低级的或类机器语言的中间表示，可以把这个表示看作某个抽象机器的程序，该中间表示具有两个性质：易于生成、能够被轻松翻译为目标机器上的语言。
下面用三地址代码（three-address code）的中间表示，这种中间表示由一组类似于汇编语言的指令组成，每个指令具有三个运算分量，每个运算分量都像一个寄存器。
t1=inttofloat(60)
t2=id3*t1
t3=id2+t2
id1=t3
关于三地址指令
- 每个三地址赋值指令的右部最多只有一个运算符，因此这些指令确定了运算完成的顺序。
- 编译器应该生成一个临时名字存放一个三地址指令计算得到的值
- 有些三地址指令的运算分量少于三个
（5）代码优化
机器无关的代码优化步骤试图改进中间代码，以便生成更好后的目标代码。
使用一个简单的中间代码生成算法，然后再进行代码优化步骤是生成优质目标代码的一个合理方法。
把60从整数转为浮点数的运算可以在编译时刻一劳永逸地完成
- 用浮点数60.0来代替整数60就可以消除相应的inttofloat运算
- t3仅被使用一次，用来把它的值传递给id1
t1=id3*60.0
id1=id2+t1
有些简单的优化方法可以极大地提高目标程序的运行效率而不会过多降低编译的速度
（6）代码生成
以源语言的中间表示形式作为输入，并把它映射到目标语言，如果目标语言为机器语言，那么必须为程序使用的每个变量选择寄存器或内存地址，然后中间指令被翻译成为能够完成相同任务的机器指令序列。
使用寄存器R1和R2，（1.4）中的中间代码可以被翻译成为如下的机器代码：
| LDF | R2, id3 |
| MULF | R2, R2, #60.0 |
| LDF | R1, id2 |
| ADDF | R1, R1, R2 |
| STF | id1, R1 |
每条指令的第一个运算分量制定了一个目标地址（这里指寄存器地址），各个指令中的F表示处理的是浮点数。
- 第一条指令把地址id3中的内容移到寄存器R2中
- 第二条指令将R2寄存器中的数与浮点常数60.0相乘，“#”表示60.0作为一个立即数处理
- 第三条指令把id2移动到寄存器R1中
- 第四条指令把前面计算得到并存放在R2中的值加到R1上
- 第五条指令把寄存器R1的值被存放到id1的地址中去
上述代码忽略了对源程序中的标识符进行存储分配的重要问题。
符号表管理
记录源程序中使用的变量的名称，并收集和每个名字的各种属性相关的信息，包括类型、作用域、等信息；对于过程名字，这些信息还包括：它的参数数量和类型、每个参数的传递方法以及返回类型。
符号表数据结构为每个变量名字创建一个记录条目，记录的字段就是名字的各个属性。这个数据结构能够让编译器迅速查找到每个名字的记录，并向记录中快速存放和获取记录中的数据。
将多个步骤组合成趟
在一个特定的实现中，多个步骤的活动可以被组成一个趟（pass），每趟读入一个输入文件并产生一个输出文件。
前端步骤中的词法分析、语法分析、语义分析，以及中间代码生成可以被组合在一起成为一趟，代码优化可以作为一个可选的趟，然后有一个为特定目标机生成代码的后端趟。
有些编译器是围绕中间表示形式而创建的，这些中间表示形式可以把特定语言的前端和特定目标机的后端相结合，使用这些集合，可以把不同的前端和某个目标机的后端结合起来，为不同的源语言建立该目标机上的编译器；同理可以把一个前端和不同的目标机后端结合，建立针对不同目标机的编译器。
1.2.2 编译器构造工具
开发编译器可以利用现代的软件开发环境，包括语言编辑器、调试器、版本管理、程序描述器、测试管理等工具。
常用的编译器构造工具：
- 语法分析器的生成器：可以根据一个程序设计语言的语法描述自动生成语法分析器
- 扫描器的生成器：可以根据一个语言的语法单元的正则表达式描述生成词法分析器
- 语法制导的翻译引擎：可以生成一组用于遍历分析树并生成中间代码的过程
- 代码生成器的生成器：依据一组关于如何把中间语言的每个运算翻译成目标机上的机器语言的规则，生成一个代码生成器
- 数据流分析引擎：可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。数据流分析是代码优化的一个重要部分
- 编译器构造工具集：提供了可用于构造编译器的不同阶段的例程的完整集合
1.3 程序设计语言的发展历程
1.3.1 通过语言的代来分类
- 第一代语言是机器语言
- 由0、1序列组成，这个序列明确告诉计算机以什么样的顺序执行哪些运算
- 运算本身很低层（把数据从一个位置移动到另一个位置，把两个寄存器中的值相加、比较两个值等）
- 第二代语言是汇编语言
- 一开始汇编语言中的指令仅仅是机器指令的助记表示
- 后来宏指令被加入到汇编语言，程序员可以通过宏指令为频繁使用的机器指令序列定义带有参数的缩写
- 第三代语言是高级程序设计语言
- 包括Fortran、Cobol、Lisp、C、C++、C#、Java
- 第四代语言是为特定应用设计的语言
- 用于生成报告的NOMAD、用于数据库查询的SQL、用于文字排版的Postscript
- 第五代语言指的是基于逻辑和约束的语言
- Prolog、OPS5
1.3.2 强制式（imperative）语言和声明式（declarative）语言
强制式语言
- 指明如何完成一个计算任务的语言称为强制式语言
- 所有强制式语言中都有用于表示程序状态和语句的表示方法，这些语句可以改变程序状态
- C、C++、Java
声明式语言
- 指明要进行哪些计算的语言称为声明式语言
- ML、Haskell等函数式语言和Prolog等约束逻辑语言
冯·诺依曼语言（von Neumann language）：指以冯·诺依曼计算机体系结构为计算模型的程序设计语言
面向对象语言（object-oriented language）：支持面向对象编程的语言
面向对象编程：用一组相互作用的对象组成程序的编程风格
脚本语言（scripting language）：具有高层次运算符的解释型语言，通常把多个计算过程“粘合”在一起，这些计算过程称为“脚本”
1.3.3 程序设计语言与编译器
- 编译器的设计者不仅要跟踪新的语言特征，还需要设计出新的翻译算法，以便尽可能利用新硬件的能力
- 计算机系统的性能非常依赖编译技术，编译器会被用作评价一个体系结构概念的工具
- 现代语言处理系统包括多种编译器来处理多种源语言和目标机
- 编译器必须能够正确翻译用源语言书写的所有程序，以便解决高效代码生成的问题
1.4 构建一个编译器的相关科学
编译器的设计过程是通过数学方法抽象出问题本质而解决现实中的复杂问题，过程包括：
- 接受一个问题
- 写出抓住了问题的关键特性的数学抽象表示
- 用数学技术解决它
编译器必须接受所有符合语言规范的源程序
1.4.1 编译器设计和实现中的建模
对编译器的研究主要是关于如何设计正确的数学模型和选择正确的算法的研究
- 考虑因素：通用性、功能的要求与简单性及有效性之间的平衡
- 基本的数学模型：有穷状态自动机和正则表达式
- 用于描述程序中的词法单元以及被编译器用来识别这些单位的算法
- 基本模型：上下文无关法
- 描述程序设计语言的语法结构，比如嵌套的括号和控制结构
- 树形结构是表示程序结构以及程序到目标代码的翻译方法的重要模型
1.4.2 代码优化的科学
优化：编译器为了生成比较浅显直观、更加高效的代码而做的工作
所有编译器都面临充分利用多核处理器计算机的优势的问题
编译器优化过程中，图、矩阵和线性规划之类的模型是必不可少的
编译器优化必须满足下面的设计目标：
- 优化必须是正确的，不能改变被编译程序的含义。设计一个编译器最重要的目标是使它正确
- 优化必须能够改善很多程序的性能，编译器应该有效提高很多输入程序的性能
- 优化所需的时间必须保持在合理的范围内。编译时间需要保持在较短的范围内，以支持快速的开发和调试周期
- 所需要的工程方面的工作是可管理的，必须使系统保持简单以保证编译器的设计和维护费用是可管理的
1.5 编译技术的应用
编译器的设计方法和思想影响了计算机科学中的其他领域
1.5.1 高级程序设计语言的实现
一个高级语言定义了一个编程抽象：程序员使用这个语言表达算法，而编译器必须把这个程序翻译成目标语言
所有的通用程序设计语言都支持用户定义的聚合类型（如数组或结构体）和高级控制流（如循环和过程调用），编译器优化的一个组成部分为数据流优化，可以对程序的数据流进行分析，并消除这些构造之间的冗余，生成的目标代码更加高效
面向对象的主要思想：数据抽象、特性的继承
Java语言的特性
- 安全，即一个对象不能被当作另一个无关类型的对象来使用
- 没有指针，不允许指针运算
- 内建垃圾回收机制来自动释放不再使用的变量所占内存
- 支持可移植性和可移动的代码，程序以Java字节码的方式分布
1.5.2 针对计算机体系结构的优化
高性能系统都利用了两种技术：并行（parallelism）和内存层次结构（memory hierarchy）
并行可以出现在多个层次上：
- 在指令层次上，多个运算可以被同时执行
- 在处理器层次上，同一个应用的多个不同线程在不同的处理器上运行
内存层次结构是应对下述局限性的方法：无法制造非常大又非常快的内存
(1) 并行性
现代的微处理器都采用了指令级并行性，硬件动态地检测顺序指令之间的依赖关系，并且在可能的时候并行地发出指令。机器包含一个硬件调度器，该调度器可以改变指令的顺序以提高程序的并行性。
指令级的并行也显式地出现在指令集中，VLIW（very long instruction word，非常长指令字）机器拥有可并行执行多个运算的指令。程序员可以为多处理器编写多线程代码，也可以通过编译器从传统的顺序程序自动生成并行代码。
(2) 内存层次结构
如果一个程序的大部分内存访问都能够由层次结构中最快的层满足，那么程序平均访问内存的时间就会降低。
高效使用寄存器是优化一个程序时要处理的最重要的问题。
- 寄存器由软件管理
- 高速缓存和物理内存是对指令集合隐藏的，由硬件管理
可以通过改变数据的布局或数据访问代码的顺序来提高内存层次结构的效率，也可通过改变代码的布局来提高指令高速缓存的效率
1.5.3 新计算机体系结构的设计
在计算机体系结构设计的早期，编译器是在机器建造好之后再开发的，现在，使用高级程序设计语言是一种规范，编译器在处理器设计阶段就进行开发，编译后的代码运行在模拟器上
(1) RISC
编译器影响计算机体系结构设计的例子，RISC（Reduced Instruction-Set Computer，精简指令集计算机）的发明。
在RISC之前，趋势是开发的指令集越来越复杂，以使得汇编编程原来越容易，这种体系结构称为CISC（Complex Instruction-Set Computer，复杂指令集计算机），由于编译器优化能消除复杂指令之间的冗余，把这些指令削减为少量较简单的运算，所以期望设计出简单的指令集，以便编译器有效的使用和硬件优化。
(2) 专用体系结构
过去三十年有很多体系机构概念，包括：数据流机器、向量机、VLIW（非常长指令字）机器，SIMD（单指令，多数据）处理器阵列、心动阵列（systolic array）等，每种体系结构概念的发展都伴随相应编译技术的研究和发展。通用处理器趋于雷同，专用处理器趋于多样，编译器技术为这些体系编程提供支持和衡量该体系结构设计的评价
1.5.4 程序翻译
编译技术可以用在不同种类语言之间的翻译
(1) 二进制翻译
- 编译器技术可以把一个机器上的二进制代码翻译成另一个机器上的二进制代码，使得可以在一个机器上运行原本为另一个指令集编译的程序
- 二进制翻译也可以被用来提供向后兼容
(2) 硬件合成
- 大部分硬件设计都是用Verilog和VHDL（very high-speed integrated circuit hardware description language，甚高速集成电路硬件描述语言）高级硬件描述语言描述的
- 硬件设计是在寄存器传输层（Register Transfer Level，RTL）上描述，在RTL中，变量代表寄存器，表达式代表组合逻辑
- 硬件合成工具把RTL描述自动翻译成门电路，门电路再被翻译为晶体管，最后生成一个物理布局
(3) 数据库查询解释器
- 除了描述软件和硬件，语言在应用在其他方面
- 查询语句（SQL语言（Structured Query Language，结构化查询语言））被用来搜索数据库，它们可以被解释执行或编译为代码
(4) 编译然后模拟
- 模拟是在很多科学和工程领域通用的技术，用来理解一个现象或验证一个设计
- 两种模拟方法
- 写一个模拟器来解释不同的输入集合
- 对输入集合编译并生成能够在机器上直接模拟特定设计的机器代码
1.5.5 软件生产率工具
为了检测程序错误可以通过数据流分析技术静态地（即在程序运行之前）定位错误，这些分析是在原本为编译器代码优化而开发的技术的基础上建立的，但优化器是保守的，在任何情况下都不能改变程序的语义。
(1) 类型检查
- 捕捉程序中的不一致性
- 捕捉某种安全漏洞
(2) 边界检查
- 较低级语言没有边界检查，访问超出边界，易发生缓冲区溢出
- 数据流分析技术可以消除程序中的冗余区间，定位缓冲区溢出错误
- 要获得高质量的结果需要更复杂的分析技术，比如在过程之间跟踪指针值的技术
(3) 内存管理工具
- 垃圾回收机制是在效率、易编程和软件可靠性之间折衷的一个例子
- 自动的内存管理消除了所有内存管理错误（比如内存泄漏）
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！