编译原理笔记

第 01 讲 ~ 第 02 讲：概论、文法与语言

第 01 讲概论

基本概念

程序

源程序：用汇编语言或高级语言书写的程序
目标程序：用目标语言书写的程序，也就是编译转换的目标
翻译程序：将源程序转换为目标程序的程序，是汇编程序、编译程序、变换程序的总称

源程序是翻译程序的输入，目标程序是翻译程序的输出

编译与解释

编译程序：对高级语言的源程序进行翻译的程序，过程称为编译
汇编程序：特指能将汇编语言的源程序翻译成机器语言的翻译程序，过程称为汇编

相对而言，编译程序处理高级语言所以更加复杂，汇编程序处理机器码的方式相对固定，处理简单

除编译外，还有一种处理程序的方式：解释。解释对源程序进行解释执行，它们的区别在于：

编译：先编译，后运行，语法、语义等报错产生在编译过程中，运行时也会产生错误
解释：解释程序对源代码边解释边运行，所有错误都是运行过程中产生的

编译过程

编译一般来说可以分为 5 个过程：

词法分析：识别字母序列中合法的单词（token），一般而言语言具有四类词：
- 关键字或保留字（如 begin、end 、if）、标识符、常数分界符（运算符）（如 +、-、*、/、;、() 等）
语法分析：根据语法规则分辨语法成分、语句过程，并对语法进行正确性检查
语义分析、生成中间代码：对语法成分进行语义分析，产生对应的中间代码
- 中间代码：介于目标语言和源语言间的其他语言，有利于优化处理与编译程序的移植
- 分类有四元式、三元式、逆波兰表示等
代码优化：获得更高质量的目标程序，节省程序运行开销
生成目标程序：由中间代码生成目标程序的过程

编译程序构造

编译的基本阶段

按照上面的过程，我们可以把编译程序的逻辑划分为五段，每段都需要进行建表查表和出错处理两件事。

符号表管理：在进行编译的过程中，我们需要时刻保证来自源程序和编译过程中产生的信息等级于各个符号中，并对符号进行管理（增删改查等）
出错处理：编译程序要对源程序中出现的各种问题进行筛查并予以反馈

遍

将源程序和中间程序从头到尾扫描，并做相关的加工处理，生成新的程序的过程被称为一遍

通常而言，遍和基本阶段没有明显关联，执行一遍可能能够完成多个基本阶段

一遍扫描即可完成整个编译工作的称为一遍扫描编译程序

前端与后端

前端：与源语言有关的处理部分，词法、语法的分析，以及到中间代码的生成，都属于前端的部分
后端：与目标语言有关的部分，通常是目标程序生成

第 02 讲文法与语言

预备知识

符号串：符号形成的有穷序列，对字母集合 $\Sigma$ 上的符号串，其形式定义如下：
- $\varepsilon$（空串）是 $\Sigma$ 上的符号串
- 若 $x$ 是 $\Sigma$ 上的符号串，且 $a\in\Sigma$，则 $ax$ 与 $xa$ 都是符号串
- $y$ 是 $\Sigma$ 上的符号串，$iff$ $y$ 可由前两条推出
符号串集合的乘积运算：$A、B$ 为两符号串集合，则乘积为

$$
AB={xy\ |\ x\in A,y\in B}
$$

类似地，${\varepsilon}A=A{\varepsilon}=A$，${}A=A{}=\emptyset$

正闭包：对符号串集合 $A$，正闭包是所有幂运算的总和（不限长度的全排列）
闭包：正闭包 + 空串

词法：若把字符看成符号，那么单词就是符号串，单词集合就是符号串集合
句法：若把单词看成符号，那么句子就是符号串，句子集合就是符号串集合

文法与语言的定义

文法：文法是对语言结构的定义与描述，用于描述语言的结构
语法规则：通过语法规则定义句子的结构，使用 $::=$ 符号描述，表示“由…组成”
语法树：描述一个句子的语法结构，树中包含非终结符号和终结符号（单词形式）

文法

我们通常通过以下方式定义文法 $G$：
$$
G=(V_n,V_t,P,Z)\
V_n:非终结符号集合\
V_t:终结符号的集合\
P:语法推导规则集合\
Z:开始推导时的符号
$$

$V_n$ 包括所有在规则左侧出现过的符号，$V_t$ 则包含所有在规则出现、且未在 $V_n$ 中出现的符号

由非终结符号和终结符号共同组成文法的字汇表，表示为 $V=V_n\or V_t$

等价文法：两个不同的文法（通常规则不同），能产生的所有句子的集合相同（语言一致），则说明这两个文法等价

递归文法

递归规则：规则的右侧含有和左侧相同的符号（均为非终结符），相同符号位于左侧时为左递归、右侧为右递归，中间时为自嵌入递归
递归文法可以用有限条规则定义无穷的句子
左递归文法不能用自顶向下的方法来进行语法分析，所以用右递归？

推导的形式定义

