[形式语言] 04 Context-free Grammar

派生

派生树

(派生树)

设 CFG $G = (V, T, P, S)$，$G$ 的派生树满足下面的条件的一棵（有序）树：

树的每个顶点都有一个标记 $X \in V \cup T \cup \{\varepsilon\}$
树根的标记为 $S$
如果一个非叶结点的标记为 $A$，其从左到右的儿子的标记依次为 $X_1 X_2 \dots X_n$，则 $A \rightarrow X_1 X_2 \dots X_n \in P$。
如果一个叶子结点的标记为 $X$，则 $X \in V$
如果一个顶点的标记是 $\varepsilon$，那么这是一个叶子结点，且它是其父节点的唯一儿子

满足除第二条定义外的规则的树称为派生子树（derivation subtree），顶点为 $A$ 也可以称为 $A$ 子树。

(结果)

设有文法 $G$ 的一棵派生树 $T$ 的所有叶子顶点从左到右依次标记为 $X_1, X_2, \dots, X_n$，则称符号串 $X_1, X_2, \dots, X_n$ 是 $T$ 的结果（yield）。

设 CFG $G = (V, T, P, S)$，$S \xRightarrow{*} \alpha$ 的充要条件是 $G$ 有一棵结果为 $\alpha$ 的派生树。

为了方便，先证明一个更一般的结论：对于任意 $A \in V$，$A \xRightarrow{*} \alpha$ 的充要条件是 $G$ 有一棵结果为 $\alpha$ 的 $A$ 子树。

下面证明充分性。设 $G$ 有一棵结果为 $a$ 的 $A$ 子树，对这棵子树的非叶顶点数量 $n$ 进行归纳
- $n = 1$，那么树的高度为 $2$，设结点 $A$ 的叶结点从左到右分别为 $X_1 X_2 \dots X_n$，根据定义有 $A \rightarrow X_1 X_2 \dots X_n \in P$，又因为该子树结果为 $\alpha$，因此 $X_1 X_2 \dots X_n = \alpha$，即 $A \xRightarrow{*} \alpha$
- 设 $n \le k$ 时命题成立，那么当 $n = k+1$ 时，设 $A$ 的儿子从左到右分别为 $X_1 X_2 \dots X_m$，则根据定义必有 $A \rightarrow X_1 X_2 \dots X_m \in P$。设 $X_i$ 的结果为 $\alpha_i$，根据归纳假设有 $X_i \xRightarrow{*} \alpha_i$，且 $\alpha = \alpha_1 \alpha_2 \dots \alpha_m$，因此 \[A \xRightarrow{} X_1 X_2 \dots X_m \xRightarrow{*} \alpha_1 X_2 \dots X_m \xRightarrow{*} \alpha_1 \alpha_2 \dots X_m \xRightarrow{*} \dots \xRightarrow{*} \alpha_1 \alpha_2 \dots \alpha_m \]
下面证明必要性。设 $A \xRightarrow{n} \alpha$，下面对派生步数进行归纳。
- $n=1$，那么 $A \Rightarrow \alpha \in P$，令 $\alpha = X_1 X_2 \dots X_m$，则存在 $A \Rightarrow X_1 X_2 \dots X_m$ 子树，成立。
- 设 $n = k$ 时成立，则当 $n = k + 1$ 时，设派生为
  \[A \xRightarrow{} X_1 X_2 \dots X_m \xRightarrow{*} \alpha_1 X_2 \dots X_m \xRightarrow{*} \alpha_1 \alpha_2 \dots X_m \xRightarrow{*} \dots \xRightarrow{*} \alpha_1 \alpha_2 \dots \alpha_m \]
  其中 $X_i \Rightarrow \alpha_i$。当 $X_i = \alpha_i$ 时，$X_i$ 子树只有一个 $X_i$ 结点；当 $X_i \xRightarrow{+} \alpha_i$ 时，由归纳假设，存在一棵结果为 $\alpha_i$ 的 $X_i$ 子树。又由于 $A \Rightarrow X_1 X_2 \dots X_m$，因此存在一棵 $A$ 子树使得叶结点为 $X_i$。此时将上面对应的 $X_i$ 子树接到 $X_i$ 上，即得到了一棵结点为 $\alpha$ 的 $A$ 子树。

综上所述，命题成立。

最左派生和最右派生

(最左派生)和(最右派生)

设 CFG $G = (V, T, P, S)$， $\alpha$ 是 $G$ 的一个句型，如果存在派生使得 $\alpha$ 中的每一步都是对当前句型中的最左变量进行替换，则该派生称为最左派生（leftmost derivation），相应的规约叫最右规约（rightmost derivation）。中间得到的每一个句型都称为左句型（left sentence form）。

