形式语言与自动机：-上下文无关语言（新）

1、形式语言与自动机Formal Languages and Automata Theory第六、八章 上下文无关语言及性质第六章 上下文无关语言上下文无关文法的引入上下文无关文法的派生上下文无关文法的化简上下文无关文法的规范形式上下文无关语言的性质文法的乔姆斯基体系：语言之间的包含关系0型语言上下文有关语言上下文无关语言正则语言设 G= ( V, T, P, S )，P= ， ( V T )+， ( V T )* G ：0 型文法，或短语结构文法（PSG） L(G)： 0 型语言或 短语结构语言（PSL）、递归可枚举集。 对于 P，均有 | | | | G：为 1 型文法，上下文有关文法（CSG

2、） L(G): 1 型语言或上下文有关语言 ( CSL )对于 P, 均有 | | | |, 且 V G：为 2 型文法，上下文无关文法（CFG） L(G): 2型语言或上下文无关语言 ( CSL )对于 P, 均具有以下形式：A ， A B G：为 3型文法，正则文法(RG) L(G): 3型语言或正则语言 ( RL )关于乔姆斯基麻省理工学院语言学的荣誉退休教授美国科学杂志评选出的20世纪全世界前10名最伟大的科学家中目前唯一的在世者http:/wiki/乔姆斯基/view/67358.htm上下文无关文法的提出 正则文法与词法分析：单词的识别例：八进制数无符号整数的识别正则表达式：0+(

3、1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*上下文无关文法的提出（续）例：, , =, 的识别上下文无关文法的提出（续）例：number的识别例：回文不是正则语言上下文无关文法的提出（续）回文：正向和反向读起来都一样的字符串Madamimadam Madam, Im adam Able was I ere I saw Elba在我看到厄尔巴岛之前，我曾所向无敌 0和1上的回文语言 Lpal 不是正则语言上下文无关文法的提出（续）证明思想：泵引理泵引理：设 L 为 RL，存在仅依赖于语言 L 的某个正整数 n，对于 z L， 如果 | z | n，则存在 u,

4、 v, w，满足以下条件：z = uvw，|uv | n，| v | 1，且对于任意整数 i 0，uvi w L。（反证法）：假设Lpal 是正则语言，且n是相关的正整数，令z=0n10n , 则z可写作z= uvw，满足|uv | n，| v | 1，且对于任意整数 i 0，uvi w Lpal 。不失一般性，令u=0k, v=0m, w=0j10n , 且满足k+m n, m 1。则有uw=0k+j10n Lpal 。然而，0k+j10n 不是回文(k+jn)，矛盾。0110， 1101111011上下文无关文法的提出（续） 0和1上的回文语言 Lpal 不是正则语言 0和1上的回文语言

5、Lpal的文法：一个回文的开头和结尾的字母一定相同一个回文去掉开头和结尾的字母后还是一个回文1 1 0 1 1 1 1 0 1 11 0 1 1 1 1 0 10 1 1 1 1 0递归定义：基础: ,0,1都是回文归纳：如果w是回文，那么0w0与1w1都是回文文法Gpal=(P, 0,1, A, P) P |0|1 P 0P0|1P1上下文无关文法的提出（续） 正则语言描述模型能力有限，无法描述高级程序设计语言表达式中 “良嵌套”的括号对、( begin end ) 以及HTML中标记对 等配对符号序列的语法规则例: 文法 Gbal = (B, ( , ) , P, B) BBB | (B)

6、 | 能够产生所有的括号匹配的串。, (), ()(), ()()()()()同样可由正则语言的泵引理证明Gbal不是正则语 BNF：Backus normal form，巴克斯范式，又叫Backus-naur form，是CFG的一种特殊形式，在计算机中很常见，常用于表达语言的文法结构上下文无关文法文法 G =（V，T，P，S）称为上下文无关文法，如果 对于所有产生式 P，均有 | | | | 且 V, ( VT )“上下文无关”：对于所有 A V，如果 A P，则无论 A 出现在句型的什么位置，都可以用 自由替换 A，无需考虑 A 出现的上下文“上下文有关”： A BcD, Bc aEF,

7、 CD bGH文法Gpal=(P, 0,1, A, P) P |0|1 P 0P0|1P1第六章 上下文无关语言及其性质上下文无关文法的引入上下文无关文法的派生上下文无关文法的化简上下文无关文法的规范形式上下文无关语言的性质上下文无关文法的派生 一个句子可能有多个派生例：给定文法：Gexpl: E E+T | E-T | T TT*F | T/F| F FF P | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2派生1：E E+T T+T F+T P+T x+T x+T/F x+F/F x

8、+P/F x+x/F x+x/F P x+x/P P x+x/y P x+x/y 2派生2：E E+T E+T/F E+T/FP E+T/F 2 E+T/P 2 E+T/y 2 E+F/y 2 E+P/y 2 E+x/y 2 T+x/y 2 F+ x/y 2 P+x/y 2 x+x/y 2派生1与2使用了相同的变量替换，仅顺序不一样： EE+T, ET, TF, FP, Px, TT/F, TF, FP, Px, FF P, FP, Py, P2 如何体现句子结构的本质？上下文无关文法的派生用树表示句子的结构 例：给定文法：Gexpl: E E+T | E-T | T TT*F | T/F|

9、F FF P | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2变量替换：EE+T, ET, TF, FP, Px, TT/F, TF, FP, Px, FF P, FP, Py, P2派生树：略去变量替换的顺序，只保留所需的替换EE+T上下文无关文法的派生派生1：E E+T T+T F+T P+T x+T x+T/F x+F/F x+P/F x+x/F x+x/F P x+x/P P x+x/y P x+x/y 2派生2：E E+T E+T/F E+T/FP E+T/F 2 E+T/P

10、2 E+T/y 2 E+F/y 2 E+P/y 2 E+x/y 2 T+x/y 2 F+ x/y 2 P+x/y 2 x+x/y 2定义6-1：设有 CFG G = （ V, T, P, S ），G 的派生树是满足如下条件的有序树： 1、树的每个节点都有一个标记 X，且 X V T 2、树的根节点标记为 S 3、如果 X 是一个非叶节点的标记，则有 X V 4、如果一个非叶节点 v 的标记为 A，v 的子节点从左到右依此为 v1, v2, , vn, 并且，它们分别标记为 X1,X2, , Xn，则有 A X1, X2, , Xn P 5、如果一个节点 v 标记为，则 v 是该树的叶节点，并且

11、，v 是其父节点的唯一子节点 上下文无关文法的派生生成树、分析树(parse tree)、语法树(syntax tree) 根结点：开始符号 中间节点：非终结符 叶结点：终结符或者 非终结符EE+TEE/FET派生树定义6-3：设有 文法G 的一棵派生树T，v1,v2是T的两个不同的顶点，如果存在顶点v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。定义6-4：设有文法G的一棵派生树T，T的所有叶子顶点从左到右依次标记为X1,X2,Xn，则称符号串X1X2Xn是T的结果。G的结果为a的派生树，简称句型a的派生树

12、v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v16v17v20v19v18v5在v6的左边v18在v20的左边 x+x/y 2是T的结果T是x+x/y 2的派生树定义6-1：设有 CFG G = （ V, T, P, S ），G 的派生子树是满足如下条件的有序树： 1、树的每个节点都有一个标记 X，且 X V T 2、树的根节点标记为 S 3、如果 X 是一个非叶节点的标记，则有 X V 4、如果一个非叶节点 v 的标记为 A，v 的子节点从左到右依此为 v1, v2, , vn, 并且，它们分别标记为 X1,X2, , Xn，则有 A X1, X2, , Xn P

13、 5、如果一个节点 v 标记为，则 v 是该树的叶节点，并且，v 是其父节点的唯一子节点 派生子树（派生树去掉第二个条件）v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v16v17v20v19v18派生树定理 6 1：设 CFG G =（ V, T, P, S ）， S 的充分必要条件为 G 有一棵结果为 的派生树。v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v16v17v20v19v18例：给定自述表达式的文法：Gexpl: E E+T | E-T | T TT*F | T/F| F FF P | P P (E) | N(L) | id

14、N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2E x+x/y 2 如何证明： 数学归纳法 考虑子树T x/y 2 证明：证一个更为一般的结论：对于任意AV，A的充分必要条件为G有一棵结果为的A-子树。 充分性：设G有一棵结果为的A-子树，对非叶子顶点的个数n进行归纳，证明A成立。n=0时，A-子树只有一个叶子节点，显然结论成立； n=1时，A-子树是一个二级子树（只有一个根节点，其他均为叶子节点） ；假设所有叶子节点为X1, Xm, 则由A-子树的定义知，必有A X1 Xm P 又由于该 A-子树的结果为，故X1 Xm = ，因

15、此有A 定理 6 1：设 CFG G =（ V, T, P, S ）， S 的充分必要条件为 G 有一棵结果为 的派生树AX1X2Xm证明（续）假设当nk（k 1）时，结论成立 ，下面证明当n=k+1地时结论成立。 设A-子树有k+1个非叶子顶点，根顶点A的儿子从左到右依次为v1，v2，vm，并且它们分别标记为X1，X2，Xm ，则必有AX1X2XmP ，且以X1，X2，Xm为根的子树的结果依次为1，2，m 。 显然，以X1，X2，Xm为根的子树的非叶子顶点的个数均不大于k。由归纳假设知X11X22Xmm而且=12mAX1X2Xm 1X2Xm 12Xm 12m结论成立证明（续）：证一个更为一般

16、的结论：对于任意AV，A的充分必要条件为G有一棵结果为的A-子树。 定理 6 1：设 CFG G =（ V, T, P, S ）， S 的充分必要条件为 G 有一棵结果为 的派生树 必要性：设A，对派生步数n进行归纳，证明存在结果为的A子树。 n=0时，A= , 结论成立； n=1时，由A知 AP；令=X1Xm, 则可构造一棵A子树（如下图所示）, 结论成立。AX1X2Xm证明（续） 设n k(k1)时结论成立，往证当n=k+1时结论也成立。令Ak+1，则有AX1X2Xm 1X2Xm 12Xm *12m 其中，对于任意的i， 1im, 有Xi i 显然，所用步数 k，由归纳假设知道，存在以i为

17、结果的Xi子树。又由于 A X1X2Xm P,从而可以得到A子树的上半部分，把所有的Xi-子树对应地接在Xi所标识的顶点上，从而得到A-子树。所以结论对n=k+1成立 。定义 6 5：设 CFG G =（ V, T, P, S ）， 是 G 的一个句型。如果在 的派生过程中， 每一步都是对当前句型的最左变量进行替换，则该派生为最左派生，每一步所得到的句型叫做左句型。 每一步都是对当前句型的最右变量进行替换，则该派生为最右派生，每一步所得到的句型叫做右句型。最左派生被视为规范派生，常被计算机系统用来处理输入字符串。多种派生方式例：文法：Gexpl: E E+T | E-T | T TT*F |

18、T/F| F FF P | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2派生1：E E+T T+T F+T P+T x+T x+T/F x+F/F x+P/F x+x/F x+x/F P x+x/P P x+x/y P x+x/y 2多种派生方式最左派生最右派生派生2：E E+T E+T/F E+T/FP E+T/F 2 E+T/P 2 E+T/y 2 E+F/y 2 E+P/y 2 E+x/y 2 T+x/y 2 F+ x/y 2 P+x/y 2 x+x/y 2对任意的 P, 均有以下

19、形式：| | | |， V, ( VT ) 一次替换可能产生多个变量多种派生方式正则文法有没有多种派生方式？ 没有 对任意的 P, 均有以下形式：A , A B , A, B V, T+ 一次替换只产生一个变量为什么上下文无关文法有多种派生方式？派生树定理 6 2：如果 是 CFG G 的一个句型，则G中存在 的最左派生和最右派生。证明思路：对派生的步数 n 施归纳，证明对于任意AV，如果An，在G中，存在对应的从A到的最左派生An左。 AX1X2Xm *1X2Xm *12Xm *12mA左X1X2Xm *左1X2Xm *左12Xm *左12m 同理可证，句型有最右派生。 上下文无关文法的二义

20、性例：文法：Gexp2: E E+E | E-E | E/E | E*E | E E | (E) | N(L) | id | N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2最左派生1：E E+E x+E x+E/E x+x/E x+x/E E x+x/y E x+x/y 2 最左派生2：E E/E E+E/E x+E/E x+x/E x+x/E E x+x/y E x+x/y 2 最左派生2：E E E E/E E E+E/E E x+E/E E x+x/E E x+x/y E x+x/y 2 x+(x/(y 2)(x+x)/(

21、y 2)(x+x)/y) 2上下文无关文法的二义性例：文法：Gexp2: E E+E | E-E | E/E | E*E | E E | (E) | N(L) | id | N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2x+(x/(y 2)(x+x)/(y 2)(x+x)/y) 2三个不同的派生树甚至还有其他派生树同一表达式 “x + x / y 2” 可对应多种不同的派生树：上下文无关文法的二义性定理 6 - 6：设有 CFG G=(V, T, P, S)，如果存在w L(G)，w至少有两棵不同的派生树，则称G是二义性的（am

22、biguity）；否则，G为非二义性的。文法：Gexp2: E E+E | E-E | E/E | E*E | E E | (E) | N(L) | id | N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2Gexp2是二义性的例：文法：Gexp1: E E+T | E-T | T TT*F | T/F| F FF P | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L L, E | E句子：x+x/y 2派生1：E E+T T+T F+T P+T x+T x+T

23、/F x+F/F x+P/F x+x/F x+x/F P x+x/P P x+x/y P x+x/y 2派生2：E E+T E+T/F E+T/FP E+T/F 2 E+T/P 2 E+T/y 2 E+F/y 2 E+P/y 2 E+x/y 2 T+x/y 2 F+ x/y 2 P+x/y 2 x+x/y 2非二义性的文法Gexp1是非二义性文法派生树唯一派生不一定唯一去除文法的二义性 判断一个CFG 是否有二义性是不可判定的（Undecidable）定义6-7 如果语言 L 不存在非二义性方法，则L是固有二义性的，又称 L 是先天二义性的 文法可以二义性的；语言可以是固有二义性的； 一般不说

24、文法是固有二义性的，也不说语言是二义性的如何去除文法的二义性？消除二义性例6-2 消除二义性。Gifa：Sif E then S else S | if E then S （二义性）有不同的理解：If E then if E then S else if E then S ( ) ( ) ( ( )Gifm：SU|M （非二义性?）Uif E then SUif E then M else UMif E then M else M|SGifh：STS|CS （非二义性?）Cif E thenT CS else 派生与归约 问题：设有 CFG G=(V, T, P, S)和字符串w T*，判断是

25、否w L(G) 两类方法 自顶向下的分析方法 自底向上的分析方法例：文法 S aAb| bBa A aAb| bBa Bd判断aabdabb是否为该文法的句子S aAb aaAbb aabBabb aabdabb自顶向下自底向上第六章 上下文无关语言及其性质上下文无关文法的引入上下文无关文法的派生上下文无关文法的化简上下文无关文法的规范形式上下文无关语言的性质问题提出：根据语言的结构特征构造文法时，由于使用的符号及定义的产生式不恰当，可能会引入一些多余或者错误的符号。文法的化简规则例：设语言 L = 0 x | x 0,1 * 0 x_y | x 0,1 *, y 0,1 + ，该文法存在什么

26、问题？G1: S 0 | 0A | E A | 0A | 1A|B B_C C 0 | 1 | 0C | 1C D 1 | 1D | 2D E 0E2 | E02 文法的化简规则1、识别G1 中的无用符号：1) 终结符 2 没在L中出现，因此不应出，相关产生式无用2 ) 句型的派生过程中，不会涉及变元 D ，相关产生式无用；3) 变元E 一旦出现，则永远不会消失，其不能构成句子，相关产生式无用G2: S 0 | 0A | E A | 0A | 1A|B B_C C 0 | 1 | 0C | 1C例：设语言 L = 0 x | x 0,1 * 0 x_y | x 0,1 *, y 0,1 + ，

