# 编译器概述

# 语言的分类

语言可以分为形式语言 (程序设计语言) 和自然语言。编译原理的研究对象是形式语言。形式语言的语法是严格的，这与自然语言不相同。研究语言的思路包括符号主义、连接主义。符号主义的思想是从语言中发掘逻辑规律，而连接主义的思想是将句子中的相邻词语进行词频统计，进而采用概率分析的方法得到语言分析的结果。因此，符号主义多用于程序语言，连接主义多用于自然语言。

# 程序设计语言的分类

程序设计语言可以分为四类：

机器语言：机器直接识别的语言或指令码。
汇编语言：采用易于记忆的符号表示的计算机指令。
高级语言
MSIL 和 ByteCode：在虚拟机上运行的中间语言。

# 编译程序

翻译程序：把一种语言翻译成另一种语言的程序。
编译程序：把高级语言翻译成低级语言的程序，又称编译器。
解释程序：以源语言为输入，不产生目标程序，边编译边执行。
汇编程序：把汇编语言翻译成机器语言的程序，又称为汇编器。

# 编译程序的生成

宿主机、目标机

# 高级程序设计语言

IBM704 标志着汇编语言的成熟 (1956)。

1954 年 IBM 发布 Fortran, 1956 年正式使用。

# 分类

高级程序语言
- 命令式语言
  - 面向过程的语言
  - 面向对象的语言：封装性、继承性、多态性三个主要特点。
- 声明式语言
  - 函数式语言： Lisp
  - 基于规则的语言： Prolog
  - 数据库查询语言： SQL
  - 正则表达式
  - 组态语言与图形化语言： UML

# 命令式编程

命令式编程 (Imperative programming), 又称强制式语言。

# 面向过程的语言

# 声明式

# 编译器框架

编译器一般包括五部分：

词法分析 (Lexical analysis)
语法分析 (Syntax analysis)
语义分析和中间代码生成 (Semantic analysis)
代码优化
目标代码生成

# 文法和语言设计

这部分内容与计算理论的内容相似，但更偏向应用层面。

# 文法

# 文法的形式化定义

一个文法 (grammar) 是一个四元组 $(V_N,V_T,P,S)$ . 其中

$V_N$ 是一个非空有限集，称为变元集 (variables) 或非终结符集 (non-terminals).
$V_T$ 是一个非空有限集，且 $V_N \cap V_T = \varnothing$ , 称为终结符集 (terminals).
$P$ 是一个非空有限集，称为产生式集合 (productions), 其中的元素称为产生式，表示为 $\alpha \to \beta$ , 其中 $\alpha \in (V_T\cup V_N)^*V_N(V_T\cup V_N)^*$ , $\beta \in (V_T\cup V_N)^*$ . 特别地，若 $P$ 中存在多个产生式左部相同，如 $\alpha \to \beta_1, \alpha \to \beta_2 \in P$ , 则可以简记作 $\alpha \to \beta_1|\beta_2$ .
$S \in V_N$ 是一个非终结符，称为开始符号或起始变元 (start variable).

# 文法的分类

根据文法的定义，可以对文法给出一个严谨的分类方式。乔姆斯基 (Chomsky) 最早进行了文法的分类，其将文法分为四类，称为 0 型文法、1 型文法、2 型文法和 3 型文法。其中，

0 型文法又称无限制文法，对应的语言为递归可枚举语言，或图灵可识别语言；
2 型文法又称上下文无关文法 (context-free grammar), 对应的自动机是下推自动机 (PDA);
3 型文法又称右线性文法或正则文法 (regular grammar), 对应的自动机是有穷自动机 (FA).

而在编译原理中，主要研究的是 1 型文法，又称上下文有关文法。这也是其与计算理论课程的一个重大区别。

# 语言

若 $G[S]$ 是一个文法，且 $S \Rightarrow^{\!*} \alpha$ , 则称 $\alpha$ 是一个句型 (sentential form). 不含非终结符的句型称为句子 (sentence).

# 短语和句柄

对文法 $G[S]$ , 若有 $S \Rightarrow^{\!*} \alpha A\delta$ , 且 $A \Rightarrow \!\!\!\!\!\!\!\!\!\ ^{\ ^+}\ \ \beta$ , 则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于非终结符 $A$ 的短语 (phrase).

# 二义文法

如果一个文法的某个句子错在两个不同的语法树，那么称该文法为二义文法.

