编译原理复习

第一章 引论

1.2.3 编译阶段的组合

前端：词法、语法、语义

中端：中间代码生成、代码优化

后端：中端+目标代码生成

词法分析(Lexical Analysis)

从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出(拼)一个个的单词（Token/word）,Token分以下几类 ：

①字面量(literal）：3 ‘Hello,world’

②保留字(reserved word): if while

③标识符(identifier): 字母打头，后跟字母,数字等

④运算符(operater): + - < <= &&

⑤界符等类型: , ; ( ) [ ] { } .

词法分析的结果是二元组：(token的类型, token的值),

词法分析的过程，其实就是对一个字符串进行模式匹配的过程.

正则表达式

语法分析(Syntax Analysis)

又叫Parsing，语法检查（归约或推导)

把 Token 串，转换成体现语法规则的、树状的数据结构，这个数据结构叫做抽象语法树（AST，Abstract Syntax Tree）。

语义分析(Syntax Analysis)

上下文相关分析，类型匹配，类型转换，引用消解

中间(IR)代码生成

代码优化

目标代码生成

•选择合适的指令，生成性能最高的代码。

•优化寄存器的分配，让频繁访问的变量（比如循环变量）放到寄存器里，因为访问寄存器要比访问内存快 100 倍左右。

•在不改变运行结果的情况下，对指令做重新排序，从而充分运用 CPU 内部的多个功能部件的并行计算能力。

第二章 文法和语言

2.1 文法的直观概念

归约

推导

巴科斯范式（BNF）

程序语言-形式语言

形式语言是符号串集合

字母表上的符号按一定的规则组成的所有符号串集合；其中的每个符号串称为一个句子

2.2 符号和符号串

n 字母表：字母表∑是非空有穷集合，其元素称为符号。

n 符号串：由字母表∑中的符号组成的有穷序列称为 (字母表∑上的)符号串. 不含任何符号的有穷序列称为空串,记为ε。

n 规则：以某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成规则。

符号串长度 ：︱α︱

符号串集合

符号串的运算：连接，或，方幂，闭包

2.3 文法与语言的形式化定义

文法G的形式化定义包含哪些内容？

文法的生成规则（<主语> := <名词>｜<代词>）

文法使用的非终结符（代词）

文法使用的终结符（‘我’）

文法的开始符号（句子）

n定义：文法 G 定义为一个四元组（VN，VT，P，S），
记为 G ＝（VN，VT，P，S）。其中，

VN是非空有穷集合，称为非终结符集，其元素称为非终结符；

VT是有穷集合，称为终结符集，其元素称为终结符；

P是非空有穷集合，称为规则集，其元素是字母表VN∪VT上的规则，VN∪VT称为文法的字母表 V，且VN ∩VT＝F；

pS ∈ VN ，称为开始符。

