符号和符号串

符号：可以相互区别的记号（元素）
字母表（$\Sigma$）：符号（元素）的非空有穷集合
符号串：由字母表中的符号组成的任何有穷序列
- 空符号串 $\varepsilon$ 是字母表 $\Sigma$ 上的符号串
- 若 $x$ 是 $\Sigma$ 上的符号串，$a$ 是 $\Sigma$ 的元素，则 $xa$ 是 $\Sigma$ 上的符号串
- $y$ 是 $\Sigma$ 上的符号串，当且仅当它可以由上面两个表述导出
  - 如 $\Sigma={a,b}$ 则：$\varepsilon,a,b,aa,ab,aabba,…$ 都是 $\Sigma$ 上的符号串
前缀（头）：移去符号串尾部的大于等于零个符号
- $s$ 和 $\varepsilon$ 也是前缀
- 真前缀（固有头）：所有前缀的集合去除 $s$
后缀（尾）：移去符号串头部的大于等于零个符号
- $s$ 和 $\varepsilon$ 也是后缀
- 真后缀（固有尾）：所有后缀的集合去除 $s$
子串：移去一个头和一个尾
- $s$ 和 $\varepsilon$ 也是子串

符号串的长度

符号串 $s$ 的长度记为 $|s|$，$|\varepsilon|=0$

符号串的连接

对于符号串 $x$ 和 $y$ 的连接：将 $y$ 写在 $x$ 之后得到 $xy$

$\varepsilon a = a\varepsilon=a$

方幂：符号串自身连接 n 次得到的符号串

$$
(ab)^n=abab…ab\ \ (ab\times n)
$$

其中，$a^0=\varepsilon$

符号串的集合

若集合 $A$ 中所有元素都是字母表 $\Sigma$ 上的符号串，则称 $A$ 为字母表 $\Sigma$ 上的符号串集合

符号串集合的乘积：$AB={xy|x\in A\ &\ y\in B}$（即做连接操作）

闭包

闭包 $\Sigma^*$：$\Sigma$ 上的一切符号串（包括 $\varepsilon$）组成的集合
正闭包 $\Sigma^+$： $\Sigma$ 上除了 $\varepsilon$ 外的所有符号串组成的集合

文法和语言的形式定义

规则

形如 $\alpha\rightarrow\beta$ 或 $\alpha::=\beta$ 的 $(\alpha,\beta)$ 有序对，且 $\alpha\in V^+,\beta\in V^*$，$V$ 为符号表

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

别称：

重写规则
产生式
生成式

文法

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

$V_N$：非终结符集
$V_T$：终结符集
$P$：产生式（规则）集合
$S$：开始符号，$S\in V_N$，$S$ 必须要在一条规则的左部出现

其中：

$V_N\cap V_T=\phi$
$V=V_N\cup V_T$，即为文法 $G$ 的文法符号集合

例如：$V_N={A},V_T={0,1},P={A\rightarrow0A1,A\rightarrow 01}$，$A$ 为文法 $G$ 的开始符号

一般约定：

第一条产生式的左部是开始符号
用尖括号括起的是非终结符，否则为终结符
- 或用大写字母表示非终结符；小写字母表示终结符
$G$ 可以表示为：$G[S]$，$S$ 为开始符号

直接推导

如果 $\alpha\rightarrow\beta$ 是文法 $G$ 的产生式，若有 $v,w$ 满足：

$$
v=\gamma\alpha\delta,w=\gamma\beta\delta\ \ and\ \ \gamma\in V^,\delta\in V^
$$

则称 $v$ 直接推导到 $w$，记作：$v\Rightarrow w$；或 $w$ 直接归约到 $v$

例：$G$: $A\rightarrow 0A1,A\rightarrow01,v=0A1,w=0011$

因为有 $A\rightarrow01,v=0A1,w=0011$ ，所以有 $v\Rightarrow w$

对于：$\varepsilon A\varepsilon\rightarrow\varepsilon 0A1\varepsilon$，可得： $A\Rightarrow 0A1 \Rightarrow 00A11$

$\Rightarrow 000A111 \Rightarrow 00001111$

（间接）推导