27、文法的化简规则G2: S 0 | 0A | E A | 0A | 1A|B B_C C 0 | 1 | 0C | 1C1、识别G1 中的无用符号（续）： 4) 未出现在L中，可去掉A， 但需增加 A0|1A 可用来产生0与1G3: S 0 | 0A | E A0 | 1 | 0A | 1A|B B_C C 0 | 1 | 0C | 1C5) A B 没有引进终止符号，可去掉,但需增加A_C A B与B_C 可产生A_CG4: S 0 | 0A | E A0 | 1 | 0A | 1A| _C C 0 | 1 | 0C | 1C保持方法语义不变例：设语言 L = 0 x | x 0,1 * 0

28、x_y | x 0,1 *, y 0,1 + ，G1: S 0 | 0A | E A | 0A | 1A|B B_C C 0 | 1 | 0C | 1C D 1 | 1D | 2D E 0E2 | E02 文法的化简规则三类化简规则 去无用符号：2，D，E 去-产生式 去单一产生式： AB 定义 6 - 8：设 有CFG G = ( V, T, P, S )。对于任意 X V T，如果存在 w L( G )，X 出现在w 的派生过程中，即，存在 , ( V T ) *，使得S X w则称 X 是有用的；否则，称 X 是无用符号。文法的化简规则1 - 删除无用符号 直观理解：文法G=(V, T,

29、 P, S) 中的不在任何句子的派生中出现的符号都是无用的 X是可达的 X是可终止的（产生的）：存在w T*，使得Xw 有穷语法使得可以设计算法来删除无用符号 例：考虑文法文法的化简规则1 - 删除无用符号 B以外的符号都是可终止的 S a, A b, a与b产生它们自己S AB | aA bS aA b 只有S, a可达S a 不存在无用符号（均可达和可终止）输入： CFG=(V, T, P, S) （算法6-1） 输出： CFG G=(V, T, P, S)，其中V不含非终止符，且L(G)=L(G)OLDV=;NEWV=A| A w P 且 w T*;While OLDV NEWV do

