形式语言与自动机ch4.2.ppt

§ 4.2 上下文无关文法的变换 ;生成式的标准形式;变换算法 -- 消去无用符号; 计算生成符号（generating symbol）集;计算生成符号集;步骤: (1) N 0 = ? (赋为?) N 0为有用的非终结符集 (2) N’ = {A | A→ω且ω∈T*} N’为非终结符集合 (3) 如果N 0≠N’ 则转(4),否则转(6) (4) N 0=N’ (5) N’= N 0∪{ A | A→α且α∈(T∪N 0)* }, 转(3) (6) N 1 = N’ 小结: 算法1找出能推出终结符串的非终结符作为有用符号. ; 一层层向外扩展，直至最外两层相等为止。所得集合即是算法1的有用符号。 ;计算可达符号集;算法步骤: (1) N 0 = {S} (2) N’= {x | A∈N 0 且A→αxβ}∪∈ N 0 (N’为有用符号集合) (3) 如果N 0≠N’转(4), 否则转(5) (4) N 0=N’; 转(2) (继续迭代下去) (5) N 0 = 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|β1 Ai ’|βp Ai ’ Ai ’→α1|…|αn|α1 Ai ’|…|αn Ai ’ i=m？ Y 结束 ? i：=i+1，j：=1  对每个Ai →Ajα，Aj→β1|…|βn 用Ai →β1α|β2α|…|βnα代替 Y j=i-1？ N j：=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 | A2 A3b | ab （4） β1 α1 β2 消直接左递归 A2→A3A1|ab| A3A1 A2’|abA2’ （5） A2’→ A3 b | A3b A2’ （6） 当i=3，j=1 A3→A1A2 | A3A3 | a →A2 A3 A2 | a A2 |A3A3 | a （7） ; α1 β1 α2 j=2 A3→A3A1 A3A2 | a b A3 A2 | A3 A1 A2’A3 A2 | a b A2’A3 A2 | a A2 | A3A3 | a （8） β2 β3