形式语言与自动机课件——上下文无关文法.ppt

§4.2上下文无关文法的变换生成式的标准形式变换算法--消去无用符号计算生成符号（generatingsymbol）集计算生成符号集步骤:
(1)N0=(赋为)N0为有用的非终结符集
(2)N’={A|A→ω且ω∈T*}N’为非终结符集合
(3)如果N0≠N’则转(4),否则转(6)
(4)N0=N’
(5)N’=N0∪{A|A→α且α∈(T∪N0)*},转(3)
(6)N1=N’
小结:算法1找出能推出终结符串的非终结符作为有用符号.一层层向外扩展，直至最外两层相等为止。所得集合即是算法1的有用符号。计算可达符号集算法步骤:
(1)N0={S}
(2)N’={x|A∈N0且A→αxβ}∪∈N0
(N’为有用符号集合)
(3)如果N0≠N’转(4),否则转(5)
(4)N0=N’;转(2)(继续迭代下去)
(5)N0=N’∩N
T1=N’∩T
P1由P内只含N’中符号的生成式组成
(即删去了从S起不可达的符号).一层层外扩,找出从S可达的所有符号(含非终结符和终结符)消去非生成符号及不可达符号消去非生成符号及不可达符号消去产生式算法3:生成无文法算法3:生成无文法算法3:生成无文法消去产生式消去产生式消去单产生式消去单产生式消去单产生式CFG的简化消去单产生式（例）消去单产生式（续）消去单产生式（续）消除递归生成式的代换生成式的代换生成式的代换消除直接左递归消除直接左递归（例）消除直接左递归对推导树的影响消除左递归的算法排列非终结符N={A1,A2,…,Am}
i:=1

将Ai→Aiα1|…|Aiαn|β1|…|βp变换为
Ai→β1|…|βp|β1Ai’|βpAi’Ai’→α1|…|αn|α1Ai’|…|αnAi’

i=m？Y结束

i：=i+1，j：=1
对每个Ai→Ajα，Aj→β1|…|βn用Ai→β1α|β2α|…|βnα代替

Yj=i-1？Nj：=j+1 A1→A2A3|a （1）
A2→A3A1|A1b （2）
A3→A1A2|A3A3|a （3）
排序：{A1，A2，A3}
当i=1对（1）变换，不用变。A1→A2A3|a
当i=2对（2）变换A2→A3A1|A2A3b|ab （4）
β1α1β2
消直接左递归A2→A3A1|ab|A3A1A2’|abA2’（5）
A2’→A3b|A3bA2’（6）
当i=3，j=1A3→A1A2|A3A3|a
→A2A3A2|aA2|A3A3|a（7）
α1β1α2
j=2A3→A3A1A3A2|abA3A2|A3A1A2’A3A2
|abA2’A3A2|aA2|A3A3|a （8）
β2β3α3β4
对（8）消直接左递归
A3→β1A3’|β2A3’|β3A3’|β4A3’|β1|β2|β3|β4
A3’→α1|α2|α3|α1A3’|α2A3’|α3A3’|

作业

Ch4习题：6.8.9.