编译原理课后答案(陈火旺)

第6章属性文法和语法制导翻译7. 下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：试设计求的属性文法，其中，已知B的综合属性c, 给出由B产生的二进位的结果值。

例如，输入时，=，其中第一个二进位的值是4，最后一个二进位的值是。

【答案】11. 设下列文法生成变量的类型说明：(1)构造一下翻译模式，把每个标识符的类型存入符号表；参考例。

【答案】第7章语义分析和中间代码产生1. 给出下面表达式的逆波兰表示（后缀式）：【答案】3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

【答案】间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6)4. 按节所说的办法，写出下面赋值句A:=B*(－C+D) 的自下而上语法制导翻译过程。

给出所产生的三地址代码。

【答案】5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码：A[i, j]:=B[i, j] + C[A [k, l]] + d[ i+j]【答案】6. 按7.4.1和节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。

【答案】用作数值计算时产生的四元式：用作条件控制时产生的四元式：其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。

7. 用7.5.1节的办法，把下面的语句翻译成四元式序列： While A<C and B<D do if A=1 then C:=C+1 else while A ≦D do A:=A+2; 【答案】第9章 运行时存储空间组织4. 下面是一个Pascal 程序：当第二次( 递归地) 进入F 后，DISPLAY 的内容是什么当时整个运行栈的内容是什么 【答案】第1次进入F 后，运行栈的内容： 第2次进入F 后，运行栈的内容： 109 87 6 5 4 3 2 1 017 1615 14 13 12 11 10 9 8 7 6 5第2次进入F 后，Display 内容为：5. 对如下的Pascal 程序，画出程序执行到(1)和(2)点时的运行栈。

第二章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 -iiiEEFT+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 AC S →→→ L2:bcbBc B aA A AB S ||→→→εL3:εε||aBb B aAb A AB S →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)确定化：最小化：{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,012345601234513501234512460123456012341350123456012310100==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}=====P64–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)确定化：给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====(b)已经确定化了,进行最小化最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a baP64–14(2):确定化：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====1 第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T TS T T a S S G '→''→→' 递归子程序： procedure S; begin if sym='a' or sym='^' then abvance else 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)={)}预测分析表是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,^,+,),#} (2)考虑下列产生式:'→+'→'→'→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)(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='(' thenbegin advance; E; if sym=')' then advance else error endelse errorend;P81–3/***************(1) 是，满足三个条件。

第6章属性文法和语法制导翻译7. 下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：试设计求S.val的属性文法，其中，已知B的综合属性c, 给出由B产生的二进位的结果值。

例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。

【答案】11. 设下列文法生成变量的类型说明：(1)构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。

【答案】第7章语义分析和中间代码产生1. 给出下面表达式的逆波兰表示（后缀式）：【答案】3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

【答案】间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6)4. 按7.3节所说的办法，写出下面赋值句A:=B*(－C+D) 的自下而上语法制导翻译过程。

给出所产生的三地址代码。

5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码：A[i, j]:=B [i, j] + C[A [k, l]] + d [ i+j]【答案】6. 按7.4.1和7.4.2节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。

【答案】用作数值计算时产生的四元式： 用作条件控制时产生的四元式：其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。

7. 用7.5.1节的办法，把下面的语句翻译成四元式序列：While A<C and B<D do if A=1 then C:=C+1 else while A ≦D do A:=A+2; 【答案】第9章 运行时存储空间组织4. 下面是一个Pascal 程序：当第二次( 递归地) 进入F 后，DISPLAY 的内容是什么？当时整个运行栈的内容是什么？ 【答案】第1次进入F 后，运行栈的内容： 第2次进入F 后，运行栈的内容： 109 8 7 6 5 4 3 2 1第2次进入F 后，Display 内容为：5. 对如下的Pascal 程序，画出程序执行到(1)和(2)点时的运行栈。

编译原理考试陈火旺（含答案）编译原理试题 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)构造优先函数。