《编译原理试题》由会员分享，可在线阅读，更多相关《编译原理试题（9页珍藏版）》请在金锄头文库上搜索。
1、中间语言与语法制导翻译重点与难点重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。三地址码，各种语句的目标代码结构、属性文法与翻译模式。难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。基本要求掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法(结构)树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的
2、翻译、过程调用翻译。例题解析例1给定文法E-TR.i:=T.pRE.p:=R.sR-addopTR1.i:=mknode(addop.val,R.i,T.p)RR.s:=R1.sR-:R.s:=R1.sT(E)T.p:=E.pT-idT.p:=mkleaf(id,id.entry)T-numT.p:=mkleaf(num,num.val)(1)指出文法中的各非终结符具有哪些综合属性和哪些继承属性画出按本翻译模式处理表达式a+20+(b-10)时所生成的语法树【解】(1)E的综合属性p,R的继承属性i,综合属性s；T的综合属性p处理表达式a+20+(b-10)时所生成的语法树如下例2定义一个计算
3、器的属性文法，完成一个输入表达式值的计算和显示【解】计算器的文法LfEE-E1+T|TT-T1*F|FFf(E)|digit引进属性val,计算器的属，庄文法：L6Eprint(E.val)(L的虚属性)EE1+TE.val:=El.val+T.valE6TE.val:=T.valTT1*FT.val:=Tl.val*F.valT6FT.val:=F.valF)(E)F.val:=E.valFdigitlexvalF.val:=digit.lexval是单词digit的属性例3给出对输入串6-33*5+4的分析树与属性计算3*5+3*5+4的分析树与属性计算LPrint(19)E.val=19
4、digit.lexval=3例4定义一个说明语句的属性文法【解】说明语句的文法DfTLTfintTfrealLfL1,idLfid要解决的问题：记录标识符的类型和类型信息传递方法：引进属性type,和in,用T.type记录类型信息，并传给L.in,说明语句的属性文法如下：DfTLL.in:=T.typeT-intT.type:=integerTfrealT.type:=realLfL1,idL1.in:=L.inaddtype(id.entry,L.in)Lfidaddtype(id.entry,L.in)entry单词id的属性addtype在符号表中为变量填加类型信息区55给出输入串re
5、alid1,id2,id3的分析树和属性计算例6设下列文法生成变量的类型说明DfidLLf,idL|:TTfinteger|real试构造一个翻译模式，把每个标识符的类型存入符号表。解解】解题思路这是一个对说明语句进行语义分析的题目，不需要产生代码，但要求把每个标识符的类型填入符号表中。解答对D,L,T设置综合属性type。过程addtype(id,type)用来把标识符id及其类型type填入到符号表中。翻译模式如下：DfidLaddtype(id.entry,L.type)Lf,idL1addtype(id.entry,L1.type);L.type:=L1.type;Lf:TL.type
6、:=T.typeTfintegerT.type:=intergerTfrealT.type:=real例7文法G的产生式如下：S-(L)|aLfL,S|S(1)试写出一个语法制导定义，它输出配对括号个数；(2)写一个翻译方案，打印每个a的嵌套深度。如(a),a),打印2,1。解解】解题思路本题包括两部分，第1部分要求写语法制导定义，第2部分要求写翻译方案。语法制导定义(或属性文法)可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案(也称翻译模式)给出了使用语义规则进行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。解
7、答为SL引入属性h,代表配对括号个数。语法制导定义如下：产生式S - (L)S f a语义规则S.h:=L.h+1S.h:=0LfL1,SL.h:=L1.h+S.hL-SL.h:=S.hSfSprint(S.h)(2)为S、L引入d，代表a的嵌套深度。翻译方案如下：SfS.d:=0;SS，(L.d:=S.d+1;L)Sfaprint(S.d);LfL1.d:=L.d;L1S.d:=L.d;SLfS.d:=L.dS例8下列文法对整型常数和实型常数施用加法运算符“+”生成表达式;当两个整型数相加时，结果仍为整型数，否则，结果为实型数：EfE+T|TT-num.num|num(1) 试给出确定每个子
8、表达式结果类型的属性文法。(2) 扩充(1)的属性文法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该注意使用一元运算符inttoreal把整型数转换成实型数，以便使后缀形如加法运算符的两个操作数具有相同的类型。【解】解题思路确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文法，使之把表达式翻译成后缀形式。我们将不在name或num.num向T归约的时候输出该运算对象，而是把运算对象的输出放在T或E+T向E归约的时候。这是因为考虑输出类型转换算符inttoreal的动作可能在E+T归约的时候进行，如果这时两个运算又t象都在前面name或num.num向T归约的
9、时候已输出，需要为第1个运算对象输出类型转换算符时就已经为时太晚。还要注意的是，在E+T向E归约时，该加法运算的第1个运算对象已经输出。所以E-E+T的语义规则不需要有输出E运算对象的动作。解答(1)为文法符号E和T配以综合属性type,用来表示它们的类型。类型值分别用int和real来表示。确定每个子表达式结果类型的属性文法如下：产生式语义规则EE1+TT.type:=ifE1.type=intandT.type=intthenintelserealE-TE.type:=T.typeT-num.numT.type:=realT-numT.type:=int(2)下面属性文法将表达式的后缀表示
10、打印输出，其中lexeme属性表示单词的拼写。产生式语义规则EE1+TifE1.type=realandT.type=intthenbeginE.type:=real;print(T.lexeme);print(inttoreal);endelseifE1.type=intandT.type=realthenbeginE.type:=real;print(inttoreal);print(T.lexeme);endelsebeginE.type:=E1.type;print(T.lexeme);endprint(+);EfTE.type:=T.type;print(T.lexeme);T-nu
11、m.numT.type:=real;T.lexeme:=num1.lexeme|.|num2.lexemeT-numT.type:=int;T.lexeme:=num.lexeme;例9将下列语句翻译为逆波兰表示(后缀式)、三元式和四元表示：a:=(b+c)*e+(b+c)/f【解】解题思路把中缀式转换为后缀式的简单方法：按中缀式中各运算符的优先规则，从最先执行的部分开始写，一层层套。如avb+cAadVa+bwe,先把b+c写为bc+；然后把av套上去，成为abc+v；再把ad表示为ad;然后把A套上去，成为abc+vadA,依此类推。四元式由4个部分组成：算符op、第1和第2运算量arg1
12、和arg2，以及运算结果result。运算量和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。如果op是一个算术或逻辑算符，则result总是一个新引进的临时变量，用于存放运算结果。三元式只需3个域：op、arg1和arg2。与四元式相比，三元式避免了临时变量的填入，而是通过计算这个临时变量的语句的位置来引用这个临时变量。我们很容易把一个算术表达式或一个赋值句表示为四元式序列或三元式序列。解答逆波兰表示为：bc+e*bc+f/+:=三元式序列为：(1)(+，b，c)(2)(*，(1)，e)(3)(+，b，c)(4)(/，(3)，f)(5)(+，(2)，(4)(6)(:=，a，(5
13、)四元式序列为：(1)(+，b，c，T1)(2)(*，T1，e，T2)(3)(+，b，c，T3)(4)(/，T3，f，T4)(5)(+，T2，T4，T5)(6)(:=，T5，-，a)例10利用回填技术把语句whilea0orb0doifc0andd0orb0将被翻译为：ifa0gotoLtruegotoL1L1:ifb0gotoLtruegotoLfalse而c0andd0gotoL3gotoLfalseL3:ifd0gotoLtruegotoLfalse有关if和while语句的属性文法如表2所示。应用表1和表2不难生成含if和while的语句的三地址代码表1产生布尔表达式三地址代码的语义规则产生式语义规则EfE1orE2E1.true:=E.true;E1.false:=newlable;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.codeEfE1andE2E1.true:=newlable;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.true:)|E2.codeEfnotE1E1.tr