若存在：$v\Rightarrow w_0\Rightarrow w_1 \Rightarrow…\Rightarrow w_n=w\ (n>0)$，则称 $v$ 推导出 $w$，或 $w$ 归约到 $v$，记为 $v\Rightarrow ^+w$

若有: $v\Rightarrow ^+ w$ 或 $v=w$，则记为 $v\Rightarrow^* w$

文法的句型和句子

句型

从开始符号 $S$ 经过零步或多步推导得到的任意符号串

可以包含：非终结符 + 终结符
也可以只含非终结符，或只含终结符

若 $S\Rightarrow^∗ \alpha$，则 $\alpha$ 是 $G$ 的一个句型

句子

从文法推导出的、只由终结符组成的句型

不含任何非终结符
是语言中的合法串

若 $S\Rightarrow^∗\alpha\ and\ \alpha\in V_T^∗$ ，则 $\alpha$ 是 $G$ 的一个句子

$\text{句子}\subset \text{句型}$

文法的语言

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

$$
L(G)={x|S\Rightarrow^x,x\in V_T^}
$$

句子：全是终结符，没有非终结符
语言：所有合法句子组成的集合

语言举例

文法 $G[S]$：
$(1)S\rightarrow aSBE; (2)S\rightarrow aBE; (3)EB\rightarrow BE ;(4)aB\rightarrow ab;(5)bB\rightarrow bb ;(6)bE\rightarrow be; (7)eE\rightarrow ee$

$$
S\Rightarrow aBE\Rightarrow abE\Rightarrow abe
$$

$$
\begin{aligned}
S\Rightarrow aSBE\ (S\rightarrow aSBE)\
\Rightarrow aaBEBE\ (S\rightarrow aBE)\
\Rightarrow aaBBEE\ (EB\rightarrow BE)\
\Rightarrow aabBEE\ (aB\rightarrow ab)\
\Rightarrow aabbEE\ (bB\rightarrow bb)\
\Rightarrow aabbeE\ (bE\rightarrow be)\
\Rightarrow aabbee\ (eE\rightarrow ee)
\end{aligned}
$$

可得 $L(G)={a^nb^ne^n|n\geq1}$

就是将所有非终结符（大写字母）推导为终结符（小写字母）

文法的等价

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

文法的类型

0 型文法（短语文法）
1 型文法（上下文有关文法）
2 型文法（上下文无关文法）
3 型语法（正规/正则文法）

$$
\text{3型}\subset\text{2型}\subset\text{1型}\subset\text{0型}
$$

短语文法

$$
\alpha\rightarrow \beta
$$

$\alpha$ 至少含一个非终结符
$\beta$ 任意（可以为空）

几乎没有限制

上下文有关文法

必须满足

$$
|\alpha|\leq|\beta|
$$

不能变短

上下文无关文法

$$
A\rightarrow \beta
$$

左部必须是单个非终结符
右部任意（需要满足 1 型的长度条件）

正规文法

右线性：

$$
A\rightarrow aB,A\rightarrow a
$$

左线性：

$$
A\rightarrow Ba,A\rightarrow a
$$

只能线性展开，不能嵌套递归

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

上下文无关文法（Context-Free Grammar，CFG）是最重要的文法类型，适合描述程序设计语言的大部分语法结构。

为什么叫”上下文无关”

在上下文无关文法中，产生式形如 $A\rightarrow\beta$：

左部必须是单个非终结符 $A$
$A$ 的推导不依赖于它周围的符号（即”上下文”）
无论 $A$ 出现在什么位置，都可以用 $\beta$ 替换

相比之下，上下文有关文法的产生式可能是 $\alpha A\gamma\rightarrow\alpha\beta\gamma$，表示只有当 $A$ 的左边是 $\alpha$、右边是 $\gamma$ 时才能替换，这就依赖于”上下文”。

语法树（推导树/分析树）

语法树是推导过程的图形化表示，能够清晰地展示句型的结构。

语法树的定义

对于文法 $G=(V_N,V_T,P,S)$，一棵语法树满足：