$$
G:v=xUy,w=xuy\
其中x、y\in V^*,U\in V_n,u\in V*\
若U::=u\in P, 则v\underset{G}\to w\
若x=y=\varepsilon,有U::=u,则U\underset{G}\to u
$$

简而言之，就是非终结符号根据语法规则，拆分出终结符号的过程。当符号串没有非终结符号时，推导就终止了

如果通过一次或以上的推导，最后将一个非终结符号转化为终结符号，可以用这样的符号表示：$U\underset{G}{\overset{+}\to} u$

如果两个符号是直等的，那么可以这样表示：$U\underset{G}{\overset{*}\to} u$

规范推导

规范推导实际上是从最右侧的非终结符号开始执行的推导，也就是最右推导，可以用 $=|=>$ 表示

句型、句子和语言

句型是非终结符号，或推导至一半的词
句子是推导后得到的只包含终结符号的词
语言（$L(G[Z])$）：是文法能产生的所有句子的集合，已知文法可以通过推导得出所有的语言

编译器处理时，已知了句子，已知所有的文法，检测句子是否属于文法所形成的语言

短语、简单短语和句柄

给定文法 $G[Z]$，$w=xuy\in V^+$ 为句型

若 $Z\overset{*}{==>} xUy$ ，且
- $U\overset{+}{==>}u$，则 $u$ 是句型 $w$ 相对于 $U$ 的短语
简单短语则将后半句的加号去掉

简单来说，如果某个非终结符能够推出一些符号，那这部分符号就属于短语，如果能够一步直接得到，那么就是简单短语

句柄：任一句型的最左简单短语为该句型的句柄

对于找短语、简单短语而言，从语法树入手会比较简单。

语法树

我们画出某个句型的语法树，然后遍历每个子树的根节点（包括自身根节点），然后把自身范围下的所有叶子节点连成一条线，即可找出这个子树的短语（叶子节点是子树相对于整个语法树的短语）；如果在这个过程中，某个树和自己的叶子节点之间没有子树，那这个短语就是直接短语

我们以下面这个树为例（$S\to (Sd(T)db)$）：

寻找这个树的短语，我们要从每个子树开始：

左下角的 $T$：所有的叶子连起来是 $S$，短语就是 $S$，同时也是直接短语（不含子树根节点）
左下角的 $S$：叶子是 $(T)$，同时也是直接短语
上一层的 $T$：这里的叶子是 $Sd(T)$（只找最下面的一排然后连起来），因为有“左下角的 $T$ ”、“左下角的 $S$ ”两个子树，所以没有直接短语
再上一层的 $T$：同理，叶子是 $Sd(T)db$，也不是直接短语
右侧的 $S$：叶子是 $b$，是直接短语
最顶层的 $S$：相当于把所有叶子都连上，得到 $(Sd(T)db)$

最后的句柄比较好找，从所有的直接短语找一个最靠左的就可以了，这里很显然是第一棵子树的叶子 $S$

语法树的生成

对于句型 $w$，以 $Z$ 为根节点，对其进行语法树的推导，最终使得所有叶子节点项链形成 $w$，这个过程就是句型 $w$ 的推导，生成的语法树就是 $w$ 的语法树。

某些文法可以使用不同的推导序列（顺序不同），最后获得相同的语法树，某些文法则不能。
语法树的推导过程和语法树的生长过程是同步的
子树：由语法树的某个节点与其下派生的部分组成
某子树的叶子节点按序连接形成的是子树根的短语

推导与规约

自上而下地对语法树进行扩展，是句型的推导过程，而相反地，自下而上地对语法树进行剪枝，是语法树的规约过程。

规范规约：每次都剪去语法树中的句柄，实现规约的过程
规范句型：能从规范推导、规范规约过程得到的句型

二义性文法

对于一个文法的某一句子/句型，若存在两棵不同的语法树，说明其是二义性文法，若句子的推导过程不同，但只有一棵语法树，其也是无二义性的文法。
对语法树而言，若同一个规范句型具有两个不同的句柄就说明有二义性：

语法的二义性是不可判定的：没有一个有限步骤的算法判定文法是否具有二义性

有害规则与多余规则

有害规则：形如 $U::=U$ 的规则，会导致文法的二义性
多余规则：分为两种
- 不可达符号：在推导文法中的所有句子时始终用不到的规则，左侧非终结符根本不出现在其他规则里
- 不活动符号：使用该规则会推导出一个非终结符，其不能推导出一个终结符号串（这个非终结符就相当于去不掉了）
压缩文法：若文法中没有有害规则和多余规则，说明文法是压缩过的

形式语言和语言分类

文法差别在于对规则的不同限制，分为0型、1型、2型、3型
0型，短语结构文法：左右均可为符号串
1型，上下文敏感文法：$U$ 只有确定 $xy$ 作为上下文时才能进行符号改写

$$
P: xUy ::= xuy\
U\in V_n\
x, y, u\in V^*
$$

2型：上下文无关文法：在改写的过程中不需要考虑上下文，直接改写（与 BNF 文法等价）
3型：正则文法：