浅学编译原理

为考试而学——CS课程的悲哀

~~教材字多，懒的看~~

语言和语法

基本术语及概念

字母表和符号

符号：语言中不可再分的单位

例如：

汉字的字母表：汉字、数字和标点符号等。
英文的字母表：{a,b,…,z , A,b,…,Z}。
二进制的字母表：{0,1}。
标识符的字母表：{a,b,…,z , A,b,…,Z , 0…9 , _ }。

字母表：符号的非空有穷集合

$\sum= \{ x |x\in ASCII \}$

$V_1 = \{ a,b,c\}$

符号串

某个字母表上的符号的有穷集合

$V_1 ：a,b,c,ab,bc, ac,abc,...$

$V_2: 123,+12,-2,...$

空串（ε）：不含任何符号的串

语句

字符表上符号某种构成规则的符号串序列

用a, b, c,…表示符号

用 $\alpha,\beta,\gamma,...$ 表示符号串

用A, B, C, …表示符号或符号串的集合

语言

某个字母表上的句子集合

符号串集合的积

若 $A = \{a,b\}, B = \{c,e,d\},$ 则 $AB = \{ac,ae,ad,bc,be,bd\}$

即二者的笛卡尔积 $AB=\{ \alpha \beta |\alpha \in A,\beta \in B \}$

字符串集合的幂

$A^0 = \{\epsilon \}$ ，空串 $\epsilon$

$A^n = \{AA^{n-1} \}$

若 $|A| = m,$ 则， $|A^0| = 1, |A^1|=m,|A^m| = m^n$

闭包和正闭包

闭包： $A^* = A^0 \cup A^1 \cup A^2 \cup ...$

正闭包： $A^+ = A^* - \{\epsilon \}$ ，正闭包就是不包含空串

一个语言是其字母表上闭包的子集

文法

表达语言构成规则的形式化方法： $G = {V_N,V_T,S,P}$

下面有更详细的介绍。

推导与规约

推导：使用产生式的右部替代左部的过程

归纳：推导的逆过程，即用产生式的左部替换右部的过程

句型、句子和语言

句型：从文法开始符号S开始，每步推导（包括0步）所得到的字符串 $\alpha,S → \alpha$ ,其中 $\alpha \in (V_N,V_T)^*$

句子：仅含终结符的句型

语言：由S推导得到的句子集合

$L(G) = \{\alpha | S → \alpha,且\alpha \in V_T ^* \},G$ 为文法。

文法递归

非终结符的定义中包含了非终结符自身

$\sum = \{0,1 \}$

$<S> → <D><S><D>$

$<D> → 0|1$

BNF范式

巴科斯范式（BNF）所描述的语法是与上下文无关的。

( )：提出因子

$U → ax|ay|az$ 可写成 $U → a(x|y|z)$

{ }：指定重复次数

$<标识符> →<字母>\{<字母>|<数字>\}^{(3)}_{(0)}$

[ ]：任选符号

$<数字> → [+|-]<数字>\{<数字>\}$

文法和语言的形式定义

文法的直观概念

文法是对语言结构的定义与描述。

即从形式上用于描述和规定语言结构的成为“文法”（语法）。

所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。

“形式”是指：语言的所有规则只以什么符号串能出现的方式来陈述。

语法规则

规定用 ::=表示 由...组成。

例如：

<句子> ::= <主语><谓语>
<主语> ::= <代词>|<名词>
<代词>  ::= 你|我|他
<名词> ::= 王民|大学生|工人|英语
<谓语> ::= <动词><直接宾语>
<动词> ::= 是|学习
<直接宾语>::=<代词>|<名词>

规则

规则（重写规则、产生式、生成式）是形如 $\alpha → \beta$ 或 $\alpha ::= \beta$ 的 $(\alpha,\beta)$ 的有序对。

其中 $\alpha \in V^+,\beta \in V^*$

$\alpha$ 称为规则的左部
$\beta$ 称为规则的右部

例如：

<程序> → <分程序>

<条件语句> → IF<条件>THEN<语句>

文法的定义

文法G定义为四元组 $(V_N,V_T,P,S)$

$V_N$ ：非终结符集

**非终结符(nonterminal)**是用来表示语法成分的符号，有时也成为“语法变量”

例： $V_N = \{<句子>,<名词短语>,<名词短语>,<动词>,...\}$

$V_T$ ：终结符集

**终结符(terminal symbol)**是文法所定义的语言的基本符号，有时也称为token

例： $V_T = \{apple,boy,eat,little\}$

$P$ ：产生式集合（规则集合）

**产生式(production)**描述了将终结符和非终结符组合成串的方法

产生式的一般形式： $\alpha → \beta$ 读作： $\alpha$ 定义为 $\beta$

$S$ ：开始符号（识别符号）

**开始符号(start symbol)**表示的是该文法中最大的语法成分， $S \in V_N$

其中，

$V_N,V_T和P是非空有穷集$
$S \in V_N,并且S至少在一条规则中作为左部出现$
$V_N \cap V_T = ∅$
$V = V_N \cup V_T,V称为文法G的字母表$