30、begin OLDV=NEWV; NEWV=OLDVA|AP且(TOLDV)*; end V= NEWV; P=AP且AV且(TV)*;V 包含所有有用语法变元；从 P 中挑选与V 、T 中变元A 终结符号 a 相关的产生式，构成 P 删除不可终止符号 计算文法G=(V, T, P, S) 的所有可终止符号文法的化简规则1 - 删除无用符号基础：T中每个符号都是可终止的归纳：对于产生式A，并且中的符号都是可终止的，则A 是可终止定理6-4 算法6-1是正确的证明：(1) 对任意的A V，A被放入V的充分必要条件是存在w T*, A= w (2) L(G)=L(G) 删除可终止符号 计算文法G=

31、(V, T, P, S) 的所有可终止符号文法的化简规则1 - 删除无用符号必要性。设A在算法的第n次循环中被放入NEWV，对n进行归纳，证明必存在wT*，满足A= w (充分性同样可证)输入： CFG=(V, T, P, S) （算法6-1） 输出： CFG G=(V, T, P, S)，其中V不含非终止符，且L(G)=L(G)OLDV=;NEWV=A| A w P 且 w T*;While OLDV NEWV do begin OLDV=NEWV; NEWV=OLDVA|AP且(TOLDV)*; end V= NEWV; P=AP且AV且(TV)*;n=0时，显然成立n=k+1时，AX1X

