上下文无关语言.ppt

1、1,形式语言与自动机,第6章 上下文无关语言,2,文法的乔姆斯基体系,3型文法 或正则文法 Aw | wB,3,引言,上下文无关文法和它所描述的上下文无关语言，在定义程序设计语言、语法分析、简化程序设计语言的翻译等方面有重要意义。 高级程序设计语言的绝大多数语法结构都可以用上下文无关文法 (CFG) 描述。 近年来，上下文无关文法也被用来描述文档格式：XML 中使用的 DTD(文档类型定义)就是用来描述 Web 上的信息交换格式的。,4,主要内容,关于 CFL 的分析 派生和归约、派生树 CFG 的化简 无用符、单一产生式、空产生式 CFG 的范式 CNF、GNF CFG 的自嵌套特性,5,6

2、.1 上下文无关文法,文法 G = ( V, T, P, S ) 被称为是上下文无关的，如果除了形如 A 的产生式之外，对于 P，均有|，并且V 成立。 关键：对于 AV，如果 AP，则无论 A 出现在句型的任何位置，都可以将 A 替换成 ，而不考虑 A 的上下文。 例如： G：S ABA aA | aB bB | b 可以产生形如 anbn 或 anbm 的句子。,6,符号的使用约定,回忆符号的使用约定 A, B, C, 表示语法变量； a, b, c, 表示终极符号； X, Y, Z, 表示该符号是语法变量或者终极符号； x, y, z, 表示由终极符号组成的行； , , 表示由语法变量和

3、终极符号组成的行。,7,算术表达式的文法,算术表达式的文法 Gexp1：EE+T | E-T | T TT*F | T/F | F FFP | P P(E) | N(L) | id Nsin | cos | exp | abs | log | int LL, E | E,语法变量的含义 E表达式(expression) T项(term) F因子(factor) P初等量(primary) N函数名(name of function) L列表(list) id标识符(identifier) 幂运算,8,算术表达式的文法,算术表达式 x + x / y2 的不同派生,E E+T T+T F+T P

4、+T x+T x+T/F x+F/F x+P/F x+x/F x+x/FP x+x/PP x+x/yP x+x/y2,E E+T E+T/F E+T/FP E+T/F2 E+T/P2 E+T/y2 E+F/y2 E+P/y2 E+x/y2 T+x/y2 F+x/y2 P+x/y2 x+x/y2,E E+T T+T T+T/F F+T/F F+T/FP P+T/FP x+T/FP x+F/FP x+F/F2 x+F/P2 x+P/P2 x+P/y2 x+x/y2,9,算术表达式的文法,文法Gexp1句子 x + x / y2 的结构。,10,派生树(derivation tree),设有 CFG

5、 G=(V, T, P, S)，G 的派生树是满足如下条件的(有序)树(ordered tree) ： (1) 树的每个顶点有一个标记 X，且 XVT 。 (2) 树根的标记为 S。 (3) 如果一个非叶子顶点 v 标记为 A，v 的儿子从左到右依次为 v1 , v2 , , vn，并且它们分别标记为 X1 , X2 , , Xn，则AX1X2XnP。 (4) 如果 X 是一个非叶子顶点的标记，则 XV。 (5) 如果顶点 v 标记为 ，则 v 是该树的叶子，并且 v 是其父顶点的惟一儿子。,11,上下文无关文法的派生树,别称 生成树(derivation tree)、分析树(parse tr

6、ee)、语法树(syntax tree) 顺序 v1 , v2 是派生树 T 的两个不同顶点，如果存在顶点 v，v 至少有两个儿子，使得 v1 是 v 的较左儿子的后代，v2 是 v 的较右儿子的后代，则称顶点 v1 在顶点 v2 的左边，顶点 v2 在顶点 v1 的右边。 结果(yield) 派生树 T 的所有叶子顶点从左到右依次标记为 X1 , X2 , , Xn，则称符号串 X1X2Xn 是 T 的结果。 一个文法可以有多棵派生树，它们可以有不同的结果。 称 “G 的结果为 的派生树”为 G 的对应于句型 的派生树，简称句型 的派生树。,12,上下文无关文法的派生树,派生子树(subtr

7、ee) 满足派生树定义中除了对根结点的标记的要求以外各条的树叫派生子树(subtree)。 如果这个子树的根标记为 A，则称之为 A子树。 惟一差别是根结点可以标记非开始符号。,13,定理6-1,定理6-1 设 CFG G=(V, T, P, S)，S* 的充分必要条件为 G 有一棵结果为 的派生树。 先证一个更为一般的结论：对于任意 AV，A* 的充分必要条件为 G 有一棵结果为 的 A 子树。 充分性：设 G 有一棵结果为 的 A子树，非叶子顶点的个数 n 施归纳，证明 A*成立。,14,定理6-1,当 n=0 时，结论显然成立。 当 n=1 时，该 A 子树是一个二级子树。 假设此树的叶