例：

文法 $G = (V_N,V_T,P,S)$

$V_N = \{S\}$

$V_T = \{0,1\}$

$P=\{S → 0S1,S → 01\}$

$S$ 为开始符号

文法的简写形式：

只写出产生式 或者 G写成G[S]，S是开始符号

$G: S → 0S1$

$S → 01$

文法的类型

0型、1型、2型和3型。

差别在于对产生式的不同限制。

0型文法（短语文法）

$\alpha → \beta$ , 其中 $\alpha \in (V_N \cup V_T)^*$ ，（*表示闭包，用集合中的任意一个元素组合形成的串), 且至少含有一个非终结符，而 $\beta \in (V_N \cup V_T)^*$ 。

0型文法也称短语文法。

0型文法的能力相当于图灵机，任何0型语言都是递归可枚举的，即递归可枚举集必定是一个0型语言。

一般见到的文法都可看做0型文法。

例如： $A → ab, A → Cb, A→b$

1型文法（上下文有关文法）

$\alpha → \beta$ , 均满足 $|\alpha| \le |\beta|$ ，除 $\alpha → \epsilon$ 外。

1型文法又称上下文有关文法。

产生式左部可以有多个字符，但必须有一个非终结符；产生式右部可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符且左部长度必须小于右部（ $\alpha → \epsilon$ 除外）。

例如： $A → B, A →Bab, Bc → A$

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

产生式形式： $A → \beta$

2型文法又称上下文无关文法。

产生式左部必须是非终结符，然而一个终结符一个非终结符的组合不是非终结符，如Ab就不是一个非终结符，但是两个非终结符的组合就是一个非终结符，如AB。

产生式右部字符任意，可终结符，也可非终结符，但必须是有限个字符。

例如： $AB → ab, B → Ab$

3型文法（正规文法）

3型文法又称正规文法，而正规文法又包括左线性文法和右线性文法。

左线性文法

产生式形式： $A → \alpha B$ 或 $A → \alpha$

左部只能有一个字符，且必须为非终结符；

右部最多有两个字符，如果有两个字符，必须为终结符+非终结符格式，如果是一个字符，必须为终结符。

例如： $B → aB$

右线性文法

产生式形式：或 $A → \alpha$

左部只能有一个字符，且必须为非终结符；

右部最多有两个字符，如果有两个字符，必须为非终结符+终结符格式，如果是一个字符，必须为终结符。

例如： $B → Ba$

所以左右线性文法的区别就在于右部的非终结符在右部两个字符的左还是右。

推导⇒

给定文法 $G=\{V_T,V_N,P,S\}$ ，如果 $\alpha →\beta \in P$ ，那么可以将符号串中的 $\alpha$ 替换为 $\beta$ ，即将** $\gamma \alpha \delta$ **重写(rewrite)为 $\gamma \beta \delta$ ，记作 $\gamma \alpha \delta$ ⇒ $\gamma \beta \delta$ 。

此时，称文法中的符号串 $\gamma \alpha \delta$ **直接推导（directly derive）**出 $\gamma \beta \delta$

即，用产生式的右部替换产生式的左部

$⇒^n$ ：经过n步推导
$⇒^+$ ：表示经过正数步推导
$⇒^*$ ：表示经过若干（可以是0）步推导

归纳

上文有讲，归纳即推导的逆过程，看下图可直观理解推导与归纳的关系。

最左（最右）推导

所谓最左（最右）推导，是指对于一个推导序列中的每一步直接推到 $\alpha$ ⇒ $\beta$ ，都是对 $\alpha$ 中的最左（最右）非终结符进行替换。

例如，设有文法G[S]:

S → N
N → NH | H
H → 0 | 1 | 2

该文法所定义的语言是由数字0, 1, 2组成的所有无符号整数集合，其中符号串01是该文法的一个句子，那么此句子可以通过不同的推到序列得到（注意加粗字符）：

S ⇒ N ⇒ NH ⇒ N1 ⇒ H1 ⇒ 01
S ⇒ N ⇒ NH ⇒ HH ⇒ 0H ⇒ 01
S ⇒ N ⇒ NH ⇒ HH ⇒ H1 ⇒ 01

在上面三个推导序列中：

是最右推导，每次都是把最右边的字符推导完成；
是最左推导，每次都是把最左边的字符推导完成；
这次左下次右，跟渣男（女）似的推导，既不是最右推导也不是最左推导。

规范推导和规范归纳

最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。

规范推导的逆过程称为最左归纳，也称为规范归纳。

句型和句子

如果，则称 $a$ 是 $G$ 的一个 句型(sentential form) ，

一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串。

如果 $S⇒^* w,w \in V_{T}^{*}$ ，则称 $w$ 是 $G$ 的一个句子(sentence),

句子是不包含非终结符的句型。

语言的定义

$L(G) = \{ x|S ⇒^* x,其中S为文法的开始符号, x \in V_T^* \}$

由文法G生成的语言记为L(G)，它是文法G的一切句子的集合。