根节点：标记为开始符号 $S$
内部节点：标记为非终结符 $V_N$ 中的符号
叶节点：标记为终结符 $V_T$ 中的符号或 $\varepsilon$
父子关系：如果有产生式 $A\rightarrow X_1X_2…X_n$，则节点 $A$ 有 $n$ 个子节点，从左到右标记为 $X_1,X_2,…,X_n$

语法树的特点

叶节点从左到右连接起来，就是一个句型
如果所有叶节点都是终结符，则这个句型是一个句子
同一个句型可能有多棵不同的语法树（对应不同的推导顺序）

语法树示例

文法 $G[E]$：
$E\rightarrow E+E$ > $E\rightarrow E*E$ > $E\rightarrow (E)$ > $E\rightarrow id$

对于句子 $id+id*id$，可以有以下推导：

推导 1：

$$
E\Rightarrow E+E\Rightarrow id+E\Rightarrow id+EE\Rightarrow id+idE\Rightarrow id+id*id
$$

对应的语法树：

        E
       /|\
      E + E
      |  /|\
     id E * E
        |   |
       id  id

推导 2：

$$
E\Rightarrow EE\Rightarrow E+EE\Rightarrow id+EE\Rightarrow id+idE\Rightarrow id+id*id
$$

对应的语法树：

        E
       /|\
      E * E
     /|\  |
    E + E id
    |   |
   id  id

这两棵语法树的叶节点序列都是 $id+idid$，但*结构不同，导致运算优先级不同！

而这样能够构建出不同语法树的文法，称其为具有二义性

最左推导和最右推导

为了规范推导过程，我们定义两种特殊的推导方式。

最左推导

在推导的每一步，总是替换最左边的非终结符。

记作：$\Rightarrow_{lm}$（leftmost derivation）

最右推导（规范推导）

在推导的每一步，总是替换最右边的非终结符。

记作：$\Rightarrow_{rm}$（rightmost derivation）

示例

对于文法 $G[E]$：$E\rightarrow E+T\ |\ T$，$T\rightarrow T*F\ |\ F$，$F\rightarrow(E)\ |\ id$

句子 $id+id*id$ 的最左推导：

$$
\begin{aligned}
E&\Rightarrow_{lm} E+T \
&\Rightarrow_{lm} T+T \
&\Rightarrow_{lm} F+T \
&\Rightarrow_{lm} id+T \
&\Rightarrow_{lm} id+TF \
&\Rightarrow_{lm} id+FF \
&\Rightarrow_{lm} id+idF \
&\Rightarrow_{lm} id+idid
\end{aligned}
$$

句子 $id+id*id$ 的最右推导：

$$
\begin{aligned}
E&\Rightarrow_{rm} E+T \
&\Rightarrow_{rm} E+TF \
&\Rightarrow_{rm} E+Tid \
&\Rightarrow_{rm} E+Fid \
&\Rightarrow_{rm} E+idid \
&\Rightarrow_{rm} T+idid \
&\Rightarrow_{rm} F+idid \
&\Rightarrow_{rm} id+id*id
\end{aligned}
$$

注意：虽然推导顺序不同，但它们对应的语法树是同一棵！

二义性文法

定义

如果文法 $G$ 的某个句子存在两棵不同的语法树（或有两个不同的最左推导，或有两个不同的最右推导），则称文法 $G$ 是二义性的（ambiguous）。

二义性的判定

判定一个文法是二义性的：只需找到一个句子，它有两棵不同的语法树
判定一个文法是无二义性的：没有通用算法！（不可判定问题）

二义性文法的例子

文法 $G[E]$：$E\rightarrow E+E\ |\ E*E\ |\ (E)\ |\ id$

对于句子 $id+idid$，前面已经展示了两棵不同的语法树，所以这是一个*二义性文法。

消除二义性

二义性文法往往不符合我们的语义要求（如运算优先级），需要改写文法消除二义性。

改写方法：引入多层非终结符，将优先级编码到文法结构中

改写后的无二义性文法：

$$
\begin{aligned}
E&\rightarrow E+T\ |\ T \
T&\rightarrow T*F\ |\ F \
F&\rightarrow (E)\ |\ id
\end{aligned}
$$

这个文法保证了：