32、m P，其中Xi是终极符号或OLDV中符号且来自于第k次循环，由归纳假设知Xi* w P 删除不可达符号, ( V T )*，使得 S X ：正向地查找在句型推导中出现的语法变元与终结符号文法的化简规则1 - 删除无用符号基础：S 显然是可达的归纳：对于产生式A，并且A是可达的，则中的所有符号 都是可达的算法 6-2：输入：CFG G = ( V, T, P, S )；输出：CFG G = ( V, T, P, S )， 其中, V T 中符号出现必在 G 的某个句型中 且 L( G ) = L( G ) ，V可称为可达变量集*定理6-5 算法6-2是正确的证明：(1) 对任意的X VT，X被

33、放入NEWV或者NEWT的充分必要条件是存在, (NEWV NEWT)*,使得 S=n X , n 0 (2) L(G)=L(G) 删除不可达符号文法的化简规则1 - 删除无用符号定理 6 6： 对于任意 CFL L，L ，存在不含无用符号的 CFG G2，并有 L(G2) = L。证明：设 L 为 CFL，一定存在 CFG G，使得 L(G)= L。3、输出文法 G2将 G1 作为输入，运行算法 6-2 得 G2，G2 中已删除 G1 产生式中所有无用终结符号。用算法 6-1 对 G 进行处理，可得 G1，G1 中所有变元都可用于派生终结符号串 w，并且， L(G1)= L(G)。文法的化简

