1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory胡春明胡春明 邓婷邓婷 赵永望赵永望 第六、八章第六、八章 上下文无关语言及性质上下文无关语言及性质第六章第六章 上下文无关语言上下文无关语言上下文无关文法的引入上下文无关文法的引入上下文无关文法的派生上下文无关文法的派生上下文无关文法的化简上下文无关文法的化简上下文无关文法的规范形式上下文无关文法的规范形式上下文无关语言的性质上下文无关语言的性质文法的乔姆斯基体系：文法的乔姆斯基体系：语言之间的包含关系语言之间的包含关系0型语言型语言上下文有上下文有关语言关语言上下文无上下文无关语言关语言
2、正则语言正则语言设设 G= ( V, T, P, S )，P= ， ( V T )+， ( V T )* G ：0 型文法型文法，或，或短语结构文法（短语结构文法（PSG） L(G)： 0 型语言或型语言或 短语结构语言（短语结构语言（PSL）、递归可枚举集。递归可枚举集。 对于对于 P，均有，均有 | | | | G：为：为 1 型文法型文法，上下文有关文法（上下文有关文法（CSG） L(G): 1 型语言或型语言或上下文有关上下文有关语言语言 ( CSL )对于对于 P, 均有均有 | | | |, 且且 V G：为：为 2 型文法型文法，上下文无关文法（上下文无关文法（CFG） L(G)
3、: 2型语言或型语言或上下文无关上下文无关语言语言 ( CSL )对于对于 P, 均具有以下形式：均具有以下形式：A ， A B G：为：为 3型文法型文法，正则文法，正则文法(RG) L(G): 3型语言或正则语言型语言或正则语言 ( RL )关于乔姆斯基关于乔姆斯基u麻省理工学院语言学的荣誉退休教授u美国科学杂志评选出的20世纪全世界前10名最伟大的科学家中目前唯一的在世者uhttp:/zh.wikipedia.org/wiki/乔姆斯基uhttp:/ 正则文法与词法分析：单词的识别例：八进制数无符号整数的识别正则表达式：0+(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+
4、6+7+8+9)*上下文无关文法的提出（续）上下文无关文法的提出（续）例：, , =, 的识别上下文无关文法的提出（续）上下文无关文法的提出（续）例：number的识别例：回文不是正则语言上下文无关文法的提出（续）上下文无关文法的提出（续）回文：正向和反向读起来都一样的字符串Madamimadam Madam, Im adam Able was I ere I saw Elba在我看到厄尔巴岛之前，我曾所向无敌u 0和1上的回文语言 Lpal 不是正则语言上下文无关文法的提出（续）上下文无关文法的提出（续）证明思想：泵引理泵引理泵引理：设 L 为 RL，存在仅依赖于语言 L 的某个正整数 n，
5、对于 z L， 如果 | z | n，则存在 u, 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上下文无关
6、文法的提出（续）上下文无关文法的提出（续）u 0和1上的回文语言 Lpal 不是正则语言u 0和1上的回文语言 Lpal的文法：1.一个回文的开头和结尾的字母一定相同一个回文的开头和结尾的字母一定相同2.一个回文去掉开头和结尾的字母后还是一个回文一个回文去掉开头和结尾的字母后还是一个回文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上下文无关文
7、法的提出（续）上下文无关文法的提出（续）u 正则语言描述模型能力有限，无法描述高级程序设计语言表正则语言描述模型能力有限，无法描述高级程序设计语言表达式中达式中 “良嵌套良嵌套”的括号对、的括号对、( begin end ) 以及以及HTML中标中标记对记对 等配对符号序列的语法规则等配对符号序列的语法规则例例: 文法文法 Gbal = (B, ( , ) , P, B) BBB | (B) | 能够产生所有的括号匹配的串。能够产生所有的括号匹配的串。, (), ()(), ()()()()()同样可由正则语言的泵引理证明Gbal不是正则语u BNF：Backus normal form，巴克
8、斯范式，又叫，巴克斯范式，又叫Backus-naur form，是，是CFG的一种特殊形式，在计算机中很常见，常的一种特殊形式，在计算机中很常见，常用于表达语言的文法结构用于表达语言的文法结构上下文无关文法上下文无关文法文法文法 G =（V，T，P，S）称为上下文无关文法，如果）称为上下文无关文法，如果 对于对于所有产生式所有产生式 P，均有均有 | | | | 且且 V, ( V T ) “上下文无关上下文无关”：对于所有对于所有 A V，如果，如果 A P，则无论，则无论 A 出现在句型的什么位置，都可以用出现在句型的什么位置，都可以用 自由替换自由替换 A，无需考虑，无需考虑 A 出现的
9、上下文出现的上下文“上下文有关上下文有关”： A BcD, Bc aEF, CD bGH文法Gpal=(P, 0,1, A, P) P |0|1 P 0P0|1P1第六章 上下文无关语言及其性质上下文无关文法的引入上下文无关文法的引入上下文无关文法的派生上下文无关文法的派生上下文无关文法的化简上下文无关文法的化简上下文无关文法的规范形式上下文无关文法的规范形式上下文无关语言的性质上下文无关语言的性质上下文无关文法的派生上下文无关文法的派生u 一个句子可能有多个派生例：给定文法：Gexpl: E E+T | E-T | T TT*F | T/F| F FF P | P P (E) | N(L)
10、| 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派生1与2使用了相同的变量替换，仅顺序不一样： EE+T, ET, TF, FP, Px, TT/F, TF,
11、 FP, Px, FF P, FP, Py, P2 如何体现句子结构的本质？如何体现句子结构的本质？上下文无关文法的派生上下文无关文法的派生u用树表示句子的结构 例：给定文法：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变量替换：EE+T, ET, TF, FP, Px, TT/F, TF, FP, Px, FF P, FP, Py, P2派生树派生树：略去变量替换的顺序，只保留所需的替换EE+T上下
12、文无关文法的派生上下文无关文法的派生派生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定义定义6-1：设有：设有 CFG G = （ V, T, P, S ），G 的的派生树派生树是满足如下条件的是满足如下条件的有序树有序树： 1、树的、树的每个节点每个节点都有一个标记都有一个标记
13、 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 是是该树的该树的叶节点叶节点，并且，并且，v 是其父节点的是其父节点的唯一子唯一子节点节点 上下文无关文法的派生上下文无关文法的派生生
14、成树、分析树(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的一棵派生树的一棵
15、派生树T，T的的所有叶子顶点所有叶子顶点从左到右依次标记为从左到右依次标记为X1,X2,Xn，则称，则称符号串符号串X1X2Xn是是T的结果的结果。G的结果为的结果为a的派生树，简称的派生树，简称句型句型a的派的派生树生树v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v16v17v20v19v18v5在v6的左边v18在v20的左边 x+x/y 2是T的结果T是x+x/y 2的派生树定义定义6-1：设有：设有 CFG G = （ V, T, P, S ），G 的的派生子树派生子树是满足如下条件是满足如下条件的的有序树有序树： 1、树的、树的每个节点每个节点都有一个标记
16、都有一个标记 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 是该树的是该树的叶节点叶节点，并且，并且，v 是其父节是其父节点的唯一子点的唯一子节点节点 派生子树（派生树去掉第二个条
17、件）派生子树（派生树去掉第二个条件）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 N sin | cos | exp
18、 | 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=0n=0时，时，A-A-子树只有一个叶子节点，显然结论成立；子树只有一个叶子节点，显然结论成立； n=1时，A-子树是一个二级子树（只有一个根节点，
19、子树是一个二级子树（只有一个根节点，其他均为叶子节点）其他均为叶子节点） ；假设所有叶子节点为；假设所有叶子节点为X1, Xm, 则由则由A-子树的定义知，必有子树的定义知，必有A X1 Xm PP 又由于该又由于该 A-A-子树的结果为子树的结果为，故，故X1 Xm = ，因，因此有此有A 定理定理 6 1：设设 CFG G =（ V, T, P, S ），）， S 的充分必要的充分必要条件为条件为 G 有一棵结果为有一棵结果为 的派生的派生树树AX1X2Xm证明（续）证明（续） 假设当假设当n nk（k 1）时，结论成立）时，结论成立 ，下面证明当，下面证明当n=k+1地时结地时结论成立。
20、论成立。 设设A-子树有子树有k+1个非叶子顶点，根顶点个非叶子顶点，根顶点A的儿子从左到右依次的儿子从左到右依次为为v1，v2，vm，并且它们分别标记为，并且它们分别标记为X1，X2，Xm ，则必有则必有AX1X2XmP ，且，且以以X1，X2，Xm为根的子树为根的子树的结果依次为的结果依次为1，2，m 。 显然，以显然，以X1，X2，Xm为根的子树的非叶子顶点的个数为根的子树的非叶子顶点的个数均不大于均不大于k。由归纳假设知。由归纳假设知X11X X2 22X Xm mm而且而且=1 12 2m mAX1X2Xm 1X2Xm 12Xm 12m结论成立结论成立证明（续）：证明（续）：证证一个
21、更为一般的结论：一个更为一般的结论：对于任意对于任意AV，A的充分必要条件为的充分必要条件为G有一棵结果为有一棵结果为的的A-子树子树。 定理定理 6 1：设设 CFG G =（ V, T, P, S ），）， S 的充分必要的充分必要条件为条件为 G 有一棵结果为有一棵结果为 的派生的派生树树 必要性必要性：设：设A A，对派生对派生步数步数n n进行归纳进行归纳，证明存在结证明存在结果为果为的的A A子子树树。 n=0 n=0时，时，A= , A= , 结论成立；结论成立； n=1 n=1时，由时，由A A知知 A APP；令；令=X1=X1XmXm, , 则可则可构造一棵构造一棵A A子
22、树（如下图所示）子树（如下图所示）, , 结论成立。结论成立。AX1X2Xm证明（续）证明（续） 设设n n k(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 其中，对于任意的其中，对于任意的i i， 1 1im, 有有Xi i i 显然，所用步数显然，所用步数 k，由归纳假设知道，存在以，由归纳假设知道，存在以i i为结果的为结果的XiXi子树。子树。又由于又由于 A A X X
23、1 1X X2 2X Xm m P, P,从而可以得到从而可以得到A A子树的上半部分，子树的上半部分，把所有的把所有的Xi-Xi-子树对应地接在子树对应地接在XiXi所标识的顶点上，从而得所标识的顶点上，从而得到到A-A-子树。所以结论对子树。所以结论对n=k+1n=k+1成立成立 。定义定义 6 5：设：设 CFG G =（ V, T, P, S ）， 是是 G 的一个句型的一个句型。如果如果在在 的派生过程中的派生过程中， 每每一步都是对当前句型的一步都是对当前句型的最左变量最左变量进行替换，则该派生为进行替换，则该派生为最最左派生左派生，每一步所得到的句型叫做，每一步所得到的句型叫做左
24、句型左句型。 每每一步都是对当前句型的一步都是对当前句型的最右变量最右变量进行替换，则该派生为进行替换，则该派生为最最右派生右派生，每一步所得到的句型叫做，每一步所得到的句型叫做右句型右句型。最左派生被视为规范派生最左派生被视为规范派生，常被计算机系统用来处理输入字符串。，常被计算机系统用来处理输入字符串。多种派生方式多种派生方式例：文法：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
25、 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, 均有以下形式：均有以下形式：| | | |， V, ( V T ) 一次替换可能产生多个变量一次替换可能产生多个变量多种派生方式多种派生方式正则文法有没有多种派生方式？正则文法有没有多种
26、派生方式？ 没有没有 对任意的对任意的 P, 均有以下形式：均有以下形式：A , A B , A, B V, T+ 一次替换只产生一个变量一次替换只产生一个变量为什么上下文无关文法有多种派生方式？为什么上下文无关文法有多种派生方式？派生树派生树定理定理 6 2：如果如果 是是 CFG G 的一个句型，则的一个句型，则G中存在中存在 的最的最左派生和最右派生左派生和最右派生。证明思路证明思路：对派生的步对派生的步数数 n 施施归纳归纳，证明对于任意，证明对于任意AV，如果如果An，在，在G中，存在对应的中，存在对应的从从A到到的最左派的最左派生生An左左。 AX1X2Xm *1X2Xm *12X
27、m *12mA左左X1X2Xm *左左1X2Xm *左左12Xm *左左12m 同理可证，句型同理可证，句型有最右派生。有最右派生。 上下文无关上下文无关文法的二义性文法的二义性例：文法：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
28、/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)/(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
29、 2” 可对应多种不同的派生树可对应多种不同的派生树：上下文无关文法上下文无关文法的二义性的二义性定理定理 6 - 6：设有设有 CFG G=(V, T, P, S)，如果存在，如果存在w L(G)，w至少有两棵不至少有两棵不同的派生树同的派生树，则称，则称G是二义性的（是二义性的（ambiguity）；否则，）；否则，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是二义
30、性的例：文法：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/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/
31、y 2 x+x/y 2非二义性的文法非二义性的文法Gexp1是非二是非二义性文法义性文法派生树唯一派生树唯一派生不一定唯一派生不一定唯一去除文法的二义性去除文法的二义性u 判断一个CFG 是否有二义性是不可判定的（Undecidable）定义定义6-7 如果语言如果语言 L 不存在非二义性方法，则不存在非二义性方法，则L是是固固有二义性有二义性的，又称的，又称 L 是先天二义性的是先天二义性的 文法可以二义性的；语言可以是固有二义性的； 一般不说文法是固有二义性的，也不说语言是二义性的如何去除文法的二义性？如何去除文法的二义性？消除二义性消除二义性例例6-2 消除消除二义性。二义性。Gifa：
32、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 派生与归约派生与归约u 问题：设有设有 CFG G=(V, T, P, S)和字符串和字符串w T*，判断是否判断是否w L(G)u 两类方法两类方法p 自顶向
33、下的分析方法自顶向下的分析方法p 自底向上的分析方法自底向上的分析方法例：文法例：文法 S aAb| bBa A aAb| bBa Bd判断判断aabdabb是否为该文法的句子是否为该文法的句子S aAb aaAbb aabBabb aabdabb自顶向下自顶向下自底向上自底向上第六章 上下文无关语言及其性质上下文无关文法的引入上下文无关文法的引入上下文无关文法的派生上下文无关文法的派生上下文无关文法的化简上下文无关文法的化简上下文无关文法的规范形式上下文无关文法的规范形式上下文无关语言的性质上下文无关语言的性质问题提出：问题提出：根据语言的结构特征构造文法时，由于使用的符号及定义根据语言的结
34、构特征构造文法时，由于使用的符号及定义的产生式不恰当，可能会引入一些多余或者错误的符号。的产生式不恰当，可能会引入一些多余或者错误的符号。文法的化简规则文法的化简规则例：设语言例：设语言 L = 0 x | x 0,1 * 0 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 文法的化简规则文法的化简规则1、识别、识别G1 中的无用符号：中的无用符号：1) 终结终结符符 2 没在没在L中出现，因此不中
35、出现，因此不应出，应出，相关产生式无用相关产生式无用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 + ，文法的化简规则文法的化简规则G2: S 0 | 0A | E A | 0A | 1A|B B_
36、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保持方法语保持方法语义不变义不变例：设语言例
37、：设语言 L = 0 x | x 0,1 * 0 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 的派生过程中的派生过程中，即，存在
38、即，存在 , ( V T ) *，使得，使得S X w则称则称 X 是有用的是有用的；否则，称；否则，称 X 是无用符号是无用符号。文法的化简文法的化简规则规则1 - 删除无用符号删除无用符号u 直观理解：文法直观理解：文法G=(V, T, P, S) 中的中的不在任何句子不在任何句子的派生中出现的符号的派生中出现的符号都是无用的都是无用的 X是是可达的可达的 X是是可终止的可终止的（产（产生的）：存在生的）：存在w T*，使得，使得Xw 有穷语法使得可有穷语法使得可以设计算法来删除以设计算法来删除无用符号无用符号 例：考虑文法例：考虑文法文法的化简文法的化简规则规则1 - 删除无用符号删除无
39、用符号p B以外的符号都是可终止的 S a, A b, a与b产生它们自己S AB | aA bS aA bp 只有S, a可达S ap 不存在无用符号（均可达和可终止）输入： CFG=(V, T, P, S) （算法（算法6-1） 输出： CFG G=(V, T, P, S)，其中V不含非终止符，且L(G)=L(G)1.OLDV=;2.NEWV=A| A w P 且 w T*;3.While OLDV NEWV do4. begin5. OLDV=NEWV;6. NEWV=OLDVA|AP且(TOLDV)*;7. end8. V= NEWV;9. P=AP且AV且(TV)*;V 包含所有有用
40、语法变元；包含所有有用语法变元；从从 P 中挑选与中挑选与V 、T 中中变元变元A 终结符号终结符号 a 相关的相关的产生式，构成产生式，构成 P u 删除不可终止符号p 计算文法G=(V, T, P, S) 的所有可终止符号文法的化简文法的化简规则规则1 - 删除无用符号删除无用符号基础：基础：T中每个符号都是可终止的中每个符号都是可终止的归纳：归纳：对于产生式对于产生式A，并且，并且中的符号都是可终止的，则中的符号都是可终止的，则A 是可终止是可终止定理定理6-4 算法6-1是正确的证明：证明：(1) 对任意的对任意的A V，A被放入被放入V的充分必要的充分必要条件是存在条件是存在w T*
41、, A= w (2) L(G)=L(G)u 删除可终止符号p 计算文法G=(V, T, P, S) 的所有可终止符号文法的化简文法的化简规则规则1 - 删除无用符号删除无用符号(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)1. OLDV=;2. NEWV=A| A w P 且 w T*;3. Whi
42、le OLDV NEWV do4. begin5. OLDV=NEWV;6. NEWV=OLDVA|AP且(TOLDV)*;7. end8. V= NEWV;9. P=AP且AV且(TV)*;n=0时，显然成立n=k+1时，AX1Xm P，其中Xi是终极符号或OLDV中符号且来自于第k次循环，由归纳假设知Xi* w P u 删除不可达符号删除不可达符号p , ( V T )*，使得，使得 S X ：正向地查正向地查找在句型推导中出现的语法变元与终结符号找在句型推导中出现的语法变元与终结符号文法的化简文法的化简规则规则1 - 删除无用符号删除无用符号基础：基础：S 显然是可达的显然是可达的归纳：
43、归纳：对于产生式对于产生式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被放入被放入NEWV或者或者NEWT的充分必要条件是存在的充分必要条件是存在, (NEWV NEWT)*
44、,使得使得 S=n X , n 0 (2) L(G)=L(G)u 删除不可达符号删除不可达符号文法的化简文法的化简规则规则1 - 删除无用符号删除无用符号定理定理 6 6： 对于任意对于任意 CFL L，L ，存在不含无用符号的存在不含无用符号的 CFG G2，并，并有有 L(G2) = L。证明：证明：设设 L 为为 CFL，一定存在，一定存在 CFG G，使得，使得 L(G)= L。3、输出文法、输出文法 G22. 将将 G1 作为输入，运行算法作为输入，运行算法 6-2 得得 G2，G2 中已删除中已删除 G1 产产生式中所有无用终结符号。生式中所有无用终结符号。1. 用用算法算法 6-
45、1 对对 G 进行处理，可得进行处理，可得 G1，G1 中所有变元都可中所有变元都可用于派用于派生终结符生终结符号串号串 w，并且，并且， L(G1)= L(G)。文法的化简文法的化简规则规则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可终止可达可
46、达可达可终止文法的化简文法的化简规则规则2 - 删除删除- 产生式产生式定义定义 6 9： 形形如如A 的产生式叫作的产生式叫作 产生式产生式( -production)，又称为，又称为空产生式空产生式 (null production)。对。对于文法于文法 G=(V, T, P, S) 中的任意变量中的任意变量A，如果，如果A=+ ，则称则称 A为为可空可空 (nullable) 变量变量。消除消除A ： 当当 L(G)时，可以消除所有的时，可以消除所有的-产生式产生式 当当 L(G)时，可以先构造出语言时，可以先构造出语言L(G)，然后，然后再加上产生式再加上产生式S .定理定理2-5 一
47、定存在与一定存在与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 | 01 A 2A | 2正确地删去正确地删
48、去u 不能简单所有不能简单所有- 产生式产生式增加增加 A2A无法消除无法消除补充补充A2, S01u 基本思想：基本思想：对任意的对任意的AX1Xm Pp 找出找出X1,Xm中所有中所有可空变量可空变量，构成集合，构成集合U;p 对于对于U中的中的所有子集所有子集 H，从，从AX1Xm 中删去中删去H中的变量；中的变量；p 避免产生新的避免产生新的- 产生式产生式：若：若X1, , Xm都为可空都为可空变量，则不可将变量，则不可将X1,Xm同时删除同时删除文法的化简文法的化简规则规则2 - 删除删除- 产生式产生式例：例：考虑文法考虑文法文法的化简文法的化简规则规则2 - 删除删除- 产生式
49、产生式 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 aAA| aA | a 可空变量集合可空变量集合A,B的子集：的子集： , A, B, AB 不能把不能把AB都去掉都去掉 G1: S AB|A|B A aAA | aA| a B bBB | bB| bu求可空变量集求可空变量集 A | A np从从 A 开始，逆向地找出包含所有与开始，逆向地找出包含所有与 A 有有关的可空变量集合关的可空变量集合 文法的化简文法的化简规则规则2 -
50、 删除删除- 产生式产生式基础：基础：对任意的对任意的A P ，A是可空变量是可空变量归纳：归纳：对任意的对任意的A P ，如果，如果中的变量都是可空变量，中的变量都是可空变量， 则则A也是可空变量也是可空变量数学归纳法证明数学归纳法证明算法的正确性算法的正确性算法算法6-3文法的化简文法的化简规则规则2 - 删除删除- 产生式产生式定理定理 6 7：对于任意对于任意 CFC G，存在，存在不含不含 的的 CFG G使得使得 L(G)=L(G) 证明思想：证明思想：1.算法算法6-3 求出可空变量集合求出可空变量集合2. 对任意的对任意的AX1Xm P 找出找出X1,Xm中所有可空变量，构成集
