计算理论课件第三章

第三章上下文无关文法与下推自动机Context Free Grammar (CFG)and Push Down Automaton (PDA)上下文无关文法（CFG）在程序设计语言和编 译原理中有着重要的应用，因为上下文无关文法 可以用来阐述绝大多数的程序设计语言的句法结 构此外上下文无关语言也可以作为描述语言翻 译方案的基础 本章重点讨论:CFG的简化CFG的两种范式下推自动机（PDA）的概念PDA与CFG之间的等价转换上下文无关语言运算的封闭性以及CFL的有关判定问题3.1 上下文无关文法的派生树(推导树) 一个上下文无关文法中的一个句型的派生过程可以用 —棵树来描述 【例3-1.1】 给定文法G=({S,A},{a,b},P,S)，其中 P： SaAS|a, ASbA|ba|SS句型aabbaa的派生过程就可以 用一棵树来描述，如图3-1.1所示将此树的叶结点符号 从左到右读取下来构成的符 号串就是aabbaaS๐ a๐A๐๐SS๐b๐๐Aa๐b๐๐a๐a图3-.11 aabbaa的派生树1．派生树的定义 设文法 G =(ＶＮ,ＶＴ,Ｐ,S)是上下文无关文法,如果一棵有序树满足下面四个条件，则它是棵派生树： (1) 它的每个结点标记的符号是(ＶＮ∪ＶＴ∪{ε})中的符号； (2) 根结点标记开始变元S； (3) 内结点标记的符号是变元，即是ＶＮ中的符号。

(4) 如果一个内结点标记为A，且X1,X2,…,Xk是A的从左 到右的所有子结点, 则AX1X2…Xk是P中一个产生式 (5) 如果一个结点标记符号是ε，则它是其父结点的唯一儿子结点其中第(5)条是为了防止下面情况发生： 如产生式Aa(a是个终极符)被误认为 是Aaε或Aεa，而在派生树中被 画成如图3-2形式 2．派生树的结果设T是棵派生树，将此树的叶结点符号从左到右依次读 取下来构成的符号串就是此派生树的结果例如，图3-1.1派生树的结果就是aabbaa 3．派生树与句型的派生关系设G =(ＶＮ,ＶＴ,Ｐ,S)是CFG，如果G中有派生S*α， 则在G中必有一棵以α为结果的派生树反之，如果G中 有一棵以α为结果的派生树，则G中也必有派生S * α 可以说派生与派生树是一一对应的A๐ ๐๐ ๐ε๐ ๐Aa๐ ๐ε๐ ๐๐ ๐a图 3-1.24．最左派生与最右派生所谓最左派生，就是在一个派生的每一步都是对句型 中最左边的变元进行替换例如，例3-1中aabbaa的派生：SaASaSbASaabASaabbaSaabbaa ， 此派生是最左派生所谓最右派生，就是在一个派生的每一步都是对句型 中最右边的变元进行替换。

SaASaAaaSbAaaSbbaaaabbaa, 此派生是最右派生 5．上下文无关文法的二义性设G是个CFG，如果它的某个句子有两棵不同构的派生 树，则称G是二义性的上下文无关文法例3-1.2】 给定CFG G=({S},{a,b},P,S)，其中P：SaSbS|bSaS|ε 句子abab的两棵不同构的派生树，如图3-1.3所示图3-1.3 abab的两棵不同构的派生树S๐ ๐ a๐ ๐ S๐ ๐๐ ๐Sb๐ ๐ S๐ ๐ ๐ ๐aε๐ ๐๐ ๐ε๐ ๐ε๐ ๐S๐ ๐bS๐ ๐a๐ ๐S๐ ๐๐ ๐Sb๐ ๐๐ ๐Sa ๐ ๐ε๐ ๐๐ ๐εε๐ ๐S ๐ ๐๐ ๐b这说明此CFG G是有二义性的3.2 上下文无关文法的简化 一个上下文无关文法有时可以去掉一些符号，或者去 掉一些产生式以后，仍然和原来的文法等价，这就是所 谓文法的简化这里简化文法主要是指：去掉无用符号、去掉ε产生 式和去掉单一产生式 1．去掉无用符号定义：给定CFG G=(ＶＮ,ＶＴ,Ｐ,S)，如果在G中存在派 生S *αXβ*w，其中w∈ＶＴ*，X∈ＶＮ∪ＶＴ，则称 符号X是有用的，否则X是无用的。

