04-05第二学期编译原理试题.doc

20042005年度第2学期 计算机学院02级【编译原理】考试题（A）考试形式： 开卷 考试时间：2005年 6月24日9:55-11:30学号姓名1234567附加题总分分数1. （6分）回答下列问题1） 在存储管理中，为什么在活动记录内为临时变量分配空间？答：在栈式存储管理方式中，以活动记录的形式为一次过程调用（函数调用）中的局部数据提供存储空间，该活动记录随过程调用被分配，随过程调用的结束而释放；临时变量通常用于保存表达式计算中的中间结果，在活动记录中为临时变量分配空间，可以保证该空间随过程调用被分配，随活动记录的释放被自动释放。2） 在符号表管理中，为什么将变量名保存在符号表中？答：符号表中将保存变量名及其各种属性，变量名将用于变量的识别、涉及变变量名与存储空间的绑定、以及类型、作用域、存储地址等各种变量属性的设置、获取等各种维护功能。2. (8分)试消除下列文法中的左递归。 S SaA|Se|BA BbA|BB cSd|e解： 消除左递归 提取左因子 改写后的文法 S SaA|Se|B A BbA | B S BS S（aA | e ）| B B ( bA | e) S aA S | e S | e 引进非终结符S 引进非终结符A A B A S BS A B A A bA | eS（aA | e ）S | e A bA | e B cSd|e3. (15分)写出下列文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL（1）分析表，并说明它是否为LL（1）文法。 S aA|BAA cB|eB bB|e各候选式的FIRST集 (4分) FIRST（aA）=a FIRST（BA）= b，c，e FIRST（cB）=cFIRST（e）=e FIRST（bB）= b FIRST（e）=e各非终结符的FOLLOW集 (4分)FOLLOW(S)= # FOLLOW(A)= # FOLLOW(B)= c，#LL（1）分析表 (5分) a b c # S S aA S BA S BA S BA A A cB A e B B bB B e B e 说明它是否为LL（1）文法 (2分) 判断1分，理由1分因为LL（1）分析表无冲突，所以该文法是LL（1）文法。4.（18分）给定文法GS S L + L L L LB|BB 0|1(1) 构造拓广文法，按LR(0)分析的需要画出识别这个拓广文法的所有规范句型活前缀的DFA。解1：相应的DFA如下图所示。0SI0:S.SS .L+ LS .L L .LBL .BB .0B .1I8:S L + L. L L.BB .0B .1I2:S L.+ LS L.L L.BB .0B .1I3:L B.I1:S S.LL01B0BB01+BI7:L LB.I6:S L + .LL .LBL .BB .0B .1I5:B 1.I4:B 0.11解2：0 S0 S 11S 0 L 2 + 6 L 82S 0 L 23L 0，6 L 2，8 B 74L 0，6 B 35B 0，2，6，8 0 46B 0，2，6，8 1 5I0：（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）I1：（0，1）I2：（1，1），（2，1），（3，1），（5，0），（6，0）I3：（4，1）I4：（5，1）I5：（6，1）I6：（1，2），（3，0），（4，0），（5，0），（6，0）I7：（3，2）I8：（1，3），（3，1），（5，0），（6，0）0SI0:（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）I8:（1，3），（3，1），（5，0），（6，0）I2:（1，1），（2，1），（3，1），（5，0），（6，0）I3:（4，1）I1:（0，1）LL01B0BB01+BI7:（3，2）I6:（1，2），（3，0），（4，0），（5，0），（6，0）I5:（6，1）I4:（5，1）11(2) 求出这个文法的SLR（1）分析表。解：给产生式编号：SL + L SL LLB LB B 0 B1FOLLOW(S)=#FOLLOW(L)=0,1,+,# FOLLOW(B)=0,1,+,#状态ACTIONGOTO01+#SLB0S4S51231acc2S4S5S6r273r4r4r4r44r5r5r5r55r6r6r6r66S4S5837r3r3r3r38S4S5r175.（7分）写出能产生字母表x,y上的不含两个相邻的x,且不含两个相邻的的全体符号串的有限状态自动机。解：6.（16分）设文法GE:E RP|P P (E)|i R RP+| RP* |P+|P*画出句子i+i*(i+i)的语法分析树，给出其最右推导和最左归约，并指出它的句柄。解：(1)语法分析树：（2）最右推导：E RP R(E) R(RP) R(Ri) R(P+i) R(i+i) RP*(i+i) Ri*(i+i) P+i*(i+i) i+i*(i+i)最左归约：i+i*(i+i) P + i*(i+i)P+i*(i+i) Ri*(i+i)Ri*(i+i) RP*(i+i)RP*(i+i) R(i+i)R(i+i) R(P+i)R(P+i) R(Ri)R(Ri) R(RP)R(RP) R(E)R(E) RPRP E句子i+i*(i+i)的句柄为：i；7. (10分)下面是关于文法S xYS|yXS|e X yXX|xY xYY|y的一个语法制导定义，S xYS1S.nx := Y.nx + S1.nx + 1 S.ny := Y.ny + S1.nyS yXS1 S.nx := X.nx + S1.nx S.ny := X.ny + S1.ny + 1S eS.nx := 0 S.ny := 0X yX1 X2 X.nx := X1.nx + X2.nx X.ny := X1.ny + X2.ny + 1X x X.nx := 1 X.ny := 0Y xY1 Y2 Y.nx := Y1.nx + Y2.nx + 1Y.ny := Y1.ny + Y2.nyY yY.nx := 0 Y.ny := 1 (1) 请说明上述语法制导定义的作用是什么。(2) 按照此语法指导定义给出句子xxxyyyxy的语义分析过程或画出带注释的语法分析树解：（1）该语法制导定义的作用是统计句子中的x和y的个数；（4分）（2）按照该语法制导定义对句子xxxyyyxy进行语义分析的结果为：S.nx = 4；S.ny = 4；（6分）附加题将左线性文法G=(VN,VT,P,S)转换成等价的有限状态自动机M=(Q,VT, ,q0,F)的一种等价变换中认为“对产生式ABaP则M中用移动A(B，a)与之对应”，请问这种对应使用的是自顶向下的分析思想还是自底向上的分析思想？为什么？（本题第一问最高奖励3分，第二问最高奖励7分）解：使用的是自底向上的分析方法归约。A(B，a)表示在状态B遇到输入a时，到达状态A，将状态看成是目前已经分析出来的中间结果，这样就相当于目前的分析已经得到了前缀B，加上a后相当于获得前缀A，也就是相当于B和紧接着的a可以归约成A，这与产生式ABa所表示出来