自动机与形式语言_第六章

1、2021-12-121第第6章章 上下文无关语言上下文无关语言 Gbra：SS(S)| L(Gbra)不是不是RL,是是CFLhhnnnnnn10.10102211高级程序设计语言的绝大多数语法结构都高级程序设计语言的绝大多数语法结构都可以用上下文无关文法可以用上下文无关文法(CFG)(CFG)描述。描述。BNF(BNF(巴科斯范式：巴科斯范式：Backus normal formBackus normal form，又叫又叫Backus-naur form)Backus-naur form)。2021-12-122第第6章章 上下文无关语言上下文无关语言 主要内容主要内容关于关于CFL的分析

2、的分析 派生和归约、派生树派生和归约、派生树 CFG的化简的化简 无用符、单一产生式、空产生式无用符、单一产生式、空产生式 CFG的范式的范式 CNF GNF CFG的自嵌套特性的自嵌套特性 2021-12-123第第6章章 上下文无关语言上下文无关语言 重点重点 CFG的化简。的化简。 CFG到到GNF的转换。的转换。 难点难点 CFG到到GNF的转换，特别是其中的用右递归替的转换，特别是其中的用右递归替换左递归的问题。换左递归的问题。2021-12-1246.1 上下文无关语言上下文无关语言 文法文法G=(V，T，P，S)被称为是上下文无关被称为是上下文无关的。的。 如果除了形如如果除了形

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

4、文法的派生树 算术表达式算术表达式x+x/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/y2 E+F/y2 E+P/y2 E+x/y2 T+x/y2 F+x/y2 P+x/y2x+x/y2 E EE+TT+TT+T/FF+T/FF+T/FPP+T/FPx+T/FPx+F/FPx+F/F2x+F/P2x+P/P2x+P/y2x+x/y2 2021-12-1276.1.1 上下文无关文法的派生树上下文无关文法的派生树 文法文法

5、Gexp1句子句子x+x/y22的结构。的结构。 86.1.1 上下文无关文法的派生树上下文无关文法的派生树S - SS | (S) | () ()()SSSS)()()96.1.1 上下文无关文法的派生树上下文无关文法的派生树 派生树派生树(derivation tree) 一棵一棵(有序有序)树树(ordered tree) 树的每个顶点有一个标记树的每个顶点有一个标记X， 且且XVT 树根的标记为树根的标记为S； 如果非叶子顶点如果非叶子顶点v标记为标记为A，v的儿子从左到右的儿子从左到右依次为依次为v1，v2，vn，并且它们分别标记为，并且它们分别标记为X1，X2，Xn，则，则AX1X

6、2XnP；如果如果X是一个非叶子顶点的标记，则是一个非叶子顶点的标记，则XV；如果顶点如果顶点v标记为标记为，则，则v是该树的叶子，并且是该树的叶子，并且v是其父顶点的惟一儿子。是其父顶点的惟一儿子。 SSSS)()()2021-12-12106.1.1 上下文无关文法的派生树上下文无关文法的派生树 别称别称 生成树生成树 分析树分析树(parse tree) 语法树语法树(syntax tree) 顺序顺序 v1，v2是派生树是派生树T的两个不同顶点，如果存在顶的两个不同顶点，如果存在顶点点v，v至少有两个儿子，使得至少有两个儿子，使得v1是是v的较左儿子的较左儿子的后代，的后代，v2是是v

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

8、()2021-12-12126.1.1 上下文无关文法的派生树上下文无关文法的派生树 派生子树派生子树(subtree) 满足派生树定义中除了对根结满足派生树定义中除了对根结点的标记的点的标记的要求以外各条的树叫要求以外各条的树叫派生子树派生子树(subtree)。 如果这个子树的根标记为如果这个子树的根标记为A，则称之为，则称之为A子子树。树。 惟一差别是根结点可以标记非开始符号。惟一差别是根结点可以标记非开始符号。SSSS)()()2021-12-12136.1.1 上下文无关文法的派生树上下文无关文法的派生树定理定理6-1 设设CFG G=(V，T，P，S)，S*的的充分必要条件为充分必

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

10、记为X1，X2，Xm 。 AX1X2XmP 。 以以X1，X2，Xm为根的子树的结果依次为根的子树的结果依次为为1，2，m 。 X1，X2，Xm为根的子树的非叶子顶点为根的子树的非叶子顶点的个数均不大于的个数均不大于k。 2021-12-12156.1.1 上下文无关文法的派生树上下文无关文法的派生树 X1*1X X2 2*2X Xm m*m而且而且=1 12 2m m2021-12-12166.1.1 上下文无关文法的派生树上下文无关文法的派生树AX1X2Xm *1X2Xm *12Xm *12m2021-12-12176.1.1 上下文无关文法的派生树上下文无关文法的派生树2021-12-1

