形式语言与自动机理论电子教案.ppt

《形式语言与自动机理论电子教案.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机理论电子教案.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章上下文无关语言上下文无关语言G Gbrabra：S SS(S)|S(S)|L(Gbra)不是不是RL,是是CFL高级程序设计语言的绝大多数语法结构都高级程序设计语言的绝大多数语法结构都可以用上下文无关文法可以用上下文无关文法(CFG)(CFG)描述。描述。BNF(BNF(巴科斯范式：巴科斯范式：Backus normal formBackus normal form，又叫又叫Backus-naur form)Backus-naur form)。2/17/20231第第6 6章章 上下文无关语言上下文无关语言 主要内容主要内容关于关于CFL的分析的分析派生和归约、派生树派生和归约、派生

2、树CFG的化简的化简无用符、单一产生式、空产生式无用符、单一产生式、空产生式CFG的范式的范式CNFGNFCFG的自嵌套特性的自嵌套特性2/17/20232第第6 6章章 上下文无关语言上下文无关语言 重点重点CFG的化简。的化简。CFG到到GNF的转换。的转换。难点难点CFG到到GNF的转换，特别是其中的用右递归替的转换，特别是其中的用右递归替换左递归的问题。换左递归的问题。2/17/202336.1 6.1 上下文无关语言上下文无关语言 文法文法G=(V，T，P，S)被称为是上下文无关被称为是上下文无关的。的。如果除了形如如果除了形如A的产生式之外，对的产生式之外，对于于 P，均有，均有|

3、，并且，并且V成立。成立。关键：对于关键：对于 AV，如果，如果AP，则无，则无论论A出现在句型的任何位置，我们都可以将出现在句型的任何位置，我们都可以将A替换成替换成，而不考虑，而不考虑A的上下文。的上下文。2/17/202346.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树 算术表达式的文法算术表达式的文法 Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2/17/202356.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树 算术表达式算术表达式x+x/

4、y22的不同派生的不同派生 E EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx+x/Fx+x/FPx+x/PPx+x/yPx+x/y2 E EE+TE+T/FE+T/FPE+T/F2E+T/P2E+T/y2E+F/y2E+P/y2E+x/y2T+x/y2F+x/y2P+x/y2x+x/y2E EE+TT+TT+T/FF+T/FF+T/FPP+T/FPx+T/FPx+F/FPx+F/F2x+F/P2x+P/P2x+P/y2x+x/y22/17/202366.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树文法文法Gexp1句子句子x+x/y22的结构。的结构。2

5、/17/202376.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树派生树派生树(derivation tree)(derivation tree)一棵一棵(有序有序)树树(orderedtree)树的每个顶点有一个标记树的每个顶点有一个标记X，且，且XVT 树根的标记为树根的标记为S；如果非叶子顶点如果非叶子顶点v标记为标记为A，v的儿子从左到右的儿子从左到右依次为依次为v1，v2，vn，并且它们分别标记为，并且它们分别标记为X1，X2，Xn，则，则AX1X2XnP；如果如果X是一个非叶子顶点的标记，则是一个非叶子顶点的标记，则XV；如果顶点如果顶点v标记为标记为，则，则v

6、是该树的叶子，并且是该树的叶子，并且v是其父顶点的惟一儿子。是其父顶点的惟一儿子。2/17/202386.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树别称别称生成树生成树分析树分析树(parse tree)(parse tree)语法树语法树(syntax tree)(syntax tree)顺序顺序v1，v2是派生树是派生树T的两个不同顶点，如果存在顶的两个不同顶点，如果存在顶点点v，v至少有两个儿子，使得至少有两个儿子，使得v1是是v的较左儿子的较左儿子的后代，的后代，v2是是v的较右儿子的后代，则称顶点的较右儿子的后代，则称顶点v1在顶点在顶点v2的左边，顶点的左边，

