第七章

7.1 CFG 的范式

为了得到 CNF 的 CFG,我们需要做一些简化操作。

顺序如下:

  1. 消空生成式
  2. 消单生成式
  3. 消无用符号

7.1.1 消无用符号(非生成、不可达)

如果存在 $S \stackrel {*}{\Rightarrow} \alpha X \beta \stackrel {*}{\Rightarrow} w$ 形式的推导,则 X 是有用的,称 X 是有用符号。( $w$ 属于 $T^*$ )。否则是 无用符号

设有终结串 $w$,若 $X \stackrel {*}{\Rightarrow} w$ ,则 $X$ 是有生成能力的(generaing),或称 X 是 生成符号

设有终结串 $\alpha , \beta $,如果 $S \stackrel {*}{\Rightarrow} \alpha X \beta $,则 $X$ 是 可抵达的(reachable),或称 X 是可达符号

有用符号就是既有生成能力,又可以抵达的符号。

无用产生式就是所有与无用符号有连接的乘积。例如 $S \to a + abB$ ,而 $B$ 是无用符号,则 $abB$ 是无用产生式。

7.1.3 消除可致空符号($\varepsilon$ 产生式)

$\varepsilon $ 产生式:形如 $A \to \varepsilon $ 的产生式。也叫 $\lambda $ 产生式。

可致空符号:能够最终产生 $\lambda $ 的产生式。

消除可致空符号的步骤如下:

假设有 CFG $G$ :

  • $S \to AB$
  • $A \to aAA \mid \varepsilon $
  • $B \to bBB \mid \varepsilon $

目标:构造 $G_1$ 使得 $L (G_1) = L (G) - {\varepsilon}$

分析:

显然 A,B 是可致空符号。将 $A \to \varepsilon , B \to \varepsilon $ 带入 G 的生成式。对于 AB,有四种组合:两个都是 $\varepsilon $ , 或只有 A 是 $\varepsilon $ ,或只有 B 是 $\varepsilon $ ,或两个都不是 $\varepsilon $. 都要带入考虑。不妨简记为 00, 01, 10, 11。对于 AA,BB 同理。可以列出下面的表:

代入的产生式 00 01 10 11
$S \to AB$ $\varepsilon$ B A AB
$A \to aAA $ $a$ $aA$ $aA$ $aAA$
$B \to bBB $ $b$ $bB$ $bB$ $bBB$

从而得到:

  • $S \to \varepsilon \mid A\mid B\mid AB$
  • $A\to a\mid aA\mid aAA$
  • $b\to b\mid bB\mid bBB$

我们去除其中的 $S\to \varepsilon$,从而得到 $G_1$:

  • $S \to A\mid B\mid AB$
  • $A\to a\mid aA\mid aAA$
  • $b\to b|bB|bBB$

$G_1$ 与原文法 $G$ 不再是同一个文法,因此存在且唯一存在的差别是 $G_1$ 不产生 $\varepsilon$ 串。

7.1.4 消除单生成式

形如 $A\to B$ 的生成式称为单变量生成式,简称 单生成式。如果经过 $A$ 的任意次推导,导出 $A', A'', \cdots$,则 $(A, A'),(A,A''),(A',A''),\cdots$ 称为单元偶对

【例子】设二型文法 $G = (\{S,A,B\}, \{(,),+,*,a\},P,S)$,其中 $P$:

  • $S\to S+A\mid A$
  • $A\to A*B\mid B$
  • $B\to(S)\mid a$

构造无单生成式的文法 $G_1$。

分析:注意到 $S\to A \to B$,所以存在单元偶对:$(S,A), (S,B), (A,B)$

对于 $(A,B)$:$A \to A*B\mid (S)\mid a$

对于 $(S,A)$:$S\to S+A \mid A*B\mid (S)\mid a$

所以 $P_1$ 为:

  • $S\to S+A \mid A*B\mid (S)\mid a$
  • $A \to A*B\mid (S)\mid a$
  • $B\to(S)\mid a$

7.1.5 消除左递归

若有非终结符 $A$,其推导出的句型以 $A$ 为最左符号,则所属的文法是左递归文法

直接左递归

形如 $A\to A \alpha \mid \beta$ 的句型是直接左递归的。

消除方法:

【例子】现有:$A \to A \alpha _1 \mid A \alpha _2 \mid \beta _1 \mid \beta 2$

第一步:

$A \to \beta _1 A' \mid \beta _2 A'$

第二步:

$A ' \to \varepsilon \mid \alpha _1 A' \mid \alpha _2 A'$

也即,所有 $P \to P \alpha \mid \beta $ 都可以转化为:

$P \to \beta P', P' \to \alpha P' \mid \varepsilon $

间接左递归

需要解一次以上引用的左递归是间接左递归。

例如:

$A \to B\alpha \mid C$ $B \to A\beta \mid D$

移除间接左递归,只需要解引用,使之变成直接左递归。

7.2 CFL 的封闭性

设 $L_1,L_2$ 是二型语言,则 $L_1 \cup L_2, L_1L_2, L_1 ^*$ 是二型语言。

二型语言对交不封闭,对补不封闭,对置换封闭