反之，如果 $\alpha$ 中的每一步都是对当前句型中的最右变量进行替换，则该派生称为最右派生（rightmost derivation），相应的规约叫最左规约（leftmost derivation）。中间得到的每一个句型都称为右句型（right sentence form）。

由于计算机处理输入串时是从左到右进行的，因此称最左规约为规范规约（normal reduction），对应的派生为规范派生（normal derivation），对应的句型为规范句型（normal sentence form）。

如果 $\alpha$ 是 CFG $G$ 中的一个句型，那么 $G$ 中存在 $\alpha$ 的最左派生和最右派生。

首先证明最左派生的情况，对派生的步数 $n$ 进行归纳。

n = 1，此时就是最左派生，显然成立
设当 $1 \le n \le k$ 时都成立，那么当 $n = k+1$ 时，设
\[A \xRightarrow{} X_1 X_2 \dots X_m \xRightarrow{*} \alpha_1 X_2 \dots X_m \xRightarrow{*} \alpha_1 \alpha_2 \dots X_m \xRightarrow{*} \dots \xRightarrow{*} \alpha_1 \alpha_2 \dots \alpha_m \]
其中对于每一步 $X_i \xRightarrow{n_i} \alpha_i$，都有 $n_i \le k$，因此存在一个最左派生 $X_i \xRightarrow{n_i} \alpha_i$。令上面的每一步 $X_i \xRightarrow{n_i} \alpha_i$ 都采取最左派生，从而上面派生的每一步都是最左派生，因此这个派生即为 $A \xRightarrow{*} \alpha$ 的最左派生。

最右派生的证明同理。

用反证法可以证明派生树与最左派生、最右派生是一一对应的。

二义性

(二义性)

设 CFG $G = (V, T, P, S)$，如果存在 $w \in L(G)$ 使得 $w$ 至少存在两棵不同的派生树，则称 $G$ 是有二义性的（ambiguity）。

注意二义性是文法的性质，而不是语言的性质。一个语言的众多文法中有的是有二义性的，有的是没有二义性的。而判断一个 CFG 是否具有二义性是一个不可判定的问题。

判定一个 CFG 是否存在二义性是一个不可解的问题。

一些文法可以通过某种方式修复成没有二义性的语法，但是有一些语言是不存在非二义性的，称为固有二义性（inherent ambiguity）或先天二义性。

例如 $\{0^i 1^j 2^k | i = j \vee j = k\}$ 的所有文法都是固有二义性的，这是因为语言本身就蕴含了一种“或”的关系，对于 $0^n 1^n 2^n$ 这样的句子可以走两条派生的路径，且它们最终都能推出这个句子。后面会用 Ogden 引理证明这个语言是固有二义性的。

自顶向下分析和自底向上分析

判定一个句子是否属于一个文法对应的语言时，可以采取从起始符号派生为句子的方式，也可以采用从句子规约到起始符的方式，前者称为自顶向下的分析，后者称为自底向上的分析。

上下文无关文法的化简

无用符号

设 CFG $G = (V, T, P, S)$，对于任意 $X \in V \cup T$，如果存在 $w \in L(G)$ 使得 $w$ 的派生过程中存在 $X$（即 $\exists \alpha, \beta \in (V \cup T)^{*}. S \xRightarrow{*} \alpha X \beta \xRightarrow{*} w$），则称 $X$ 是有用的，否则称为是无用的。

注意终结符也有可能是无用的，因此需要考虑 $V \cup T$ 内的所有字符。

这个定义实际上包含了两层，即要求 $S \xRightarrow{*} \alpha X \beta$，又要求 $\alpha X \beta \xRightarrow{*} w$。在两个条件下发现无用符号的方法类似，分别是从起始符号和终结符集开始，将能够从已有集合的符号所组成的派生/规约得到的符号加入到集合中，并求这个过程的闭包。