7、顶点v2在顶点在顶点v1的右边。的右边。2/17/202396.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树结果结果(yield)(yield)派生树派生树T的所有叶子顶点从左到右依次标记的所有叶子顶点从左到右依次标记为为X1 1，X2，Xn，则称符号串，则称符号串X1X2Xn是是T的的结果。结果。一个文法可以有多棵派生树，它们可以有一个文法可以有多棵派生树，它们可以有不同的结果。不同的结果。句型句型的派生树：的派生树：“G“G的结果为的结果为的派生树的派生树”。2/17/2023106.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树派生子树派生子树(su

8、btree)(subtree)满足派生树定义中除了对跟结点的标记的满足派生树定义中除了对跟结点的标记的要求以外各条的树叫要求以外各条的树叫派生子树派生子树(subtree)(subtree)。如果这个子树的根标记为如果这个子树的根标记为A，则称之为，则称之为A子子树。树。惟一差别是根结点可以标记非开始符号。惟一差别是根结点可以标记非开始符号。2/17/2023116.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树定理定理6-16-1设设CFGG=(V，T，P，S)，S*的的充分必要条件为充分必要条件为G有一棵结果为有一棵结果为的派生树的派生树。证明：证明：证一个更为一般的结论

9、：对于任意证一个更为一般的结论：对于任意AV，A*的充分必要条件为的充分必要条件为G有一棵结果为有一棵结果为的的A-子树。子树。充分性：设充分性：设G有一棵结果为有一棵结果为的的A-子树，非叶子子树，非叶子顶点的个数顶点的个数n施归纳，证明施归纳，证明A*成立。成立。2/17/2023126.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树设设A-子树有子树有k+1个非叶子顶点，根顶点个非叶子顶点，根顶点A的的儿子从左到右依次为儿子从左到右依次为v1，v2，vm，并且，并且它们分别标记为它们分别标记为X1，X2，Xm。AX1X2XmP。以以X1，X2，Xm为根的子树的结果依次为

10、根的子树的结果依次为为1，2，m。X1，X2，Xm为根的子树的非叶子顶点为根的子树的非叶子顶点的个数均不大于的个数均不大于k。2/17/2023136.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树 X1*1X X2 2*2X Xm m*m而且而且=1 12 2m m2/17/2023146.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树AX1X2Xm*1X2Xm*12Xm*12m2/17/2023156.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树2/17/2023166.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树

11、必要性必要性设设A An n，现施归纳于派生步数，现施归纳于派生步数n n，证明存在结果为，证明存在结果为的的A-A-子树。子树。设设n nk(kk(k1)1)时时结结论论成成立立，往往证证当当n=k+1n=k+1时时结结论论也也成成立立：令令A Ak+1k+1，则有：，则有：A AX X1 1X X2 2X Xm m *1 1X X2 2X Xm m *1 12 2X Xm m *1 12 2m m 2/17/2023176.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树2/17/2023186.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树例例6-16-

12、1设设Gbra：SS(S)|，()()和和(S)(S)的派生树。的派生树。2/17/2023196.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树关于标记关于标记的结点的结点2/17/2023206.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树最左派生最左派生(leftmost derivation)(leftmost derivation)的派生过程中，每一步都是对当前句型的最的派生过程中，每一步都是对当前句型的最左变量进行替换。左变量进行替换。左句型左句型(left sentencial form)(left sentencial form)最左派生得

13、到的句型可叫做左句型。最左派生得到的句型可叫做左句型。最右归约最右归约(rightmost reduction)(rightmost reduction)与最左派生对相的归约叫做最有归约。与最左派生对相的归约叫做最有归约。2/17/2023216.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树最右派生最右派生(rightmost derivation)(rightmost derivation)的派生过程中，每一步都是对当前句型的最的派生过程中，每一步都是对当前句型的最右变量进行替换。右变量进行替换。右句型右句型(right sentencial form)(right se

14、ntencial form)最右派生得到的句型可叫做右句型。最右派生得到的句型可叫做右句型。最左归约最左归约(leftmost reductionleftmost reduction)与最左派生对相的归约叫做最右归约。与最左派生对相的归约叫做最右归约。2/17/2023226.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树规范派生规范派生(normal derivation)(normal derivation)最右派生。最右派生。规范句型规范句型(normal sentencial form)(normal sentencial form)规范派生产生的句型。规范派生产生的

15、句型。规范归约规范归约(normal reduction)(normal reduction)最左归约。最左归约。2/17/2023236.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树定理定理6-26-2如果如果是是CFGG的一个句型，则的一个句型，则G中中存在存在的最左派生和最右派生。的最左派生和最右派生。证明：证明：基本思路：基本思路：对派生的步数对派生的步数n施归纳，证明对于施归纳，证明对于任意任意AV，如果，如果An，在，在G中，存在对中，存在对应的从应的从A到到的最左派生：的最左派生：An左左。2/17/2023246.1.1 6.1.1 上下文无关文法的派生树上