简单地说，无用符号就是G中对任何w∈L(G)的派生中 都不会出现的符号例3-2.1】给定文法G=({S,A,B,C},{a,b},P,S)，其中P： SAB|a, ABC|a,Cb G中有派生：可见再往下就无法推导了，因而由S只能推出a，不能推 出其他符号串所以此文法中，A、B、C、b都是无用的 符号，只有S和a是有用符号如何去掉无用符号？分两步走，使用两个引理，就可以做到这一点下面介绍这两个引理引理3-2.1 给定CFG G=(ＶＮ,ＶＴ,Ｐ,S)，且L(G)≠Φ，可 以找到一个与G等价的CFG G’=(ＶＮ’,ＶＴ,Ｐ’,S)，使得 每个A∈ＶＮ’，都有w∈ＶＴ*，且在G’中有A*w 证明：1）求ＶＮ’的算法： begin⑴ OLDＶＮ:=Φ⑵ NEWＶＮ:={A|Aw∈P 且w∈ＶＴ*}⑶ While OLDＶＮ≠NEWＶＮ dobegin⑷ OLDＶＮ:=NEWＶＮ⑸ NEWＶＮ:= OLDＶＮ∪{A|Aα∈P,且α∈(ＶＴ∪OLDＶＮ)*}end⑹ ＶＮ’ :=NEWＶＮ, end下面证明此算法的有效性 显然对任何变元A∈NEWＶＮ,不论A是在第⑵步还是在第 ⑸步加入到NEWＶＮ中的,都有派生A*w,其中w∈ＶＴ*。

只证明G中任何派生A*w ，w∈ＶＴ*,必有A∈NEWＶＮ (对派生的步数归纳证明) a）若此派生是一步完成的，即有Aw，则说明P中有产 生式Aw，于是A在算法的第⑵步被添加到NEWＶＮ中 b）假设G中派生A*w是少于k步完成的,则A∈NEWＶＮ c）当G中有k步派生AX1X2 …Xnk-1w，不妨设 w=w1w2 …wn，其中Xi*wi，(i=1,2,…,n)，而且由于这些 派生的步数少于k步，如果Xi是变元，则根据假设b）得Xi 最终会加入到NEWＶＮ中在执行算法的第⑷步时 OLDＶＮ:=NEWＶＮ,当最后一个Xi加入OLDＶＮ时，在执 行算法的第⑸步时，就将A加入到NEWＶＮ中 这说明此算法是有效的，即凡是可以推出终极符串的变 元都会添加到NEWＶＮ中 于是，最后得到变元集合ＶＮ’ 2）构造文法G’： G’＝(ＶＮ’,ＶＴ,Ｐ’,S)，其中P’：由P中只含有(ＶＮ’∪ＶＴ)的符号的产生式构成的 3）下面证明L(G)=L(G’) a）显然有L(G’)L(G)，因为ＶＮ’ＶＮ，P’Ｐ，所以 G’ 中任何派生S*w，在G中也有S*w所以L(G’)L(G) 。

b）证明L(G)L(G’)，(反证法) 任取w∈L(G)，假设 wL(G’),则说明在G中w的派生S*w中必用到P－P’中的 产生式，即用到了ＶＮ－ＶＮ’中的变元，而这些变元又 能 推出终极符串，这与上面证明的此算法有效矛盾所以 必有w∈L(G’),从而L(G)L(G’) 最后得L(G)=L(G’)例3-2.2】 给定CFG G=({S,A,B,C},{a,b},P,S)，其中 P：SA|B, AaB|bS|b, BAB|Ba, CAS|b 求一个与之等价的文法G’，使得G’中的每个变元都可以推出终极符串 解：对G应用引理3-2.1，执行上述算法，得到的结果如 表3-2.1所示循环次数i 初值 1 2 3OLDＶＮNEWＶＮ当算法执行第三次循环时，判定OLDＶＮ=NEWＶＮ, 算 法终止最后得G’CFG G’=({S,A,C},{a,b},P’,S), 其中 P’：SA, AbS|b, CAS|b 实际上，只去掉了不能推出终极符串的变元B{A,C,S}{A,C}Φ{A,C}{A,C,S}{A,C,S}引理3-2.2 给定CFG G =(ＶＮ,ＶＴ,Ｐ,S)， 可以找到一个与 G等价的CFG G’， G’=(ＶＮ’,ＶＴ’,Ｐ’,S)，使得每个 X∈(ＶＮ’∪ＶＴ’)，都有α,β∈(ＶＮ’∪ＶＴ’)*，且在G’ 中有派生S*αXβ。