11、2186.1.1 上下文无关文法的派生树上下文无关文法的派生树 必要性必要性设设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 2021-12-12196.1.1 上下文无关文法的派生树上下文无关文法的派生树2021-12-12206.1.1

12、 上下文无关文法的派生树上下文无关文法的派生树 例例6-1设设Gbra：SS(S)|，()()和和(S)(S)的派生树。的派生树。2021-12-12216.1.1 上下文无关文法的派生树上下文无关文法的派生树 关于标记关于标记的结点的结点x+x/y222021-12-12226.1.1 上下文无关文法的派生树上下文无关文法的派生树 最左派生最左派生(leftmost derivation) 的派生过程中，每一步都是对当前句型的最的派生过程中，每一步都是对当前句型的最左变量进行替换。左变量进行替换。 左句型左句型(left sentencial form)最左派生得到的句型可叫做左句型。最左派

13、生得到的句型可叫做左句型。 最右归约最右归约(rightmost reduction)(rightmost reduction)与最左派生对相的归约叫做最有归约。与最左派生对相的归约叫做最有归约。Grammmar:S - SS | (S) | () S =lm SS =lm (S)S =lm ()S =lm ()()2021-12-12236.1.1 上下文无关文法的派生树上下文无关文法的派生树 最右派生最右派生(rightmost derivation) 的派生过程中，每一步都是对当前句型的最的派生过程中，每一步都是对当前句型的最右变量进行替换。右变量进行替换。 右句型右句型(right s

14、entencial form)最右派生得到的句型可叫做右句型。最右派生得到的句型可叫做右句型。 最左归约最左归约( (leftmost reduction) )与最左派生对相的归约叫做最右归约。与最左派生对相的归约叫做最右归约。Grammmar:S - SS | (S) | () S =rm SS =rm S() =rm (S)() =rm ()()2021-12-12246.1.1 上下文无关文法的派生树上下文无关文法的派生树 规范派生规范派生(normal derivation)最右派生。最右派生。 规范句型规范句型(normal sentencial form)规范派生产生的句型。规范派

15、生产生的句型。 规范归约规范归约(normal reduction)最左归约。最左归约。2021-12-12256.1.1 上下文无关文法的派生树上下文无关文法的派生树定理定理6-2 如果如果是是CFG G的一个句型，则的一个句型，则G中中存在存在的最左派生和最右派生。的最左派生和最右派生。证明：证明：基本思路：基本思路：对派生的步数对派生的步数n施归纳，证明对于施归纳，证明对于任意任意AV，如果，如果An，在，在G中，存在对中，存在对应的从应的从A到到的最左派生：的最左派生：An左左。 2021-12-12266.1.1 上下文无关文法的派生树上下文无关文法的派生树AX1X2Xm *1X2X

16、m *12Xm *12mA左左X1X2Xm *左左1X2Xm *左左12Xm *左左12m 同理可证，句型同理可证，句型有最右派生。有最右派生。 2021-12-12276.1.1 上下文无关文法的派生树上下文无关文法的派生树定理定理6-3 如果如果是是CFG G的一个句型，的一个句型，的的派生树与最左派生和最右派生是一一对应派生树与最左派生和最右派生是一一对应的，但是，这棵派生树可以对应多个不同的，但是，这棵派生树可以对应多个不同的派生。的派生。2021-12-12286.1.2 二义性二义性 简单算术表达式的二义性文法简单算术表达式的二义性文法Gexp2：EE+E|E-E|E/E|E*EE

17、 EE|(E)|N(L)|idE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2021-12-12296.1.2 二义性二义性 E E+E x+E x+E/E x+x/E x+x/EEEx+x/yEEx+x/y22句子句子x+x/y22在文法中的三个不同的最左派生在文法中的三个不同的最左派生 E E/E E+E/E x+E/E x+x/E x+x/EEE x+x/yEE x+x/y22 E EE E/EE E+E/EE x+E/EE x+x/EE x+x/yE x+x/y2 2021-12-12306.1.2 二义性二义性 x+x/y22对应对应3个不个