16、下文无关文法的派生树AX1X2Xm*1X2Xm*12Xm*12mA左左X1X2Xm*左左1X2Xm*左左12Xm*左左12m同理可证，句型同理可证，句型有最右派生。有最右派生。2/17/2023256.1.1 6.1.1 上下文无关文法的派生树上下文无关文法的派生树定理定理6-3 6-3 如果如果是是CFGG的一个句型，的一个句型，的的派生树与最左派生和最右派生是一一对应派生树与最左派生和最右派生是一一对应的，但是，这棵派生树可以对应多个不同的，但是，这棵派生树可以对应多个不同的派生。的派生。2/17/2023266.1.2 6.1.2 二义性二义性 简单算术表达式的二义性文法简单算术表达式的

17、二义性文法Gexp2：EE+E|E-E|E/E|E*EEEE|(E)|N(L)|idE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2/17/2023276.1.2 6.1.2 二义性二义性 EE+Ex+Ex+E/Ex+x/Ex+x/EEEx+x/yEEx+x/y22句子句子x+x/y22在文法中的三个不同的最左派生在文法中的三个不同的最左派生EE/EE+E/Ex+E/Ex+x/Ex+x/EEEx+x/yEEx+x/y22EEEE/EEE+E/EEx+E/EEx+x/EEx+x/yEx+x/y22/17/2023286.1.2 6.1.2 二义性二义性

18、对应对应3 3个不同个不同的语法的语法树树2/17/2023296.1.2 6.1.2 二义性二义性 二义性二义性(ambiguity)(ambiguity)CFG G=(V，T，P，S)，如果存在wL(G)，w至少有两棵不同的派生树，则称G是二二义性的义性的。否则，G为非二义性的。二义性的问题是不可解的不可解的(unsolvable)(unsolvable)问问题。题。2/17/2023306.1.2 6.1.2 二义性二义性 例例6-26-2 用其他方法消除二义性。用其他方法消除二义性。Gifa：SifEthenSelseS|ifEthenSGifm：SU|MUifEthenSUifEth

19、enMelseUMifEthenMelseM|SGifh：STS|CSCifEthenTCSelse 2/17/2023316.1.2 6.1.2 二义性二义性 例例6-3设设Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法产生语言可以用如下文法产生语言Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2 语言语言Lambiguity不存在非二义性的文法。不存在非二义性的文法。2/17/2023326.1.2 6.1.2 二义性二义性 固有二义性的固有二义性的(inherent ambiguity)(i

20、nherent ambiguity)如果语言如果语言L不存在非二义性文法，则称不存在非二义性文法，则称L是是固有二义性的固有二义性的，又称，又称L是是先天二义性的。先天二义性的。文法可以是二义性的。文法可以是二义性的。语言可以是固有二义性的。语言可以是固有二义性的。2/17/2023336.1.3 6.1.3 自顶向下的分析和自底向自顶向下的分析和自底向上的分析上的分析 自顶向下的分析方法自顶向下的分析方法通过考察是否可以从给定文法的开始符号派生通过考察是否可以从给定文法的开始符号派生出一个符号串，可以判定一个符号串是否为该出一个符号串，可以判定一个符号串是否为该文法的句子。文法的句子。例例S

21、aAb|bBaAaAb|bBaBd2/17/202334aabdabb的派生树的自顶向下的的派生树的自顶向下的“生长生长”过程过程 2/17/2023356.1.3 6.1.3 自顶向下的分析和自底向自顶向下的分析和自底向上的分析上的分析 自底向上自底向上的分析方法的分析方法通过考察是否可以将一个符号串归约为通过考察是否可以将一个符号串归约为给定文法的开始符号，完成判定一个符给定文法的开始符号，完成判定一个符号串是否为该文法的句子的任务。号串是否为该文法的句子的任务。和归约与派生是互逆过程相对应，自顶向和归约与派生是互逆过程相对应，自顶向下的分析与自底向上的分析互逆的分析过下的分析与自底向上的

