《编译原理》习题参考答案(一)《编译原理》习题参考答案(一)Bugreport:zpli@mail.ustc.edu.cnOrfind:电一楼二楼全球计算实验室李兆鹏第二章2.3叙述由下列正规式描述的语言a)0(0|1)*0b)((ε|0)1*)*c)(0|1)*0(0|1)(0|1)d)0*10*10*10*e)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*Answer:a)以0开始和结尾,而且长度大于等于2的0、1串b)所有0,1串(含空串)c)倒数第三位是0的0、1串d)仅含3个1的0、1串e)偶数个0和偶数个1的0、1串(含空串)2.4为下列语言写出正规定义:f)由偶数个0和偶数个1构成的所有0和1的串g)由偶数个0和奇数个1构成的所有0和1的串Answer:标准答案见《编译原理习题精选》P1-P21.1&1.2题2.7用算法2.4为下列正规式构造非确定的有限自动机,给出它们处理输入串ababbab的转换序列。c)((ε|a)b*)*d)(a|b)*abb(a|b)*Answer:c)NFA:0965231ee4ee78aeeebe10eeeeestartzpli@mail.ustc.edu.cn2004-3-7version1.1Page1of7《编译原理》习题参考答案(一)输入串ababbab的转换序列:01456789145678789145678910Or0145678914567891236789145678910d)NFA:0987653421eeaeb10161513141211eeaeebestarteabbe17eeee输入串ababbab的转换序列:012361456789101112131611141516172.8用算法2.2把习题2.7的NFA变换成DFA。给出它们处理输入串ababbab的状态转换序列。Answer://针对2.7(c)3个不同的状态集合:A={0,1,2,3,4,6,7,9,10}B={1,2,3,4,5,6,7,9,10}C={1,2,3,4,6,7,8,9,10}NFA的转换表:输入符号状态abABCBBCCBCACBabbaabstart子集构造法应用于2.7(c)得DFA:zpli@mail.ustc.edu.cn2004-3-7version1.1Page2of7《编译原理》习题参考答案(一)2.11我们可以从正规式的最简DFA同构来证明两个正规式等价。使用这种技术,证明下面正规式等价。(a)(a|b)*(b)(a*|b*)*(c)((ε|a)b*)*Answer:(c)NFA见2.7(c)用子集构造法化简得DFA见2.8。最简的DFA为:0Startba同理可求出(a)(b)正规式对应的最简DFA亦是如此,故(a)(b)(c)等价。2.15修改算法2.4,使之尽可能少使用ε转换,并保持所产生的NFA只有一个接收状态。Answer:算法2.4改进(3)(a)N(s)N(t)开始状态合并作为N(s|t)的开始状态N(s)N(t)接受状态合并作为N(s|t)的接受状态(3)(c)N(s)开始状态与接受状态合并成一个状态j。N(s)startijfzpli@mail.ustc.edu.cn2004-3-7version1.1Page3of7《编译原理》习题参考答案(一)第三章3.2考虑文法SaSbS|bSaS|ε(a)为句abab构造两个不同的子最左推导,以此说明该文法是二义的。(b)为abab构造对应的最右推导。(c)为abab构造对应的分析树。(d)这个文法产生的语言是什么?Answer:(a)S⇒lmaSbSS-------○1S⇒lmaSbS-------○2可同的最左推导,(b)S⇒rmaSbSb-------○3⇒rmaSbS---------○4)○1○4对应的分析树:○2○3对应的分析树:⇒lmabS⇒lmabaSb⇒lmababS⇒lmabab--知,对于句子abab存在两个不⇒lmabSaSbS⇒lmabaSbS⇒lmababS⇒lmabab---所以该文法是二义的⇒rmaSb⇒rmabSaS⇒rmabSab⇒rmabab---S⇒rmaSbaSbS⇒rmaSbaSb⇒rmaSbab⇒rmabab---(cεεε)该文法产生a、b个数相等的ab串(含空串)(dzpli@mail.ustc.edu.cn2004-3-7εεεversion1.1Page4of7《编译原理》习题参考答案(一)3.4文法‘|’R|RR|R*|(R)|a|b产条竖线是正规式的符号“或”,而(b)它给予算符*、链接和|的优先级和结合性同2(c)ab|b*a的分析树。AnsRR生字母表{a,b}上所有不含ε的正规式。注意,第一不是文法产生式右部各选择之间的分隔符,另外“*”在这儿是一个普通的终结符。该文法是二义的。为该文法写一个等价的非二义的文法。.2节中定义的一致。按上面两个文法构造句子wer:(b)标准答案见《编译原理习题精选》P17多个分析树二义文法的分析树:(c)原文法的分析树://文法二义,存在无aRRT*EFaFbTTaF|bTFFE*RRaRR|RbbRRRaRR|RRRab*bzpli@mail.ustc.edu.cn2004-3-7version1.1Page5of7《编译原理》习题参考答案(一)3.6为字母表{a,b}上的下列每个语言设计一个文法,其中哪些语言是正规的?(a)每个a后面至少有一个b跟随的所有串(b)a和b的个数相等的所有串Answer:(a)SabS|bS|ε该语言是正规,对应的正规式是(ab|b)*(b)解法一:SaSbS|bSaS|ε解法二:SaB|bA|εAaS|bAABbS|aBB解法三:SabS|aSb|Sab|baS|bSa|Sba|ε该文法不是正规的。3.8(a)消除习题3.1文法的左递归。(b)为(a)的文法构造预测分析器。Answer:(a)S(L)|aLSL1L1,SL1|ε(b)上述文法的预测分析器为:procedurematch(t:token);beginiflookahead=tthenlookahead:=nexttoken()elseerror()end;procedures;beginiflookahead=‘(’thenbeginmatch(‘(’);L();match(‘)’)endelseiflookahead=‘a’thenmatch(‘a’)elseerror()end;zpli@mail.ustc.edu.cn2004-3-7version1.1Page6of7《编译原理》习题参考答案(一)procedureL;beginS();L1()end;procedureL1;beginiflookahead=‘,’thenbeginmatch(‘,’);S();L1()endelsematch(‘’)end;———————————————————————————————————————————TheEnd2004-3-7zpli@mail.ustc.edu.cn2004-3-7version1.1Page7of7