18、不同的语法同的语法树树2021-12-12316.1.2 二义性二义性 二义性二义性(ambiguity) CFG G=(V，T，P，S)，如果存在wL(G)，w至少有两棵不同的派生树，则称G是二义二义性的性的。否则，G为非二义性的。 二义性的问题是不可解的不可解的(unsolvable)(unsolvable)问问题。题。 2021-12-12326.1.2 二义性二义性 例例6-2 用其他方法消除二义性。用其他方法消除二义性。Gifa：Sif E then S else S | if E then SGifm：SU|MUif E then SUif E then M else UMif E

19、 then M else M|SGifh：STS|CSCif E thenT CS else 2021-12-12336.1.2 二义性二义性 例例 6-3 设设Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法产生语言可以用如下文法产生语言Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2 语言语言Lambiguity不存在非二义性的文法。不存在非二义性的文法。 2021-12-12346.1.2 二义性二义性 固有二义性的固有二义性的(inherent ambiguity) 如果语言如果语言L不存在

20、非二义性文法，则称不存在非二义性文法，则称L是是固有二义性的固有二义性的，又称，又称L是是先天二义性的。先天二义性的。 文法可以是二义性的。文法可以是二义性的。 语言可以是固有二义性的。语言可以是固有二义性的。 2021-12-12356.1.3 自顶向下的分析和自底向自顶向下的分析和自底向上的分析上的分析 自顶向下的分析方法自顶向下的分析方法 通过考察是否可以从给定文法的开始符号派生通过考察是否可以从给定文法的开始符号派生出一个符号串，可以判定一个符号串是否为该出一个符号串，可以判定一个符号串是否为该文法的句子。文法的句子。 例例 SaAb|bBa AaAb|bBa Bd 2021-12-1

21、236aabdabb的派生树的自顶向下的的派生树的自顶向下的“生长生长”过程过程 2021-12-12376.1.3 自顶向下的分析和自底向自顶向下的分析和自底向上的分析上的分析 自底向上自底向上的分析方法的分析方法 通过考察是否可以将一个符号串归约为通过考察是否可以将一个符号串归约为给定文法的开始符号，完成判定一个符给定文法的开始符号，完成判定一个符号串是否为该文法的句子的任务。号串是否为该文法的句子的任务。 和归约与派生是互逆过程相对应，自顶向和归约与派生是互逆过程相对应，自顶向下的分析与自底向上的分析互逆的分析过下的分析与自底向上的分析互逆的分析过程。程。2021-12-1238aabd

22、abb的派生树的自底向上的的派生树的自底向上的“生长生长”过程过程 2021-12-12396.2 上下文无关文法的化简上下文无关文法的化简 如下文法如下文法含有无含有无用的用的“东西东西”G1：S0|0A|EA|0A|1A|BB_CC0|1|0C|1CD1|1D|2DE0E2|E02 去掉去掉无用无用“东西东西”后的后的文法文法G2：S0|0AA|0A|1A|BB_CC0|1|0C|1C 2021-12-12406.2 上下文无关文法的化简上下文无关文法的化简 去掉产生式去掉产生式A后后的的文法文法G3：S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C 去掉产生式去掉产生式AB后

23、的后的文法文法G4：S0|0AA0|1|0A|1A| _CC0|1|0C|1C 可以去掉文法中的无用符号、可以去掉文法中的无用符号、 产生式和产生式和单一产生式。单一产生式。2021-12-12416.2.1 去无用符号去无用符号 无用符号无用符号(useless symbol) 对于任意对于任意XVT，如果存在，如果存在wL(G)，X出现在出现在w的派生过程中，即存在的派生过程中，即存在，(VT)*，使得，使得S*X*w，则称，则称X是有用的，否则，称是有用的，否则，称X是是无用符号。无用符号。 对对CFG G=(V，T，P，S) G中的符号中的符号X既可能是有用的，也可能既可能是有用的，也

24、可能是无用的。当是无用的。当X是无用的时候，它既可能是无用的时候，它既可能是终极符号，也可能是语法变量。是终极符号，也可能是语法变量。2021-12-12426.2.1 去无用符号去无用符号 对于任意对于任意XVT，如果，如果X是有用的，是有用的，它必须同时满足如下两个条件：它必须同时满足如下两个条件： 存在存在wT*，使得，使得X*w； ，(VT)*，使得，使得S*X。 注意到文法是语言的有穷描述，所以，注意到文法是语言的有穷描述，所以，集合集合V，T，P都是有穷的。从而我们有都是有穷的。从而我们有可能构造出有效的算法，来完成消除文可能构造出有效的算法，来完成消除文法的无用符号的工作。法的无

