编译原理第3章文法和语言(共84页).doc

《编译原理第3章文法和语言(共84页).doc》由会员分享，可在线阅读，更多相关《编译原理第3章文法和语言(共84页).doc（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第3章文法和语言第1题文法G(A,B,S,a,b,c,P,S)其中P为：SAc|aBAabBbc写出L(GS)的全部元素。答案：L(GS)=abc第2题文法GN为：ND|NDD0|1|2|3|4|5|6|7|8|9GN的语言是什么？答案:GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9N=ND=NDD.=NDDDD.D=D.D或者：允许0开头的非负整数？第题为只包含数字、加号和减号的表达式，例如9-25，3-1，等构造一个文法。答案：GS:S-S+D|S-D|DD-0|1|2|3|4|5|6|7|8|9第4题已知文法GZ：ZaZb|ab写出L(GZ)的全部

2、元素。答案：Z=aZb=aaZbb=aaa.Z.bbb=aaa.ab.bbbL(GZ)=anbn|n=1第5题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答案：(1)允许0开头的偶正整数集合的文法ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8(2)不允许0开头的偶正整数集合的文法ENT|DTFT|GND|1|3|5|7|9D2|4|6|8FN|0GD|0第6题已知文法G：:=:=*:=（）i试给出下述表达式的推导及语法树。（）i+(i+i)（）i+i*i答案：(5)=（）=（）=（）=（i）=（i）=（i）=（ii）=（ii）=（ii）=i

3、（ii）(6)=*=*i=*i=i*i=i*i=i*i=ii*i+iii（)+*iii第7题证明下述文法G表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/答案：可为句子a+a*a构造两个不同的最右推导:最右推导1表达式表达式运算符表达式表达式运算符a表达式*a表达式运算符表达式*a表达式运算符a*a表达式+a*aa+a*a最右推导2表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符a表达式运算符表达式*a表达式运算符a*a表达式+a*aa+a*a第8题文法GS为：SAc|aBAabBbc该文法是否为二义的？为什么？答案：对于串abc(

4、1)S=Ac=abc(2)S=aB=abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。第9题考虑下面上下文无关文法：SSS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。(2)GS的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。SA ca bSa Bb cSS S*S S+aa a第10题文法SS(S)S|(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案

5、：（）嵌套的括号（）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列:E=E+T=E+T*F，所以E+T*F句型此句型相对于E的短语有:E+T*F；相对于T的短语有T*F直接短语为：T*F句柄为：T*F第13题一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？(3)找出该句子的所有短语、直接短语、

6、句柄。BaSA B SaS B Ab b a答案：(1)串abbaa最左推导:S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2)产生式有：SABS|Aa|Aa BSBB|b可能元素有：aa ab abbaa aaabbaa(3)该句子的短语有：a是相对A的短语是相对S的短语b是相对B的短语bb是相对B的短语aa是相对S的短语abbaa是相对S的短语直接短语有：ab句柄是：a第14题给出生成下述语言的上下文无关文法：（1）anbnambm|n，m=0（

7、2）1n0m 1m0n|n，m=0（3）WaWr|W属于0|a*，Wr表示W的逆答案：（）SAAAaAb|（）S1S0|AA0A1|（）S0S0|1S1|第16题给出生成下述语言的三型文法：(1)an|n=0(2)anbm|n,m=1(3)anbmck|n,m,k=0答案：(1)SaS|(2)SaAAaA|BBbB|b(3)AaA|BBbB|CCcC|第17题习题和习题11中的文法等价吗？答案：等价。第18题解释下列术语和概念：（）字母表（）串、字和句子（）语言、语法和语义答案：（）字母表：是一个非空有穷集合。（）串：符号的有穷序列。字：字母表中的元素。句子：如果Z x,xV*T则称x是文法G

8、的一个句子。+（）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。附加题问题1：给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0答案：R=(01|10)(01|10)*问题2：已知文法GA，写出它定义的语言描述GA:A0B|1CB1|1A|0BBC0|0A|1CC答案:GA定义的语言由0、1符号串组成，串中0和1的个数相

9、同.问题3：给出语言描述，构造文法.构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案一：GEEE+T|TTT*F|FF(E)|a答案二：GEEE+E|E*E|(E)|a问题4：已知文法GS:SdABAaA|aB|bB相应的正规式是什么？GS能否改写成为等价的正规文法？答案：正规式是daa*b*；相应的正规文法为(由自动机化简来)：GS:SdA Aa|aB BaB|a|b|bC CbC|b也可为(观察得来):GS:SdA Aa|aA|aB BbB|问题5：已知文法G：EE+T|E-T|TTT*F|T/F|FF(E)|i试给出下述表达式的推导及语法树(1)i;

