编译原理(第2版)陈意云+张昱编著课后答案

1编译原理习题2003.42目录•chap1基本知识•chap3词法分析•chap4语法分析•chap5语法制导翻译•chap6运行时刻环境•chap7中间代码生成•chap8代码生成3第一章练习1.1文法S(L)|aLL,S|S(a)指出文法的终结符号,非终结符号,开始符号.文法的四个组成部分:终结符号VT:语言不可再分的基本符号非终结符号VN:语法范畴(语法概念)开始符号S:最终感兴趣的语法范畴产生式P:定义语法范畴的一种书写形式终结符号:(,)a非终结符号:SL开始符号:S元语言符号:表示“定义为”|表示“或”4(b)给出句子的分析树分析树:(推导树)表示一个句型的推导(a,(a,a))S(L)L,SS(L)aSa5(c)给出句子的最左推导给出每次推导后得到的句型的短语,直接短语最左推导:推导中任何一步都是对中的最左非终结lm符号进行替换的推导.短语是文法的句型(S*)S*A且A+则是关于A的句型的短语.直接短语是文法的句型(S*)S*A且A则是关于A的句型的直接短语.句柄:一个句型的最左直接短语称为句柄.6S(L)(L,S)(S,S)(a,S)(a,(L))短语(L)L,SSaa(L,S)S,Sa,Sa,(L)(S,S)(a,S)(a,(L))(L)直接(L)L,SSaa短语(L)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))短语aaaaa,(L,S)a,(S,S)a,(a,S)a,(a,a)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))L,SSaa(L,S)S,Sa,Sa,a(S,S)(a,S)(a,a)直接aaaa短语L,SSaaa7(d)构造各个句子的最右推导.最右推导(规范推导)(e)这个文法产生的语言是什么?a(a)(a,a)((a,a),a)......a和数据元素为a的广义表全体81.2考虑文法SaSbS|bSaS|(a)试说明此文法是二义性的.(定义1.5)如果一文法的句子存在两棵分析树,则该句子是二义性的.如果一文法包含二义性的句子,则这个文法是二义性的.可以从句子abab有两个不同的最左推导来说明.SaSbSabSabaSbSababSabablmlmlmlmlmSaSbSabSaSbSabaSbSababSabablmlmlmlmlm句子abab有两个不同的最左推导,该句子是二义性的.所以此文法是二义性的.9(b)对于句子abab构造两个相应的最右推导.SaSbSaSbabSaSbabSabababrmrmrmrmrmSaSbSaSbaSbSaSbaSbaSbabababrmrmrmrmrm(c)对于句子abab构造两个相应的分析树.SSaSbSaSbSbSaSaSbS(d)此文法产生的语言是什么?由相同个数的a和b组成的字符串.101.3考虑文法bexprbexprorbterm|btermbtermbtermandbfactor|bfactorbfactornotbfactor|(bfactor)|true|false(a)请指出此文法的终结符号,非终结符号和开始符号.终结符号:or,and,not,(,),true,false非终结符号:bexpr,bterm,bfactor开始符号:bexpr11(b)试对于句子not(trueorfalse)构造一棵分析树.bexprbtermbfactornotbfactor(bexpr)bexprorbtermbtermbfactorbfactorfalsetrue12(c)试说明此文法产生的语言是全体布尔表达式.13练习:长度为n的字符串,分别有多少个前缀,后缀,子串,真前缀,子序列?前缀:n+1后缀:n+1子串:1+n+(n-1)+...+1=1+n(n+1)/2真前缀:n子序列:1+Cn1+Cn2+Cn3+...+Cnn=2n14EE+TT*Fi给出句型E+T*i的短语,直接短语和句柄EE+TFT*F给出句型F+T*F的短语,直接短语和句柄短语:i,T*i,E+T*i直接短语:i句柄:i短语:F,T*F,F+T*F直接短语:F,T*F句柄:F15第三章练习3.3试描述下列正规表达式所表示的语言:(a)0(0|1)*0(b)((|0)1*)*由0和1组成且以0开始和结束的符号串全体.(c)(0|1)*0(0|1)(0|1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体.长度大于等于3且倒数第3个字符为0的01符号串全体.16(d)0*10*10*10*(e)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*有且只有3个1的0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体.((aa|bb)|(ab|ba)(aa|bb)*(ab|ba))*173.4对于下列语言分别写出它们的正规表达式:(a)英文字母组成的所有符号串,要求符号串中顺序包含五个元音字母.令letter={非元音的英文字母}letter*(a|A)letter*(e|E)letter*(i|I)letter*(o|O)letter*(u|U)letter*(b)英文字母组成的所有符号串,要求符号串中的字母依照字典序排列.(a|A)*(b|B)*(c|C)*......(z|Z)*18(c)没有重复出现的数字的数字符号串全体.(d)最多有一个重复出现的数字的数字符号串全体令ri=i|,i=0,1,2,...,9R0|R1|R2|...|R9记为Rii(0,1,2...,9)P(0,1,2...,9)表示0,1,2...,9的全排列ri0ri1...ri9i0i1...i9P(0,1,2...,9)iri0ri1...ri9i(0,1,2...,9)i0i1...i9P(0,1,2...,9)19(e)带有偶数个0和奇数个1的由0和1组成的符号串全体.E为带有偶数个0和1的由0和1组成的符号串全体.即(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*E1E|E0E1E0E(f)不包含子串011的由0和1组成的符号串全体.(g)不包含子序列011的由0和1组成的符号串全体1*0*10*|1*(0*|(10)*)*20练习:1.令A,B和C是任意正规式,证明以下关系成立:A|A=A(A*)*=A*A*=|AA*(AB)*A=A(BA)*(A|B)*=(A*B*)*=(A*|B*)*A=b|aA当且仅当A=a*b213.6给出接受下列在字母表{0，1}上的DFA。（a）所有以00结束的符号串的集合；AstartB0C010NFA等价于A1startBC00011DFA(1|0)*0022（b）所有具有三个0的符号串的集合。1*01*01*01*AstartB0C01DFA11B01233.7构造等价于下列正规表达式的有限自动机.(a)10|(0|11)0*100011AstartD1BEC1NFA01ADBCDDEBCEDE//1010AstartBC0DEDFA124(b)((0|1)*|(11))*0|111AstartCBEDNFA01ABDEABDEABCDEABCDEABDEABCDE11A'start0B'DFA01A'start最小化DFA0253.8给定右线性文法G:S0S|1S|1A|0BA1C|１B0C|1C0C|1C|0|1试求一个等价的左线性文法G’.000,11SstartB1ACf状态转移图100,10,1左线性文法G’:fA1|B0|C1|C0AS1BS0CA1|B0|C1|C0SS0|S1|图中状态C和f可合并,得到左线性文法G’:CA1|B0|C1|C0AS1BS0SS0|S1|263.9-3.11(d)(a|b)*abb(a|b)*1start2a4ba3bbba由正规表达式构造NFA1start12a14b13bbaaba124a134bba由NFA得到DFAABCDEFBCDEFABCDEABaDbCbabaab最小化DFA273.13对于下列正规表达式构造最小状态的DFA.(b)(a|b)*a(a|b)(a|b)a1start2a43babNFAbaAstartBabHGaCDaaaEFabaaabbbb最小化DFA284.4考虑文法RR‘|’R|RR|R*|(R)|a|b(a)试说明此文法生成在符号a和b之上的所有正规表达式.(b)试说明此文法是二义性的.(c)试构造一个等价的无二义性文法.(b)句子a|aa的两种最左推导.句子aa*的两种最左推导.RRRaR*aRR*RRaa(c)消除二义性RR‘|’S|SSST|TTU*|UU(R)|a|b294.5dangling-else文法:stmtifexprthenstmt|matched-stmtmatched-stmtifexprthenmatched-stmtelsestmt|other试说明此文法是二义性的。句子ife1thenife2thens1elseife3thens2elses3ife1thenife2thens1elseife3thens2elses3SMSifEthenMSelseSe1ifEthenMSelseSMSe2otherifEthenSothers1e3MSs3others2SifEthenSe1MSifEthenMSelseSe2otherMSs1ifEthenMSelseSe3otherMSs2others3304.3对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？(a)使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。(b)具有相同数目的0和1的由0和1组成的符号串的全体。(c)具有不同数目的0和1的由0和1组成的符号串的全体。S1S|01S|(1|01)*S0S1S|1S0S|非正规语言S'SASS0S1S|1S0S|AB|C非正规语言B1B|1C0C|0SA|BA0|0A|A0|10A|01A|A10|A01|1A0|0A1B0|0B|B0|10B|01B|B10|B01|1B0|0B131(d)所有形如xy而xy的由0和1组成的符号串。S0E|1E|LBRE00E|01E|10E|11E|BII1B|OO1B|IO1C|OI1CCIO1C|OI1C|I1OOI1O1IIO1I1III1O1OOO1LI1LLO0LI1RR1O1RR0LR所有形如xy而x=y的由0和1组成的符号串。S0S0|1S1|324.5(a)给出一个上下文无关产生式的集合，使它与AB*a(C|D)生成同样的符号串集合。AB’aEB’BB’|EC|D(b)是否可以把ET|E+T写为：ET{+T}是否可以把ET|E+T|E-T写为：ET{(+|-T)}ET{+T}等价于ETT’T’+TT’|334.7对于文法SaSbS|bSaS|构造一个带有回溯的递归下降分析器.问能否构造一个预测分析器.procedurematch(t:token);beginifkahead=tthenend;procedureS;beginifmatch344.9对于文法bexprbexprorbterm|btermbtermbtermandbfactor|bfactorbfactornotbfactor|(bexpr)|true|false构造一个预测分析器。1.消除左递归bexprbtermbexpr’bexpr’orbtermbexpr’|btermbfactorbterm’bterm’a