证明：1．执行下面迭代算法求ＶＮ’和ＶＴ’1）置初值：ＶＮ’:={S}，ＶＴ’:=Φ;2）如果A∈ＶＮ’ ，在P中又有产生式Aα1|α2|…|αm ， 则可以将α1,α2,…,αm中的所有变元加到ＶＮ’中，将 α1,α2 , …, αm中的所有终极符加到中ＶＴ’中重复2)3）若没有新的符号可加入到ＶＮ’ 、ＶＴ’中，算法停止 最后得到ＶＮ’ 、ＶＴ’ 2．构造P’：是由P中只含有(ＶＮ’∪ＶＴ’)中的符号的产生 式构成的 3．证明L(G)=L(G’) a）显然有L(G’)L(G)，因为ＶＮ’ＶＮ，ＶT’ＶT，P’ Ｐ，所以G’中任何派生S*w，在G中也有S*w所以 L(G’)L(G) b）证明L(G)L(G’)，任取w∈L(G)，不妨设w在G中的 派生为S*αXβ*w，其中α,β∈(ＶＮ∪ＶＴ)*，由上 述算法可知，在此派生中出现的所有符号，都不会因为 对G使用此引理而被去掉，所以这些符号必在ＶＮ’∪ＶＴ’ 中，此派生中所用到的产生式也在P’中，所以这个派生 在G’中也可以实现，因而必有w∈L(G’) 故 L(G)L(G’) 最后得L(G)=L(G’)定理3-2.1 设L是一个非空的上下文无关语言，则L可由一 个不含无用符号的上下文无关文法产生。

证明：设G=(ＶＮ,ＶＴ,Ｐ,S)是个CFG，且L(G)=L≠Φ 先对G用引理3-2.1处理后，得G’＝(ＶＮ’,ＶＴ,Ｐ’,S)， 再 将G’ 用引理3-2.2处理得G’’＝(ＶＮ’’,ＶＴ’’,Ｐ’’,S)，由两 个引理得L(G’’)=L(G)下面证明G’’中不含无用符号假设G’’中有无用符号Y根据引理3-2.2得，在G’’中必 存在派生S*αYβ，其中α,β∈(ＶＮ’’∪ＶＴ’’) *，因为 G’’的符号也都是G’中的符号，所以此派生在G’中也可以 实现，又根据引理3-2.1得，α和β中的变元以及Y都可 以推出终极符串，于是G’中有派生： S*αYβ*w，w∈ＶＴ*，又因为派生αYβ*w中的 符号不会因为对G’用引理3-2.2而被去掉，所以在G’’中也 会实现派生αYβ* w，于是G’’中也有派生 S*αYβ*w，这与符号Y是无用符号矛盾所以G’’ 中不含无用符号值得注意的是，去掉G中无用符号时，一定要先用引理 3-2.1，后用引理3-2.2应用引理的次序不可颠倒，否则可能遗漏一些无用符号请看下面例子 【例3-2.3】 给定CFG G=({S,A,B},{a,b},P,S)，其中 P：SAB|a, Aa 求一个与之等价的文法G”，使得G”中不含无用符号。

解：先对G应用引理3-2.1方法处理，执行此算法得到的 结果如表3-2.2所示循环次数i 初值 1 2 3OLDＶＮ Φ {S,A} NEWＶＮ {S,A} {S,A } 当算法执行第二次循环时，判定OLDＶＮ＝NEWＶＮ，算法终止 最后得G’：CFG G’=({S,A},{a,b},P,S)，其中 P’：Sa, Aa 再对G’用引理3-2.2处理，执行算法的结果如表3-2.3所示：循环次数i 初值 1 2 3ＶＮ’’ {S} {S} ＶT’’ Φ { a } 最后得文法G’’＝({S},{a},P’’,S)，其中P’’={Sa}但是，如果先对G用引理3-2.2，后用引理3-2.1就得到 如下结果：对G用引理3-2.2执行算法的结果，如表3。