22、分析互逆的分析过程。程。2/17/202336aabdabb的派生树的自底向上的的派生树的自底向上的“生长生长”过程过程 2/17/2023376.2 6.2 上下文无关文法的化简上下文无关文法的化简 如下文法如下文法含有无含有无用的用的“东西东西”G1：S0|0A|EA|0A|1A|BB_CC0|1|0C|1CD1|1D|2DE0E2|E02 去掉去掉无用无用“东西东西”后的后的文法文法G2：S0|0AA|0A|1A|BB_CC0|1|0C|1C2/17/2023386.2 6.2 上下文无关文法的化简上下文无关文法的化简去掉产生式去掉产生式A后后的的文法文法G3：S0|0AA0|1|0A|

23、1A|BB_CC0|1|0C|1C去掉产生式去掉产生式AB后的后的文法文法G4：S0|0AA0|1|0A|1A|_CC0|1|0C|1C可以去掉文法中的无用符号、可以去掉文法中的无用符号、产生式和产生式和单一产生式。单一产生式。2/17/2023396.2.1 6.2.1 去无用符号去无用符号 无用符号无用符号(useless symbol)(useless symbol)对于任意对于任意XVT，如果存在，如果存在wL(G)，X出现在出现在w的派生过程中，即存在的派生过程中，即存在，(VT)*，使得，使得S*X*w，则称，则称X是有用的，否则，称是有用的，否则，称X是是无用符号。无用符号。对对

24、CFG G=(VCFG G=(V，T T，P P，S)S)G G中的符号中的符号X既可能是有用的，也可能既可能是有用的，也可能是无用的。当是无用的。当X是无用的时候，它既可能是无用的时候，它既可能是终极符号，也可能是语法变量。是终极符号，也可能是语法变量。2/17/2023406.2.1 6.2.1 去无用符号去无用符号 对于任意对于任意XVT，如果，如果X是有用的，是有用的，它必须同时满足如下两个条件：它必须同时满足如下两个条件：存在存在wT*，使得，使得X*w；，(VT)*，使得，使得S*X。注意到文法是语言的有穷描述，所以，注意到文法是语言的有穷描述，所以，集合集合V，T，P都是有穷的。

25、从而我们有都是有穷的。从而我们有可能构造出有效的算法，来完成消除文可能构造出有效的算法，来完成消除文法的无用符号的工作。法的无用符号的工作。2/17/2023416.2.1 6.2.1 去无用符号去无用符号 算法算法 6-1 6-1 删除派生不出终极符号行的变量。删除派生不出终极符号行的变量。输入：输入：CFGG=(V，T，P，S)。输出：输出：CFGG=(V，T，P，S)，V中不含中不含派生不出终极符号行的变量，并且派生不出终极符号行的变量，并且L(G)=L(G)。主要步骤：主要步骤：2/17/2023426.2.1 6.2.1 去无用符号去无用符号(1)OLDV=;(2)NEWV=A|Aw

26、P且且wT*；(3)whileOLDVNEWVdobegin(4)OLDV=NEWV；(5)NEWV=OLDVA|AP且且(TOLDV)*end(6)V=NEWV；(7)P=A|AP且且 AV且且(TV)*2/17/2023436.2.1 6.2.1 去无用符号去无用符号 第第(3)条语句控制对条语句控制对NEWV进行迭代更新。进行迭代更新。第一次循环将那些恰经过两步可以派生出终第一次循环将那些恰经过两步可以派生出终极符号行的变量放入极符号行的变量放入NEWV；第二次循环将；第二次循环将那些恰经过三步和某些至少经过三步可以派那些恰经过三步和某些至少经过三步可以派生出终极符号行的变量放入生出终极

27、符号行的变量放入NEWV；，第第n次循环将那些恰经过次循环将那些恰经过n步和某些至少经过步和某些至少经过n+1步可以派生出终极符号行的变量放入步可以派生出终极符号行的变量放入NEWV。这个循环一直进行下去，直到所给。这个循环一直进行下去，直到所给文法文法G中的所有可以派生出终极符号行的变中的所有可以派生出终极符号行的变量都被放入量都被放入NEWV中。中。2/17/2023446.2.16.2.1去无用符号去无用符号 定理定理 6-4 6-4算法算法6-1是正确的。是正确的。证证明明要要点点：首首先先证证明明对对于于任任意意AV，A被被放放入入V中中的的充充要要条条件件是是存存在在wT，Anw。

