资源描述：
《编译原理考试试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、回答下列问题：(30分)1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？解答：S-属性文法是只含有综合属性的属性文法。（2分）L-属性文法要求对于每个产生式AàX1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1,X2…Xj-1的属性；（2）A的继承属性。（2分）S-属性文法是L-属性文法的特例。（2分）2．什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）3．划分程序的基本块时，
2、确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。5．(6分)对下列
3、四元式序列生成目标代码：A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本块出口的活跃变量，R0和R1是可用寄存器答：LDR0，BMULR0，CLDR1，EADDR1，FADDR0，R1MULR0，2STR0，H6二、设S={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(0
4、1)*1(0
5、1)(3分)NFA:(2分)1110432eeee100确定化：(3分)I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,
6、2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}014321001000111三、写一个文法使其语言为L(G)={anbmambn
7、m,n≥1}。(6分)答：文法G(S):S®aSb
8、BB®bBa
9、ba四、对于文法G(E):(8分)E®T
10、E+TT®F
11、T*FF®(E)
12、iETF(E)E+TFiTT*F1.写出句型(T*F+i)的最右推导并画出语法树。2.写出上述句型的短语，直接短语、句柄和素短语。答：1.(4分)EÞTÞFÞ(E)Þ(E+T)Þ(E+F)6Þ(E+i)Þ(T+i)Þ(T*F+i)2.(4分)短语：(T*F+i
13、),T*F+i,T*F,i直接短语：T*F,i句柄：T*F素短语：T*F,i五、设文法G(S)：(12分)1．构造各非终结符的FIRSTVT和LASTVT集合；2．构造优先关系表和优先函数。(12分)答：(6分)FIRSTVT(S)={i，+，)，(}FIRSTVT(A)={+，)，(}FIRSTVT(B)={)，(}LASTVT(S)={i，+，*，(}LASTVT(A)={+，*，(}LASTVT(B)={*，(}优先关系表:(3分)i+()*i><<<+>><<>(>>>)<<<*>>>优先函数:(3分)i+()*f26616g14661六、设某语言的do-while语句
14、的语法形式为(9分)S®doS(1)WhileE其语义解释为：真假S(1)的代码E的代码6针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1)写出适合语法制导翻译的产生式；(2)写出每个产生式对应的语义动作。答：(1).适合语法制导翻译的文法(3分)G(S):R®doU®RS(1)WhileS®UE(2).(6分)R®do{R.QUAD:=NXQ}U®RS(1)While{U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN,NXQ)}S®UE{BACKPATCH(E.TC,U.QUAD);S.CHAIN:=E.FC}答案二：(1)S®doM1S(1)W
15、hileM2EM®ε(3分)(2)M®ε{M.QUAD:=NXQ}(6分)S®doM1S(1)WhileM2E{BACKPATCH(S(1).CHAIN,M2.QUAD);BACKPATCH(E.TC,M1.QUAD);S.CHAIN:=E.FC}七、(8分)将语句6if(A0)thenwhileC>0doC:=C+D翻译成四元式。(8分)答：100(j<，A，X，102)101(j，-，-，109)102(j>，B，0，104)103(j，-，-，109)104(j>，C，0