规则：(重写规则、产生式、生成式）:

a∷＝b 简写为 a→b。

a∈V+ ，规则的左部，符号串b∈V*称为规则的右部。

a→ε 空规则

左部相同的多个规则，可以使用符号∣简写。如：

a→b

a→δ 可简写为 a → b∣δ

1
2
3
4
5
6
7
8
9
10

[例]  定义文法G1如下：
 G1＝(VN，VT，P，S)，其中:
  VN ＝｛S｝，
  VT ＝｛a，b｝，
  P ＝｛S→aSb，S→ab｝
亦可写成：
G1＝(｛S｝，｛a，b｝，P，S)， P＝｛S→aSb，S→ab｝
G1＝(｛S｝，｛a，b｝，｛S→aSb，S→ab｝，S)
G1[S]: S→aSb，S→ab

句型与句子

G[S] 有S ⇒┴∗ β，则称β是文法G[S]的句型。

若β∈VT*，则称β是文法G的句子。

句型:

<主语><谓语><宾语>

我 < 谓语> <宾语>

句子(当然也是句型)：我喜欢音乐

2.4 文法的类型

n乔姆斯基于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型

1 型文法（上下文有关文法，线性界限自动机）

如果一个文法的所有规则，左侧符号串的长度不大于右侧符号串的长度（空规则除外），且左侧至少含有一个非终结符， 则称此文法为 1 型文法，也称为上下文相关文法。

2 型文法（上下文无关文法）

即任一产生式左部均为一非终结符

3 型文法（正规文法，有限自动机）

文法(N, Σ, P, S)的产生式只能是以下两者之一：

pA→ e | a | aB A,B ∈ VN , a ∈ VT – 右线性文法

pA→ e | a | Ba A,B ∈ VN , a ∈ VT – 左线性文法

统称3型文法，又叫正则文法

2.5 上下文无关文法及其语法树

1
2
3
4
5
6
7
8

最左/最右推导过程示例
   [例]  已知文法如下，试给出句子aabbaa的推导过程。
G[S]：S→aAS︱a
          A→SbA︱SS︱ba
最左推导：S  aAS  aSbAS  aabAS  aabbaS  aabbaa
最右推导：S  aAS  aAa  aSbAa  aSbbaa  aabbaa

语法的二义性

如果文法G的某个句子存至少两棵不同的语法树，则称文法G是二义性的。

如果文法是无二义性的，一个句子的语法树反映了该句子的全部推导过程；

如果文法是无二义性的，一个句子的最左（最右）推导是唯一的。

二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的

2.6 句型的分析

自顶向下分析法

从文法开始符号出发，反复使用规则，寻找匹配符号串（推导）的句型，直到推导出句子或穷尽规则也不能推导出。进行每步推导时，存在两个选择问题：

选择句型中哪一个非终结符进行推导

选择非终结符的哪一个规则进行推导

最左推导，穷举规则

推导过程中一旦出现符号串α：α是合法的句子

穷尽规则，不存在α的推导过程: α不是合法的句子

1
2
3
4
5
6
7

自下而上的分析法
从输入符号串α开始，逐步进行“归约”，直至归约出文法的开始符号 S，则输入串α是文法G定义的语言的句子，否则不是。
归约是推导的逆过程
每步归约时，存在如何选择句型α的子串β进行归约的问题(α=β δ)
方案：按句柄归约-规范归约(移进-归约)
简单优先分析法(第5章)
LR分析法(第6章)

自底向上：简单优先分析法

短语，直接短语，句柄

任一子树的叶节点符号串皆为短语；一步推导就是直接短语，*步推导就是间接短语。

若子树的根是子树所有叶节点的父亲，则叶节点符号串为简单短语

右句型的最左直接短语，称为该句型的句柄。

文法化简：消除有害规则，无用符号与无用规则

有害规则： A→A

不可达(用)规则：不在任何产生式右部出现的非终结符及其规则

不可终止规则：从某非终结符开始，不可能推导出任意终结符串来。

1
2
3
4
5
6

epsilon (ε) 规则
在文法设计中，ε规则带来方便，也导致文法讨论和证明的复杂性
一个上下文无关文法G是否必须使用ε规则，完全取决于文法G产生的语言L(G[S])中是否含有ε语句。
可以证明，如果εL(G[S]),则存在一个等价的文法G’[S’] ，且G’ 不含ε规则。 
如果ε L(G[S]),则存在一个等价的文法G’[S’] ，且G’ 仅含
   S’→ε的一个空规则。

设文法G[S], ε∉L(G),消除ε规则

1
2
3
4
5
6
7

1. 首先构造可以推出空串的非终结符集：V 
① 若有 A → ; 则 令 A∈V ;
② 若有 B → A1 …An 且全部 Ai∈V ;则令 B∈V ;
③ 重复步骤①②，直到V不再扩大为止。
2. 删除 G(Z)中的 A →   形式的产生式；
3. 依次改写G[S]中的产生式 B →  X1 X2 …Xn :
※  若有 j 个 Xi∈ V ，则一个产生式将分裂为2j个!

????

第三章 词法分析

3.2　单词的形式化描述工具

1
2
3
4
5
6
7
8
9
10

正规式(正则表达式),及其表达的语言(正规集)
对给定的字母表∑
 𝜀和𝜙都是正规式，其正规集分别是{ε}和𝜙
∀𝑎∈"∑"， 𝑎是∑上的正规式，其正规集为 {a}
如果r和s都是∑上的正规式，则（算符优先级由高到低 ：*，·，|）
 (r)是正规式，它表示的正规集为L(r)
 r︱s是正规式，它表示的正规集为L(r)∪L(s)
 r·s是正规式，它表示的正规集为L(r)·L(s)
 r *  是正规式，它表示的正规集为L(r *)＝L(r)* 
有限次使用上述步骤而定义的表达式仍是正规表达式，它们表示的符号串的集合是正规集。

正规式->正规文法

1
2
3
4

正规式和正规文法之间转换
如果正规式r和文法G，有L(r)＝L(G)则称正规式r和文法G是等价的。
正规式r→文法G转换方法
设∑上正规式r，则等价文法G＝(VN, VT, P, S)。其中，VT＝∑；从形如产生式 S→r 开始，按下表规则进行转换， 直到全部符合正规文法之产生式为止，可得到P和VN 

正规文法->正规式

反过来也是一样

3.3有穷自动机

分为两类

NFA:不确定的有穷自动机(Nondeterministic Finite Automata/NFA)：输入符号包括ε, 一个符号可以标记在离开同一个状态的多条边上

DFA:确定的有穷自动机(Deterministic Finite Automata/DFA)：输入符号不含ε，每个状态以及每个符号，最多只有一条边

1
2
3
4
5
6
7

DFA形式化定义
确定有限自动机(DFA)M是一个五元组  M=(K, , f, S, Z),其中：
K: 有穷状态集
:  输入字母表(有穷)，输入符号集
f: 状态转换(移)函数，为KK的单值部分映射，f(ki，a)=kj表示：当现行状态为ki，输入字符为a时，将状态转换到下一状态kj，kj称为ki的一个后继状态
SK: 初始状态
ZK: 终态集，也称可接受状态或结束状态

1
2
3
4
5
6
7
8

NFA的形式化定义
一个非确定有限自动机(NFA) M是一个五元式M=(K, , f, S, Z)，其中：
K: 有穷状态集
: 输入字母表(有穷)
f: 状态转换函数,为K(∪{ε})P(K)的部分映射，P(K)表示K的幂集
SK是初态状态
ZK: 终态集

NFA->DFA：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

NFA→DFA的转换算法(子集构造法)
输入：NFA N    (K, , f, S0, Z)
输出：等价的DFA D   (D, , g, S= ε-closure  （{ s0} ）, F)         g(T, a)= ε-closure(move(T, a))=U;
方法：一开始，ε-closure  （{ s0 }）   是D 中的唯一状态，且它未加标记；        
              while（在D中有一个未标记状态T ）  ｛
                         给T加上标记；
                         for（每个输入符号a ）  ｛
                                 U = ε-closure(move(T, a));
                                 if ( U不在D中)
                                      将U加入到D中，且不加标记；
                                 Dtran[T, a]=U ;
                         }
              }