$*$ 的优先级高于 $+$
同级运算符左结合
每个句子只有唯一的语法树

悬挂 else 问题

另一个经典的二义性例子：

文法 $G[S]$：

$$
\begin{aligned}
S&\rightarrow \text{if}\ E\ \text{then}\ S \
S&\rightarrow \text{if}\ E\ \text{then}\ S\ \text{else}\ S \
S&\rightarrow \text{other}
\end{aligned}
$$

对于句子：if E1 then if E2 then S1 else S2

有两种理解：

if E1 then (if E2 then S1 else S2) —— else 匹配内层 if
if E1 then (if E2 then S1) else S2 —— else 匹配外层 if

消除方法：规定 else 总是与最近的未匹配的 if 匹配

改写文法：

$$
\begin{aligned}
S&\rightarrow M\ |\ U \
M&\rightarrow \text{if}\ E\ \text{then}\ M\ \text{else}\ M\ |\ \text{other} \
U&\rightarrow \text{if}\ E\ \text{then}\ S \
U&\rightarrow \text{if}\ E\ \text{then}\ M\ \text{else}\ U
\end{aligned}
$$

其中 $M$ 表示匹配的语句（matched），$U$ 表示未匹配的语句（unmatched）。

句型的分析

句型分析是编译器语法分析器的核心任务：给定一个符号串，判断它是否是文法的句型，如果是，构造出它的语法树。

短语、直接短语和句柄

这些概念用于描述句型的结构，是自下而上分析的理论基础。

短语

设有文法 $G[S]$，$\alpha$ 是 $G$ 的一个句型，如果有：

$$
S\Rightarrow^*\beta A\delta\ \text{且}\ A\Rightarrow^+\gamma
$$

其中 $\alpha=\beta\gamma\delta$，则称 $\gamma$ 是句型 $\alpha$ 相对于非终结符 $A$ 的短语。

通俗理解：短语是语法树中某个子树的所有叶节点连起来的符号串。

直接短语

如果有 $A\Rightarrow\gamma$（一步推导），则称 $\gamma$ 是句型 $\alpha$ 相对于非终结符 $A$ 的直接短语。

通俗理解：直接短语是语法树中某个子树高度为 2（根到叶只有一步）的所有叶节点连起来的符号串。

句柄

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

通俗理解：句柄是我们在自下而上分析时，下一步应该归约的部分。

示例

文法 $G[E]$：

$$
\begin{aligned}
E&\rightarrow E+T\ |\ T \
T&\rightarrow T*F\ |\ F \
F&\rightarrow (E)\ |\ id
\end{aligned}
$$

句型 $id_1*id_2+id_3$ 的语法树：

          E
         /|\
        E + T
		|   |
		T	F
	   /|\  |
	  T * F id3
	  |   |
	  F  id2
	  |
	 id1

短语：
- $F: id_1,id_2,id_3$
- $T:id_1, id_3, id2*id3$
- $E: id_1id_2, id_1+id_2id_3$
直接短语：$id_1$（$F\rightarrow id$）、$id_2$（$F\rightarrow id$）、$id_3$（$F\rightarrow id$）
句柄：$id_1$（最左边的直接短语）

总结：就是选取一个结点，其子树的叶子结点组合即为一个短语；如果选取结点与其叶子结点相邻，则为直接短语

自上而下的分析方法

从开始符号 $S$ 出发，尝试推导出输入串，使用最左推导。

基本思想

从文法的开始符号 $S$ 开始
每次选择一个非终结符进行推导
选择合适的产生式进行替换
最终推导出输入串

面临的问题

问题 1：回溯问题

当有多个产生式可选时，可能需要回溯（backtracking）。

例如，文法 $G[S]$：$S\rightarrow aAd$，$A\rightarrow ab\ |\ a$

输入串：$aad$

尝试 $A\rightarrow ab$：$S\Rightarrow aAd\Rightarrow aabd$ ❌ 失败，需要回溯
尝试 $A\rightarrow a$：$S\Rightarrow aAd\Rightarrow aad$ ✓ 成功

回溯会严重影响效率！

问题 2：左递归问题

如果文法中有左递归（如 $A\rightarrow A\alpha$），自上而下分析会陷入无限循环。

