编译基本知识考试陈火旺(含答案解析)

_编译原理试题A (2003.12.4)一、回答下列问题：(30分)1.(6分)对于下面程序段program test(input,output)谢谢阅读var i,j:integer;procedure CAL(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→ABCB.u:=S.uA.u:=B.v+C.vS.v:=A.vA→aA.v:=3*A.uB→bB.v:=B.uC→cC.v:=1画出字符串abc的语法树;对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少?谢谢阅读(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？精品文档放心下载5. (5分)对下列四元式序列生成目标代码：_A:=B*CD:=E+AG:=B+CH:=G*D其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。精品文档放心下载(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。二、(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。精品文档放心下载三、(6分)写一个文法使其语言为L(G)={anbncm|m,n≥1，n为奇数，m为偶数}。谢谢阅读四、(8分)对于文法G(S):SbMbM(L|aLMa）写出句型b(Ma)b的最右推导并画出语法树。写出上述句型的短语，直接短语和句柄。五、(12分)对文法G(S)：→a|^|(T)→T，S|S构造各非终结符的FIRSTVT和LASTVT集合;谢谢阅读构造算符优先表;是算符优先文法吗?构造优先函数。六、(8分)设某语言的do-while语句的语法形式为SdoS(1)WhileE感谢阅读其语义解释为：S(1)的代码 真E的代码 假_针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：感谢阅读写出适合语法制导翻译的产生式；写出每个产生式对应的语义动作。七、(10分)将语句whileC>0doifA B=0thenC:=C+DelseC:=C*D感谢阅读翻译成四元式。八、(10分)设有基本块如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T2画出DAG图；设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分析表0

br3

ACTIOND as3

#

S1

GOTOB

D21

accs4r24r6S5r665r4r46s7r17S88r5r5_(注：答案格式为 步骤 状态 符号 输入串)_编译原理试题A (2003.12.4)一、回答下列问题：(30分)(6分)对于下面程序段programtest(input,output)谢谢阅读var i,j:integer;procedure CAL(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分)谢谢阅读(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。精品文档放心下载G(M)：M→TBT→Ba|B→Db|eT|D→d|解答：计算文法的FIRST和FOLLOW集合：(4分)精品文档放心下载FIRST(M)={a，b，e，d，} FIRST(T)={a，b，e，d，}精品文档放心下载FIRST(B)={b，e，d，} FIRST(D)={d，}感谢阅读FOLLOW(M)={#} FOLLOW(T)={a，b，e，d，#}精品文档放心下载FOLLOW(B)={a，#} FOLLOW(D)={b}精品文档放心下载检查文法的所有产生式，我们可以得到：_该文法不含左递归，该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相感谢阅读交。该文法的非终结符T、B和D，它们都有候选式，而且感谢阅读FIRST(T)∩FOLLOW(T)={a，b，e，d}≠感谢阅读所以该文法不是LL(1)文法。(2分)(4分)考虑下面的属性文法产生式语义规则S→ABCB.u:=S.uA.u:=B.v+C.vS.v:=A.vA→aA.v:=3*A.uB→bB.v:=B.uC→cC.v:=1画出字符串abc的语法树;对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少。谢谢阅读答：(1) (2分)SA B Ca b c(2)S.v的值为18(2分)(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？精品文档放心下载答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。精品文档放心下载_(5分)对下列四元式序列生成目标代码：A:=B*C谢谢阅读D:=E+AG:=B+CH:=G*D其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。感谢阅读答: 目标代码序列LDR0BMULR0CLDR1EADDR1R0LDR0BADDR0CMULR0R1STR0H(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。谢谢阅读答：逆波兰式：(abcd-*+)(1分)三元式序列:(2分)OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)抽象语法树：(2分)+*-ab c d二、(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。谢谢阅读答：_(2分)构造相应的正规式：(a|b)*ab(a|b)*感谢阅读(3分)aa0123456abbb(3分)确定化：II0I1{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}bbbaaaaa012345abbb最小化：{0，1，2} {3，4，5}{0，2}，1，{3，4，5}b a a0a1b3三、(6分)写一个文法使其语言b为L(G)={anbncm|m,n≥1，n为奇数，m为偶数}。精品文档放心下载答：文法G(S):SACAaaAbb|abCccCcc|cc四、(8分)对于文法G(S):SbMbM(L|aLMa）写出句型b(Ma)b的最右推导并画出语法树。写出上述句型的短语，直接短语和句柄。答：1.(4分)SbMbb(Lbb(Ma)bb2.(4分)(短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)

_SbLTM a )五、(12分)对文法G(S)：→a|^|(T)→T，S|S构造各非终结符的FIRSTVT和LASTVT集合;谢谢阅读构造算符优先表;是算符优先文法吗?构造优先函数。答：(1)(4分)FIRSTVT(S){a,^,(}FIRSTVT(T){,,a,^,(}谢谢阅读LASTVT(S){a,^,)}LASTVT(T){,,a,^,)}感谢阅读(2)(4分)a ^ ( ) ,_a>>^>>(<<<=<)>>,<<<>>是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。(1分)精品文档放心下载优先函数(3分)a^(),F44244G55523六、(8分)设某语言的do-while语句的语法形式为SdoS(1)WhileE精品文档放心下载其语义解释为：S(1)的代码 真E的代码 假针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：精品文档放心下载写出适合语法制导翻译的产生式；写出每个产生式对应的语义动作。答：(1).适合语法制导翻译的文法(4分)G(S):RdoUR S(1) WhileSU E(2).(4分)Rdo{ R.QUAD:=NXQ }_UR S(1) While{U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN,NXQ)}精品文档放心下载SUE{BACKPATCH(E.TC,U.QUAD);S.CHAIN:=E.FC}谢谢阅读答案二：(1)SdoM1S(1)WhileM2EMε(4分)(2)Mε{M.QUAD:=NXQ}(4分)SdoM1S(1)WhileM2E{BACKPATCH(S(1).CHAIN,M2.QUAD);感谢阅读BACKPATCH(E.TC,M1.QUAD);S.CHAIN:=E.FC}七、(10分)将语句whileC>0doifAB=0thenC:=C+DelseC:=C*D翻译成四元式。精品文档放心下载答：(j>，C，0，102)(j，-，-，112)(jnz，A，-，106)(j，-，-，104)(j=，B，0，106)(j，-，-，109)(+，C，D，T1)(:=，T1，-，C)(j，-，-，100)(*，C，D，T2)(:=，T2，-，C)_(j，-，-，100)八、(10分)设有基本块如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T2画出DAG图；设L，M，N是出基本块后的活跃变量，请给出优化后的四元式序列。感谢阅读答：1.(6分)n9 L*n10n4n8T2,MT4T2,N* - +n1 n2 n3 n5 n6 n7_T1T33AB12CD(4分)M:=A*BS1:=C-DL:=12*S1N:=C+D九、(8分)文法G(S)及其LR分析表如下，请给出串bab