例如： $G: S → 0S1, S → 01$ ，显然任意句子的左边都是0，右边都是1，且个数相等。

$L(G)= \{ 0^n 1^n | n\ge 1 \}$

文法的等价：若 $L(G_1)=L(G_2)$ ，则文法 $G_1$ 和 $G_2$ 是等价的。

例如： $G_1[A]: A → 0R, A → 01, R →A1$ 等价于 $G_2[S]: S→0S1, S→01$ 。

根据已知文法求语言 $^*$

根据语言定义：语言是文法的一切句子的集合。

集合的表示形式为： $L(G)= \{ \alpha | S⇒^+ \alpha ,\alpha \in V_T^* \}$

假设有文法： $G(S): S → aSb | ab$ .

可知开始符为G，有两个产生式，分别为 $S → aSb, S → ab$ ，采用递归的方式，任意组合，进行一步或有限步的推导，使得生成式右部不含有非终结符。

如果右部存在非终结符（类似于递递递…不归）时，就需要进行归纳。

所以 $L(G) = \{ a^n b^n|n \ge 1 \}$

按产生式出现的顺序规定优先级由高到低。

再来一个例题：

G[S]：S->aSPQ|abQ

QP->PQ

bP->bb

bQ->bc

cQ->cc

求其语言为？

solution：

假设递归S三次，可得S → aaabQPQPQ

由QP → PQ，可得S → aaabPPQQQ

由bP → bb，可得S → aaabbbQQQ

由bQ → bc，可得S → aaabbbcQQ

由cQ → cc，可得S → aaabbbccc

至此产生式右部无非终结符，递归S三次的句子为aaabbbccc

将递归推广至n次这句子为aa...aabb...bbcc...cc

即 $L(G)= \{ a^n b^n c^n |n \ge 1 \}$

递归之所以递归，就是其运算规则不变，所以1次和n次是一样的。

文法构造与文法简化 $^*$

文法构造（由语言构造文法）

常用方法有4个：对称法、分解法、等价法、电路状态转换法

记两个常用的。

对称法

适用于存在对称性的语言

上面求语言的例子就是存在对称性的语言

对称法构造的核心是找出对称轴、找对称性。

例如： $L(G) = \{ a^{2n} b^n | n \ge 1 ,a,b \in V_T \}$

n = 1时，L = aab；n = 2时，L = aaaabb

所以可以推出 $S → aaSb | aab$

分解法

分解法也叫逐步求精法，有两种方法：自上而下、从左至右。

使用前提是语言中各成分之间没有关联。

例如： $L(G) = \{ a^ib^jc^k | i,j,k \ge 1 且a,b,c \in V_T \}$

自上而下：

将 $a^ib^jc^k$ 各自看成一个整体，由 $i \ge 1$ ，可知语言中最少存在一个a，因此可得 $A → aA|a$ 。

同理可得其他两个整体， $B→bB|b,C→cC|c$ .

综上所述 $S → ABC, A → aA|a, B→bB|b, C→cC|c$ 。

从左至右：

$a^ib^jc^k=a^*a^{i-1}b^jc^k$ ，其中 $i - 1\ge 0$ 。

当 $i-1\ge 1$ 时， $S → aS$ ；当 $i - 1 = 0$ 时， $S→ aA$ .

其中A对应的语言是 $b^j c^k$ ，同理推出 $A → bA|bB$ 。

综上所述， $S→aS|aA, A→bA|bB,B→cB|c$ 。

~~我觉得自上而下简单些。~~

文法化简^*

化简步骤：

删除形如P→P的产生式；
删除永不被使用的产生式，即由文法的开始符号无法推导出其左部；
删除不能从中导出终结符串的产生式；
整理产生式；

下面是几个例题：

例1

S → aABS | bCACd

A → bAB | cSA | cCC

B → bAB | cSB

C → cS | c

B能推导的两个右部都包含自己，即满足第三个步骤不从中导出终结符的产生式，所以删去所有和B有关的产生式，得到：

S → bCACd A → cSA | cCC C → cS | c

此时这个文法与原文法等价，并且不包含无用符号和无用产生式。

例2

S → aAB | E

A → dDA | e

B → bE | f

C → cAB | dSD | a

D → eA

E → fA | g

这种题就从开始符号出发，看看谁不会被推导到，这时发现C推导不出，因此C是无用符号，删去所有和C有关的产生式，得到：

S → aAB | E A → dDA | e B → bE |f D → eA E → fA | g

此时这个文法与原文法等价，并且不包含无用符号和无用产生式。

例3（暂不确定是否正确）

S → ac | bA

A → cBC

B → SA

C → bC | d

A → cBC 而 B → SA，显然这将不可得到终结符串，因此需要删去所有和A B有关的产生式，得到：S → ac C → bC | d

而此时C永远不会被使用，因此它是一个无用符号，删去后最终得到：S → ac

构造无产生式的上下文无关文法

语法树与文法的二义性

语法树

基本术语

文法的二义性

词法分析

词法分析是编译的第一个阶段，其主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。