F＝{q︱q∈D, q∩Z≠Φ}

DFA化简

消除无用状态

无用状态：不可达，没有通路到达终态

合并等价状态

一致性条件：p和q同时是可接受状态或不可接受状态

蔓延性条件：对所有输入符号，p和q必须转换到等价的状态中

方法：分割法-状态被分成不同子集，不同的子集不等价，同一子集等价

3.4　正规式和有穷自动机的等价性

NFA M’ → 正规式r

正规式r→NFA M’

反过来即可

3.5　正规文法和有穷自动机的转换

文法->自动机

自动机->文法

反过来就行

第4章 自顶向下语法分析方法

语法分析方法

自顶向下 推导

自底向上 规约

4.1　确定的自顶向下语法分析思想

1
2
3

每一步推导中，都需要做两个选择
替换当前句型中的哪个非终结符
用该非终结符的哪个候选式进行替换

对第一个疑问：

最左推导

对第二个：

想办法选择唯一可能推导出输入串w的规则进行推导

因此需要语法设计

LL(1)文法

定义4.4 文法G是LL(1)的，当且仅当对每个VN，A的两个不同产生式A→α，A→β，满足SELECT(A→α) ∩ SELECT(A→β) = Φ 其中，α、β不能同时推导出ε。

​ L – Left to right parsing 从左至右分析token

​ L – Left-most derivation 最左推导

​ 1 –只需向右看1个符号便可以决定选择哪个产生式进行推导

FIRST(α)-串首(终结)符号集

定义4.1 设文法G＝（VN，VT，P，S），则

​ FIRST(α)＝{a︱α⇒∗aβ，a∈VT，α，β∈V*}

​ 特别地，α ⇒∗ ε，约定ε∈FIRST(α)。

FIRST集就是某个VN能推导到的第一个VT的集合

同一非终结符的多个产生式,若右部的FISRT集无交集, 则推导是确定的

FOLLOW(A)-非终结符的后继(终结)符号集

定义 4.2 设文法G＝(VN,VT,P, S)，A∈ V_N ,则

FOLLOW(A)＝{a︱S ⇒∗ αAβ, a∈V_T, a∈FIRST(β),α,β∈V*}

（或者：FOLLOW(A)＝{a︱S ⇒∗ ···Aa···，a∈VT }）

FOLLOW(A)是由任意句型中紧邻非终结符号A之后出现的终结符号a组成的集合。

SELECT(A→α) - 产生式的可选集

设文法G＝(VN,VT,P, S)，A∈VN ，A→α∈P，则

SELECT(A→α) =

FIRST(α), α/=>*epthelon

(First(α) - {epthelon}) U FOLLOW(A) α=>*epthelon

SELECT(A→α)称为规则A→α的选择集。它是FIRST(α)和FOLLOW(A)组成，是终结符号集VT的子集。

一些求解算法

求FIRST(X) 的算法

⑴ 若X ∈VT ，FIRST(X)＝{X};

⑵ 若X→ε，FIRST(X)∪＝{ε};

⑶ 对于所有形如X→a···规则，且a∈VT，FIRST(X)∪＝{a};

⑷ 对于所有形如X→Y1Y2···Yn规则，

若vi中存在不能*步推导到ε的，则

FIRST(X) ∪＝(FIRST(Y1)∪FIRST(Y2)…∪FIRST(Yi))－{ε};

如果所有的Yi都能*步推导到ε，则

FIRST(X)∪＝ (FIRST(Y1)∪FIRST(Y2)…∪FIRST(Yn))∪{ε};

⑸ 重复⑷，直到FIRST()不再扩大为止

求FIRST(α) 的算法，α ∈V*, 设|α| = n

α＝Y1 Y2···Yn∈（VN∪VT）*，置FIRST(α)= Φ 。计算FIRST(α)：

如果 Y1 ∈VT ,则 FIRST(α）＝{ Y1}；

后面两种情况与上面第四步相同

求FOLLOW(A)的算法, A ∈ VN

①置FOLLOW(A)= Φ ; 置FOLLOW(S)＝