8、子顶点的标记从左到右依次为 X1 , X2 , , Xm ， 由定义6-1的第(3)条，必有 AX1X2XmP。 注意到该子树的结果为，所以， X1 X2Xm= ， 故 A*。,15,定理6-1,设 nk (k1) 时结论成立，往证当 n=k+1 时结论成立。 设 A 子树有 k+1 个非叶子顶点，根顶点 A 的儿子从左到右依次为v1 , v2 , vm，并且它们分别标记为 X1 , X2 , , Xm 。 则必有 AX1X2XmP 。 设分别以 X1 , X2 , , Xm 为根的子树的结果依次为 1, 2 , , m， 其中，当 Xi 为一个叶子的标记时，取 i =Xi。 显然分别以 X1

9、, X2, , Xm 为根的子树的非叶子顶点的个数均不大于 k。,16,定理6-1,由归纳假设 X1*1 X2*2 Xm*m 而且=12m A X1X2Xm *1X2Xm *12Xm *12m 即结论对 n=k+1 成立。 由归纳法原理，结论对任意的 n 成立。,17,定理6-1,必要性。 设 An，现施归纳于派生步数 n，证明存在结果为 的 A子树。 当 n=0 时，结论显然成立。 当 n=1 时，由 A 知 AP。 令 = X1X2Xm，则有下图所示的A子树。所以，结论对 n=1 成立。,18,定理6-1,设 nk (k1) 时结论成立，往证当 n=k+1 时结论也成立。 令Ak+1，则有

10、： AX1X2Xm *1X2Xm *12Xm *12m 其中， 对于任意的 i， 1 i m，Xi*i。 当 Xi=i 时，Xi 是一个 “只有一个顶点的 Xi 子树”，Xi 所标记的顶点既是叶子又是根； 当 Xi*i，所用的步数 ni1 时，必有 ni k，由归纳假设，存在以 i 结果的 Xi 子树。 即对于任意的 i，1 i m，对应于 Xi*i，存在以 i 结果的 Xi 子树。,19,定理6-1,由于 AX1X2Xm，所以 AX1X2XmP 可以得到 A 子树的上半部分。,然后再将所有的 Xi 子树对应地接在 Xi 所标识的顶点上，就可以得到树。,显然该树的结果为 。所以结论对 n=k+

11、1 成立。 由归纳法原理，结论对任意的 n 成立。,20,例6-1 设Gbra : SS(S)|，()()和(S)(S)的派生树如下,可见派生树的结果可以是句子，也可以是句型。,21,如果顶点 v 标记为，则 v 是该树的叶子,文法 Gexp1 的句子 x + x / y2 对应的“派生树”,22,最左派生,最左派生(leftmost derivation) 的派生过程中，每一步都是对当前句型的最左变量进行替换。 左句型(left sentencial form) 最左派生得到的句型可叫做左句型。 最右归约(rightmost reduction) 与最左派生对相的归约叫做最右归约。,最右派生

12、,最右派生(rightmost derivation) 的派生过程中，每一步都是对当前句型的最右变量进行替换。 右句型(right sentencial form) 最右派生得到的句型可叫做右句型。 最左归约(leftmost reduction) 与最右派生对相的归约叫做最左归约。,24,规范派生,规范派生(normal derivation) 最右派生。 规范句型(normal sentencial form) 规范派生产生的句型。 规范归约(normal reduction) 最左归约。,25,最左派生与最右派生,定理6-2 如果 是 CFG G 的一个句型，则 G 中存在 的最左派生和

13、最右派生。 基本思路：对派生的步数 n 施归纳，证明对于任意 AV，如果 An，在 G 中，存在对应的从 A 到的最左派生：An左。 当 n=1 时， A 就是最左派生： A左。 设 n k 时，结论成立。 令 Ak+1，则有 A X1X2Xm *1X2Xm *12Xm *12m 其中， =12m。对于任意的 i， 1 im，Xi*i。,26,最左派生与最右派生,当 Xi=i 时，Xi 是由 A 开始的第一步派生得到的，所以，为了描述的统一起见，不妨认为， Xi0i 成立时，有 Xi*左i成立； 当 Xii 时，注意到 Xi*i，所用的步数 nik，由归纳假设，存在与之对应的 Xi 到i 的最

14、左派生： Xi*左i。从而 A左X1X2Xm *左1X2Xm *左12Xm *左12m 所以，结论对 n=k+1成立。由归纳法原理，结论对任意的 n 成立。 设是 CFG G=(V, T, P, S) 的一个句型。由句型的定义， S*。 由于 S 是 V 中的一个元素，由上述证明， S*左。 同理可证，句型有最右派生。,27,定理6-3,定理6-3 如果是 CFG G 的一个句型，的派生树与最左派生和最右派生是一一对应的，但是，这棵派生树可以对应多个不同的派生。,28,6.1.2 二义性,简单算术表达式的二义性文法 Gexp2：EE+E | E-E | E/E | E*E E EE | (E)