28、再证所构造出的文法是等价的。再证所构造出的文法是等价的。(1)对对A被被放放入入NEWV的的循循环环次次数数n施施归归纳纳，证明必存在证明必存在wT，满足，满足Aw。2/17/2023456.2.16.2.1去无用符号去无用符号(2)施施归归纳纳于于派派生生步步数数n，证证明明如如果果Anw，则则A被被算算法法放放入入到到NEWV中中。实实际际上上，对对原原教教材材所所给给的的证证明明进进行行分分析析，同同时时考考虑虑算算法法6-1的的实实际际运运行行，可可以以证证明明，A是是在在第第n次次循循环环前被放入到前被放入到NEWV中的。中的。(3)证证明明L(G)=L(G)。显显然然有有L(G)L

29、(G)，所以只需证明所以只需证明L(G)。2/17/2023466.2.1 6.2.1 去无用符号去无用符号 算法算法6-2删除不出现在任何句型中的语法符号。删除不出现在任何句型中的语法符号。输入：输入：CFGG=(V，T，P，S)。输出：输出：CFGG=(V，T，P，S)，VT中的中的符号必在符号必在G的某个句型中出现，并且有的某个句型中出现，并且有L(G)=L(G)。主要步骤：主要步骤：2/17/2023476.2.1 6.2.1 去无用符号去无用符号 主要步骤：主要步骤：(1)OLDV=;(2)OLDT=;(3)NEWV=SA|SAP;(4)NEWT=a|SaP;2/17/2023486

30、.2.16.2.1去无用符号去无用符号(5)whileOLDVNEWV或或者者OLDTNEWTdobegin(6)OLDV=NEWV;(7)OLDT=NEWT;(8)NEWV=OLDVB|AOLDV且且ABP且且BV;(9)NEWT=OLDTa|AOLDV且且AaP且且aT;end2/17/2023496.2.16.2.1去无用符号去无用符号(10)V=NEWV;(11)T=NEWT;(12)P=A|AP且且AV且且(TV)*。2/17/2023506.2.16.2.1去无用符号去无用符号定理定理6-5算法算法6-2是正确的。是正确的。证明要点：证明要点：(1)施施归归纳纳于于派派生生步步数数

31、n，证证明明如如果果SnX，则则当当XV时时，X在在算算法法中中被被语语句句(3)或或者者语语句句(8)放放入入NEWV；当当XT时时，它它在在算算法法中中被被语语句句(4)或者语句或者语句(9)放入放入NEWT。(2)对对循循环环次次数数n施施归归纳纳，证证明明如如果果X被被放放入入NEWT或或 者者 NEWV中中，则则 必必 定定 存存 在在，(NEWVNEWT)*，使得，使得SnX。(3)证明证明L(G)=L(G)。2/17/2023516.2.16.2.1去无用符号去无用符号定理定理6-6对于任意对于任意CFLL，L，则存在不含，则存在不含无用符号的无用符号的CFGG，使得，使得L(G

32、)=L。证明要点：证明要点：依次用算法依次用算法6-1和算法和算法6-2对文法进行处理，对文法进行处理，可以得到等价的不含无用符号的文法。可以得到等价的不含无用符号的文法。不可先用算法不可先用算法6-26-2后用算法后用算法6-16-1。2/17/2023526.2.16.2.1去无用符号去无用符号例例6-2-1设有如下文法设有如下文法SAB|a|BB，Aa，Cb|ABa先用算法先用算法6-2，文法被化简成：，文法被化简成：SAB|a|BB，Aa再用算法再用算法6-1，可得到文法：，可得到文法：Sa，Aa显然，该文法中的变量显然，该文法中的变量A是新的无用变量。是新的无用变量。2/17/202

33、3536.2.2 6.2.2 去去-产生式产生式 -产生式（产生式（-production-production）形如形如A的产生式叫做的产生式叫做-产生式。产生式。-产生式产生式又称为又称为空产生式（空产生式（null productionnull production。可空可空(nullable)(nullable)变量变量对于文法对于文法G=(V，T，P，S)中的任意变量中的任意变量A，如，如果果A+，则称，则称A为为可空变量。可空变量。2/17/2023546.2.2 6.2.2 去去-产生式产生式 对对形形如如AX1X2Xm的的产产生生式式进进行行考考察察，找找出出文文法法的的可可空