25、用符号的工作。 2021-12-12436.2.1 去无用符号去无用符号 算法算法 6-1 删除派生不出终极符号行的变量。删除派生不出终极符号行的变量。 输入：输入：CFG G=(V，T，P，S)。 输出：输出：CFG G=(V，T，P，S)，V中不含中不含派生不出终极符号行的变量，并且派生不出终极符号行的变量，并且L(G)=L(G)。 主要步骤：主要步骤： 44Testing Whether a Variable Derives Some Terminal String Basis: 对产生式 A - w, 如果 w 是终结符号行, 那么 A 能派生出终结符号行. Induction: 对产

26、生式 A - , 如果 只包含终结符号或者能派生出终结符号行的变量, 那么 A 能派生出终结符号行. 2021-12-12456.2.1 去无用符号去无用符号 (1) OLDV=;(2) NEWV=A|AwP且且wT*；(3) while OLDVNEWV dobegin(4) OLDV=NEWV；(5) NEWV=OLDVA|AP且且(TOLDV) *end(6) V=NEWV；(7) P= A| AP且且 AV且且(TV)*2021-12-12466.2.1 去无用符号去无用符号 第第(3)条语句控制对条语句控制对NEWV进行迭代更新。进行迭代更新。第一次循环将那些恰经过两步可以派生出终第

27、一次循环将那些恰经过两步可以派生出终极符号行的变量放入极符号行的变量放入NEWV；第二次循环将；第二次循环将那些恰经过三步和某些至少经过三步可以派那些恰经过三步和某些至少经过三步可以派生出终极符号行的变量放入生出终极符号行的变量放入NEWV；，第第n次循环将那些恰经过次循环将那些恰经过n步和某些至少经过步和某些至少经过n+1步可以派生出终极符号行的变量放入步可以派生出终极符号行的变量放入NEWV。这个循环一直进行下去，直到所给。这个循环一直进行下去，直到所给文法文法G中的所有可以派生出终极符号行的变中的所有可以派生出终极符号行的变量都被放入量都被放入NEWV中。中。 2021-12-12476

28、.2.1去无用符号去无用符号 定理定理 6-4 算法算法6-1是正确的。是正确的。 证明要点：首先证明对于任意证明要点：首先证明对于任意AV，A被放被放入入V中的充要条件是存在中的充要条件是存在wT，An w。再证所构造出的文法是等价的。再证所构造出的文法是等价的。(1)对对A被放入被放入NEWV的循环次数的循环次数n施归纳，证施归纳，证明必存在明必存在wT，满足，满足A w。2021-12-12486.2.1去无用符号去无用符号 (2)施归纳于派生步数施归纳于派生步数n，证明如果，证明如果An w，则，则A被算法放入到被算法放入到NEWV中。实际上，对原教中。实际上，对原教材所给的证明进行分

29、析，同时考虑算法材所给的证明进行分析，同时考虑算法6-1的实际运行，可以证明，的实际运行，可以证明，A是在第是在第n次循环次循环前被放入到前被放入到NEWV中的。中的。(3)证明证明L(G)=L(G) 。显然有显然有L(G) L(G)，所以只需证明所以只需证明L(G)。 49Example: Eliminate VariablesS - AB | C, A - aA | a, B - bB, C - cBasis: A and C are identified because of A - a and C - c.Induction: S is identified because of S

30、- C.Nothing else can be identified.Result: S - C, A - aA | a, C - c2021-12-12506.2.1 去无用符号去无用符号 算法算法 6-2 删除不出现在任何句型中的语法符号。删除不出现在任何句型中的语法符号。 输入：输入：CFG G=(V，T，P，S)。 输出：输出：CFG G=(V，T，P，S)，VT中的中的符号必在符号必在G的某个句型中出现，并且有的某个句型中出现，并且有L(G)=L(G)。 主要步骤：主要步骤： 2021-12-12516.2.1 去无用符号去无用符号 主要步骤：主要步骤：(1) OLDV=;(2) O

31、LDT=;(3) NEWV=SA|SAP;(4) NEWT=a|SaP;2021-12-12526.2.1去无用符号去无用符号 (5) while OLDVNEWV 或者或者OLDTNEWT do begin(6) OLDV=NEWV;(7) OLDT=NEWT;(8) NEWV=OLDVB| AOLDV且且 ABP 且且BV;(9) NEWT=OLDTa| AOLDV且且 AaP 且且aT; end2021-12-12536.2.1去无用符号去无用符号 (10) V=NEWV;(11) T=NEWT;(12) P= A| AP且且 AV且且(TV)*。2021-12-12546.2.1去无用