15、 | N(L) | id Nsin | cos | exp | abs | log |int LL,E | E 句子 x+x/y2 在文法中的三个不同的最左派生,29,二义性,E E+E x+E x+E/E x+x/E x+x/EE x+x/yE x+x/y2,E E/E E+E/E x+E/E x+x/E x+x/EE x+x/yE x+x/y2,E EE E/EE E+E/EE x+E/EE x+x/EE x+x/yE x+x/y2,30,二义性,二义性(ambiguity) CFG G = (V, T, P, S)，如果存在 wL(G)，w 至少有两棵不同的派生树，则称 G 是二义性的。

16、否则 G 为非二义性的。 Gexp2 是二义性的，但 Gexp1 是非二义性的，但二者是等价的。即L(Gexp1)=L(Gexp2) 判定任给 CFG G 是否为二义性的问题是一个不可解的(unsolvable)问题。,31,Gexp1是非二义性的,算术表达式的文法 Gexp1：EE+T | E-T | T TT*F | T/F | F FFP | P P(E) | N(L) | id Nsin |cos |exp |abs |log |int LL,E |E,语法变量的含义 E表达式(expression) T项(term) F因子(factor) P初等量(primary) N函数名(na

17、me of function) L列表(list) id标识符(identifier),32,例6-2,下列是描述高级程序设计语言的 if 语句的不同文法，其中，Gifa 是二义性的，Gifm 和 Gifh 是为了消除 Gifa 的二义性而对其进行改造的结果。 Gifa：Sif E then S else S | if E then S Gifm：SU|M Uif E then S Uif E then M else U Mif E then M else M|S Gifh：STS | CS Cif E then T CS else 但是，二者都没有完全消除二义性。,33,例6-3,设 Lam

18、biguity= 0n1n2m3m | n, m1 0n1m2m3n | n, m1 可以用如下文法产生语言 Lambiguity： G：SAB | 0C3 A01 | 0A1 B23 | 2B3 C0C3 | 12 | 1D2 D12 | 1D2 语言 Lambiguity不存在非二义性的文法。,S AB 0A1B 0011B 00112B3 00112233,S 0C3 00C33 001D233 00112233,34,二义性,固有二义性的(inherent ambiguity) 如果语言 L 不存在非二义性文法，则称 L 是固有二义性的，又称 L 是先天二义性的。 文法可以是二义性的。