例如：$E\rightarrow E+T$ 是左递归的，从 $E$ 出发会不断推导 $E\Rightarrow E+T\Rightarrow E+T+T\Rightarrow…$

解决方法

消除左递归：将左递归改写为右递归或使用 $\varepsilon$ 产生式
提取公共左因子：减少回溯
构造预测分析表：使用 FIRST 和 FOLLOW 集合（后续章节详细讲解）

自下而上的分析方法

从输入串出发，逐步归约到开始符号 $S$，相当于最右推导的逆过程。

基本思想

从输入串开始
找到句柄（最左边的直接短语）
用相应的非终结符替换句柄（归约）
重复步骤 2-3，直到归约到开始符号 $S$

这个过程也叫移进-归约分析（shift-reduce parsing）。

示例

文法 $G[E]$：$E\rightarrow E+T\ |\ T$，$T\rightarrow T*F\ |\ F$，$F\rightarrow(E)\ |\ id$

分析 $id_1+id_2*id_3$：

步骤	符号栈	输入串	动作
1	$	$id_1+id_2*id_3$	移进 $id_1$
2	$id_1$	$+id_2*id_3$	归约 $F\rightarrow id$
3	$F$	$+id_2*id_3$	归约 $T\rightarrow F$
4	$T$	$+id_2*id_3$	归约 $E\rightarrow T$
5	$E$	$+id_2*id_3$	移进 $+$
6	$E+$	$id_2*id_3$	移进 $id_2$
7	$E+id_2$	$*id_3$	归约 $F\rightarrow id$
8	$E+F$	$*id_3$	归约 $T\rightarrow F$
9	$E+T$	$*id_3$	移进 $*$
10	$E+T*$	$id_3$	移进 $id_3$
11	$E+T*id_3$	$	归约 $F\rightarrow id$
12	$E+T*F$	$	归约 $T\rightarrow T*F$
13	$E+T$	$	归约 $E\rightarrow E+T$
14	$E$	$	接受

优势

不需要回溯（对于 LR 文法）
可以处理更广泛的文法
是现代编译器的主流方法

句型分析的有关问题

1. 句型的分析是可判定的吗？

答：对于上下文无关文法，句型的分析是可判定的。存在多项式时间算法（如 CYK 算法），但实际编译器中使用更高效的 LL 和 LR 分析方法。

2. 如何选择分析方法？

分析方法	适用文法	优点	缺点
LL(k)	LL(k) 文法	实现简单，易于理解	文法限制较多，不能处理左递归
LR(k)	LR(k) 文法	识别能力强，接近所有上下文无关文法	实现复杂，分析表较大
LALR(k)	LALR(k) 文法	折中方案，yacc/bison 使用	某些情况下会有冲突

3. 文法的改写

有时需要改写文法以满足特定分析方法的要求：

消除左递归：将 $A\rightarrow A\alpha\ |\ \beta$ 改写为 $A\rightarrow\beta A’$，$A’\rightarrow\alpha A’\ |\ \varepsilon$
提取左公因子：将 $A\rightarrow\alpha\beta_1\ |\ \alpha\beta_2$ 改写为 $A\rightarrow\alpha A’$，$A’\rightarrow\beta_1\ |\ \beta_2$
消除二义性：如前面的表达式文法改写

有关文法实际应用

有关文法实用限制

在实际应用中，我们通常对文法施加一些限制，以便构造高效的语法分析器。

1. 无二义性

要求：文法必须是无二义性的。

原因：二义性文法会导致同一个句子有多种解释，无法确定唯一的语法树。

实践：如果原始文法有二义性，需要改写或引入优先级、结合性规则。

2. 不含左递归（针对 LL 分析）

要求：文法不能有形如 $A\Rightarrow^+ A\alpha$ 的推导。

原因：左递归会导致自顶向下分析器陷入无限循环。

消除方法：

直接左递归：$A\rightarrow A\alpha\ |\ \beta$

改写为：

$$
\begin{aligned}
A&\rightarrow\beta A’ \
A’&\rightarrow\alpha A’\ |\ \varepsilon
\end{aligned}
$$

