复习材料，不建议阅读

文法和语言

什么是语言

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

它有三个研究方面：

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

符号

首先有字母表，其中的元素为符号，符号构成的有穷序列则为符号串，它包含的符号个数就是符号串的长度。当然，什么符号都没有的就是空符号串（$\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$ 的任意一个句型都存在一个相应的语法树,它满足：

1. 树中每一个结点都有一个标记，此标记是 $V=V_N \cup V_T$ 中的一个符号。
2. 根的标记是 $S$。
3. 若树的一结点 $A$ 至少有一个子孙，则 $A \in V_N$。
4. 如结点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$。