34、空变变量量集集U，然然后后对对于于 H U，从从产产生生式式AX1X2Xm中中删删除除H中中的的变变量量。对对于于不不同同的的H，得得到到不不同同的的A产产生生式式，用用这这组组A产生式替代产生式产生式替代产生式AX1X2Xm。必必须须避避免免在在这这个个过过程程中中产产生生新新的的-产产生生式式：当当X1，X2，Xm U时时，不不可可将将X1，X2，Xm同同时时从从产产生生式式AX1X2Xm中中删除。删除。2/17/2023556.2.2 6.2.2 去去-产生式产生式 算法算法6-3求求CFGG的可空变量集的可空变量集U。输入：输入：CFGG=(V，T，P，S)。输出：输出：G的可空变量集

35、的可空变量集U。主要步骤：主要步骤：(1)OLDU=;(2)NEWU=A|AP;2/17/2023566.2.2 6.2.2 去去-产生式产生式 (3)whileNEWUOLDUdobegin(4)OLDU=NEWU;(5)NEWU=OLDU A|AP并且并且OLDU*end(6)U=NEWU2/17/2023576.2.2 6.2.2 去去-产生式产生式 定理定理6-7对于任意对于任意CFGG，存在不含，存在不含-产产生式的生式的CFGG使得使得L(G)=L(G)-。证明：证明：(1)构造构造设设CFGG=(V，T，P，S)，用用算法算法6-3求出求出G的可空变量集的可空变量集U，构造构造P

36、。2/17/2023586.2.2 6.2.2 去去-产生式产生式 对于对于 AX1X2XmP将将A12m放入放入P，其中，其中ifXiUtheni=Xi或者或者i=；ifXi Utheni=Xi要求：在同一产生式中，要求：在同一产生式中，1，2，m不不能同时为能同时为。2/17/2023596.2.2 6.2.2 去去-产生式产生式 证明对于任意证明对于任意wT+，AnGw的充分必要的充分必要条件是条件是A。必要性：设必要性：设AnGw，施归纳于，施归纳于n，证明，证明AmGw成立。成立。当当n=1时，由时，由AGw知，知，AwP，按照定，按照定理所给的构造理所给的构造G的方法，必定有的方法

37、，必定有AwP。所以，所以，AGw成立。成立。2/17/2023606.2.2 6.2.2 去去-产生式产生式 设设nk时结论成立时结论成立(k1)，当，当n=k+1时时AX1X2Xm*Gw1X2Xm*Gw1w2Xm*Gw1w2wm其中其中w1w2wm=w，且，且w1，w2，wmT*。2/17/2023616.2.2 6.2.2 去去-产生式产生式 注注意意到到w，必必存存在在1im，wi，设设i，j，k是是w1，w2，wm中中所所有有非非空空串串的的下下标，并且标，并且1ijkm，即：，即：w=wiwjwk按照按照G的构造方法，的构造方法，AXiXjXkP 再由归纳假设，再由归纳假设，Xi*

38、Gwi，Xj*Gwj，Xk*Gwk。2/17/2023626.2.2 6.2.2 去去-产生式产生式 A*GXiXjXk*GwiXjXk*GwiwjXk*Gwiwjwk所所以以，结结论论对对n=k+1成成立立。由由归归纳纳法法原原理理，结结论对所有的论对所有的n成立。成立。2/17/2023636.2.2 6.2.2 去去-产生式产生式充充分分性性：设设AmGw，施施归归纳纳于于m，证证明明AnGw成立。成立。当当m=1时时，由由AGw知知，AwP，按按照照定定理理所所给给的的构构造造G的的方方法法，必必定定有有AP。Aw是是通通过过删删除除产产生生式式A右右部部中中的的可可空空变量而构造出来

