2026-04-22

复习材料，不建议阅读

文法和语言

什么是语言

语言是句子（符号）构成的集合。

它有三个研究方面：

语法 —— 符号的构成、组合规律
语义 —— 各个符号的特定含义
语用 —— 各个符号出现的行为中，它们的来源、使用和影响

符号

首先有字母表，其中的元素为符号，符号构成的有穷序列则为符号串，它包含的符号个数就是符号串的长度。当然，什么符号都没有的就是空符号串（ $\varepsilon$ ）。

符号串 $x,y$ 的连接记为 $xy$ 。例如， $x=a, y=bbb, xy=abbb$ 。

符号串与自身连接为方幂，记为 $x^k$ 。例如， $x=a, x^3=aaa$ 。

若集合 $A$ 中元素都是某字母表 $Σ$ 上的符号串，则 $A$ 是 $Σ$ 上的符号串集合。

若 $A、B$ 均为 $Σ$ 上的符号串集合，则 $AB=\{xy | x \in A, y \in B \}$ 。例如，设 $A= \{ ab, cd \}, B= \{ ef, jh \}$ ,则 $AB= \{ abef, abjh, cdef, cdjh \}$ 。

设符号串集合 $A$ ，正闭包 $A^+ = A^1 + A^2 + ... + A^n$ 。例如， ${0}^+ = \{ 0, 00, 000, ... \}$ 。

较为常见的定义有非空有限的符号集：非终结符号集 $V_N$ ，终结符号集 $V_T$ 。

产生式

产生式是一个序偶对，也叫规则、重写规则、生成式。例如 $\alpha \to \beta$ 、 $\alpha ::= \beta$ 。

文法

语言规则的有限集合，通过规则判断句子结构是否合法。在编译原理中为四元组，表示为 $G = (V_N, V_T, P, S)$ ，其中有：

非终结符号集 $V_N$
终结符号集 $V_T$
产生式集（规则集） $P$
开始符号（识别符） $S$

例如，文法 $G=(VN, VT,P,S)$ ,其中 $V_N =\{S，B\}$ ， $V_T =\{0，1\}$ ， $P=\{S \to 0B,B \to 1,B \to 1B\}$ 。

这个文法表示：所有形如 $01,011,0111,01111$ 的串。

几种文法

0型文法

也叫短语结构文法。

$\alpha \to \beta$ 的 $\alpha \in V_N \cup V_T$ ，而且 $\alpha$ 里有非终结符号。

1型文法

也叫上下文有关文法。

$\alpha \to \beta$ 满足 $|\beta| \gt |\alpha|$ （除非 $\beta = \varepsilon$ ）。也就是非终结符能够展开更多符号。

2型文法

也叫上下文无关文法。

1 型基础上，再满足 $\alpha \in V_N$ 。也就是 $A \to \beta$ ，左边只有一个非终结符号。

3型文法

也叫正规文法或右线性文法。对应有穷自动机

2 型基础上，产生式全部形如 $A \to a | A \to aB, A、B \in V_N, a \in V_T$ 。也就是左边一个非终结符号，右边只能最右出现非终结符号。

有害文法和多余规则

$U \to U$ 这样的规则为有害规则。

不可达或不可终止规则为多余规则。例如，

G[S]: \\ S \to Ab|Cd \\ A \to b \\ D \to e \\ C \to Ca

其中 $D \to e$ 多余。

限制使用 $\varepsilon$ 规则（ $A \to \varepsilon$ ），会使有关文法证明变得复杂。

推导

直接推导

设 $\alpha \to \beta$ 是文法 $G=(VN, VT,P,S)$ 的产生式, $\gamma, \delta \in (V_N \cup V_T)^*$ ,若有符号串 $v,w$ 满足 $v=\gamma \alpha \delta, w=\gamma \beta \delta$ ,则称 $w$ 是 $v$ 的直接推导，或称 $v$ 是 $w$ 的直接归约。记作 $v \Rightarrow w$ 。

简单来说直接推导就是利用一步规则。多步就是间接了。

存在直接推导序列使得 $v \overset{+}{\Rightarrow} u$ ，那符号串 $u$ 就是 $v$ 的一个推导（归约）

语法树（推导树）

给定文法 $G=(V_N, V_T,P,S)$ ,对于文法 $G$ 的任意一个句型都存在一个相应的语法树,它满足：

树中每一个结点都有一个标记，此标记是 $V=V_N \cup V_T$ 中的一个符号。
根的标记是 $S$ 。
若树的一结点 $A$ 至少有一个子孙，则 $A \in V_N$ 。
如结点A的子孙结点从左到右次序为 $B_1,B_2,...,B_n$ ,则必有产生式 $A \to B_1,B_2,...,B_n$ 。

例如，

G[S]: \\ S \to aAS | a \\ A \to SbA |SS |ba

对句型 $aabbaa$ 的推导过程可表示为

同一语法树可以表示同一句型的不同推导，同一句型也可能产生不同的语法树。永远替换最左（右）边非终结符为最左（右）推导。同一语法树最多对应唯一的最左（右）推导。

文法中存在句子对应两颗语法树，则该文法是二义的。并不存在算法判断 2 型文法是否二义，一般用一组无二义性的充分条件构造无二义性文法。

例如，消除二义性可以引入新的非终结符、加ε规则

E \to E+E|E-E|E*E|E/E|(E)|id

变为

E \to E+T|E-T|T \\ T \to T*F|T/F|F \\ F \to (E)|id

句型和句子

句型

由开始符号推导出来的就是句型。例如， $G[S]$ 中 $S \overset{+}{\Rightarrow} x$ 的 $x$ 。

句子

属于终结符的句型是句子。例如上例 $x \in V_T$ 那就是句子。

语言

文法 $G[S]$ 的所有句子构成的集合就是它的语言。

语言相同的文法等价。例如， $L(G1) = L(G2)$ 则 $G1、G2$ 等价。

句型分析

识别一个符号串是否为某文法的一个句型。

可以自顶向下，由根（开始符号）推导；也可以自底向上，将句型串逐步归约。

短语

$S \overset{*}{\Rightarrow} uAv$ 且 $A \overset{+}{\Rightarrow} \beta$

非终结符 $A$ 经过至少一步推导得到 $\beta$ ，则 $\beta$ 是句型 $u \beta v$ 相对于 $A$ 的短语。

直接短语是 $A \to \beta$ 一步直接推导。语法树上子树高度1。

最左直接短语是句柄。

例：已知文法 $G[E]$ :

E \to E+T | T \\ T \to T*F | F \\ F \to (E) | i

对于句型i*i+i

相对于 $F$ 短语为 $i1, i2, i3$ ，对于规则 $F \to i$ 直接短语为 $i1, i2, i3$ ，句柄为 $i1$ 。