10、(2)i*i+i(3)i+i*i(4)i+(i+i)答案：(1)E=T=F=i(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i(3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i(4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i+(T+T)=i+(F+T)=i+(i+T)=i+(i+F)=i+(i+i)(2)(3)(4)E+TiTFiFiEE+TE+TiTFF(E)iTF iF问题6：已知文法GE:EET+|TTTF*|FFF|a试证：FF*是文法的句型，指出该句型的短语、简单短语

11、和句柄.答案：该句型对应的语法树如下：该句型相对于E的短语有FF*相对于T的短语有FF*,F相对于F的短语有F;F简单短语有F;F句柄为F.问题7：适当变换文法，找到下列文法所定义语言的一个无二义的文法：SSaS.SbS.ScS.d答案：该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即可消除二义性。设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为：SSaS.AAAbA.CCCcC.d规定结合性为左结合，进一步将文法变换为：SSaA.AAAbC.CCCcF.FFd该文法为非二义的。问题8：构造产生如下语言的上下文无关文法：（1）anb2ncm

12、|n，m0（2）anbmc2m|n，m0（3）ambn.mn（4）a m b n c p d q.m+n=p+q（5）uawb.u,wa,b*|u|=|w|答案：（1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如anb2n和形如cm的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。对于该语言，存在一个由以下产生式定义的上下文无关文法GS：SABA.aAbbB.cB（2）同样，要产生形如anbmc2m的串，可以分别产生形如an和形如bmc2m的串。对于该语言，存在一个由以下产生式定义的上下文无关文法GS：SABA.a

13、AB.bBcc（3）考虑在先产生同样数目的a,b，然后再生成多余的a。以下GS是一种解法：SaSb.aS.（4）以下GS是一种解法：SaSd.A.DAbAd.BDaDc.BBbBc.注：a不多于d时，b不少于c；反之，a不少于d时，b不多于c。前一种情形通过对应A，后一种情形对应D。（5）以下GS是一种解法：SAbABAB.aBa.b问题9：下面的文法G(S)描述由命题变量p、q，联结词（合取）、（析取）、.（否定）构成的命题公式集合：SST.TTTF.FF.F.p.q试指出句型.F.qp的直接短语（全部）以及句柄。答案：直接短语：p，q，.F句柄：.F问题10：设字母表A=a，符号串x=aa

14、a，写出下列符号串及其长度：x0,xx,x5以及A+.答案：x0=(aaa)0=|x0|=0xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa|x5|=15A+=A1A2.A n=a,aa,aaa,aaaa,aaaaaA*=A0A1A2.A n=,a,aa,aaa,aaaa,aaaaa问题11：令=a，b，c，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3答案：xy=abcb|xy|=4xyz=abcbaab|xyz|=7(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12问题12：已知文法GZ：Z=U0V1、U=Z

15、11、V=Z00,请写出全部由此文法描述的只含有四个符号的句子。答案：Z=U0=Z10=U010=1010Z=U0=Z10=V110=0110Z=V1=Z00=U000=1000Z=V1=Z00=V100=0100问题13：已知文法GS：S=AB A=aAB=bBcbc,写出该文法描述的语言。答案：A=aA描述的语言:an|n=0B=bBcbc描述的语言:,bncn|n=1L(GS)=anbmcm|n=0,m=1问题14：已知文法E=TE+TE-T、T=FT*FT/F、F=(E)i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。答案：开始符号：EVT=+,-,*,/,（,）,iV

16、N=E,F,T问题15：设有文法GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？答案：根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。问题16：写一文法，使其语言是奇正整数集合。答案：A:=1|3|5|7|9|NAN:=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|N:=0|1|2|3|4|5|6|7|8|9SS*SS+S aa aSS+Sa S*Sa a第4章词法分析第1题构造下列正规式相应的DFA.（）1(0|1)*101（）(1010*|1(010)*1）*0（）a(a|b)*|ab*a)*b（）b(ab)*|bb)*ab答案：

17、(1)先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:(2)先构造NFA：用子集法将NFA确定化01XXT0=XAAABFLT1=ABFLYCGYYCGCGJT2=YT3=CGJDHKDHDHKABFKLT4=DHEIEIABEFILT5=ABFKLYCGT6=ABEFILEJYCGEJYABEFGJLYT7=ABEFGJLYEHYCGKEHYABEFHLYCGKABCFGJKLT8=AB

18、EFHLYEYCGIEYABEFLYCGICGJIT9=ABCFGJKLDHYCGKDHYDHYT10=ABEFLYEYCGT11=CGJIDHJKDHJDHJT12=DHYEIT13=DHJEIKEIKABEFIKLT14=ABEFIKLEJYCGX 1 AB1 C 0 D 1 E0F 1 G 0 H 1 I 0 J 1 KL0将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因为2、7、8、10、12中含有Y，所以它们都为终态。010112323454

19、65236737898101191291010311135126131414730 1 0121 2710 83456911 13 1411010101101101010 10101(3)先构造NFA：先构造NFA：用子集法将NFA确定化abXXT0=XAAABCDT1=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=ABCDYBEBYT4=ABCDEFBEFBEYT5=ABCDEYBEFBEY将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y，所以它们都为终态。ab0112324

20、5323445545X a ABa,bD a E a FCYbb0 a 1 b 32a5a 4bababab(4)先构造NFA：用子集法将NFA确定化：abXXT0=XAAABDEFT1=ABDEFCIGCICIGGT2=CIDYDYABDEFYT3=GHHABEFHT4=ABDEFYCIGT5=ABEFHCIG将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y，所以它为终态。ab011232435423523DFA的状态图：X AbBaF b G b HEYaC D bI b0 b 1 b2a453bbabab第题已知NFA（x,y,z,0,1,M

21、,x,z），其中：M(x,0)=z，M(y,0)=x,y，,M(z,0)=x,z，M(x,1)=x，M(y,1)=，M(z,1)=y，构造相应的DFA。答案：先构造其矩阵01xzxyx,yzx,zy用子集法将NFA确定化：01xzxzxzyxzxzxyyxyxyxyzxxyzxyzxy将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F中含有z，所以它为终态。01ABABCDCCEDEEFAFFEDFA的状态图：A0 10FED0B1010101C第3题将下图确定化：答案：用子集法将NFA确定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZ

22、VZQUZZZZ重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。.01SABACBBDECFFDF.ECEFFFDFA的状态图：第4题将下图的（a）和（b）分别确定化和最小化：答案：初始分划得0：终态组0，非终态组1,2,3,4,5对非终态组进行审查：1,2,3,4,5a0,1,3,5而0,1,3,5既不属于0，也不属于1,2,3,4,54a0，所以得到新分划1：0，4，1,2,3,5对1,2,3,5进行审查：1,5b42,3b1,2,3,5，故得到新分划2：0，4，1,5，2,31,5a1,52,3a1,3，故状态2和状态3不等价，得到新分划3：0，2，3，4，

23、1,5这是最后分划了最小DFA：第5题构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。答案：按题意相应的正规表达式是(0*10)*0*，或0*(0|10)*0*构造相应的DFA，首先构造NFA为用子集法确定化：II0I1X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y222重新命名状态集：S0112342244333DFA的状态图：可将该DFA最小化：终态组为1,2,4，非终态组为3，1,2,401,2,4，1,2,413，所以1,2,4为等价状态，可合并。第题设无符号数的正规式为：=dd*|

24、dd*.dd*|.dd*|dd*10(s|)dd*|10(s|)dd*|.dd*10(s|)dd*|dd*.dd*10(s|)dd*化简，画出的DFA，其中d=0,1,2,9，s=，答案：先构造NFA：用子集法将NFA确定化：Xd.BdF GdH10dAC10dDsE dYdsds10dXXAT0=XABFABBFFGAAT1=BCCCT2=FGGHGGHHT3=ABFAT4=CDCDDET5=GHT6=HHT7=DEEYEEYYT8=EYT9=YY将XA、B、FG、A、C、G、H、DE、E、Y重新命名，分别用0、1、2、3、4、5、6、7、8、9表示。终态有0、3、4、6、9。s10d012

25、314256312347456667898999DFA的状态图：第7题给文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAEaB|bFFbD|aE|b构造相应的最小的DFA。答案：先构造其NFA：用子集法将NFA确定化：d62 5d3dd4 7890110ds1010ddsdddSaAaZQbBDaEbFbbabaabb bbababSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。ab012113224325416516625DFA的状态图：令P0（

26、0,1,2,5,6,3,4）用b进行分割：P1（0,5,6,1,2,3,4）再用b进行分割：P2（0,5,6,1,2,3,4）再用a、b进行分割，仍不变。再令为A，1，2为B，3，4为C，5，6为D。最小化为：0aa52b3aab416baabbbab第题给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0答案：解方程组S的解：S=0A|1BA=1S|1B=0S|0将A、B产生式的右部代入S中S=01S|01|10S|10=（01|10）S|（01|10）所以：S=(01|10)*(01|10)第9题将下图的DFA最小化，并用正规式描述它所识别的语言。Aa,bD CaaBbabb1a2

27、6c3cb54 7bba bbbdda答案：令P0（1,2,3,4,5,6,7）用b进行分割：P1（1,2,3,4,5,6,7）再用a、b、c、d进行分割，仍不变。再令1,2为A，3，4为B，5为C，6，7为D。最小化为：r=b*a(c|da)*bb*=b*a(c|da)*b+AaC DbdBbcab附加题问题1：为下边所描述的串写正规式，字母表是a,b.a)以ab结尾的所有串b)包含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串答案：注意正规式不唯一a)(a|b)*abb)(bb)*c)(a*ba*ba

28、*)*d)b*ab*e)(a|b)*ab(a|b)*f)b*a*问题2：请描述下面正规式定义的串.字母表0，1.a)0*(10+)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0答案：a)每个1至少有一个0跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和0结尾的串问题3：构造有穷自动机.a)构造一个DFA，接受字母表.0,1上的以01结尾的所有串b)构造一个DFA，接受字母表.0,1上的不包含01子串的所有串.c)构造一个NFA，接受字母表.x,y上的正规式x(x|y)*x描述的集合d)构造一个NFA，接受字母表.a,b上的正规式(ab|a)*b+描述

