1、编译原理第3章文法和语言第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(1
4、)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（2
7、）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.aA
13、B.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=aaa
14、，写出下列符号串及其长度：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=Z1
15、1、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=+,-,*,/,（,）,iVN
16、=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=ABE
18、FHLYEYCGIEYABEFLYCGICGJIT9=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，所以它们都为终态。0101123234546
19、5236737898101191291010311135126131414730 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，所以它们都为终态。ab01123245
20、323445545X 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.QUZV
22、ZQUZZZZ重新命名状态子集，令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，1
23、,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*|dd*.dd*|.dd*|dd*10(s|)dd*|10(s|)dd*|.dd*10(s|)dd*|dd*.dd*10(s|)dd*化简，画出的
