编译原理试题A (含答案)

《编译原理试题A (含答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理试题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集合，并判断

2、该文法是否是LL(1)的，请说明理由。G(M)：M→TBT→Ba

3、eB→Db

4、eT

5、eD→d

6、e3.(4分)考虑下面的属性文法产生式语义规则S→ABCA→aB→bC→cB.u:=S.uA.u:=B.v+C.vS.v:=A.vA.v:=3*A.uB.v:=B.uC.v:=1(1)画出字符串abc的语法树;(2)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少?4.(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？5.(5分)对下列四元式序列生成目标代码：13A:=B*CD:=E+AG

7、:=B+CH:=G*D其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。1.(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。一、(8分)构造一个DFA，它接受S={a，b}上所有包含ab的字符串。二、(6分)写一个文法使其语言为L(G)={anbncm

8、m,n≥1，n为奇数，m为偶数}。三、(8分)对于文法G(S):1.写出句型b(Ma)b的最右推导并画出语法树。2.写出上述句型的短语，直接短语和句柄。四、(12分)对文法G(S)：S→a

9、^

10、(T)T→T，S

11、S(1)构造各非

12、终结符的FIRSTVT和LASTVT集合;(2)构造算符优先表;(3)是算符优先文法吗?(4)构造优先函数。五、(8分)设某语言的do-while语句的语法形式为S®doS(1)WhileE其语义解释为：真假S(1)的代码E的代码13针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：(1)写出适合语法制导翻译的产生式；(2)写出每个产生式对应的语义动作。一、(10分)将语句whileC>0doifAÚB=0thenC:=C+DelseC:=C*D翻译成四元式。二、(10分)设有基本块如

13、下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T21.画出DAG图；2.设L，M，N是出基本块后的活跃变量，请给出优化后的四元式序列。三、(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1)S→DbB(2)D→d(3)D→ε(4)B→a(5)B→Bba(6)B→εLR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r513(注：答案格式为步骤状态符号输入串)1

14、3编译原理试题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)传名，请写出程序执行的输出结果。答：(1)3(2)16(3)16(每个值2分)2.(6分)计算文法G(M)的每

15、个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。G(M)：M→TBT→Ba

16、eB→Db

17、eT

18、eD→d

19、e解答：计算文法的FIRST和FOLLOW集合：(4分)FIRST(M)={a，b，e，d，e}FIRST(T)={a，b，e，d，e}FIRST(B)={b，e，d，e}FIRST(D)={d，e}FOLLOW(M)={#}FOLLOW(T)={a，b，e，d，#}FOLLOW(B)={a，#}FOLLOW(D)={b}检查文法的所有产生式，我们可以得到：131.该文法不含

20、左递归，2.该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。3.该文法的非终结符T、B和D，它们都有e候选式，而且FIRST(T)∩FOLLOW(T)={a，b，e，d}≠f所以该文法不是LL(1)文法。(2分)1.(4分)考虑下面的属性文法产生式语义规则S→ABCA→aB→bC→cB.u:=S.uA.u:=B.v+C.vS.v:=A