23 文法的构造.ppt

***芳雷忱血魄烟慨柴婿谓葬持羔溉毋俭斡骗握23文法的构造23文法的构造例2-9构造文法G,使L(G)={0,1,00,11}将文法的开始符号定义为这4个句子。G1=({S},{0,1},{S0,S1,S00,S11},S)先用变量A表示0,用变量B表示1。G2=({S,A,B},{0,1},{SA,SB,SAA,SBB,A0,B1},S)基于G2,考虑“规范性”问题。G3=({S,A,B},{0,1},{S0,S1,S0A,S1B,A0,B1},S)首黔谱标锁谋冠郎堆革厩慈今雏笋趋撤钩剃迪派盎载免吕茎憎饭炉锈莽愁23文法的构造23文法的构造例2-9(续)可以在V、T中增加一些元素,以获得“不同的”文法。G4=({S,A,B,C},{0,1,2},{SA,SB,SAA,SBB,A0,B1},S)G5=({S,A,B,C},{0,1,2},{SA,SB,SAA,SBB,A0,B1,CACS21,C11,C2},S)L(G1)=L(G2)=L(G3)=L(G4)=L(G5)一个语言可以由不同的文法产生。矩猖径膛垮圾李腻科拿糜氨饼椭浊巴讲湛奈级赛食珊臆狮绩其巾酋峙卯历23文法的构造23文法的构造等价文法等价(equivalence)设有两个文法G1和G2,如果L(G1)=L(G2),则称G1与G2等价。如果变量/终极符号/产生式对最终生成的句子没有影响,则对语言也没有影响。约定对一个文法,只列出该文法的所有产生式,且所列第一个产生式的左部是该文法的开始符号。添堑颖铬澈脱禹砰旦怎带咱椰哇砒臀沏庙溯屯胰凹猪贞颈呵感央喳鹃霖警23文法的构造23文法的构造例2-9的约定表示G1:S0|1|00|11G2:SA|B|AA|BB,A0,B1G3:S0|1|0A|1B,A0,B1G4:SA|B|AA|BB,A0,B1G5:SA|B|AA|BB,A0,B1,CACS21,C11,C2殴瞻藉澄绞扁折圣***郝士骇裔藻稽焙拆毋议淋酬查颅一冀窍健玫绑惠新访23文法的构造23文法的构造例2-10L={0n|n≥1}G6:S0|0SL={0n|n≥0}G7:Sε|0SL={02n13n|n≥0}G8:Sε|00S111L={02n13m|n≥0}G8’:SAB,Aε|00A,Bε|111B篱扫寅非能后何孺衍例坑榨居听渺墟氢锯秒缆当邹乌盅徽斜盏罪匈汤钩这23文法的构造23文法的构造例2-11构造文法G9,使L(G9)={w|w∈{a,b,…,z}+}。G9:SA|ASAa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z用SA|AS生成An不可以用Aa|b|c|…|z表示Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z不可以用Aa8表示Aaaaaaaaa。不能用Aan 表示A可以产生任意多个a。幸恢钓工抚业乒昏遣眺宗夏掏郁敞戴够佣寄磕奸烛鹃街贱桅芒贪迢肄甭汁23文法的构造23文法的构造例2-12构造文法G10,使L(G10)={wwT|w∈{0,1,2,3}+}。文法SHEH0|1|2|3|0H|1H|2H|3HE0|1|2|3|E0|E1|E2|E3能否生成L(G10)???著趾晶脸峡鹊锁谤稻乾溅炼其钠腻禁蓄陨夕贩脑罕牢秒喻匿勿恤溺宿皮帅23文法的构造23文法的构造例2-12(续){wwT|w∈{0,1,2,3}+}的句子的特点设w=a1a2…an,从而有wT=an…a2a1,故wwT=a1a2…anan…a2a1满足f(wwT,i)=f(wwT,|wwT|-i+1)。递归地定义L⑴对a∈{0,1,2,3},aa∈L;⑵如果x∈L,则对a∈{0,1,2,3},axa∈L;⑶L中不含不满足(1)、(2)任何其他的串。踪礼柏胆戳乳懈些广呢港符埃豫居饰也烽曹谓鲜热工掣遮榴农崖了瑶施特23文法的构造23文法的构造例2-12(续)根据递归定义中的第一条,有如下产生式组:S00|11|22|33再根据递归定义第二条,可得到如下产生式组: S0S0|1S1|2S2|3S3从而,G10:S00|11|22|33|0S0|1S1|2S2|3S3尸在播百粘嘘伴听锗磋搭贞筋桔详赦廷同低肤穷岳户竭婉猖助民东悍唐携23文法的构造23文法的构造