29、的集合并将其转换为等价的DFA.以及最小状态DFA答案：b)c)最小化的DFA问题4：设有如图所示状态转换图，求其对应的正规表达式。问题5：已知正规式：(1)(a|b)*|aa)*b;(2)(a|b)*b.试用有限自动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。分析：基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小DFA，如这两个最小DFA一样，也就证明了这两个正规式是等价的。答案：可通过消结法得出正规式R=(01)*(00|1)(0|1)*|0)也可通过转换为正则文法，解方程得到正规式。状态转换表1abX1241234124Y12341234124Y124

30、Y1234124Y状态转换表2aB123223323由于2与3完全一样，将两者合并，即见下表ab12323abX121212Y121212Y12Y1212Y可化简得下表ab123223得DFA图两图完全一样，故两个自动机完全一样，所以两个正规文法等价。对相应正规文法,令A对应1，B对应2故为：AaA|bB|bBaA|bB|b即为SaS|bS|B,此即为所求正规文法。问题6：考虑正规表达式r=a*b(a|b)，构造可以生成语言L(r)的一个正规文法。答案：Sa*b(a|b)变换为SaA,Sb(a|b),AaA,Ab(a|b)变换为SaA,SbB,B(a|b),AaA,AbC,C(a|b)变换为S

31、aA,SbB,Ba,Bb,AaA,AbC,Ca,Cb所以，一个可能的正规文法为GS：SaA,SbB,Ba,Bb,AaA,AbC,Ca,Cb或表示为：SaA|bB,Ba|b,AaA|bC,Ca|b（适当等价变换也可以，但要作说明，即要有步骤）问题7：考虑下图所示的NFA N，构造可以生成语言L(N)的一个正规文法。答案：GP:P0 P.1 P.1 QQ0 R.1 RR问题8：考虑如下文法GS：S0S.1S.1AA0B.1BBa)试构造语言为L(G)的一个正规表达式。b)试构造语言为L(G)的一个有限自动机。答案：a)由A0B，B得A0;由A1B，B得A1;由A0，A1得A0.1;由S1A，A0.

