形式语言和自动机——上下文无关文法与下推自动机论述.ppt

§4.5 上下文无关文法与下推自动机 ;从上下文无关文法构造等价的下推自动机; 构造方法 设 CFG G = (N, T, P , S ) ， 构造一个空栈接受方式的 PDA M＝（Q，T，Γ，δ，q0，z0，F） 其中 Q＝{q}, Γ=N∪T, q0＝q，z0＝S, F＝φ (∵以空栈接受) 即 M = ( {q} , T, N?T, ?, q, S , F) , 转移函数 ? 定义如下： (1) 对每一 A?N, ? (q, ?, A) = {(q,?)?A??”?P }; （即将栈顶的A换为β） (2) 对每一 a?T, ? (q, a, a) = { (q, ?) }. （即若栈顶为终结符，则退栈） ;q;自顶向下的分析过程;例2：利用下推自动机进行自顶向下的分析过程;定理的证明;定理的证明;例：构造一个PDA M，使Lφ(M)= L(G)。其中G是我们常用来生成算术表达式的文法： G＝（N，T，P，E） N＝{ E,T,F }, T ={ +,*,(,),a }, S = { E } P: E→E+T∣T ; T→T*F∣F; F→( E )∣a 解：构造M＝（{q}，T，Γ，δ，q，E，φ） δ定义为： ① δ(q,ε,E)＝{ (q, E+T ), (q, T) } ② δ(q,ε,T)＝{ (q, T*F ), (q, F) } ③ δ(q,ε,F)＝{ (q, (E) ), ( q, a) } ④ δ(q, b,b)＝{ (q, ε) } 对所有 b∈{ a,+,*,(,) };用格局说明句子分析过程;从下推自动机构造等价的上下文无关文法;从下推自动机构造等价的上下文无关文法;从下推自动机构造等价的上下文无关文法;（书P169－170）由PDA M构造文法G 设PDA M＝（{q0,q1},{a,b},{A,z0},δ,q0,z0,Φ） δ定义为：δ（q0,a,z0）={( q0,Az0)} ① δ（q0,a,A）={( q0,AA)} ② δ（q0,b,A）={( q1,ε)} ③ δ（q1,b,A）={( q1,ε)} ④ δ（q1,ε,A）={( q1,ε)} ⑤ δ（q1,ε,z0）={( q1,ε)} ⑥ ; q0 b, A/ε q1; q0 b, A/ε q1; q0 b, A/ε q1;(4)删除无用符号[ q0,A,q1] 和 [ q1,z0,q0]及相应产生式 重命名[ q0,z0,q1]为A S→A [ q1,A,q1]为B A→aCD [ q0,A,q1]为C 得 B→b∣ε [ q1,z0,q1]为D C→aCB∣b D→ε 注: 构造生成式时，可从S生成式出发，以避免生成无用产生式。;定理的关键： 当存在δ(q，a，z)含有（γ，B1B2…Bk）则对Q中的每个可能的状态序列q1 q2 … qk排成一条产生式 [q, z, qk]→a[γ, B1, q1][ q1, B2,q2]…[qk-1,Bk,qk ] ??是一个猜测过程，实质是写出从q出发，栈顶为Z，经过一系列推导走到qk的所有可能的状态序列，其中必有一条路径是正确的。 ?? ;M＝（{q}，T，Γ，δ，q，E，φ） δ定义为： ① δ(q,ε,E)＝{ (q, E+T ), (q, T) } ② δ(q,ε,T)＝{ (q, T*F ), (q, F) } ③ δ(q,ε,F)＝{ (q, (E) ), ( q, a) } ④ δ(q, b,b)＝{ (q, ε) } 对所有 b∈{ a,+,*,(,) } 算术表达式的文法 G＝（N，T，P，E） N＝{ E,T,F }, T ={ +,*,(,),a }, S = { E } P: E→E+T∣T ; T→T*F∣F; F→( E )∣a;练习: 从PDA构造等价的上下文无关文法;练习: 从PDA构造等价的上下文无关文法;作业: Ch4 习题 20，21，22