编译原理 —— 绪论
绪论
1、编译器的概念
编译程序是现代计算机系统的基本组成部分：
从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言-source language）书写的程序翻译成另一种语言（称作目标语言-target language）书写的等价的程序。
- 编译器的输入为源程序
- 编译器的输出为目标程序
- 如果源程序书写错误，编译器将会输出一个错误信息
- 源语言和目标语言是多种多样的
- 一般来说，源语言是面向人的高级语言，目标语言是面向机器的低级语言（机器语言）
- 编译器执行的是一个等价变换，源语言和目标语言的程序功能一样、执行结果一样
2、编译的阶段
2.1、编译的分析-综合模型（Analysis-Synthesis Model of Compilation）
- 分析：分析源程序，计算其基本属性，生成源程序的中间表示（intermediate representation）
- 综合：将源程序的中间表示转换为目标代码
2.2、编译的逻辑过程：
- 词法分析（Lexical Analysis）
- 语法分析（Syntax Analysis）
- 语义分析（Semantic Analysis）
- 中间代码生成（Intermediate Code Generation）
- 中间代码优化（Machine-Independent Code Optimization）
- 目标代码生成（Code Generation）
- 机器代码优化（Machine-Dependent Code Optimization ）
2.2.1、词法分析（Lexical Analysis）：
- 功能：从左至右读源程序（字符流），识别单词符号（又称记号token）
- 输入：源程序字符序列 → 输出：单词符号序列
- 词法分析又称线性分析或扫描（Linear Analysis，Scanning）
例子：position = initial + rate * 60
词法分析后的结果
| 单词类型 | 单词 |
|---|---|
| 标识符1(id1) | position |
| 算符(赋值) | = |
| 标识符2(id2) | initial |
| 算符(加) | + |
| 标识符3(id3) | rate |
| 算符(乘) | * |
| 整数 | 60 |
2.2.2、语法分析（Syntax Analysis）
- 功能：层次分析（Hierarchical Analysis）
- 依据：源程序的语法规则
- 输入：单词符号序列 → 输出：分析树（Parse Tree）（或语法树-Syntax Tree）
- 语法分析又称解析（Parsing）
例子：position = initial + rate * 60
语法分析后的结果
- 分析树
-
语法树
语法树是分析树的压缩表示
2.2.3、语义分析（Semantic Analysis）
-
功能：语义检查，即验证语法结构合法的程序是否在语义上正确（程序的各个组成部分组合在一起是否有意义）。
-
步骤：
- 收集代码生成阶段需要的语义信息
- 类型检查与类型转换
-
注意：语法正确的语句，语义不一定正确。（比如：大象吃香蕉 和 香蕉吃大象 这两句的语法都是正确的[主+谓+宾]，但是后者的语义明显是不正确的）
-
（输入）分析树 → （输出）带语义（注释）的树
例子：position = initial + rate * 60
将60 从 int 类型转化为 float 类型是语义分析语义分析阶段进行处理的
2.2.4、中间代码生成（Intermediate Code Generation）
- 功能：生成源程序的中间表示。
- 通常采用三地址代码的表现形式（three address-code）
- 输入：带语义（注释）的树 → 输出：中间代码
例子：position = initial + rate * 60
生成的中间代码：
（操作符，操作数1 操作数2 赋值数）
赋值数为临时变量
（1）将 60 从 int 转化成 float 类型，再将其赋值给 t1
（2）将 id3 与 t1 相乘，再将结果赋值给 t2
（3）将 id2 与 t2 相加，再将结果赋值给 t3
（4）将 t3 的值赋值给 id1
2.2.5、代码优化（Code Optimization）
- 功能：对中间代码进行优化（提高时间与空间效率）
例子：position = initial + rate * 60
代码优化前：
(1) (inttofloat ， 60 - t1 )
(2) ( * ， id3 t1 t2 )
(3) ( + ， id2 t2 t3 )
(4) ( := ， t3 - id1 )
代码优化后：
(1) ( * ，id3 60.0 t1)
(2) ( + ，id2 t1 id1)
2.2.6、代码生成（Code Generation）
- 功能：生成目标代码
- 目标代码：机器代码（machine code）、可重定位的机器代码（relocatable machine code ）、汇编语言代码（assembly code）
例子：position = initial + rate * 60
( * , id3 60.0 t1 ）
( + , id2 t1 id1 )
生成的目标代码：
movf id3 , R2
mulf #60.0 , R2
movf id2 , R1
addf R2 , R1
movf R1 , id1
（1）将 id3 的值存到寄存器 R2 中
（2）将 60.0 乘以 R2 再将结果存到 R2 寄存器中
（3）将 id2 的值存放到寄存器 R1 中
（4）将 R2 寄存器中的值与 R1 寄存器中的值相加，存放到 R1 寄存器中
2.2.7、目标代码优化
不同平台的目标代码优化的方法不同
2.3、两个模块
2.3.1、符号表管理（Symbal-Table Management）
- 功能：管理分析过程中得到的源程序中的标识符的各种信息
- 记录源程序中使用的标识符（identifier）
- 收集每个标识符的各种属性（attribute）信息，包括类型（type）、作用域（scope）、存储分配（storage allocated）信息
2.3.2、出错处理（Error Detection and Reporting）
功能：
- 检查错误的位置
- 检查错误的性质（词法、语法、语义…）
- 错误恢复
3、编译器的结构
3.1、编译器结构的划分
前端（Front end）与后端（Back end）
- 前端：只依赖于源程序，独立于目标机器
- 后端：依赖于目标机器，与源程序无关，只与中间语言有关
好处：
- 取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器
- 不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）
例如：
假如有 n 种前端代码 ， m 种后端代码
如果未使用前后端分离，需要开发 n * m 种编译器
如果采用了前后端分离 ，需要考法 n + m 种编译器
3.2、遍（Pass）
遍：对源程序或源程序中间表示的一次扫描，每一遍读入一个文件。执行一个或几个阶段的编译操作，并输出源程序的一个中间表示
- 每一遍的输入是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码
- 遍数多：编译器结构清晰，但时间效率不高（每一遍都需要读写一次磁盘）
- 遍数少：编译速度快，但对机器的内存要求高
在编译器的实现过程中我们经常将前端作为第一遍，将后端作为第二遍。（这样既考虑到效率问题，又考虑到了存储空间的需求问题）
4、编译器的实现
4.1、编译器实现的问题
-
如何用已有高级语言实现其它高级语言的编译程序？
用语言 L 的编译器编译用 L 书写的另一高级语言的编译器
（例如，用已有的 C 语言编写 PASCAL 语言，然后再用 C 语言的编译器编译 PASCAL 语言。
这样就避免了 PASCAL 编译器的编写）
-
世界上第一个编译程序是用什么语言书写的？
- 没有可用的高级语言
- 没有可用的编译器
因此世界上第一个编译器只能是用机器语言开发的
4.2、自展技术
直接用目标机器上的机器语言书写源语言的编译程序工作量太大
自展技术：用目标机器上的机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序。
例如：
L1：用于实现目标代码编译的基本功能的子语言，利用机器语言进行编写
L1+L2：在 L1 语言基础上进行开发的一些扩展的功能，于是L1+L2 语言的编译器是利用 L1 语言去编写的
L1+L2+L3：在 L1+L2 语言基础上进行开发的一些扩展的功能，于是L1+L2+L3 语言的编译器是利用 L2+L1 语言去编写的
…
直至完成目标语言编译器的开发
4.3、编译器的构造工具
- 词法分析器自动生成程序 — LEX
- 语法分析器自动生成程序 — YACC
5、编译器的伙伴
一个语言处理系统
5.1、预处理器（Pre-processors）
- 删除注释
- 宏（Macro）展开
- 处理包含文件
- 语言扩充
5.2、汇编器（Assemblers）
- 处理汇编语言代码，产生可重定位的机器代码
5.3、装配器和连接编辑器（Loader/Link-Editors）
- 将多个可重定位机器代码文件连接装配成一个可执行机器代码文件。