\begin{algorithm} \caption{Remove Unused Symbols} \begin{algorithmic} \procedure{StartFromTerminators}{CFG $G = (V, T, P, S)$} \state initialize $SV$ as $\{ A | A \rightarrow w \in P \wedge w \in T^{*} \}$ \repeat \state $SV \gets SV \cup \{A | A \rightarrow \alpha \in P \wedge \alpha \in (T \cup Q)^{*}\}$ \until{$SV$ is unchanged in this iteration} \state $V’ \gets SV$ \state $P’ \gets \{ A \rightarrow \alpha | A \rightarrow \alpha \in P \wedge A \in V’ \wedge a \in (T \cup V’)^{*} \}$ \return $G’ \gets (V’, T, P’, S)$ \endprocedure \procedure{StartFromStarter}{CFG $G = (V, T, P, S)$} \state initialize $SV$ as $\{S\} \cup \{ A | S \rightarrow \alpha A \beta \in P \}$ \state initialize $ST$ as $\{ s | S \rightarrow \alpha a \beta \in P \}$ \repeat \state $SV \gets SV \cup \{B | A \in SV \wedge A \rightarrow \alpha B \beta \in P \}$ \state $ST \gets ST \cup \{a | A \in SV \wedge A \rightarrow \alpha a \beta \in P \}$ \until{both $SV$ and $ST$ are unchanged in this iteration} \state $V’ \gets SV$ \state $P’ \gets SP$ \state $P’ \gets \{ A \rightarrow \alpha | A \rightarrow \alpha \in P \wedge A \in V’ \wedge a \in (T \cup V’)^{*} \}$ \return $G’ \gets (V’, T’, P’, S)$ \endprocedure \end{algorithmic} \end{algorithm}

值得注意的是，上面两个过程必须先执行 StartFromTerminators（无法导出终结串），然后执行 StartFromStarter（起始符号不可达）。例如 $S \rightarrow AB; A \rightarrow a; B \rightarrow Bb$，显然这个语言是一个空集，然后如果先执行第二步，再执行第一步，会发现 $S, A, C$，并不会被删除，需要再次执行第二步。

这是因为【删除不能导出终结串】的符号可能会产生新的【从起始符号不可达】的符号，但是【删除从起始符号不可达】的字符串并不会产生新的【不能导出终结串】的符号。

去除空串

形如 $A \rightarrow \varepsilon$ 的产生式称为空产生式（null production）。对于 $G = (V, T, P, S)$ 中的任何非终结符 $A$，如果 $A \xRightarrow{+} \varepsilon$，则称 $A$ 是可空（nullable）变量。

寻找可空变量可以从 $A \rightarrow \varepsilon$ 这样的产生式开始，寻找一个闭包：

\begin{algorithm} \caption{Find Nullable Variables} \begin{algorithmic} \procedure{main}{CFG $G = (V, T, P, S)$} \state initialize $U$ as $\{ A | A \rightarrow \varepsilon \in P \}$ \repeat \state $U \gets U \cup \{A | A \rightarrow \alpha \in P \wedge \alpha \in U^{*}\}$ \until{$U$ is unchanged in this iteration} \return $U$ \endprocedure \end{algorithmic} \end{algorithm}

化简时不能直接删除会产生空产生式的推导。在去除空串时，需要先求出可空变量集合 $U$。对于 $A \rightarrow X_1 X_2 \dots X_n$，，令 $A \rightarrow \alpha_1 \alpha_2 \dots \alpha_n$，其中

如果 $X_i \in U$，那么 $\alpha_i = X_i$ 或 $\alpha_i = ε$
否则 $\alpha_i = X_i$
$\alpha_1, \alpha_2, \dots, \alpha_n$ 不能同时为空

去除单一产生式

形如 $A \rightarrow B$ 的产生式称为单一产生式（unit production）。

例如在语法分析时，$E \rightarrow T + T | T * T | T$ 中包含的 $E \rightarrow T$ 就是单一产生式。

单一产生式的去除方法很简单：

乔姆斯基范式

如果 CFG $G = (V, T, P, S)$ 中的所有产生式都具有形式

\[A \rightarrow BC\] \[A \rightarrow a\]

其中 $A, B, C \in V$，$a \in T$，则称 $G$ 为乔姆斯基范式文法（Chomsky normal form），简称 CNF。

CNF 的特点是它的语法树是一颗类似二叉树的形式。

对于一个普通的文法，转换为 CNF 的步骤如下：

先经过去除无用符号、去除空产生式和单一产生式的化简。此时文法形如
\[A \rightarrow X_1 X_2 \dots X_n\ (X_i \in V \cup T)\] \[A \rightarrow a\]
对于每个终结符 $a \in T$，添加 $T_a \in V$，并添加 $T_a \rightarrow a \in P$，再将原来所有出现 $a$ 的地方都替换为 $T_a$。此时文法形如
\[A \rightarrow B_1 B_2 \dots B_n\ (B_i \in V)\] \[T_a \rightarrow a\]
进一步将 $A \rightarrow B_1 B_2 \dots B_n$ 进行拆解，令 $C_i \rightarrow B_i B_{i+1} \dots B_n$，则
\[A \rightarrow B_1 C_2\] \[C_2 \rightarrow B_2 C_3\] \[\dots\] \[C_{n-1} \rightarrow B_{n-1} B_n\] \[T_a \rightarrow a\]