32、1得S1(0.1);由S1A，A0.1得S1(0.1);由S0S，S1(0.1)得S0*1(0.1);由S1S，S1(0.1)得S1*1(0.1);由S0*1(0.1)，S1*1(0.1)得S0*1(0.1).1*1(0.1);所以，一个可能的正规表达式为：0*1(0.1).1*1(0.1)b)第5章自顶向下语法分析方法第1题对文法GSSa|(T)TT,S|S(1)给出(a,(a,a)和(a,a),(a),a)的最左推导。(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3)经改写后的文法是否是LL(1)的?给出它的预测分析表。(4)给出输入串(a,a)#的分析过程，并说

33、明该串是否为G的句子。答案：(1)对(a,(a,a)的最左推导为：S(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a)对(a,a),(a),a)的最左推导为：S(T)(T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(S,S,S),S)(T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),S,S),S)(a,a),S),S)(a,a),(T),S)(a,a),(S),S)(a,a),(a),S)(a,a),(a),a)(2)改写文法为：0)Sa1)S2)S(

34、T)3)TS N4)N,S N5)N非终结符FIRST集FOLLOW集Sa,(#,)Ta,().N,.).对左部为N的产生式可知：FIRST（,S N）=，FIRST（）=FOLLOW（N）=)由于SELECT(N,S N)SELECT(N)=，)=所以文法是LL(1)的。预测分析表（Predicting Analysis Table）a(),#Sa(T)TS NS NS NN,S N也可由预测分析表中无多重入口判定文法是LL(1)的。(3)对输入串（a,a）#的分析过程为：栈（STACK）当前输入符（CUR_CHAR）剩余输入符（INOUT_STRING）所用产生式（OPERATION）#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#(aaa,aa)#a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可见输入串（a,a）#是文法的句子。第3题已知文法GS：SMH|aHLSo|K