3. 提取左公因子（针对 LL 分析）

要求：减少需要向前查看的符号数量。

原因：左公因子会导致难以决策使用哪个产生式。

提取方法：

原文法：$A\rightarrow\alpha\beta_1\ |\ \alpha\beta_2\ |\ …\ |\ \alpha\beta_n\ |\ \gamma$

改写为：

$$
\begin{aligned}
A&\rightarrow\alpha A’\ |\ \gamma \
A’&\rightarrow\beta_1\ |\ \beta_2\ |\ …\ |\ \beta_n
\end{aligned}
$$

4. LL(k) 或 LR(k) 条件

LL(k)：向前看 $k$ 个符号就能决定使用哪个产生式
LR(k)：向前看 $k$ 个符号就能决定何时归约

实际中，$k=1$ 就足够了（LL(1)、LR(1)、LALR(1)）。

上下文无关文法中的 $\varepsilon$ 规则

$\varepsilon$ 规则（也叫空产生式）形如 $A\rightarrow\varepsilon$，表示非终结符 $A$ 可以推导出空串。

$\varepsilon$ 规则的作用

表示可选成分

例如：C 语言中函数的参数列表可以为空

$$
\text{params}\rightarrow\text{param-list}\ |\ \varepsilon
$$

简化文法描述

例如：标识符列表（至少一个）

$$
\begin{aligned}
\text{id-list}&\rightarrow\text{id}\ \text{id-list}’ \
\text{id-list}’&\rightarrow\text{id}\ \text{id-list}’\ |\ \varepsilon
\end{aligned}
$$

可空符号（NULLABLE）

如果 $A\Rightarrow^\varepsilon$，则称 $A$ 是*可空的（nullable）。

判定方法（不动点算法）：

初始化：所有有 $A\rightarrow\varepsilon$ 的 $A$ 是可空的
重复：如果 $A\rightarrow X_1X_2…X_n$，且 $X_1,…,X_n$ 都是可空的，则 $A$ 是可空的
直到不再有新的可空符号加入

消除 $\varepsilon$ 规则

有些分析方法不允许 $\varepsilon$ 规则（除了 $S\rightarrow\varepsilon$），需要消除。

消除方法：

找出所有可空符号
对于每个产生式 $A\rightarrow\alpha$，如果 $\alpha$ 中含有可空符号 $B$，则增加一个产生式，将 $B$ 删除
重复步骤 2，直到 $\alpha$ 中的所有可空符号组合都被考虑
删除所有 $A\rightarrow\varepsilon$ 规则（除非 $A$ 是开始符号）

示例：

原文法：

$$
\begin{aligned}
S&\rightarrow aAB \
A&\rightarrow bA\ |\ \varepsilon \
B&\rightarrow cB\ |\ \varepsilon
\end{aligned}
$$

$A$ 和 $B$ 都是可空的。

对 $S\rightarrow aAB$：

删除 $A$：$S\rightarrow aB$
删除 $B$：$S\rightarrow aA$
删除 $A$ 和 $B$：$S\rightarrow a$

消除后的文法：

$$
\begin{aligned}
S&\rightarrow aAB\ |\ aA\ |\ aB\ |\ a \
A&\rightarrow bA\ |\ b \
B&\rightarrow cB\ |\ c
\end{aligned}
$$

注意事项

消除 $\varepsilon$ 规则可能会增加产生式数量
如果开始符号 $S$ 是可空的，且 $S$ 出现在其他产生式右部，需要特殊处理：
- 引入新的开始符号 $S’$
- 添加 $S’\rightarrow S\ |\ \varepsilon$

本章小结：

本章介绍了形式语言理论的基础概念：

文法：用产生式描述语言的语法结构
推导与归约：句子的生成和识别过程
文法类型：从 3 型（正规）到 0 型（短语），其中上下文无关文法最重要
语法树：推导过程的图形化表示，直观展示句子结构
二义性：同一句子有多棵语法树，需要改写文法消除
句型分析：自顶向下和自底向上两种基本方法
文法改写：消除左递归、提取左公因子、消除 $\varepsilon$ 规则等

掌握这些概念是学习后续词法分析、语法分析等章节的基础。