34、规则1 - 删除无用符号保持顺序文法的化简规则1 - 删除无用符号G1：S AB | a | BB A a C b | ABaG2：S a A a C b算法6.1算法6.2G3：S a G1：S AB | a | BB A a C b | ABaG1：S AB | a | BB A a算法6.2算法6.1G3：S a A a G4：S a 算法6.2可终止可达可达可达可终止文法的化简规则2 - 删除- 产生式定义 6 9： 形如A 的产生式叫作 产生式( -production)，又称为空产生式 (null production)。对于文法 G=(V, T, P, S) 中的任意变量A，如果

35、A=+ ，则称 A为可空 (nullable) 变量。消除A ： 当 L(G)时，可以消除所有的-产生式 当 L(G)时，可以先构造出语言L(G)，然后再加上产生式S .定理2-5 一定存在与G同类型的方法G 使得L(G)=L(G)且G的开始符号不会出现在G的任何产生式的右部 假设S不会出现在任何产生式的右部 G1: S 0S1 | 0A1 | 01 A 2A | G2: S 0S1 | 0A1 | 01 A 2A文法的化简规则2 - 删除- 产生式简单删去例：设有文法 G1：L(G1)= 0n 2m 1n | n1 , m0L(G2)= 0n 1n | n1 G3: S 0S1 | 0A1