19、 语言可以是固有二义性的。 一般地，不说文法是固有二义性的，也不说语言是二义性的。 若干语言歧义的例子 (1)下雨天留客天留我不留。 下雨天留客，天留，我不留。 下雨天， 留客天， 留我不？留！ (2)父在母先亡 。 “在”可作 动词 (exists) 或介词 (before,at) 有不同意义。,35,二义性,在机器翻译系统中 P=“capital of China” 如何翻译？ 中国的首都(北京） 或 瓷都（景德镇） 有歧义 用前后文信息 排歧 x China y x 中国 y u China v u 瓷器 v 诡辩术 “断章取义” 的 语言学本质：前后相关语言中，去掉W 的前后文，在 W

20、 的释义集合中，选择有利于自己的意义。,36,6.1.3 自顶向下的分析和自底向上的分析,对于一个给定的文法，如何判断一个符号串是否为该文法的句子？ 可以考察是否可以从该文法的开始符号派生出此符号串。 也可以考察这个符号串是否可以归约成文法的开始符号。,37,自顶向下的分析方法,自顶向下的分析方法 通过考察是否可以从给定文法的开始符号派生出一个符号串，可以判定一个符号串是否为该文法的句子。 例 S aAb | bBaA aAb | bBaB d aabdabb 的派生树的自顶向下的“生长”过程,S,38,自底向上的分析方法,自底向上的分析方法 通过考察是否可以将一个符号串归约为给定文法的开始符

21、号，完成判定一个符号串是否为该文法的句子的任务。 和归约与派生是互逆过程相对应，自顶向下的分析与自底向上的分析互逆的分析过程。,39,aabdabb 的派生树的自底向上的“生长”过程,40,6.2 上下文无关文法的化简,给定文法： G1：S 0 | 0A | E A| 0A | 1A |B B_C C0 | 1 | 0C | 1C D1 | 1D | 2D E0E2 | E02 定义的语言为 L(G1)= 0 x | x0,1* 0 x_y | x0,1*, y0,1+,41,6.2 上下文无关文法的化简,G1：S0 | 0A | E A| 0A | 1A | B B_C C0 | 1 | 0

22、C | 1C D1 | 1D | 2D E0E2 | E02,去掉无用符号后的文法 G2：S0 | 0A A| 0A | 1A | B B_C C0 | 1 | 0C | 1C,去掉产生式 A后的文法 G3：S0 | 0A A0 | 1 | 0A | 1A | B B_C C0 | 1 | 0C | 1C,去掉产生式AB后的文法 G4：S0 | 0A A0 | 1 | 0A | 1A | _C C0 | 1 | 0C | 1C,可以去掉文法中的无用符号、 产生式和单一产生式。,42,去无用符号,无用符号 (useless symbol) 对于任意 XVT，如果存在 wL(G)，X 出现在 w

23、的派生过程中，即存在,(VT)*，使得 S*X*w，则称X 是有用的，否则，称 X 是无用符号。 对 CFG G =(V, T, P, S) (1)G 中的符号X既可能是有用的，也可能是无用的。当X是无用的时候，它既可能是终极符号，也可能是语法变量。 (2)对于任意 XVT，如果 X 是有用的，它必须同时满足如下两个条件： 存在 wT*，使得 X*w； 存在,(VT)*，使得 S*X。 (3) 注意到文法是语言的有穷描述，所以，集合V, T, P 都是有穷的。从而有可能构造出有效的算法，来完成消除文法的无用符号的工作。,43,去无用符号,根据定义判断一个符号是否有用，需从两个方面进行分析： (

24、1) 在给定的一个上下文无关文法 G 中，对每一个非终结符号A，能否由 A 推导出某些终结符串。 (算法6-1) (2)A 是否能出现在由起始符 S 开始的推导句型中。 (算法6-2),44,找出有用非终止符号的步骤,NewV = A|AwP且wT*,A1 A2 Ai,V=NewVB|BP 且(TNewV) *,Bi Bj,Cm,Cn,V,45,算法6-1,算法 6-1 删除派生不出终极符号行的变量。 输入：CFG G=(V, T, P, S)。 输出：CFG G =(V ,T, P, S )，V 中不含派生不出终极符号行的变量，并且 L(G )=L(G)。 主要步骤： (1)OldV =;

25、(2)NewV = A | AwP 且 wT* ； (3)while OldVNewV do begin (4) OldV = NewV； (5) NewV=OldV A | AP 且 (TOldV) * end (6)V =NewV； (7)P = A| AP 且 AV 且 (TV )*,46,算法6-1,第(3)条语句控制对NewV进行迭代更新。 第一次循环将那些恰经过两步可以派生出终极符号行的变量放入NewV； 第二次循环将那些恰经过三步和某些至少经过三步可以派生出终极符号行的变量放入NewV； 第 n 次循环将那些恰经过 n 步和某些至少经过 n+1 步可以派生出终极符号行的变量放入N

26、ewV。 这个循环一直进行下去，直到所给文法 G 中的所有可以派生出终极符号行的变量都被放入 NewV 中。,47,算法6-1是正确的,证明要点： 首先证明对于任意 AV，A 被放入 V 中的充要条件是存在wT，An w。再证所构造出的文法是等价的。 (1)对A被放入 NewV 的循环次数 n 施归纳，证明必存在wT，满足 A w。 (2)施归纳于派生步数 n，证明如果 An w，则 A 被算法放入到 NewV 中。可以证明，A 是在第 n 次循环前被放入到NewV 中的。 (3)证明 L(G )=L(G) 。由于 G 是通过将 G 中的某些变量和相关的产生式删除之后得到的，显然有 L(G )

27、 L(G)。 所以只需证明 L(G ) L(G) 。,48,找出有用符号的步骤,S,V=S A | SAP;,V,iAii,jAjj,mAmm,nAnn,49,去无用符号,算法 6-2 删除不出现在任何句型中的语法符号。 输入：CFG G=(V,T,P,S)。 输出：CFG G =(V ,T ,P,S)，V T 中的符号必在G的某个句型中出现，并且有L(G )=L(G)。,50,算法 6-2,主要步骤： (1)OldV=; (2)OldT=; (3)NewV=SA | SAP; (4)NewT=a | SaP; (5)while OldVNewV 或者 OldTNewT do begin (6

28、) OldV = NewV; (7) OldT = NewT; (8) NewV=OldV B | AOldV 且 ABP 且 B V ; (9) NewT=OldT a | AOldV 且 AaP 且 a T ; end (10)V =NewV; (11)T =NewT; (12)P = A| AP 且 A V 且 (T V )*,51,算法6-2是正确的,定理 6-5 算法6-2是正确的。 证明要点： (1)施归纳于派生步数 n，证明如果 Sn X，则 当 XV时，X在算法中被语句(3)或者语句(8)放入NewV； 当XT时，它在算法中被语句(4)或者语句(9)放入NewT。 (2)对循环

29、次数 n 施归纳，证明如果 X 被放入 NewT 或者 NewV 中，则必定存在,(NewVNewT)*，使得Sn X。 (3) 证明 L(G )=L(G) 。,52,去无用符号,定理6-6 对于任意CFL L，L，则存在不含无用符号的CFG G，使得L(G)=L。 证明要点： 依次用算法6-1和算法6-2对文法进行处理，可以得到等价的不含无用符号的文法。 不可先用算法6-2后用算法6-1。,53,去无用符号举例,例 6-4 设有如下文法 SAB | a | BB，Aa，Cb | ABa 先用算法6-2，文法被化简成： SAB | a | BB，Aa 再用算法6-1，可得到文法： S a，Aa

30、 显然，该文法中的变量 A 是新的无用变量。,54,6.2.2 去-产生式,-产生式(-production) 形如 A的产生式叫做-产生式。 -产生式又称为空产生式(null production)。 可空(nullable)变量 对于文法 G=( V, T, P, S )中的任意变量 A，如果 A+，则称 A 为可空变量。 所谓可空变量，就是可以派生出空串的变量。 这些变量之所以可以派生出 ，最根本的原因是给定的 CFG 中存在 -产生式。,55,去-产生式举例,有如下文法 S ABS | AB0 A CA | CBC B 2 | C 1C | 因为有 B和 C，变量 B 和 C 可以直接

31、派生出。 作如下派生： A CBC BC C 所以 A, B, C 都是可空变量。 但是不能简单地将 SABS 中的 A 删去，而是要考虑表达出 A 产生和 A 不产生的情况。,56,去-产生式举例,根据 SABS，可以得到如下产生式： SABS对应 A 和 B 均不派生出的情况 SBS对应 A 派生出和 B 不派生出的情况 SAS对应 B 派生出和 A 不派生出的情况 SS对应 A 和 B 均派生出的情况 根据 SAB0，可以得到如下产生式： SAB0对应 A 和 B 均不派生出的情况 SB0对应 A 派生出和 B 不派生出的情况 SA0对应 B 派生出和 A 不派生出的情况 S0对应 A

32、和 B 均派生出的情况,57,去-产生式举例,根据 ACA，可以得到如下产生式： ACA对应 A 和 C 均不派生出的情况 AC对应 A 派生出和 C 不派生出的情况 AA对应 C 派生出和 A 不派生出的情况 A 对应A和C均派生出的情况 根据 ACBC，可以得到如下产生式： ACBC对应 B 和 C 均不派生出的情况 ABC对应第一个 C 派生和第二个 C 不派生出的情况 ACB对应第二个 C 派生和第一个 C 不派生出的情况 ACC对应 B 产生和两个 C 均不派生出的情况 AC对应第一个 C 不派生，B 和第二个 C 均派生出的情况 AB对应 B 不派生，两个 C 均派生出的情况 AC

33、对应第二个 C 不派生，B 和第一个 C 均派生出的情况 根据 C1C，可以得到如下产生式： C1C对应右部的 C 不派生出的情况 C1对应右部的 C 派生出的情况,58,去-产生式举例,这样，可以得到其如下不含产生式的等价的文法： S ABS | BS | AS | S | AB0 | B0 | A0 | 0 A CA | C | A | CBC | BC | CB | CC | C | B B 1C | 1 C 1C | 1 对形如 AX1X2Xm 的产生式进行考察， 找出文法的可空变量集U， 然后对于 HU，从 AX1X2Xm中删除 H 中的变量。 对于不同的 H，得到不同的 A 产生式

34、，用这组 A 产生式替代产生式AX1X2Xm。 必须避免在这个过程中产生新的-产生式： 当 X1, X2, , Xm U时，不可将X1, X2 , Xm 同时从产生式AX1X2Xm 中删除。,59,算法6-3 求可空变量集,算法6-3 求 CFG G 的可空变量集 U。 输入：CFG G=( V, T, P, S )。 输出：G 的可空变量集 U。 主要步骤： (1)OldU=; (2)NewU=A| AP; (3)while NewUOldU do begin (4) OldU = NewU; (5) NewU = OldU A | AP 并且 OldU* end (6)U=NewU,60,

35、定理6-7,定理 6-7 对于任意 CFG G，存在不含-产生式的 CFG G 使得L(G )=L(G)-。 证明要点： 对于任意给定的 CFG G=( V, T, P, S ) ， (1)用算法6-3求出 G 的可空变量集 U， (2)构造P ，求产生式集合的一般方法为： 对于 AX1X2XmP ，将 A12m放入 P，其中 if XiU then i=Xi 或者i =； if Xi U then i=Xi 要求：在同一产生式中，1,2,m不能同时为。,证明略,61,定理6-7,注意到在进行文法改造的过程中并没有引进任何新的变量，而需要考虑的又只是非空串的产生，所以证明L(G )=L(G)-

36、的关键是证明这两个文法中的任何一个变量在这两个文法中都可以产生相同的终极符号行集。 即证明对于任意 wT+，AnG w 的充分必要条件是 AmG w。 必要性：设 AnG w，施归纳于 n，证明 AmG w。 关键是将 w 拆成w1w2wm，这里的w1,w2 ,wm 均是非空串。 充分性：设AmG w，施归纳于m，证明 AnG w。 需要注意的是，G 中没有产生空串的派生，而在 G 中如果要产生相应的串 w，可能会需要一系列的产生空串的派生。,62,定理6-7,定理 6-7 对于任意CFG G，存在不含-产生式的CFG G 使得L(G )=L(G)-。 证明： (1) 构造 设CFG G=(V

37、,T,P,S) ， 用算法6-3求出G的可空变量集U， 构造P。 对于 AX1X2XmP ，将A12m放入P，其中 if XiU then i=Xi或者i=； if XiU then i=Xi 要求：在同一产生式中，1,2,m不能同时为。,63,定理6-7,证明对于任意wT+，AnG w的充分必要条件是A。 必要性：设AnG w，施归纳于n，证明AmG w成立。 当n=1时，由AG w知，AwP，按照定理所给的构造G的方法，必定有AwP。所以，AG w成立。 设nk时结论成立(k1)，当n=k+1时 AX1X2Xm *G w1X2Xm *G w1w2Xm *G w1w2wm 其中w1w2wm=

38、w，且w1,w2,wmT*。,64,定理6-7,注意到w，必存在1im，wi，设i,j,k是w1,w2,wm中所有非空串的下标，并且1ijkm，即： w= wiwjwk 按照G的构造方法，A XiXjXkP 再由归纳假设， Xi*G wi，Xj*G wj，Xk*G wk。 A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk 所以，结论对n=k+1成立。由归纳法原理，结论对所有的n成立。,65,定理6-7,充分性：设AmG w，施归纳于m，证明AnG w成立。 当m=1时，由AG w知，AwP，按照定理所给的构造G的方法，必定有AP。Aw是通过删除产生式A右部中的可

39、空变量而构造出来的，所以， AG *G w 成立。 设nk时结论成立(k1)，当m=k+1时 A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w 其中Xi*G wi，Xj*G wj，Xk*G wk 。,66,定理6-7,表明A XiXjXkP。按照G的构造方法，必定存在A X1X2XmP，而且 Xi，Xj，XkX1，X2，Xm X1，X2，Xm-Xi，Xj，XkU 从而， AG X1X2Xm *G XiXjXk,67,定理6-7,再根据Xi*G wi，Xj*G wj，Xk*G wk和归纳假设，有 Xi*G wi，Xj*G wj，Xk*G wk。 这表明，如下派

40、生成立： AG X1X2Xm *G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w,68,定理6-7,表明结论对m=k+1成立。由归纳法原理，结论对任意m成立。 注意到A 的任意性，当S=A时结论成立。即： S*G w 的充分必要条件是S*G w 亦即：L(G)=L(G)-。 定理得证。,69,6.2.3 去单一产生式,考虑如下的关于算术表达式的文法： Gexp1：E E+T | E-T | T T T*F | T/F | F F FP | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L L,E

41、| E 增加了句子的分析步骤： E T F P id 原因：由形如 AB 的单一产生式造成的。,70,Gexp1中单一产生式的处理,Gexp1：E E+T | E-T | T T T*F | T/F | F F FP | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L L,E | E,去掉F P 后 F (E) | N(L) | id F FP | (E) | N(L) | id 去掉T F 后 T T*F | T/F | FP | (E) | N(L) | id 去掉E T 后 E E+T | E-T | T*F | T/F

42、 | FP | (E) | N(L) | id,71,Gexp1中单一产生式的处理,Gexp3：E E+T | E-T | T*F | T/F | FP | (E) | N(L) | id T T*F | T/F | FP | (E) | N(L) | id F FP | (E) | N(L) | id P (E) | N(L) | id N sin | cos | exp | abs | log | int L L,E | E 该文法中不存在类似的派生。,72,去单一产生式,单一产生式(unit production) 形如 AB 的产生式称为单一产生式。 定理 6-8 对于任意 CFG G

43、，L(G)，存在等价的 CFG G1，G1不含无用符号、-产生式和单一产生式。 满足本定理的 CFG 为化简过的文法。 已有去无用符号和去-产生式的结论，所以只讨论去单一产生式的问题。,73,定理6-8的证明要点,(1) 构造 G2，满足 L(G2)=L(G)，并且 G2 中不含单一产生式。 如果 AP 不是单一产生式，则将 A放入 P2； 如果 A+G B，且 B 不是单一产生式，则将 A放入P2。 (2) 证明 L(G2)=L(G)。 根据 G2 的构造方法，如果 AP2，必有 AG+。 由 wL(G) 证明 w L(G2) 的过程中，要取 w 在 G 中的一个最短的最左派生。 S=0G1

44、G2GGn=w (3) 删除 G2 中的无用符号。 由于在删除单一产生式后，文法中可能出现新的无用符号，因此，我们还需要再次删除新出现的无用符号。 此外，在去-产生式后可能会产生新的单一产生式，也可能会引进新的无用符号。这是值得注意的。,74,CFG的化简过程,(1) 删除无用符号。 (2) 删除-产生式。 (3) 删除单一产生式。 (4) 删除新出现的无用符号。,给定文法： S A | B A a B bB | b,删除单一产生式 S a | bB | b A a B bB | b,最后化简： S a | bB | b B bB | b,75,6.3 乔姆斯基范式,乔姆斯基范式文法(Chom

45、sky normal form ，CNF)简称为Chomsky文法，或 Chomsky 范式。 CFG G=( V, T, P, S ) 中的产生式形式： A BC A a 其中，A, B, CV，aT。 CNF 中，不允许有 -产生式、单一产生式。,76,例 6-5,试将文法 Gexp4 转换成等价的 GNF。 Gexp4：E E+T | T*F | FP | (E) | id T T*F| FP| (E) | id F FP | (E) | id P (E) | id,可以分两步走 (1) 变成 Aa 和 AA1A2An 的形式。 (2) 变成 CNF。,77,第一步,EEA+T | T

46、A*F | F AP | A(EA5 | id TTA*F | FAP | A(EA) | id FFAP | A(EA)|id PA(EA) | id A+ A* A A( A),78,第二步,GexpCNF： EEA1| TA2 E FA3| A(A4| id TTA2| FA3| A(A4 |id FFA3| A(A4|id PA(A4 |id A+ A*,A A( A) A1A+T A2A*F A3AP A4EA),EEA+T | T A*F | F AP | A(EA5 | id,79,定理6-9,定理6-9 对于任意CFG G，L(G)，存在等价的 CNF G2 。 证明思路：不妨

47、假设 G 为化简过的文法。 根据例6-5的思路，分两步进行规范化处理。 (1)构造 G1=(V1, T, P1, S)，其中 G1 中的所有产生式形如 AB1B2Bm Aa 其中，A, B1, B2, , BmV1，aT，m2 ，构造方法如下： 对于 P 中的每个产生式 A， 如果TV+，则直接将 A放入 P1； 否则，对 A进行如下处理： 设=X1X2Xm，则对于每一个 Xi， 如果Xi =a T，则引入新的变量 Ba和产生式Ba a(将它放入P1)， 并且用 Ba 替换产生式 A中的Xi； 如果 XiV，则取 Bi=Xi， 将处理后的形如 AB1B2Bm的产生式放入 P1。 可以证明 L(

48、G1)=L(G),80,定理6-9,(2) 构造 CNF G2=(V2 , T , P2 , S)。 按照下列方法改造 G1： 将 V1 中的全部变量放入V2。 对于 P1 中的每一个产生式 A 如果T，则直接将 A放入P2； 否则，A一定形如 AA1A2Am，进行如下处理： 当 m=2 时，则将AA1A2Am 放入P2； 当 m3 时，引入新变量：B1 , B2 , , Bm-2，将它们放入 P2， 并将下列产生式组放入 P2 AA1B1 B1A2B2 Bm-2Am-1Am 可以证明 L(G2)=L(G1)。,81,例6-6,试将下列文法转换成等价的 CNF。 SbA | aB AbAA |

49、 aS | a BaBB | bS | b,先引入变量Ba, Bb和产生式Baa, Bbb ，完成第一步变换。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb,引入新变量 B1, B2 SBbA | BaB ABbB1 | BaS | a BBaB2 | BbS | b Baa Bbb B1AA B2BB,82,例6-6,不能因为原来有产生式 A a 和 B b 而放弃引进变量Ba 、Bb 和产生式 Baa 、Bbb。 L(A)= x | xa,b+ & x 中 a 的个数比 b 的个数恰多1个。 L(B)= x | xa,b+ & x 中

50、 b 的个数比 a 的个数恰多1个。 L(Ba)= a 。 L(Bb)= b 。,83,6.4 格雷巴赫范式,格雷巴赫范式文法(Greibach normal form ,GNF)简称为Greibach文法，或 Greibach 范式。 Aa 其中，AV，aT，V* 。 在GNF中，有如下两种形式的产生式 A a A aA1A2Am(m1) 右线性文法是一种特殊的 GNF。 由于GNF中不存-产生式, 所以对任意的 GNF G,L(G)。 当L(G )时, 能够找到一个GNF G, 使得 L(G)=L(G ) 。 经过化简的 CFG, 都有一个等价的 GNF。,84,格雷巴赫范式,例6.6 中

51、的文法 SbA | aB AbAA | aS | a BaBB | bS | b,如何判断符号串 a1a2 am 是否属于一个给定的 CFG？,85,引理 6-1,对于任意的 CFG G=(V, T, P, S)，ABP，且 G 中所有的 B 产生式为 B1 |2 |n 取 G1=( V, T, P1 , S ) P1=(P-AB)A1, A2,An 则 L(G1)=L(G)。 证明要点 以下两组产生式等价 AB , B1 |2 |n A1, A2, , An,86,递归派生,问题：如何解决 AA的产生式带来的问题？ 如果 G 中存在形如 AnA的派生，则称该派生是关于变量 A 递归派生，简称

52、为递归派生。 当 n=1 时，称该派生关于变量 A 直接递归 ( directly recursive) ，简称为直接递归派生。 形如 AA的产生式是变量 A 的直接递归产生式。 当 n2 时，称该派生是关于变量 A 的间接递归(indirectly recursive)派生。简称为间接递归派生。 当=时，称相应的(直接/间接)递归为(直接/间接)左递归(left-recursive)； 当=时，称相应的(直接/间接)递归为(直接/间接)右递归(right-recursive)。,87,引理 6-2,对于任意的 CFG G=(V, T, P, S)， AA1 | A2 | | An A1 |

53、2 | | m 是 G 中所有 A 的产生式。对于 1hm， h 的最左符号都不是 A。 将这组产生式暂时记为产生式组 1，取 G1=( VB, T , P1 , S ) 其中 BV，为新引进的变量；P1 是删除 P 中的所有 A 产生式，然后加入以下产生式组(暂时记为产生式组2)得到的产生式集合： A1 | 2 | m A1B |2B | mB B1 | 2 | n B1B | 2B | nB 则 L(G1)=L(G2),88,引理6-2证明要点,用直接右递归取代原来的直接左递归。 两组产生式产生的符号串都是,前者是先产生,然后产生k 。,后者先产生k 。然后产生,89,定理6-10,定理6

54、-10 对于任意 CFG G，L(G)，存在等价的 GNF G1。 证明要点： 分 3 步进行规范化处理。 (1)构造 G1=(V1, T, P1, S )，并且 G1 中的产生式都形如 AA1A2Am AaA1A2Am-1 Aa 其中，A, A1, A2 , , AmV1，aT，m2。方法如下： 对于 P 中的每个产生式 A， 如果TV+ TV+ ，则直接将 A放入P1； 否则，对 A进行如下处理： 设=X1X2Xm，则对于每一个Xi，i2 如果 Xi =a T，则引入新的变量 Aa (放入V1)和产生式 Aaa (将它放入P1)，并且用 Aa 替换产生式 A中的 Xi； 然后将处理后的形如

55、 AA1A2Am 或者 AaA1A2Am-1 的产生式 放入 P1。 可以证明 L(G1)=L(G),90,定理6-10,(2)设 V1=A1, A2, , Am ， 构造 G2=(V2, T, P2, S)，使得 L(G2)=L(G1)， 并且 G2 中的产生式都形如 AiAji j Aia Bi 其中，V2=V1 B1, B2 , Bn， V1 B1, B2, , Bn=。 “B类变量”： B1, B2, Bn 是在文法的改造过程中引入的新变量。 V1中的变量称为“A类变量”。 构造方法见算法6-4。 根据引理 6-1和 6-2，可以证明 L(G2)=L(G1)。,91,算法6-4,输出：

56、G1=(V1, T, P1, S) 输出：G2=(V2, T, P2, S) 主要步骤： for k=1 to m do begin for j=1 to k-1 do for 每个形如 AkAj的产生式 do begin 标记产生式 AkAj。设 Aj1 |2 |n 为所有的 Aj 产生式，将产生式组 Ak1| 2| | n 添加到产生式集合 P2 中 end 设 AkAk1| Akp 是所有右部第一个字符为 Ak 的 Ak 产生式， Ak1 |2 |m 是所有其他的 Ak 产生式。 根据引理6-2, 标记所有的Ak产生式, 并引入变量B, 将下列产生式添加到P2中： Ak 1 |2 |q

57、| 1B |2B |qB B 1 |2 |p |1B |2B |pB end 将 P1 中未标记的产生式全部都添加到产生式集合 P2 中,92,定理6-10,(3) 设V2=V1 B1,B2,Bn， 构造G3=(V3, T, P3, S)，使得 L(G3)=L(G2)， 根据引理 6-1，从编号较大的变量开始，逐步替换，使所有产生式满足GNF的要求。见算法 6-5。 算法 6-5： 输出：G2=(V2, T, P2, S) 输出：G3=(V3, T, P3, S) 主要步骤： for k=m-1 to 1 do if AkAjP2 并且 j k then for 所有的 Aj 产生式 Aj d

58、o 将产生式 Ak放入 P3； for k = 1 to n do 根据引理 6-1，用 P3 中的产生式将所有的 Bk 产生式替换成 满足 GNF 要求的形式。,93,例6-7,将下列文法转换成 GNF。 A1 A2bA3 | aA1 A2 A3cA3 | b A3 A1cA3 | A2bb | a,引入变量 B 和 C 改造文法： A1 A2BA3 | aA1 A2 A3CA3 | b A3 A1CA3 | A2BB | a B b C c,用 A1 的产生式处理 A3 产生式： A3 A2BA3 CA3 | aA1CA3 | A2BB | a,用 A2 的产生式处理 A3 产生式，得到

59、A3 的全部产生式： A3 A3CA3 BA3 CA3 | bBA3 CA3 | aA1CA3| A3CA3BB | bBB | a,引入变量 B1 消除 A3 产生式中的左递归： A3 bBA3 CA3 | aA1CA3| bBB | a A3 bBA3 CA3B1 | aA1CA3B1| bBBB1 | aB1 B1 CA3 BA3 CA3 | CA3BB B1 CA3 BA3 CA3 B1 | CA3BBB1,A3 的产生式满足 GNF 的要求 将 A3 代入到 A2 和 A1 中 变换 B1 的产生式左部的 C 为c，以满足 GNF 的要求,94,6.5 自嵌套文法,设 L 是一个 CFL，G=( V, T, P, S ) 是产生 L 的文法。 如果 L 是一个有无穷多个句子的语言，由于 G 是它的有穷描述，则必存在 w L，AV， ,(VT)+，且和至少有一个不为，使得如下派生成立： S*A +A+w 即在文法中，有形如 S+A的派生。 CFG 正是利用了这种递归形式来解决对无穷语言的描述