39、的，所以，变量而构造出来的，所以，AG*Gw成立。成立。2/17/2023646.2.2 6.2.2 去去-产生式产生式设设nk时结论成立时结论成立(k1)，当，当m=k+1时时A*GXiXjXk*GwiXjXk*GwiwjXk*Gwiwjwk=w其中其中Xi*Gwi，Xj*Gwj，Xk*Gwk 。2/17/2023656.2.2 6.2.2 去去-产生式产生式表表明明AXiXjXkP。按按照照G的的构构造造方方法法，必定存在必定存在AX1X2XmP，而且，而且Xi，Xj，Xk X1，X2，XmX1，X2，Xm-Xi，Xj，Xk U从而，从而，AGX1X2Xm*GXiXjXk2/17/2023

40、666.2.2 6.2.2 去去-产生式产生式再根据再根据Xi*Gwi，Xj*Gwj，Xk*Gwk和归纳和归纳假设，有假设，有Xi*Gwi，Xj*Gwj，Xk*Gwk。这表明，如下派生成立：这表明，如下派生成立：AGX1X2Xm*GXiXjXk*GwiXjXk*GwiwjXk*Gwiwjwk=w2/17/2023676.2.2 6.2.2 去去-产生式产生式表明表明结论对结论对m=k+1成立。由归纳法原理，结成立。由归纳法原理，结论对任意论对任意m成立。成立。注意到注意到A的任意性，当的任意性，当S=A时结论成立。即：时结论成立。即：S*Gw的充分必要条件是的充分必要条件是S*Gw亦即：亦即：

41、L(G)=L(G)-。定理得证。定理得证。2/17/2023686.2.3 6.2.3 去单一产生式去单一产生式 文法文法Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E存在派生：存在派生：ETFPid2/17/2023696.2.3 6.2.3 去单一产生式去单一产生式 Gexp3：EE+T|E-T|T*F|T/F|FP|(E)|N(L)|idTT*F|T/F|FP|(E)|N(L)|idFFP|(E)|N(L)|idP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,

42、E|E该文法中不存在类似的派生。该文法中不存在类似的派生。2/17/2023706.2.3 6.2.3 去单一产生式去单一产生式 单一产生式单一产生式(unit production)(unit production)形如形如AB的产生式称为的产生式称为单一产生式。单一产生式。定理定理 6-8 6-8对于任意对于任意CFGG，L(G)，存在，存在等价的等价的CFGG1，G1不含无用符号、不含无用符号、-产生产生式和单一产生式。式和单一产生式。满足本定理的满足本定理的CFG为为化简过的文法。化简过的文法。已有去无用符号和去已有去无用符号和去-产生式的结论，所以产生式的结论，所以只讨论去单一产生式

43、的问题。只讨论去单一产生式的问题。2/17/2023716.2.3 6.2.3 去单一产生式去单一产生式 证明要点：证明要点：（1）构造）构造G2，满足，满足L(G2)=L(G)，并且，并且G2中中不含单一产生式。不含单一产生式。用非单一产生式用非单一产生式A1取代取代A1*GAn用到用到的产生式系列的产生式系列A1A2，A2A3，An-1An，An。其中，。其中，A1A2，A2A3，An-1An都是单一产生式。（都是单一产生式。（n1）2/17/2023726.2.3 6.2.3 去单一产生式去单一产生式 （2 2）证明证明L(G2)=L(G)。用用A1所所完完成成的的派派生生A1与与产产生

44、生式式系系列列A1A2，A2A3，An-1An，An所所完成的派生完成的派生A1*GAn相对应。相对应。在在原原文文法法中中可可能能会会出出现现一一个个变变量量在在派派生生过过程程中中循循环环出出现现的的情情况况，在在wL(G)证证明明wL(G2)的的过过程程中中，要要取取w在在G中中的的一一个个最最短短的的最最左左派派生。生。S=0G1G2GGn=w2/17/2023736.2.3 6.2.3 去单一产生式去单一产生式 （3 3）删除删除G2中的无用符号。中的无用符号。由于在删除单一产生式后，文法中可能出由于在删除单一产生式后，文法中可能出现新的无用符号，因此，我们还需要再次现新的无用符号，

