(19)第三章-第二讲-上下文无关文法的变换

第三章上下文无关文法与下推自动机第二讲上下文无关文法的等价变换一、对文法进行等价变换的基本概念1、变换问题引例：上下文无关文法G=(N,T,P,S),其中：N={S,A,B},T={0,1},P={S→0,A→1,B→0},容易看出，上述文法中的非终结符A、B和终结符1不可能出现在从S出发的推导的句型中，同时，生成式A→1,B→0也是无用生成式。因此，从文法G中删除这些无用终结符、非终结符和生成式，不会改变原文法所生成的语言。文法变换的定义：当给定一个文法G之后，为删除G中所有的无用符号及其所涉及到的无用生成式（或为使所有生成式满足某种标准形式）而对文法G做等价变换，这种等价变换不改变原文法G的生成能力(或描述能力)，则称这种变换为文法变换。变换问题：为了对文法进行简化，或者对文法进行某种标准形式的规范化处理，需要对所给定的文法进行等价变换。一、对文法进行等价变换的基本概念2、Chomsky(乔姆斯基)范式、Greibach(格雷巴赫)范式Chomsky范式：设有上下文无关文法G，如果每个生成式的形式均为A→BC或A→a，其中A，B，C∈N，a∈T，则称文法G是满足Chomsky范式的上下文无关文法，记为：CNFG(ChomskyNormalFormGrammar)。Greibach范式：设有上下文无关文法G，如果每个生成式的形式均为A→aβ，且不包含ε生成式，其中A∈N，a∈T，β∈N*，则称文法G是满足Greibach范式的上下文无关文法,记为:GNFG(GreibachNormalFormGrammar)。一、对文法进行等价变换的基本概念3、有用符号与无用符号有用符号与无用符号：设上下文无关文法G=(N,T,P,S),如果对某些w∈T*，X∈N∪T，若X出现在推导Sw中，则X是有用符号；若找不到这样的w使X出现在推导Sw中，则X是无用符号；有用符号的筛选：根据有用符号的定义，应通过如下两个步骤筛选出所有的有用符号：**步骤①在给定的上下文无关文法G中，对每一个非终结符A∈N，判断是否能由A推导出某终结符串w，选出所有这样的A。步骤②对于每一个符号X∈N∪T而言，在给定的上下文无关文法G中，判断X是否能出现在由起始符S开始的某个推导过程中的某个句型之中。若是，则X是有用符号；否则，X是无用符号。注意：步骤①中给出的该条件只是必要条件而并非充分条件，也既有用的非终结符一定满足该条件，但满足该条件的非终结符不一定是有用的。所以这里选择出来的所有满足该条件的A并不一定都是有用的非终结符(因为从S出发并非一定能推导出A)。注意：在做完步骤①的基础上，再做步骤②，进一步选择所有的有用符号X。此处的X可能是非终结符（已经满足步骤①中的条件），也可能是终结符。1、删除部分无用非终结符之思想定理8：已知上下文无关文法G=(N,T,P,S)产生的语言是非空的，则必能找到一个等效的文法G1，使对于G1的每一个非终结符A，都存在推导Aw，w∈T*。证明略。*算法1：删除部分无用非终结符。根据定理8，对给定的上下文无关文法G=(N,T,P,S)，删除部分无用非终结符及其相关的无用生成式，从而产生一个删除了部分无用非终结符的等效文法G1=(N1,T,P1,S)，其算法如下：二、对文法进行变换的有关算法N1NP1P二、对文法进行变换的有关算法2、删除部分无用非终结符之算法算法1：删除部分无用非终结符。根据定理8，对给定的上下文无关文法G=(N,T,P,S)，删除部分无用非终结符及其相关的无用生成式，从而产生一个删除了部分无用非终结符的等效文法G1=(N1,T,P1,S)，其算法如下：2、删除部分无用非终结符之算法①N0:=Ø，N0为非终结符集合；②N':={A|A→w∈P且w∈T*}，N'亦为非终结符集合；③如果N0≠N'，则转④；如果N0=N'，转⑥；④N0:=N'；⑤N':=N0∪{A|A→α∈P且α∈(T∪N0)*}，转③；⑥N1:=N'；⑦P1:=删除集合P中含有X的生成式；其中X∈N-N1二、对文法进行变换的有关算法算法1：删除部分无用非终结符。根据定理8，对给定的上下文无关文法G=(N,T,P,S)，删除部分无用非终结符及其相关的无用生成式，从而产生一个删除了部分无用非终结符的等效文法G1=(N1,T,P1,S)，其算法如下：当N0=N'时，说明刚才最后一次循环做步骤⑤求N'时没有往N'中添加新的非终结符，说明已找到所有有用的非终结符。逐步扩充集合N'：找出所有直接或间接能推导出终结符串w的非终结符作为有用非终结符放入集合N'中。X即无用非终结符。2、删除部分无用非终结符之算法①N0:=Ø，N0为非终结符集合；②N':={A|A→w∈P且w∈T*}，N'亦为非终结符集合；③如果N0≠N'，则转④；如果N0=N'，转⑥；④N0:=N'；⑤N':=N0∪{A|A→α∈P且α∈(T∪N0)*}，转③；⑥N1:=N'；⑦P1:=删除集合P中含有X的生成式；其中X∈N-N1二、对文法进行变换的有关算法算法1：删除部分无用非终结符。根据定理8，对给定的上下文无关文法G=(N,T,P,S)，删除部分无用非终结符及其相关的无用生成式，从而产生一个删除了部分无用非终结符的等效文法G1=(N1,T,P1,S)，其算法如下：例如：若有生成式：A→ab;B→de;C→ABb(一步推导式),则必有：Cw(实际上有：C→ABb→abBb→abdeb)故A,B,C均先后进入N',故A,B,C最后都进入N1*二、对文法进行变换的有关算法3、进一步删除无用符号之思想定理9：已知一个由算法1得到的上下文无关文法G1=(N1,T1,P1,S)，则必能找到一个等效的上下文无关文法G2=(N2,T2,P2,S)，使对于G2的每一个符号X∈N2∪T2,一定存在α,β∈(N2∪T2)*，使得SαXβ。（证明略）*算法2：进一步删除所有无用符号。根据定理9，对文法G进行算法1处理后所得文法G1=(N1,T1,P1,S)，一定可以进一步删除G1中所有无用符号及相关的生成式，从而得到一个与原文法G等效的文法G2=(N2,T2,P2,S)，其算法如下：T2T1P2P1N2N1二、对文法进行变换的有关算法4、进一步删除无用符号之算法算法2：进一步删除所有无用符号。根据定理9，对文法G进行算法1处理后所得文法G1=(N1,T1,P1,S)，一定可以进一步删除G1中所有无用符号及相关的生成式，从而得到一个与原文法G等效的文法G2=(N2,T2,P2,S)，其算法如下：二、对文法进行变换的有关算法4、进一步删除无用符号之算法算法2：进一步删除所有无用符号。根据定理9，对文法G进行算法1处理后所得文法G1=(N1,T1,P1,S)，一定可以进一步删除G1中所有无用符号及相关的生成式，从而得到一个与原文法G等效的文法G2=(N2,T2,P2,S)，其算法如下：①N0:={S}；②N':={X|A∈N0且A→αXβ∈P1,α,β∈(N1∪T1)*,X∈N1∪T1}∪N0,N'为有用符号的集合；③如果N0≠N'，则转④；如果N0=N'，转⑤；④N0:=N'，转②；⑤N2:=N0∩N1,T2=N0∩T1；⑥P2:=P1中只含有N0中的符号的生成式。逐步扩充集合N':逐步找出所有从S出发可以到达的有用符号放入集合N'中。当N0=N'时，说明本次循环N'中没有添加新的有用符号，说明已找到所有的有用符号。删除N1中无用符号构成N2；删除T1中无用符号构成T2二、对文法进行变换的有关算法5、算法1和算法2之作用及其关系作用：对给定的一个上下文无关文法G=(N,T,P,S)，经过算法1和算法2先后两次处理，可以删除所有的无用符号以及与之相关的无用生成式，从而达到对G进行等价化简变换之目的。关系：算法1必须先于算法2执行，才能有效删除所有无用符号以及与之相关的所有无用生成式。定理10：任何非空的上下文无关语言,都存在一个产生该语言的上下文无关文法G,且G是一个不含任何无用符号和无用生成式的上下文无关文法。思考：如何结合算法1和算法2对定理10进行证明？二、对文法进行变换的有关算法6、删除ε生成式目的：对上下文无关文法G来说，如果某生成式右部是空串，即形如A→ε的生成式，则在一般情况下这样的生成式是不必要的，应予以删除。但有一种情况例外：若G生成的语言L(G)中含有ε作为合法的句子，则不能删除生成式S→ε，其中S是起始符。无ε文法之定义：设有一个上下文无关文法G=(N,T,P,S)，如果生成式P中无任何ε生成式，或只有一个ε生成式S→ε且S不在任何生成式的右部出现，则称G为无ε文法。二、对文法进行变换的有关算法7、删除ε生成式之算法算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+在以下的讨论过程中,可以认为文法G已经过算法1和算法2的处理，G中已不存在无用符号及其与之相关的无用生成式。算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+①N0:=Ø，N0为非终结符集合；②N':={A|A→w∈P且w∈T*}，N'亦为非终结符集合；③如果N0≠N'，则转④；如果N0=N'，转⑥；④N0:=N'；⑤N':=N0∪{A|A→α∈P且α∈(T∪N0)*}，转③；⑥N1:=N'；算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+①N0:=Ø，N0为非终结符集合；②N':={A|A→ε∈P且A∈N,ε∈T*}③如果N0≠N'，则转④；如果N0=N'，转⑥；④N0:=N'；⑤N':=N0∪{A|A→α∈P且α∈(T∪N0)*}，转③；⑥N1:=N'；算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+①N0:=Ø，N0为非终结符集合；②N':={A|A→ε∈P且A∈N,ε∈T*}③如果N0≠N'，则转④；如果N0=N'，转⑥；④N0:=N'；⑤N':=N0∪{A|A→α∈P且A∈N,α∈N0*}，转③；⑥N1:=N'；算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+①N0:=Ø，N0为非终结符集合；③如果N0≠N'，则转④；如果N0=N'，转⑥；④N0:=N'；⑥N1:=N'；⑤N':=N0∪{A|A→α∈P且A∈N,α∈N0*}，转③；②N':={A|A→ε∈P且A∈N,ε∈T*}算法3：对给定的一个上下文无关文法G=(N,T,P,S)，一定可以删除所有形如A→ε的生成式，从而得到一个与G等效的文法G1=(N1,T,P1,S1)是无ε的上下文无关文法，其算法如下：(1)修改算法1,使之能够逐步求得集合N'={A|A∈N且Aε}+①N0:=Ø，N0为非终结符集合；③如果N0≠N'，