文法的二义性不同于语言的二义性

# 词法分析

词法分析的过程借助词法分析器完成。词法分析器 (Lexical Analyzer) 又称扫描器 (scanner), 作用是将原程序从字符流转化为单词符号序列 (即语素，lexemes).

# 单词符号

词法分析中将字符流转化为单词序列的过程，

程序语言中的单词符号可以分为以下五类：

关键字 (keyword): 又称保留字 (reserved word)、基本字，例如 C 语言中的 if , while , int 等。编码时，可以将全体关键字标为同一编码，也可以一字一码。
标识符：用来表示各种名字，如变量名、数组名、过程名等。编码时归为一种。
常数😦const) 包括整型、实型、布尔型等。编码时宜按照类型编码。
运算符 (operator): 如 + , / 等。编码时可以一符一种，也可以将一定共性的符号分至同一种。
界符：如逗号、分号、括号、注释符号等。编码时一般一符一种。

严格来讲，关键字和保留字并不等价。关键字是语义 (semantic) 定义的内容，而保留字是句法 (syntactic) 定义的内容。关键字是保留字的子集。参考 Wikipedia: Reserved word.

# 词法分析器的设计

# 预处理

预处理的目的是方便单词识别，其包括两个操作：

将连续的缩进符、换行符、多个空格转为 1 个空格
删除注释

# 超前搜索

超前搜索的目的是确定单词的类别。仅依靠当前扫描得到的信息可能难以得到当前的单词类别。一个最经典的例子来自 Fortran 语言：

DO5I=1.25
DO5I=1,25

在上面的两个语句中， DO5I 依次是循环 DO 5 I=1.25 的一部分和变量名 DO5I . 仅当语法分析器扫描到 . 或 , 时，语法分析器才能确定 DO5I 的单词类别。因此，需要借助超前搜索技术。此外，一些复合运算符，如 >= , ++ 等也需要借助超前搜索确定。

超前搜索的本质是采用贪心确定单词，即希望一个单词是尽可能长的。

# 超前搜索的避免

注意到，产生超前搜索的原因是在缺少空格标记的清空下，词法分析程序难以区分标识符和关键字。因此，现代语言一般规定

关键字都是保留字，不可作为标识符
关键字和标识符、常数等之间必须有界符或空白符间隔

这样，就在语言规则层面避免了复杂的超前搜索。

# 缓冲

如果采用 getchar() 等方式进行字符流读取，那么读取的过程是不可逆的。而对于较大的源程序，将其全部读入内存是不现实的。因此，词法分析程序需要借助缓冲区实现超前搜索功能。

假设缓冲区的大小是 64bit, 那么若语言限制标识符最大长度为 64bit, 则缓冲区内可能不能纳入完整的标识符。此时，可以借助双缓冲机制解决该问题。

在双缓冲机制中，存在两个长度相等的缓冲区，且标识符长度限制为不超过一个缓冲区的大小。这样，当语法分析器不能确定第一个缓冲区内的标识符是否完整时，其会前往下一个缓冲区进行扫描，就可以实现标识符的正确判断了。

# 状态转换图

状态转换图是词法分析程序识别单词符号的一种方式。在计算理论中，我们已经知道了状态转换图与有穷自动机等价。因此，也可以说采用有穷自动机实现词法分析中的单词识别。

# 语法分析

# 自上而下的语法分析

# 自上而下面临的问题

消除左递归
题左公因子以消除回溯

# 消除左递归

# 直接左递归

直接左递归采用转换为右递归的方式消除。例如，对直接左递归

$P \to P\alpha|\beta$

需要将其转换为

$P \to \beta P',\, P' \to \alpha P'|\varepsilon$

# 隐含左递归

对隐含左递归

# 自下而上的语法分析

# LR 分析

LR 分析器 (LR Parser) 是一种用于识别上下文无关语言的语法分析器。其在自左向右读取输入串的过程中产生文法的最右递归，是确定性分析器中最为强大的一种。

我们称一个 LR 分析器为 LR (k) 分析器，当且仅当该分析器每步需要提前向右读取 $k$ 个符号。

LR 分析包括四种方法：

LR (0) 分析
简单 LR (SLR)
规范 LR
向前 LR (LALR)

# LR (0) 分析

# LALR 分析

LALR 是在 LR (1) 的基础上合并同类项得到的。

# 语法制导翻译

# 属性文法