45、因此，我们还需要再次删除新出现的无用符号。删除新出现的无用符号。此外，在去此外，在去-产生式后可能会产生新的单一产生式后可能会产生新的单一产生式，也可能会引进新的无用符号。这产生式，也可能会引进新的无用符号。这是值得注意的。是值得注意的。2/17/2023746.3 6.3 乔姆斯基范式乔姆斯基范式 乔姆斯基范式文法乔姆斯基范式文法(Chomskynormalform，CNFCNF)简称为简称为ChomskyChomsky文法文法，或，或ChomskyChomsky范式。范式。CFGG=(V，T，P，S)中的产生式形式：中的产生式形式：ABC，Aa其中，其中，A、B、CV，aT。CNFCNF中

46、，不允许有中，不允许有-产生式、单一产生式。产生式、单一产生式。2/17/2023756.3 6.3 乔姆斯基范式乔姆斯基范式例例6-3-1试将文法试将文法Gexp4转换成等价的转换成等价的GNF。Gexp4：EE+T|T*F|FP|(E)|idTT*F|FP|(E)|idFFP|(E)|idP(E)|id 可以分两步走可以分两步走变成变成A A a和和AA1A2An的形式。的形式。变成变成CNFCNF。2/17/202376第一步第一步EEA+T|TA*F|FAP|A(EA5|idTTA*F|FAP|A(EA)|idFFAP|A(EA)|idPA(EA)|idA+A*AA(A)2/17/20

47、2377第二步第二步GexpCNF：EEA1|TA2EFA3|A(A4|idTTA2|FA3|A(A4|idFFA3|A(A4|idPA(A4|idA+A*AA(A)A1A+TA2A*FA3APA4EA)2/17/2023786.3 6.3 乔姆斯基范式乔姆斯基范式定理定理6-96-9 对于任意对于任意CFGG，L(G)，存在等，存在等价的价的CNFG2。证明要点：证明要点：1.1.构造构造CNFCNF按照上述例子所描述的转换方法，在构造给定按照上述例子所描述的转换方法，在构造给定CFGCFG的的CNFCNF时，可以分两步走。时，可以分两步走。假设假设G G为化简过的文法为化简过的文法构造构造

48、G1=(V1，T，P1，S)G1中的产生式都是形如中的产生式都是形如AB1B2Bm和和Aa的产生式，其中，的产生式，其中，A，B1，B2，BmV1，aT，m2 2/17/2023796.3 6.3 乔姆斯基范式乔姆斯基范式构造构造CNFG2=(V2，T，P2，S)。m3时，引入新变量：时，引入新变量：B1、B2、Bm-2，将将G1的形如的形如AA1A2Am的产生式替换成的产生式替换成AA1B1B1A2B2Bm-2Am-1Am2/17/2023806.3 6.3 乔姆斯基范式乔姆斯基范式2.2.构造的正确性证明。构造的正确性证明。按照上述构造，证明被替换的产生式是等按照上述构造，证明被替换的产生

49、式是等价的。价的。例如：在第二步中例如：在第二步中AA1B1，B1A2B2，Bm-2Am-1Am与与AA1A2Am等价。等价。2/17/2023816.3 6.3 乔姆斯基范式乔姆斯基范式例例 6-6 6-6 试将下列文法转换成等价的试将下列文法转换成等价的CNF。SbA|aBAbAA|aS|aBaBB|bS|b 2/17/2023826.3 6.3 乔姆斯基范式乔姆斯基范式先先引引入入变变量量Ba，Bb和和产产生生式式Baa，Bbb ，完成第一步变换。，完成第一步变换。SBbA|BaBABbAA|BaS|aBBaBB|BbS|bBaaBbb2/17/2023836.3 6.3 乔姆斯基范式乔

50、姆斯基范式引入新变量引入新变量B1、B2 SBbA|BaBABbB1|BaS|aBBaB2|BbS|bBaaBbbB1AAB2BB2/17/2023846.3 6.3 乔姆斯基范式乔姆斯基范式不能因为原来有产生式不能因为原来有产生式Aa和和Bb而放弃而放弃引进变量引进变量Ba、Bb和产生式和产生式Baa、Bbb。L(A)=x|xa，b+&x中中a的个数比的个数比b的个的个数恰多数恰多1个个。L(B)=x|xa，b+&x中中b的个数比的个数比a的个的个数恰多数恰多1个个。L(Ba)=a。L(Bb)=b。2/17/2023856.4 6.4 格雷巴赫范式格雷巴赫范式格雷巴赫范式文法格雷巴赫范式文法