36、| 01 A 2A | 2正确地删去 不能简单所有- 产生式增加 A2A无法消除补充A2, S01 基本思想：对任意的AX1Xm P 找出X1,Xm中所有可空变量，构成集合U; 对于U中的所有子集 H，从AX1Xm 中删去H中的变量； 避免产生新的- 产生式：若X1, , Xm都为可空变量，则不可将X1,Xm同时删除文法的化简规则2 - 删除- 产生式例：考虑文法文法的化简规则2 - 删除- 产生式 G1: S AB A aAA | B bBB | 可空变量：S, A, B S AB S AB|A|B S aAA S aAA| aA |aA | a S bBB S bBB| aB |b S a

37、AA| aA | a 可空变量集合A,B的子集： , A, B, AB 不能把AB都去掉 G1: S AB|A|B A aAA | aA| a B bBB | bB| b求可空变量集 A | A n从 A 开始，逆向地找出包含所有与 A 有关的可空变量集合 文法的化简规则2 - 删除- 产生式基础：对任意的A P ，A是可空变量归纳：对任意的A P ，如果中的变量都是可空变量， 则A也是可空变量数学归纳法证明算法的正确性算法6-3文法的化简规则2 - 删除- 产生式定理 6 7：对于任意 CFC G，存在不含 的 CFG G使得 L(G)=L(G) 证明思想：算法6-3 求出可空变量集合2.

38、对任意的AX1Xm P 找出X1,Xm中所有可空变量，构成集合U; 对于U中的所有子集 H，从AX1Xm 中删去H中的变量； 避免产生新的- 产生式：若X1, , Xm都为可空变量，则不可将X1,Xm同时删除3. 输出G, 并证明L(G)=L(G) 。1、推导终结符 id 过程： E T F P id2、推导过程涉及多个单 一产生式 A B 。文法的化简规则3 - 删除 单一产生式例：给定文法：Gexpl: E E+T | E-T | T TT*F | T/F| F FF P | P P (E) | N(L) | id N sin | cos | exp | abs | log | int L

39、 L, E | E句子：x+x/y 2例：用 P （E）| N(L) | id 右部替代 F P 中的 P，获产生式： F FP |（E）| N（L）| id 用上式替换 T F 中的 F，获：T T*F | T/F | FP | (E) | N(L) | id 用上式替换 E T 中的 T，获：T E+T | E-T | T*F | T/F | FP | (E) | N(L) | id 文法的化简规则 - 删除 单一产生式例：给定文法：Gexpl: E E+T | E-T | T TT*F | T/F| F FF P | P P (E) | N(L) | id N sin | cos | e

40、xp | abs | log | int L L, E | E句子：x+x/y 2文法的化简规则 - 删除 单一产生式定理 6 3：对于任意 CFG G， L(G)，存在等价的 CFG G1，G1 不含无用符号，- 产生式和单一产生式。 综合处理：1、去无用符号； 2、去- 产生式；3、去单一产生式；4、去无用符号。例：设 G：S A | B，A a，B bB | b 1、删除单一产生式，得： G1：S a | bB | b ，A a，B bB | b 2、删除无用符号 A ，得： G2：S a | bB | b，B bB | b文法的化简规则习题 教材第六章习题 3, 11-13 （第190

41、-192页）第六章 上下文无关语言及其性质上下文无关文法的引入上下文无关文法的派生上下文无关文法的化简上下文无关文法的规范形式上下文无关语言的性质CNF文法上的一个分析树是二叉树，而这个树的高度被限制于最高为这个字符串的长度。由于这些性质，在语言和可计算性领域中很多证明采用了 CNF 。这些性质还产生了基于 CNF文法的各种有效算法；例如，判定给定字符串是否可以被CNF文法生成的 CYK算法。GNF 处理字符串的过程与计算机系统从左至右处理输入字符串的模式相同; 为 CFL 的一些性质的理论证明提供方便。2、 常用的 CFG 文法范式有： 乔姆斯基范式（Chomsky Normal Form

42、- CNF）； 格雷巴赫范式（ Greibach Normal Form - GNF ）； 巴克斯范式（ BNF）- 规范派生 ALGOAL 语言的过程；1、为了便于分析与处理上下文无关语言，通常需要定义规范文法（文法范式），以便规范 CFL 的派生过程。文法的规范形式乔姆斯基范式定义 6 11：如果CFG G=(V, T, P, S )中的所有产生式都具有形式： ABC Aa则称G为乔姆斯基范式文法（Chomsky normal form），或称为乔姆斯基文法，或乔姆斯基范式，简记为CNF。其中A, B, C V, a T。不允许有-产生式、单一产生式，也不希望有无用符号转换步骤：右部长度为