格雷巴赫范式

如果 CFG $G = (V, T, P, S)$ 中的所有产生式都具有形式

\[A \rightarrow aB\]

其中 $A \in V$，$B \in V^{*}$，$a \in T$，则称 $G$ 为格雷巴赫范式（Greibach normal form），简称 GNF。

根据定义，GNF 中的文法只有两种形式：

\[A \rightarrow a\] \[A \rightarrow a B_1 B_2 \dots B_m (m \ge 1)\]

右线性文法是一种特殊的 GNF。

在文法中如果存在形如 $A \xRightarrow{n} \alpha A \beta$ 的派生，则称该派生为变量 $A$ 的递归派生。

如果 $n = 1$ 则称为是直接递归（directly recursive），否则称为间接递归（indirectly recursive）。

当 $\alpha = \varepsilon$ 时，称为左递归（left-recursive）；当 $\beta = \varepsilon$ 时，称为右递归（right-recursive）。

GNF 的特点在于它消除了所有左递归。

将一个普通的文法转换为 GNF 的步骤如下：

先经过去除无用符号、去除空产生式和单一产生式的化简。此时文法形如
\[A \rightarrow X_1 X_2 \dots X_n\ (X_i \in V \cup T)\] \[A \rightarrow a\]
对于 $A \rightarrow \alpha$，如果满足 $\alpha \in T \cup V^{+} \cup TV^{+}$，则不作处理；否则对于 $\alpha = X_1 X_2 \dots X_m$。如果 $X_i (i \ge 2) = a \in T$，则加入产生式 $T_a \rightarrow a$，并用 $T_a$ 代替所有出现 $a$ 的地方，此时文法形如
\[A \rightarrow B_1 B_2 \dots B_n\ (B_i \in V)\] \[A \rightarrow a B_1 B_2 \dots B_n\] \[A \rightarrow a\]
下面考虑去除文法中的左递归，打破文法中左递归的循环。设 $V_1 = \{A_1, A_2, \dots, A_m\}$
- 对于 $A_i \rightarrow A_j \alpha\ (i > j)$，用 $A_j$ 的产生式 $A_j \rightarrow \beta_1 | \beta_2 | \dots | \beta_n$ 替换右部的第一个 $A_j$，得到 $A_i \rightarrow \beta_1 \alpha | \beta_2 \alpha | \dots | \beta_n \alpha$
- 对于 $A_i \rightarrow A_i \alpha_1 | A_i \alpha_2 | \dots | A_i \alpha_n | \beta_1 | \beta_2 | \dots | \beta_m$，其中 $\beta_j$ 不以 $A_i$ 开头，经过第一步后也不以 $A_j\ (j < i)$ 开头，将 $A_i$ 的产生式替换为下面的产生式集
  \[A_i \rightarrow \beta_1 | \beta_2 | \dots | \beta_m\] \[A_i \rightarrow \beta_1 B | \beta_2 B | \dots | \beta_m B\] \[B \rightarrow \alpha_1 | \alpha_2 | \dots | \alpha_n\] \[B \rightarrow \alpha_1B | \alpha_2B | \dots | \alpha_nB\]
经过上面两步，保证了文法的形式如下
\[A_i \rightarrow A_j \alpha\ (i < j)\] \[A_i \rightarrow a \alpha\] \[A_i \rightarrow a\] \[B_i \rightarrow \alpha\]
设 $V = \{A_1 \cup A_2 \cup \dots \cup A_n\} \cup \{B_1 \cup B_2 \cup \dots \cup B_m\}$，则 $A_n$ 已经符合要求，因此需要从 $A_n$ 开始，对于 $i > j$ 将 $A_i$ 逐步代回到 $A_j$ 中。此时 $A_i$ 都符合要求，接下来对 $B_i$ 进行同样的化简操作即可。
考虑到每次经过这个步骤，对于单个产生式 $A_i \rightarrow A_j\alpha$ 产生的 $B \rightarrow \alpha$，其右侧的符号数量 $|\alpha|$ 是递减的（$|A_j \alpha| < |\alpha|$），因此算法能够终止。

自嵌套文法

设 CFG $G = (V, T, P, S)$ 是化简过的文法，如果 $G$ 中存在形如

\[A \xRightarrow{+} \alpha A \beta\]

的派生，则称 $G$ 是自嵌套文法（self-embedding grammar），其中 $\alpha, \beta \in (V \cup T)^{+}$。

自嵌套文法可以是正则语言，例如 $S \rightarrow 0S0 | 0S | 0$；但是非自嵌套文法一定是正则语言。

派生

派生树