上下文无关语言(精) .ppt
《上下文无关语言(精) .ppt》由会员分享,可在线阅读,更多相关《上下文无关语言(精) .ppt(108页珍藏版)》请在三一办公上搜索。
1、1,形式语言与自动机,第6章 上下文无关语言,2,文法的乔姆斯基体系,3型文法或正则文法Aw|wB,3,引言,上下文无关文法和它所描述的上下文无关语言,在定义程序设计语言、语法分析、简化程序设计语言的翻译等方面有重要意义。高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。近年来,上下文无关文法也被用来描述文档格式:XML 中使用的 DTD(文档类型定义)就是用来描述 Web 上的信息交换格式的。,4,主要内容,关于 CFL 的分析派生和归约、派生树CFG 的化简 无用符、单一产生式、空产生式CFG 的范式 CNF、GNFCFG 的自嵌套特性,5,6.1 上下文无关文法,文
2、法 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,表示由终极符号组成的行;,表示由语法变量和终极符号组成的行。,7,算术表达式的文法,算术表达式的文法 Gexp1:EE+T|E-T|TTT*
3、F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,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+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
4、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 G=(V,T,P,S),G 的派生树是满足如下条件的(有序)树(ordered tree):(1)树的每个顶点有一个标记 X,且 XVT。(2)树根的标记为 S。(3)如果一个非叶子顶点 v
5、 标记为 A,v 的儿子从左到右依次为 v1,v2,vn,并且它们分别标记为 X1,X2,Xn,则AX1X2XnP。(4)如果 X 是一个非叶子顶点的标记,则 XV。(5)如果顶点 v 标记为,则 v 是该树的叶子,并且 v 是其父顶点的惟一儿子。,11,上下文无关文法的派生树,别称生成树(derivation tree)、分析树(parse tree)、语法树(syntax tree)顺序v1,v2 是派生树 T 的两个不同顶点,如果存在顶点 v,v 至少有两个儿子,使得 v1 是 v 的较左儿子的后代,v2 是 v 的较右儿子的后代,则称顶点 v1 在顶点 v2 的左边,顶点 v2 在顶点
6、 v1 的右边。结果(yield)派生树 T 的所有叶子顶点从左到右依次标记为 X1,X2,Xn,则称符号串 X1X2Xn 是 T 的结果。一个文法可以有多棵派生树,它们可以有不同的结果。称“G 的结果为 的派生树”为 G 的对应于句型 的派生树,简称句型 的派生树。,12,上下文无关文法的派生树,派生子树(subtree)满足派生树定义中除了对根结点的标记的要求以外各条的树叫派生子树(subtree)。如果这个子树的根标记为 A,则称之为 A子树。惟一差别是根结点可以标记非开始符号。,13,定理6-1,定理6-1 设 CFG G=(V,T,P,S),S*的充分必要条件为 G 有一棵结果为 的
7、派生树。先证一个更为一般的结论:对于任意 AV,A*的充分必要条件为 G 有一棵结果为 的 A 子树。充分性:设 G 有一棵结果为 的 A子树,非叶子顶点的个数 n 施归纳,证明 A*成立。,14,定理6-1,当 n=0 时,结论显然成立。当 n=1 时,该 A 子树是一个二级子树。假设此树的叶子顶点的标记从左到右依次为 X1,X2,Xm,由定义6-1的第(3)条,必有 AX1X2XmP。注意到该子树的结果为,所以,X1 X2Xm=,故 A*。,15,定理6-1,设 nk(k1)时结论成立,往证当 n=k+1 时结论成立。设 A 子树有 k+1 个非叶子顶点,根顶点 A 的儿子从左到右依次为v
8、1,v2,vm,并且它们分别标记为 X1,X2,Xm。则必有 AX1X2XmP。设分别以 X1,X2,Xm 为根的子树的结果依次为 1,2,m,其中,当 Xi 为一个叶子的标记时,取 i=Xi。显然分别以 X1,X2,Xm 为根的子树的非叶子顶点的个数均不大于 k。,16,定理6-1,由归纳假设X1*1X2*2Xm*m而且=12mA X1X2Xm*1X2Xm*12Xm*12m即结论对 n=k+1 成立。由归纳法原理,结论对任意的 n 成立。,17,定理6-1,必要性。设 An,现施归纳于派生步数 n,证明存在结果为 的 A子树。当 n=0 时,结论显然成立。当 n=1 时,由 A 知 AP。令
9、=X1X2Xm,则有下图所示的A子树。所以,结论对 n=1 成立。,18,定理6-1,设 nk(k1)时结论成立,往证当 n=k+1 时结论也成立。令Ak+1,则有: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可以得
10、到 A 子树的上半部分。,然后再将所有的 Xi 子树对应地接在 Xi 所标识的顶点上,就可以得到树。,显然该树的结果为。所以结论对 n=k+1 成立。由归纳法原理,结论对任意的 n 成立。,20,例6-1 设Gbra:SS(S)|,()()和(S)(S)的派生树如下,可见派生树的结果可以是句子,也可以是句型。,21,如果顶点 v 标记为,则 v 是该树的叶子,文法 Gexp1 的句子 x+x/y2 对应的“派生树”,22,最左派生,最左派生(leftmost derivation)的派生过程中,每一步都是对当前句型的最左变量进行替换。左句型(left sentencial form)最左派生得
11、到的句型可叫做左句型。最右归约(rightmost reduction)与最左派生对相的归约叫做最右归约。,最右派生,最右派生(rightmost derivation)的派生过程中,每一步都是对当前句型的最右变量进行替换。右句型(right sentencial form)最右派生得到的句型可叫做右句型。最左归约(leftmost reduction)与最右派生对相的归约叫做最左归约。,24,规范派生,规范派生(normal derivation)最右派生。规范句型(normal sentencial form)规范派生产生的句型。规范归约(normal reduction)最左归约。,25
12、,最左派生与最右派生,定理6-2 如果 是 CFG G 的一个句型,则 G 中存在 的最左派生和最右派生。基本思路:对派生的步数 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
13、,所用的步数 nik,由归纳假设,存在与之对应的 Xi 到i 的最左派生: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
14、*EE EE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,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 是二义性的。否则 G 为非二义性的。G
15、exp2 是二义性的,但 Gexp1 是非二义性的,但二者是等价的。即L(Gexp1)=L(Gexp2)判定任给 CFG G 是否为二义性的问题是一个不可解的(unsolvable)问题。,31,Gexp1是非二义性的,算术表达式的文法 Gexp1:EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E,语法变量的含义 E表达式(expression)T项(term)F因子(factor)P初等量(primary)N函数名(name of function)L列表(list)id标识符(identifier),32
16、,例6-2,下列是描述高级程序设计语言的 if 语句的不同文法,其中,Gifa 是二义性的,Gifm 和 Gifh 是为了消除 Gifa 的二义性而对其进行改造的结果。Gifa:Sif E then S else S|if E then SGifm:SU|MUif E then SUif E then M else UMif E then M else M|SGifh:STS|CSCif E thenT CS else 但是,二者都没有完全消除二义性。,33,例6-3,设 Lambiguity=0n1n2m3m|n,m1 0n1m2m3n|n,m1 可以用如下文法产生语言 Lambiguity
17、:G:SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2 语言 Lambiguity不存在非二义性的文法。,S AB 0A1B 0011B 00112B3 00112233,S 0C3 00C33 001D233 00112233,34,二义性,固有二义性的(inherent ambiguity)如果语言 L 不存在非二义性文法,则称 L 是固有二义性的,又称 L 是先天二义性的。文法可以是二义性的。语言可以是固有二义性的。一般地,不说文法是固有二义性的,也不说语言是二义性的。若干语言歧义的例子(1)下雨天留客天留我不留。下雨天留客,天留,我不留。下雨天,留客天,留
18、我不?留!(2)父在母先亡。“在”可作 动词(exists)或介词(before,at)有不同意义。,35,二义性,在机器翻译系统中P=“capital of China”如何翻译?中国的首都(北京)或 瓷都(景德镇)有歧义用前后文信息 排歧 x China y x 中国 yu China v u 瓷器 v 诡辩术“断章取义”的 语言学本质:前后相关语言中,去掉W 的前后文,在 W 的释义集合中,选择有利于自己的意义。,36,6.1.3 自顶向下的分析和自底向上的分析,对于一个给定的文法,如何判断一个符号串是否为该文法的句子?可以考察是否可以从该文法的开始符号派生出此符号串。也可以考察这个符号
19、串是否可以归约成文法的开始符号。,37,自顶向下的分析方法,自顶向下的分析方法通过考察是否可以从给定文法的开始符号派生出一个符号串,可以判定一个符号串是否为该文法的句子。例S aAb|bBaA aAb|bBaB d aabdabb 的派生树的自顶向下的“生长”过程,S,38,自底向上的分析方法,自底向上的分析方法通过考察是否可以将一个符号串归约为给定文法的开始符号,完成判定一个符号串是否为该文法的句子的任务。和归约与派生是互逆过程相对应,自顶向下的分析与自底向上的分析互逆的分析过程。,39,aabdabb 的派生树的自底向上的“生长”过程,40,6.2 上下文无关文法的化简,给定文法:G1:S
20、 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|0C|1C D1|1D|2D E0E2|E02,去掉无用符号后的文法G2:S0|0AA|0A|1A|BB_CC0|1|0C|1C,去掉产生式 A后的文法G3:S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C,去掉产生式AB后的文法G4:S0|0AA0|1|0A|1A|_CC0|1|0C|1C,可以去掉文法中的无
21、用符号、产生式和单一产生式。,42,去无用符号,无用符号(useless symbol)对于任意 XVT,如果存在 wL(G),X 出现在 w 的派生过程中,即存在,(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 都是有穷的。从而有可能构造出有
22、效的算法,来完成消除文法的无用符号的工作。,43,去无用符号,根据定义判断一个符号是否有用,需从两个方面进行分析:(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 中不含派生不出
23、终极符号行的变量,并且 L(G)=L(G)。主要步骤:(1)OldV=;(2)NewV=A|AwP 且 wT*;(3)while OldVNewV dobegin(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 步可以派生出终极符号
24、行的变量放入NewV。这个循环一直进行下去,直到所给文法 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)L
25、(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 dobegin(6)OldV=NewV;(7)OldT=NewT;(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上下文无关语言精 上下文 无关 语言

链接地址:https://www.31ppt.com/p-2206800.html