32、符号去无用符号定理定理 6-5 算法算法6-2是正确的。是正确的。证明要点：证明要点：(1) 施归纳于派生步数施归纳于派生步数n，证明如果，证明如果Sn X，则当，则当XV时，时，X在算法中被语句在算法中被语句(3)或者语句或者语句(8)放入放入NEWV；当；当XT时，它在算法中被语句时，它在算法中被语句(4)或者或者语句语句(9)放入放入NEWT。(2) 对循环次数对循环次数n施归纳，证明如果施归纳，证明如果X被放入被放入NEWT或 者或 者 N E W V 中 ， 则 必 定 存 在中 ， 则 必 定 存 在 ，(NEWVNEWT)*，使得，使得Sn X。(3) 证明证明L(G)=L(G)

33、 。2021-12-12556.2.1去无用符号去无用符号定理定理6-6 对于任意对于任意CFL L，L，则存在不含，则存在不含无用符号的无用符号的CFG G，使得，使得L(G)=L。 证明要点：证明要点： 依次用算法依次用算法6-1和算法和算法6-2对文法进行处理，对文法进行处理，可以得到等价的不含无用符号的文法。可以得到等价的不含无用符号的文法。 不可先用算法不可先用算法6-2后用算法后用算法6-1。2021-12-12566.2.1去无用符号去无用符号 例例 6-2-1 设有如下文法设有如下文法 SAB|a|BB，Aa，Cb|ABa 先用算法先用算法6-2，文法被化简成：，文法被化简成：

34、 SAB|a|BB，Aa 再用算法再用算法6-1，可得到文法：，可得到文法： S a，Aa 显然，该文法中的变量显然，该文法中的变量A是新的无用变量是新的无用变量。 若先用若先用6-1，得到，得到Sa, Aa, Cb, 再用再用6-2，则得到正确的则得到正确的S a57Why It Works 算法6-1后, 所有剩下的变量都能推导出终结字符串. 算法6-2后, 所有剩下的变量都能从S出发派生到. 另外, 剩下的变量仍然保证能派生出终结字符串, 因为派生终结字符串所用到的后续符号都能从S出发到达，所以不会被6-2删掉. 反之则不然2021-12-12586.2.2 去去-产生式产生式 -产生式

35、（产生式（-production） 形如形如A的产生式叫做的产生式叫做-产生式。产生式。 -产生式产生式又称为又称为空产生式（空产生式（null production。 可空可空(nullable)变量变量 对于文法对于文法G=(V，T，P，S)中的任意变量中的任意变量A，如，如果果A+，则称，则称A为为可空变量。可空变量。 59Example: Nullable SymbolsS - AB, A - aA | , B - bB | A Basis: A is nullable because of A - . Induction: B is nullable because of B - A

36、. Then, S is nullable because of S - AB. 可空变量集S,A,B2021-12-12606.2.2 去去-产生式产生式 算法算法6-3 求求CFG G的可空变量集的可空变量集U。 输入：输入：CFG G=(V，T，P，S)。 输出：输出：G的可空变量集的可空变量集U。 主要步骤：主要步骤：(1) OLDU=;(2) NEWU=A| AP;2021-12-12616.2.2 去去-产生式产生式 (3) while NEWUOLDU do begin(4) OLDU = NEWU;(5) NEWU= OLDU A|AP并且并且OLDU* end(6) U=NE

37、WU2021-12-12626.2.2 去去-产生式产生式 对形如对形如AX1X2Xm的产生式进行考察，的产生式进行考察，找出文法的可空变量集找出文法的可空变量集U，然后对于，然后对于 H U，从产生式从产生式AX1X2Xm中删除中删除H中的变量。中的变量。对于不同的对于不同的H，得到不同的，得到不同的A产生式，用这产生式，用这组组A产生式替代产生式产生式替代产生式AX1X2Xm。 必须避免在这个过程中产生新的必须避免在这个过程中产生新的-产生式：产生式：当当 X1，X2，Xm U时，不可将时，不可将X1，X2，Xm同时从产生式同时从产生式AX1X2Xm中中删除。删除。 2021-12-126

38、36.2.2 去去-产生式产生式 定理定理 6-7 对于任意对于任意CFG G，存在不含，存在不含-产产生式的生式的CFG G使得使得L(G)=L(G)-。证明：证明： (1) 构造构造 设设CFG G=(V，T，P，S) ， 用用算法算法6-3求出求出G的可空变量集的可空变量集U， 构造构造P。 2021-12-12646.2.2 去去-产生式产生式 对于对于 AX1X2XmP 将将A12m放入放入P，其中，其中 if XiU then i=Xi或者或者i=； if Xi U then i=Xi 要求：在同一产生式中，要求：在同一产生式中，1，2，m不不能同时为能同时为。 2021-12-1