在上下文无关文法的基础上，为每个文法符号赋予若干属性。属性的特点包括：

属性中内含文法符号的相关信息
属性可以进行计算和传递
属性的计算过程就是语义的处理过程
都文法的每个产生式都有一组属性的计算规则，称为语义规则

# 语义分析和中间代码生成

语义规则中的操作：

mktable (previous) : 创建一张新符号表，并返回指向新表的指针；参数 previous 指向先前创建的一张符号表。
enter(table, name, type, offset) : 在指针 table 指向的符号表中，为名字 name 建立一个新项，并把类型 type , 相对地址 offset 填入到该项中。
addwidth(table, width) : 在指针 table 指向的符号表表头中，记录下该表中所有名字占用的总宽度。
enterproc(table, name, newtable) : 在指针 table 指向的符号表中，为名字为 name 的过程建立一个新项；参数 newtable 指向过程 name 的符号表。
tblptr 是一个栈，用于存放指向嵌套外层过程的符号表指针。
offset 是一个栈，用于存放变量的相对地址，当过程结束时， offset 里记录的是过程占用的所有字节数。
lookup(name) : 从 top(tblptr) 符号表寻找名字，找到即返回，找不到则转到外围（上层）符号表继续查找，直到找到或者所有外围过程都找不到为止。
gen(op, arg1, arg2, result) : 生成三地址代码。
newtemp : 是一个方法，生成一个临时变量。
place : 是一个属性，存放文法符号的值（变量）的名字。
nxq : 即 Next Quadruplet, 指向下一条将要产生，但尚未产生的四元式地址 (标号)，执行一次 gen 增 1.
mklist(i) : 创建一个链表，这个链表仅含标号为 𝑖的四元式，并返回链表指针。
merge(p1, p2) : 把以 p1 和 p2 为链首的两条链合并，返回新的链首。当遇到 E1⋀E2 时，它们的 falselist 链表需要合并；当遇到 E1⋁E2 时，它们的 truelist 链表需要合并。
backpatch(p,t) : 回填，把 p 所链接的每个四元式的第四区段都填 t . 当遇到 E1⋀E2 时， E2 确定了 E1 的 truelist 链表需要回填的地址；当遇到 E1⋁E2 时， E2 确定了 E1 的 falselist 链表需要回填的地址。

# 运行时的存储空间组织

# 代码优化

# 概述

# 代码优化的原则

代码优化应考虑以下三原则：

等价原则：经过优化的代码不应改变程序运行的结果。
有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小。
合算原则：应尽可能以较低的代价取得较好的优化效果。

# 代码优化的环节

代码优化按照代码生成的顺序可以划分成以下几个环节：

源代码级别：选择适当的算法，比如排序算法中，快速排序优于插入排序。
语义动作级别：
- 生成更高效的中间代码。
- 加入对优化的预备工作。如循环的开头和结尾处打上标记，方便控制流和数据流分析；代码分叉和交汇处打上标记，方便识别流程图中的直接前驱和直接后继。
中间代码级别：安排专门的优化阶段。
目标代码级别：考虑如何有效的利用寄存器，如果选择指令，以及进行窥孔优化等。

# 局部优化

要对代码进行局部优化，首先需要对代码进行划分，划分的单元称为基本块，其指的是程序中一段顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一条语句，出口是其中最后一条语句。

# 基本块优化的方式

基本块优化包括以下基本方法：

删除无用子表达式
删除无用赋值
合并已知量
临时变量改名
交换语句位置
代数变换

# 期末考试考点总结

# 简答与计算

编译过程的各阶段
二义文法
短语和句柄
FA / 正则表达式 / 线性文法的互相转换
消除左递归 (包括间接左递归)
提取左公因子
后缀表达式 (需要知道运算符的优先级)
符号表
运行时空间组织

# 综合题

词法分析
- 构造 NFA
- 确定化
- 最小化
LL (1) 分析
- 构造 First 集合，Follow 集合和 LL (1) 分析表
- 二义文法冲突的解决
- 识别句子
LR 分析
- 构造拓广文法
- 构造项目集规范族
- 构造 LR 分析表，消除冲突
- 识别句子
给出翻译模式和高级语言程序，翻译句子
- 填写声明语句的符号表
基本块优化
- 给出 DAG
- 构造优化后的中间代码
- DAG 目标优化后的中间代码
- 根据变量活跃性和寄存器信息写出目标代码