文法的构造.pptx

例例2-9n构造文法构造文法G，使，使L(G)=0，1，00，11 n将文法的开始符号定义为这将文法的开始符号定义为这4个句子。个句子。nG1=(S，0，1，S0，S1，S00，S11，S)n先用变量先用变量A表示表示0，用变量，用变量B表示表示1。nG2=(S，A，B，0，1，SA，SB，SAA，SBB，A0，B1，S)n基于基于G2，考虑，考虑“规范性规范性”问题。问题。nG3=(S，A，B，0，1，S0，S1，S0A，S1B，A0，B1，S)例例2-9（续）（续）n可以在可以在V、T中增加一些元素，以获得中增加一些元素，以获得“不不同的同的”文法。文法。nG4=(S，A，B，C，0，1，2，SA，SB，SAA，SBB，A0，B1，S)nG5=(S，A，B，C，0，1，2，SA，SB，SAA，SBB，A0，B1，CACS21，C11，C2，S)L(G1)=L(G2)=L(G3)=L(G4)=L(G5)一个语言可以由不同的文法产生。一个语言可以由不同的文法产生。等价文法等价文法n等价等价(equivalence)n设有两个文法设有两个文法G1和和G2，如果，如果L(G1)=L(G2)，则称则称G1与与G2等价。等价。n如果变量如果变量/终极符号终极符号/产生式对最终生成的产生式对最终生成的句子没有影响，则对语言也没有影响。句子没有影响，则对语言也没有影响。n约定约定n对一个文法，只列出该文法的所有产生式，对一个文法，只列出该文法的所有产生式，n且所列第一个产生式的左部是该文法的开始且所列第一个产生式的左部是该文法的开始符号。符号。例例2-9的约定表示的约定表示G1：S0|1|00|11G2：SA|B|AA|BB，A0，B1G3：S0|1|0A|1B，A0，B1G4：SA|B|AA|BB，A0，B1G5:SA|B|AA|BB，A0，B1，CACS21，C11，C2例例 2-10nL=0n|n1 G6：S0|0S nL=0n|n0 G7：S|0SnL=02n13n|n0 G8：S|00S111nL=02n13m|n0 G8：SAB,A|00A，B|111B例例2-11 n构造文法构造文法G9，使，使L(G9)=w|wa，b，z+。G9：SA|AS Aa|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 n用用SA|AS生成生成 An n不可以用不可以用Aa|b|c|z表示表示Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zn不可以用不可以用Aa8表示表示Aaaaaaaaa。n不能用不能用Aan表示表示A可以产生任意多个可以产生任意多个a。例例2-12n构造文法构造文法G10，使使L(G10)=wwT|w0，1，2，3+。文法文法SHEH0|1|2|3|0H1H|2H|3HE0|1|2|3|E0|E1|E2|E3能否生成能否生成L(G10)？例例2-12（续）（续）nwwT|w0，1，2，3+的句子的特点的句子的特点 设设w=a1a2an，从而有，从而有wT=ana2 a1，故故 wwT=a1a2anana2 a1 满足满足f(wwT，i)=f(wwT，|wwT|-i+1)。递归地定义递归地定义L n 对对 a0，1，2，3，aaL；n如如 果果 xL，则则 对对 a0，1，2，3，axaL；n L中不含不满足中不含不满足(1)、(2)任何其他的串。任何其他的串。例例2-12（续）（续）n根据递归定义中的第一条，有如下产生式组：根据递归定义中的第一条，有如下产生式组：S00|11|22|33n再根据递归定义第二条，可得到如下产生式组：再根据递归定义第二条，可得到如下产生式组：S0S0|1S1|2S2|3S3n从而，从而，G10：S00|11|22|33|0S0|1S1|2S2|3S3 例例2-13n构造文法构造文法G12，使使L(G12)=w|w是十进制有理数是十进制有理数。n解：易知有理数分为负有理数和非负有理数，解：易知有理数分为负有理数和非负有理数，以以S为开始符号，有为开始符号，有 S R|+R|R 其中其中R表示非负有理数表示非负有理数n R又可以划分成无符号整数、无符号带小数和无又可以划分成无符号整数、无符号带小数和无符号纯小数符号纯小数 R N|B|P例例2-13(续续)nB N.D P 0.Dn由于由于B表示的为无符号带小数，表示的为无符号带小数，N不应以不应以0开始：开始：N AM A 1|2|3|4|5|6|7|8|9M为任意的十进制数串，包括为空为任意的十进制数串，包括为空M|0M|1M|2M|3M|4M|5M|6M|7M|8M|9Mn与之相对应，与之相对应，D不应以不应以0结束，而其余部分可以结束，而其余部分可以是任意的十进制数串，包括为空是任意的十进制数串，包括为空D MA例例2-13(续续)S R|+R|R|0R N|B|PB N.D P 0.DN AM D MAA 1|2|3|4|5|6|78|9M|0M|1M|2M|3M|4M|5M|6M|7M|8M|9M思考思考与书上的结果有什么不同？与书上的结果有什么不同？不允许不允许D为为0(会对结果产生影响，特别注意会对结果产生影响，特别注意是否允许是否允许0.0的存在的存在)，且多一个，且多一个P(不会对不会对结果产生影响结果产生影响)由于由于N不允许以不允许以0开始，这使得开始，这使得0 N，即按，即按前面分类方式没有包括前面分类方式没有包括0，因此在最终结，因此在最终结果时将其加上：果时将其加上：S R|+R|R|0。例例2-15n构造产生语言构造产生语言anbncn|n1的文法。的文法。文法文法G=(S1，a，b，S1ab|aS1b，S1)产产生生的的语语言言anbn|n1形形式式上上看看起起来来与与语语言言anbncn|n1比较接近。比较接近。G=(S2，c，S2c|cS2，S2)产产生生的的语语言言是是cn|n1。anbncn|n1?=anbn|n1cn|n1例例2-15（续）（续）文法文法SS1S2S1ab|aS1bS2c|cS2 不能产生语言不能产生语言anbncn|n1 而是产生语言而是产生语言 anbn|n1cn|n1 例例2-15（续）（续）文法文法G：Sabc|aSbc 产生的语言为：产生的语言为：an(bc)n|n1 焦点：交换焦点：交换b和和c的位置。的位置。例例2-15（续）（续）G14 ：SaBC|aSBC，CBBC aBab bBbb bCbc cCccG14：Sabc|aSBc，bBbb cBBc小结小结n给定一个文法后，要清楚地说出该给定一个文法后，要清楚地说出该文法所定义语言的特点比较困难；文法所定义语言的特点比较困难；n根据语言构造文法没有太直接的方根据语言构造文法没有太直接的方法可用。法可用。小结小结n文法的构造文法的构造n由开始符号直接构造（任意有穷语言）；由开始符号直接构造（任意有穷语言）；n引进语法变量进行构造；引进语法变量进行构造；n分析要构造文法的特性、结构特点。分析要构造文法的特性、结构特点。练习练习(见习题见习题)n8.(1)(3)注：不使用空产生式注：不使用空产生式习题评讲习题评讲(续续)8.(1)G1:S 0|0A,A 0|1|0A|1A或：或：G1:S S0|S1|0(3)G2:S 11|111|1111|11A11,A 0|1|0A|1A2.4 文法的乔姆斯基体系文法的乔姆斯基体系n乔姆斯基根据产生语言的文法的特性，将乔姆斯基根据产生语言的文法的特性，将语言分成了语言分成了4种类型种类型n定义定义2-6 设文法设文法G=(V,T,P,S)，则，则条件条件文法文法(G)语言语言(L)G0型文法型文法短语结构文法短语结构文法(PSG)0型语言型语言PSL P，均有均有|1型文法型文法上下文有关文法上下文有关文法(CSG)1型语言型语言CSL P，均有均有|，且且 V2型文法型文法上下文无关文法上下文无关文法(CFG)2型语言型语言CFL 均具有形式均具有形式A w,A wB，A A,B V,w T+3型文法型文法正则文法正则文法(RG)3型语言型语言RL G (0型型)G1：S0|1|00|11G2：SA|B|AA|BB，A0，B1G3：S0|1|0A|1B，A0，B1G4：SA|B|AA|BB，A0，B1G5:SA|B|AA|BB，A0，B1，CACS21，C11，C2 P，均有均有|(1型型)P，均有均有|，且且 V (2型型)均具有形式均具有形式A w,A wB，A A,B V,w T+(3型型)结论结论n该体系指明了形式语言研究的方式，该体系指明了形式语言研究的方式，0型文法型文法最为一般，最为一般，3型文法最为特殊。且具有关系型文法最为特殊。且具有关系 RG CFG CSG PSG RL CFL CSL PSL P70 (1)-(9)n1型文法规定推导过程中句型长度递增；型文法规定推导过程中句型长度递增；n2型文法规定产生式的左边只能为一个语法变型文法规定产生式的左边只能为一个语法变量，这样某个语法变量的推导不会依赖于其上量，这样某个语法变量的推导不会依赖于其上下文，这也是其名称的来历；下文，这也是其名称的来历；n3型文法则允许从一个语法变量最多产生出一型文法则允许从一个语法变量最多产生出一个语法变量，且该语法变量只能在句型尾。个语法变量，且该语法变量只能在句型尾。例例2-16 文法的分类文法的分类(1)G1:S 0|1|00|11 G3:S 0|1|0A|1B,A 0,B 0(2)G5:S A|B|AA|BB,A 0,B 0(3)G14:S aBC|aSBCaB ab,bB bb,bC bc,cC cc(4)G7:S|0S练习练习(见习题见习题)n2.习题评讲习题评讲2.(1)G1:S 0|0S(2)G2:S 0|SS(3)G3:S 0|0S,0S 00(4)G4:S 0|SS,SS 0