39、2656.2.2 去去-产生式产生式 证明对于任意证明对于任意wT+，AnG w的充分必要的充分必要条件是条件是A。 必要性：设必要性：设AnG w，施归纳于，施归纳于n，证明，证明AmG w成立。成立。 当当n=1时，由时，由AG w知，知，AwP，按照定，按照定理所给的构造理所给的构造G的方法，必定有的方法，必定有AwP。所以，所以，AG w成立。成立。 2021-12-12666.2.2 去去-产生式产生式 设设nk时结论成立时结论成立(k1)，当，当n=k+1时时AX1X2Xm *G w1X2Xm *G w1w2Xm *G w1w2wm其中其中w1w2wm=w，且，且w1，w2，wmT

40、*。 2021-12-12676.2.2 去去-产生式产生式 注意到注意到w，必存在，必存在1im，wi，设，设i，j，k是是w1，w2，wm中所有非空串中所有非空串的下标，并且的下标，并且1ijkm，即：，即： w= wiwjwk按照按照G的构造方法，的构造方法，A XiXjXkP 再由归纳假设，再由归纳假设，Xi*G wi，Xj*G wj，Xk*G wk。2021-12-12686.2.2 去去-产生式产生式 A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk所以，结论对所以，结论对n=k+1成立。由归纳法原理，成立。由归纳法原理，结论对所有的结论对所有的n成

41、立。成立。2021-12-12696.2.2 去去-产生式产生式充分性：设充分性：设AmG w，施归纳于，施归纳于m，证明，证明AnG w成立。成立。当当m=1时，由时，由AG w知，知，AwP，按照定，按照定理所给的构造理所给的构造G的方法，必定有的方法，必定有AP。Aw是通过删除产生式是通过删除产生式A右部中的可空右部中的可空变量而构造出来的，所以，变量而构造出来的，所以，AG *G w 成立。成立。 2021-12-12706.2.2 去去-产生式产生式设设nk时结论成立时结论成立(k1)，当，当m=k+1时时A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjw

42、k=w其中其中Xi*G wi，Xj*G wj，Xk*G wk 。2021-12-12716.2.2 去去-产生式产生式表明表明A XiXjXkP。按照。按照G的构造方法，的构造方法，必定存在必定存在A X1X2XmP，而且，而且Xi，Xj，Xk X1，X2，XmX1，X2，Xm-Xi，Xj，Xk U从而，从而，AG X1X2Xm *G XiXjXk2021-12-12726.2.2 去去-产生式产生式再根据再根据Xi*G wi，Xj*G wj，Xk*G wk和归纳和归纳假设，有假设，有Xi*G wi，Xj*G wj，Xk*G wk。这表明，如下派生成立：这表明，如下派生成立： AG X1X2X

43、m *G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w2021-12-12736.2.2 去去-产生式产生式表明表明结论对结论对m=k+1成立。由归纳法原理，结成立。由归纳法原理，结论对任意论对任意m成立。成立。注意到注意到A 的任意性，当的任意性，当S=A时结论成立。即：时结论成立。即：S*G w 的充分必要条件是的充分必要条件是S*G w亦即：亦即：L(G)=L(G)-。定理得证。定理得证。 74Example: Eliminating -ProductionsS - ABC, A - aA | , B - bB | , C - A, B, C, and S

44、 are all nullable. New grammar:S - ABC | AB | AC | BC | A | B | CA - aA | aB - bB | bNote: C is now useless.Eliminate its productions.2021-12-12756.2.3 去单一产生式去单一产生式 文法文法Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E存在派生：存在派生：ETFPid2021-12-12766.2.3 去单一产生式去单一产生式 Gexp3：EE+T|

45、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,E|E 该文法中不存在类似的派生。该文法中不存在类似的派生。2021-12-12776.2.3 去单一产生式去单一产生式 单一产生式单一产生式(unit production) 形如形如AB的产生式称为的产生式称为单一产生式。单一产生式。 定理定理 6-8对于任意对于任意CFG G， L(G)，存在，存在等价的等价的CFG G1，G1不含无用符号、不含无用符号、-产生产生式和单一产生式