43、1的产生式都满足要求 右部长度2的产生式中的终极符号用新的变量代替 把所有右部长度2的产生式变换为右部长度=2的产生式乔姆斯基范式-如何转换例 6-3-1 试将文法Gexp4转换成等价的 CNF。Gexp4：EE+T | T * F | F P | ( E ) | id TT*F | FP | (E) | id FFP | (E) | id P(E) | id 只含变量EEA+T| T A*F|F AP| A(EA)| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+, A*, A, A(, A) 乔姆斯基范式-如何转换Gexp4：EE+T |

44、 T*F |FP| ( E ) | id TT*F | FP | (E) | id FFP | (E) | id P(E) | id 右部长度2的产生式中的终极符号用新的变量代替EEA+T| T A*F|F AP| A(EA)| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+, A*, A, A(, A) GexpCNF：EEA1| TA2|FA3| A(A4| idTTA2| FA3| A(A4 |idFFA3| A(A4|idPA(A4 |idA+, A*, A, A(, A) A1A+T, A2A*F, A3AP, A4EA) 乔姆斯基

45、范式-如何转换把所有右部长度2的产生式变换为右部长度=2的产生式乔姆斯基范式定理 6 - 9：对于任意CFG G，L(G)，存在等价的 CNF G2 。证明思想 CNF G2 的构造方法：假设G为化简过的文法构造CFG G1=(V1，T，P1，S) ，使得L(G1)=L(G)，且G1中的产生式都是形如 AB1B2Bm A a的产生式，其中，A，B1，B2，BmV1，aT，m22. 构造CNF G2 =(V1，T，P1，S) 使得L(G2)=L(G1)右端只含变量右端是一个终极符1. 构造G1=(V1，T，P1，S) ，使得L(G1)=L(G)，且G1中的产生式都是形如AB1B2Bm和Aa的产生

46、式，其中，A，B1，B2，BmV1，aT，m2 对于P中每个产生式A，如果 TV+，直接将其放入P1；否则， A X1X2Xm ，对于每个Xi：如果Xi =a T，则引人新变量Ba 和产生式Ba a（将它放入P1），并用Ba替换A中的Xi；如果XiV，则取Bi= Xi ；将处理后形如AB1B2Bm 的产生式放入P1。右端只含变量或只含一个终极符2. 构造CNF G2=(V2，T，P2，S)，使得L(G2)=L(G1)先将V1的变量全部放入V2 ，然后对于P1中的每个产生式A若 T，则直接放入P2若= A1A2Am ，m=2，则直接放入P2= A1A2Am ，m3时，引入新变量：B1、B2、Bm

47、-2，将G1的形如AA1A2Am的产生式替换成AA1B1B1A2B2Bm-2Am-1Am最后证明以上两步构造的正确性：证明被替换的产生式是等价的。已是CNF乔姆斯基范式举例S bA | aBA bAA | aS | aB aBB | bS | bS BbA | BaBA BbAA | BaS | aB BaBB | BbS | bBa aBb bS BbA | BaBA BbB1 | BaS | aB BaB2 | BbS | bBa aBb bB1 AAB2 BB第一步第二步定义 6 - 12： 如果 CFG G =（V, T, P, S）中所有产生式都有如下形式：A a ，其中， A V

48、，a T， V ，则 G 被称为格雷巴赫范式（ GNF ）GNF 产生式的两种形式： A a, A aA1A2 Am ( m1 ) 格雷巴赫范式例：S bA | aB A bAA | aS | a B aBB | bS | b右线性文法 1、将 G 转换成相应的 GNF G1； 2、 G1 按照最左派生模式推导符号串 a1a2am： 对 G1 的起始产生式从左向右扫描， 判断当前产生式右部句型中的最左变量是哪个候选产生式的左部符号， 以便选择那个产生式作为下一轮的派生式。问题：如何将给定 CFG 转换成 等价的 GNF ？给定 CFG G，判断字符串 a1a2am 是否为G的合法句子。格雷巴赫

49、范式应用由于GNF中不存-产生式，所以对任意的GNF G，L(G)。目标：对CFG G，当L(G)时，能够找到一个GNF G，使得 L(G)=L(G) 。即：经过化简的CFG，都有一个等价的GNF。 格雷巴赫范式引理 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 证明思路：G和G1除了A产生式不同，其他都相同仅需证明两个产生式组可以互相替换引理 6-2：证明思路 产生式组1中，

50、从A出发所能进行的所有最左派生都是如下形式： 产生式组2中，从A出发所能进行的最右派生都是如下形式：而在任意CFG中，任意一个派生序列，都对应有（唯一的）最左派生和最右派生，也就是说考虑CFG所能派生出来的符号串时，仅需考虑最左或最右派生即可步骤1：消除常元消除产生式 A = X1X2 X m 中所含常元 Xi (i=2) ( Xi = a T )，使 CFG G1 的产生式形式如下： A A1A2 Am， A a A1A2 Am-1， A a, 其中，Ai V1，a T， m2 例：设 CFG G = ( V, T, P, S ) P： A1 A2 b A3 | a A1 A2 A3 c A

51、3 | b A3 A1 c A3 | A2 bb | a CFG G1 = ( V B,C , T, P1, S ) P1：A1 A2 B A3 | a A1 A2 A3 C A3 | b A3 A1 C A3 | A2 BB | a B b C c定理 6-10：对于任意CFG G, L(G)，存在等价的GNF G1。步骤(2)：变量排序算法6-4输入：G1=(V1, T, P1, S)；输出：G2=(V2, T, P2, S);for k=1 to m do /排序for j=1 to k-1 do for 每个形如AkAj的产生式 do /对(kj)的产生式进行处理标记产生式AkAj。设

52、Aj1 |2 |n为所有Aj产生式，根据引理6-1，将产生式组Ak1 |2 |n添加到P2中 /处理左递归设Ak Ak 1 | Ak 2 | | Ak p 是所有右部第一个字符为Ak的Ak产生式， Ak 1 | 2 | | q 是所有其他的Ak产生式。据引理6-2，标记所有的Ak产生式，并引入新的变量B，将下列产生式添加到P2中：Ak 1 | 2 | | qAk 1 B | 2 B | | q B B 1 | 2 | | pB 1 B | 2 B | | p B将P1中未被标记的产生式全部添加到P2中。步骤(3)：根据引理6-1，从编号较大的变量开始，逐步替换，使所有产生式满足GNF的要求算法

53、6-5输入：G2=(V2, T, P2, S)；输出：G3=(V3, T, P3, S);for k=m-1 to 1 doif AkAjP2 & j k thenfor 所有的Aj产生式Aj do 将产生式Ak放入P3；for k= 1 to n do根据引理6-1，用P3中的产生式将所有的Bk产生式替换成满足GNF要求的形式。GNF转换举例G：A1 A2 b A3 | a A1 A2 A3 c A3 | b A3 A1 c A3 | A2 b b | a步骤(1)：引入变量B、C，改造为：A1 A2 B A3 | a A1A2 A3 C A3 | bA3 A1 C A3 | A2 BB |

54、 aB bC c只有A3不满足步骤(2)的要求步骤(2)：用A1产生式的所有候选式替换产生式A3 A1 C A3 中的A1，得到所有的A3产生式：A3 A2 B A3C A3 | a A1C A3| A2 BB | a再用A2产生式的所有候选式替换产生式A3 A2 B A3C A3和A3 A2 BB中的A2 ，得到所有的A3产生式：A3 A3 C A3 B A3C A3 | b B A3C A3 | a A1C A3| A3 C A3 BB | bBB |a引入变量B1，消除产生式中的左递归：A3 b B A3C A3 | a A1C A3| bBB |aA3 b B A3C A3 B1| a

55、 A1C A3 B1 | bBB B1 |a B1B1 C A3 B A3C A3 | C A3 BB B1 C A3 B A3C A3 B1 | C A3 BB B1 A1 A2 B A3 | a A1A2 A3 C A3 | bA3 A1 C A3 | A2 BB | aB bC c引理 6-2： A A 1 | A 2 | | A n A 1 | 2 | | m A 1 | 2 | | m A 1 B | 2 B | | m B B 1 | 2 | | n B 1 B | 2 B | | n B在我们的算法中1 | 2 | | m有何特征？步骤(3)：此时具有最大下标的A3产生式已经满足GNF的要求，将它们代入到还未满足要求的A2产生式，使其满足GNF的要求：A2 bBA3CA3CA3 | aA1CA3CA3 | bBBCA3 |aCA3 | bBA3CA3B1CA3 | a A1CA3B1CA3 | bBBB1CA3 | aB1CA3 |