形式语言与自动机：上下文无关文法与下推自动机

推导树

最左推导：每次推导只替换出现在最左边的非终结符。

最右推导：每次推导只替换出现在最右边的非终结符。

二义性：2型文法是二义的，当且仅当对于串 $\omega$ ，存在两棵不同的具有边缘为 $\omega$ 的推导树。

上下文无关文法的变换

CNF

A -> BC
A -> a

GNF

A -> aω

其中 $\omega$ 为非终结符串

找出生成符号

略

找出可达符号

略

消除 $\epsilon$ 产生式

可致空符号：可通过一系列变换生成空串的符号
无 $\epsilon$ 文法：生成式中无任何 $\epsilon$ 产生式，或只有一个可致空符号 S -> $\epsilon$ 且 S 不出现在任何生成式的右边

举例：假设存在生成式S -> ABCDE，其中A、C、E可致空

S -> BD    (000)
S -> BDE   (001)
S -> BCD   (010)
S -> BCDE  (011)
S -> ABD   (100)
S -> ABDE  (101)
S -> ABCD  (110)
S -> ABCDE (111)

消除单产生式

S -> S + A | A
A -> A * B | B
B -> (S) | a

中的单元偶对可删掉，同时添加新的生成式：

(S, A) & A -> A * B  =>  S -> A * B
(A, B) & B -> (S)    =>  A -> (S)
(A, B) & B -> a      =>  A -> a
(S, B) & B -> (S)    =>  S -> (S)
(S, B) & B -> a      =>  S -> a

消除左递归

A -> Aa | b 消除左递归之后应存在如下生成式：

A -> b | bB
B -> aB | a

2 型文法转 CNF

如有必要，添加新的非终结符。

CNF 转 GNF*

对非终结符进行编号
若生成式左侧非终结符编号大于右侧第一个非终结符编号，则将小编号非终结符的生成式带入，直至满足要求。
消除左递归
将得到的新生成式带入其他生成式，重复步骤 2, 3