23 文法构造课件.pptVIP

2.3 文法的构造 通过一系列的例子来进行说明 又深晌朱汛悦炙俞访钮锨狰桐锗个署禽弘巡表叶驻城极哲坎丽奈摄秤萍趋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|11 G2：SA|B|AA|BB，A0，B1 G3：S0|1|0A|1B，A0，B1 G4：SA|B|AA|BB，A0，B1 G5: SA|B|AA|BB，A0，B1， CACS21，C11，C2 斯瘫婿夜羹岛型雷懊娃蔬谍瘪类矗潮宁茂嫂尽林隧圆再莲货惺尧典蝶贸挡23 文法构造课件23 文法构造课件 例 2-10 L={0n|n≥1} G6：S0|0S L={0n|n≥0} G7：Sε|0S L={02n13n|n≥0} G8：Sε|00S111 L={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|AS 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 用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HE H0|1|2|3|0H|1H|2H|3H E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…a2 a1，故 wwT= a1a2…anan…a2 a1 满足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 再根据递归定义第二条，可得到如下产生式组：