46、。式和单一产生式。 满足本定理的满足本定理的CFG为为化简过的文法。化简过的文法。 已有去无用符号和去已有去无用符号和去-产生式的结论，所以产生式的结论，所以只讨论去单一产生式的问题。只讨论去单一产生式的问题。 2021-12-12786.2.3 去单一产生式去单一产生式 证明要点：证明要点： （1）构造）构造G2，满足，满足L(G2)=L(G)，并且，并且G2中中不含单一产生式。不含单一产生式。用非单一产生式用非单一产生式A1取代取代A1*G An用到用到的产生式系列的产生式系列 A1A2，A2A3，An-1An，An。其中，。其中，A1A2，A2A3，An-1An都是单一产生式。都是单一产

47、生式。（n1） 2021-12-12796.2.3 去单一产生式去单一产生式 （2） 证明证明L(G2)=L(G)。 用用A1所完成的派生所完成的派生A1与产生式系列与产生式系列A1A2，A2A3，An-1An，An所所完成的派生完成的派生A1*G An相对应。相对应。在原文法中可能会出现一个变量在派生过程中在原文法中可能会出现一个变量在派生过程中循环出现的情况，在循环出现的情况，在wL(G) 证明证明w L(G2)的过程中，要取的过程中，要取w在在G中的一个最短的最左派中的一个最短的最左派生。生。S=0G1G2GGn=w2021-12-12806.2.3 去单一产生式去单一产生式 （3）删除

48、删除G2中的无用符号。中的无用符号。由于在删除单一产生式后，文法中可能出由于在删除单一产生式后，文法中可能出现新的无用符号，因此，我们还需要再次现新的无用符号，因此，我们还需要再次删除新出现的无用符号。删除新出现的无用符号。 此外，在去此外，在去-产生式后可能会产生新的单一产生式后可能会产生新的单一产生式，也可能会引进新的无用符号。这产生式，也可能会引进新的无用符号。这是值得注意的。是值得注意的。 81Cleaning Up (2)Proof: Start with a CFG for L.Perform the following steps in order:1. Eliminate -p

49、roductions.2. Eliminate unit productions.3. Eliminate variables that derive no terminal string.4. Eliminate variables not reached from the start symbol.Must be first. Can createunit productions or uselessvariables.2021-12-12826.3 乔姆斯基范式乔姆斯基范式 乔姆斯基范式文法乔姆斯基范式文法(Chomsky normal form ，CNF)简称为简称为Chomsky文法

50、文法，或，或Chomsky范式。范式。CFG G=(V，T，P，S)中的产生式形式：中的产生式形式：ABC，Aa其中，其中，A、B、CV，aT。 CNF中，不允许有中，不允许有-产生式、单一产生式。产生式、单一产生式。 2021-12-12836.3 乔姆斯基范式乔姆斯基范式 例例 6-3-1 试将文法试将文法Gexp4转换成等价的转换成等价的 CNF。Gexp4：EE+T| T*F|FP| (E)| idTT*F| FP| (E) |idFFP| (E) |idP(E) |id 可以分两步走可以分两步走 变成变成A a和和A A1A2An的形式。的形式。 变成变成CNF。2021-12-12

