下载文档原格式
编译原理考试陈火旺（含答案）编译原理试题 A (2003.12.4)一、回答下列问题：(30 分)1.(6分)对于下面程序段programtest(input,output)vari,j:integer;procedureCAL(x,y:integer);beginy:=y*y;x:=x-y;y:=y-xend;begini:=2;j:=3;CAL(i,j)writeln(j)end.若参数传递的方法分别为(1) 传值、(2) 传地址，(3)传名，请写出程序执行的输出结果。
2.(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1) 的，请说明理由。
G(M)：M→TBT→Ba|B→Db|eT|D→d|3. (4分)考虑下面的属性文法产生式语义规则S→ABC B.u:=S.uA.u:=B.v+C.vS.v:=A.vA→a A.v:=3*A.uB→b B.v:=B.uC→c C.v:=1(1)画出字符串abc的语法树;(2)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v 的值为多少?4.(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？5.(5分)对下列四元式序列生成目标代码：1A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。
6.(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
二、(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。
三、(6 分)写一个文法使其语言为L(G)={ a n b n c m|m,n≥1，n 为奇数，m为偶数}。
四、(8分)对于文法G(S):S bMbM(L|aLMa）1.写出句型b(Ma)b的最右推导并画出语法树。
2.写出上述句型的短语，直接短语和句柄。
五、(12 分)对文法G(S)：S→a|^|(T)T→T，S|S(1)构造各非终结符的FIRSTVT和LASTVT集合;(2)构造算符优先表;(3)是算符优先文法吗?(4)构造优先函数。
第二章P36-6(1)L G ()1是0~9组成的数字串(2)最左推导:N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334556568最右推导:N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434886868568P36-7G(S)O N O D N S O AO A AD N→→→→→1357924680|||||||||||P36-8文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒P36-10/**************)(|)(|S T TTS S →→***************/P36-11/*************** L1:ε||cC C ab aAb A ACS →→→ L2:bcbBc B aA A ABS ||→→→ε L3:εε||aBb B aAb A ABS →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)101101(|)*1 ε ε 1 0 1 1确定化：0 1 {X} φ {1,2,3} φ φ φ {1,2,3} {2,3} {2,3,4} {2,3} {2,3} {2,3,4} {2,3,4} {2,3,5} {2,3,4}{2,3,5} {2,3} {2,3,4,Y} {2,3,4,Y}{2,3,5}{2,3,4,}1 00 0 1 1 00 1 0 1 1 1 最小化：X 1 2 3 4 Y5 XY60 12 35 4{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,01234560123451350123451246012345601234135012345601231010==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}===== 0 10 0 1 00 1 0 1 1 1P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)aa,b a 确定化：a b {0} {0,1} {1} {0,1} {0,1} {1} {1} {0} φ φφφ给状态编号：a b 0125 01 2 4 3 011 12 2 03 333aaa b b bba 最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====a ab bab (b)b b aa baa bb aa a 已经确定化了,进行最小化 最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a b0 1 2 3 01 2 0 2 3 14 5b b aa b aP64–14(1) 01 0 (2):(|)*0100 1 ε ε0 确定化：0 1 {X,1,Y} {1,Y} {2} {1,Y} {1,Y} {2} {2} {1,Y} φ φφφ 给状态编号：0 1 0 1 2 1 1 2 2 1 3 33 30 1 01 1 10 最小化：0 1 2 01YX YX2 1 0 2 13{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====1 1 1 0第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T T S T T a S S G '→''→→'递归子程序： procedure S; beginif sym='a' or sym='^' then abvance else if sym='(' then begin advance;T;if sym=')' then advance; else error; end else error end;procedure T; begin S;'T end;procedure 'T ; beginif sym=',' then begin advance; S;'T end1 3其中:sym:是输入串指针IP 所指的符号 advance:是把IP 调至下一个输入符号 error:是出错诊察程序 (2)FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST('T )={,,ε} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW('T )={)} 预测分析表a^() , # S S a →S →^S T →()TT ST →' T ST →' T ST →''T'→T ε '→'T ST ,是LL(1)文法P81–2文法：|^||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε(1)FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#}考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3)+ * ( ) a b ^ # EE TE →'E TE →' E TE →' E TE →'E' '→+E E'→E ε'→E εTT F T →' T F T →' T F T →' T F T →'T' '→T ε '→T T '→T ε '→T T '→T T '→T T '→T εF F P F →' F P F →' F P F →' F P F →'F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F εPP E →() P a → P b → P →^(4)procedure E; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else error endprocedure E'; beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else error endprocedure T';if sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P81–3/***************(1)是，满足三个条件。
第二章P36-6(1)L ( G1) 是0~9组成的数字串(2)最左推导 :N ND NDD NDDD DDDD0DDD01DD012D 0127N ND DD3D34N ND NDD DDD5DD56 D568最右推导 :N ND N 7ND 7N 27ND 27N 127D1270127N ND N 4 D 434N ND N 8ND 8N 68 D 68568P36-7G(S)O1|3|5|7|9N 2|4|6|8|O D0|NS O|AO AAD|NP36-8文法：ET|E T|E TT F|T*F|T/F F( E)|i最左推导 :E E T T TF T i T i T * F i F * F i i * Fi i * iE T T *F F * F i * F i *( E ) i *( E T )i *( T T )i *( F T )i *( i T )i *( i F )i *( i i )最右推导 :E E T E T*F E T * i E F * i E i * i T i * i F i * i i i * iE TF * T F * F F*( E)F*( E T)F*( E F) F *( E i )F *( T i ) F *( F i ) F *( i i )i *( i i )语法树： /********************************E E EE+T E+T E-TE-T F E+T FT T*FT F i T F iF F iF iF ii ii ii+i+i i-i-i i+i*i*****************/P36-9句子 iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-10/**************S TS |TT(S) |()***************/P36-11/***************L1:S ACA aAb | abC cC |L2:S ABA aA |B bBc | bcL3:S ABA aAb | BaBb |L4:S A | BA 0A1| B1B0| A***************/第三章习题参考答案P64–7(1)1(01|) * 101XY1101X12345Y1确定化：01 {X}φ{1,2,3}φφφ{1,2,3}{2,3}{2,3,4}{2,3}{2,3}{2,3,4}{2,3,4}{2,3,5}{2,3,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4,}102300110101564111最小化：{ 0,1,2,3,4,5},{ 6}{ 0,1,2,3,4,5} 0{1,3,5}{0,1,2,3,4,5} 1{1,2,4,6}{ 0,1,2,3,4},{ 5},{ 6}{ 0,1,2,3,4} 0{1,3,5}{ 0,1,2,3},{ 4},{ 5},{ 6}{ 0,1,2,3} 0{1,3}{0,1,2,3}1{12,,4}{ 0,1},{2,3}{ 4},{5},{6}{ 0,1} 0{1}{0,1} 1{1,2}{ 2,3} 0{ 3}{ 2,3}1{4}{ 0},{ 1},{ 2,3},{ 4},{ 5},{ 6}1020010011345111P64–8(1)(1 | 0)* 01(2)(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5) |(0|5)(3)0*1(0 | 10*1) * |1* 0(0 |10* 1) *P64–12(a)aa,b01a确定化：a b{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ给状态编号：a b012112203333 aa01a b b bb23a最小化：{ 0,1},{2,3}{ 0,1} a{1}{0,1} b{ 2}{ 2,3} a{ 0,3}{ 2,3} b{3}{ 0,1},{2},{3}a ab b012ab(b)b b a023a baabb a514a a已经确定化了 , 进展最小化最小化：{{ 0,1}, { 2, 3,4, 5}}{ 0,1} a{1}{ 0,1} b{ 2,4}{ 2, 3,4,5} a { 1, 3, 0, 5}{ 2,3,4,5} b { 2, 3,4,5} { 2, 4} a{1,0}{ 2,4} b{ 3,5}{ 3, 5} a{ 3,5}{ 3,5} b{ 2,4}{{ 0,1},{2, 4},{3, 5}}{ 0,1} a{1}{ 0,1} b{ 2,4}{ 2, 4} a{1,0}{ 2,4} b{ 3,5}{ 3, 5} a{ 3,5}{ 3,5} b{ 2,4}bb a012abaP64–14(1)0101(2):X(| )*Y0102 01X1Y确定化：01 {X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：01 01211221333311011123最小化：{ 0,1},{ 2, 3}{ 0,1} 0{1}{ 0,1} 1{ 2}{ 2,3} 0{1,3}{ 2,3}1{ 3}{ 0,1},{ 2},{ 3}111013第四章P81–1(1)按照 T,S 的顺序消除左递归G (S)Sa |^ | (T )TSTT,ST |递归子程序：procedure S;beginif sym='a' or sym='^'then abvanceelse if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS; Tend;procedure T ;beginif sym=','then beginadvance;S; Tendend;其中 :sym: 是输入串指针IP 所指的符号advance: 是把 IP 调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST( T )={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(T )={)}预测分析表a^(),#S SaS ^S (T)T TSTTSTT STT TT,ST是LL(1) 文法P81–2文法：ETEEE |TFTT T |FPFF* F |P( E) | a | b |^(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε }FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε }FIRST(F)={(,a,b,^}FIRST(F')={*,ε }FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑以下产生式:EE|TT|F* F |P( E)|^| a|bFIRST(+E) ∩ FIRST( ε )={+}∩{ ε }= φFIRST(+E) ∩ FOLLOW(E')={+} ∩ {#,)}=φFIRST(T)∩FIRST( ε)={(,a,b,^}∩ { ε}= φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩ {+,),#}=φFIRST(*F')∩ FIRST(ε )={*}∩ {ε }=φFIRST(*F')∩ FOLLOW(F')={*}∩ {(,a,b,^,+,),#}= FIRST((E)) ∩ FIRST(a)∩ FIRST(b)∩FIRST(^)=所以 , 该文法式LL(1) 文法 .φφ(3)+ *()ab^#E ETE 'ETE 'ETE' ETE 'E'E E E E T TFT TFT T FT T FTT'T T T TTT TT T T TF F' PFPFFPF FPF F PF F F*F FFFFFFP( E )Pa P b P ^(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P81–3/***************(1)是，满足三个条件。