51、84第一步第一步EEA+T| T A*F|F AP| A(EA5| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+A*AA(A) 2021-12-1285第二步第二步GexpCNF：EEA1| TA2E FA3| A(A4| idTTA2| FA3| A(A4 |idFFA3| A(A4|idPA(A4 |idA+A*AA(A)A1A+T A2A*FA3APA4EA) 2021-12-12866.3 乔姆斯基范式乔姆斯基范式定理定理6-9 对于任意对于任意CFG G， L(G)，存在等，存在等价的价的 CNF G2 。 证明要点：证明要点：1

52、. 构造构造CNF按照上述例子所描述的转换方法，在构造给定按照上述例子所描述的转换方法，在构造给定CFG的的CNF时，可以分两步走。时，可以分两步走。 假设假设G为化简过的文法为化简过的文法 构造构造G1=(V1，T，P1，S) G1中的产生式都是形如中的产生式都是形如AB1B2Bm和和Aa的产生式，其中，的产生式，其中，A，B1，B2，BmV1，aT，m2 2021-12-12876.3 乔姆斯基范式乔姆斯基范式 构造构造CNF G2=(V2，T，P2，S)。 m3时，引入新变量：时，引入新变量：B1、B2、Bm-2，将将G1的形如的形如AA1A2Am的产生式替换成的产生式替换成AA1B1B

53、1A2B2Bm-2Am-1Am2021-12-12886.3 乔姆斯基范式乔姆斯基范式2. 构造的正确性证明。构造的正确性证明。 按照上述构造，证明被替换的产生式是等按照上述构造，证明被替换的产生式是等价的。价的。 例如：在第二步中例如：在第二步中A A1B1， B1A2B2 ， ， Bm-2Am-1Am与与AA1A2Am等价。等价。2021-12-12896.3 乔姆斯基范式乔姆斯基范式 例例 6-6 试将下列文法转换成等价的试将下列文法转换成等价的 CNF。 SbA | aB AbAA | aS | a BaBB | bS | b 2021-12-12906.3 乔姆斯基范式乔姆斯基范式

54、先引入变量先引入变量Ba，Bb和产生式和产生式Baa，Bbb ，完成第一步变换。完成第一步变换。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb2021-12-12916.3 乔姆斯基范式乔姆斯基范式 引入新变量引入新变量B1、B2 SBbA | BaBABbB1 | BaS | aBBaB2 | BbS | b Baa Bbb B1AA B2BB2021-12-12926.3 乔姆斯基范式乔姆斯基范式 不能因为原来有产生式不能因为原来有产生式A a和和B b而放而放弃引进变量弃引进变量Ba 、Bb和产生式和产生式Baa 、Bbb。 L(A

55、)=x | xa，b+ & x中中a的个数比的个数比b的个的个数恰多数恰多1个个。 L(B)=x | xa，b+ & x中中b的个数比的个数比a的个的个数恰多数恰多1个个。 L(Ba)= a 。 L(Bb)= b 。 2021-12-12936.4 格雷巴赫范式格雷巴赫范式格雷巴赫范式文法格雷巴赫范式文法(Greibach normal form ,GNF)简称为简称为Greibach文法文法，或，或Greibach范式。范式。Aa 其中，其中，AV，aT，V* 。在在GNF中，有如下两种形式的产生式中，有如下两种形式的产生式AaAaA1A2Am(m1) 2021-12-129

56、46.4 格雷巴赫范式格雷巴赫范式 右线性文法是一种特殊的右线性文法是一种特殊的GNF。 由于由于GNF中不存中不存-产生式，所以对任意的产生式，所以对任意的GNF G， L(G)。 当当 L(G)时，能够找到一个时，能够找到一个GNF G，使得，使得 L(G)=L(G) 。 经过化简的经过化简的CFG，都有一个等价的，都有一个等价的GNF。 2021-12-12956.4 格雷巴赫范式格雷巴赫范式引理引理 6-1 对于任意的对于任意的CFG G=(V，T，P，S)，ABP，且，且G中所有的中所有的B产生式为产生式为 B1 |2 |n 取取G1=( V，T，P1，S)P1=(P-AB)A1，A

57、2，An则，则，L(G1)=L(G)。 2021-12-12966.4 格雷巴赫范式格雷巴赫范式 证明证明 以下两组产生式等价以下两组产生式等价 AB ；B1 |2 |n A1，A2，An 2021-12-12976.4 格雷巴赫范式格雷巴赫范式 递归递归(recursive) 如果如果G中存在形如中存在形如AnA的派生，则称该的派生，则称该派生是关于变量派生是关于变量A递归的，递归的，简称为递归派生。简称为递归派生。 当当n=1时，称该派生关于变量时，称该派生关于变量A直接递归直接递归(directly recursive)，简称为直接递归派简称为直接递归派生。生。 形如形如AA的产生式是变

58、量的产生式是变量A的的直接递归直接递归的的(directly recursive)产生式。产生式。2021-12-12986.4 格雷巴赫范式格雷巴赫范式 当当n2时，称该派生是关于变量时，称该派生是关于变量A的的间接递间接递归归(indirectly recursive)派派生。简称为间接生。简称为间接递归派生。递归派生。 当当=时，称相应的时，称相应的(直接直接/间接间接)递归为递归为(直接直接/间接间接)左递归左递归(left-recursive)； 当当=时，称相应的时，称相应的(直接直接/间接间接)递归为递归为(直接直接/间接间接)右递归右递归(right-recursive)。2021-12-12996.4 格雷巴赫范式格雷巴赫范式 引理引理 6-2 对于任意的对于任意的CFG G=(V，T，P，S)，G中所有中所有A的产生式的产生式 A1 |2 |mA1B |2 B |m BB1 |2 |nB1B |2 B |n B 可以被等价地替换为产生式组可以被等价地替换为产生式组AA1 |A2 |AnA1 |2 |m2021-12-121006.4 格雷巴赫范式格雷巴赫范式 证明要点：证明要点： 用直接右递归取代原来的直接左