编译原理试题.doc

中间语言与语法制导翻译重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。基本要求掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。例题解析例1 给定文法 E - T R.i := T.p R E.p := R.s R - addopT R1.i := mknode( addop.val, R.i, T.p ) R R.s := R1.s R - e R.s := R1.s T - ( E ) T.p := E.p T - id T.p := mkleaf( id, id.entry ) T - num T.p := mkleaf( num, num.val ) (1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性 画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树【解】(1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p(2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下 +(ID, a) +（NUM, 20） - ( ID, b) (NUM, 10)例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示,【解】计算器的文法L E E E1 + T | T T T1 * F | FF ( E ) | digit引进属性val，计算器的属性文法：L E print( E.val )（L的虚属性）E E1 + T E.val := E1.val + T.valE T E.val := T.valT T1 * F T.val := T1.val * F.valT F T.val := F.valF ( E ) F.val := E.valF digit F.val := digit.lexvallexval 是单词 digit 的属性例3给出对输入串6-3 3*5+4 的分析树与属性计算【解】3*5+4 的分析树与属性计算+ *E.val=19E.val=15T.val=4T.val=15F.val=4digit.lexval=4F.val=5T.val=3F.val=3digit.lexval=3 LPrint(19)digit.lexval=5例4定义一个说明语句的属性文法【解】说明语句的文法D T LT intT real L L1,idL id要解决的问题：记录标识符的类型和类型信息传递方法：引进属性type,和in,用T.type记录类型信息，并传给L.in, 说明语句的属性文法如下: D T LL.in := T.typeT int T.type := integerT realT.type := realL L1,idL1.in := L.in addtype( id.entry, L.in )L idaddtype( id.entry, L.in )entry 单词 id 的属性addtype 在符号表中为变量填加类型信息例5 给出输入串real id1,id2,id3 的分析树和属性计算 D T.type=realL.in=real real, Id3, Id2L.in=realL.in=realId1addtypeaddtype例6 设下列文法生成变量的类型说明 D id L L , id L | : T T integer | real 试构造一个翻译模式，把每个标识符的类型存入符号表。【解】解题思路这是一个对说明语句进行语义分析的题目，不需要产生代码，但要求把每个标识符的类型填入符号表中。解答对D，L，T设置综合属性type。过程addtype(id,type)用来把标识符id及其类型type填入到符号表中。翻译模式如下：D id Laddtype(id.entry,L.type)L ,id L1 addtype(id.entry,L1.type);L.type:=L1.type;L : T L.type:=T.typeT integer T.type:=intergerT real T.type:=real例7文法G的产生式如下： S (L) | a L L , S | S (1)试写出一个语法制导定义，它输出配对括号个数; (2)写一个翻译方案，打印每个a的嵌套深度。如(a),a),打印2,1。【解】解题思路本题包括两部分，第1部分要求写语法制导定义，第2部分要求写翻译方案。语法制导定义（或属性文法）可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案（也称翻译模式）给出了使用语义规则进行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。解答为S、L引入属性h,代表配对括号个数。语法制导定义如下：产生式语义规则S (L)S.h:=L.h+1S aS.h:=0L L1 , SL.h:=L1.h+S.hL SL.h:=S.hSSprint(S.h)(2)为S、L引入d，代表a的嵌套深度。翻译方案如下：SS.d:=0;SS (L.d:=S.d+1; L )S aprint(S.d);L L1.d:=L.d; L1 S.d:=L.d; SL S.d:=L.dS例8下列文法对整型常数和实型常数施用 加法运算符“+”生成表达式;当两个整型数相加时，结果仍为整型数，否则，结果为实型数： E E+T | T T num.num | num (1)试给出确定每个子表达式结果类型的属性文法。 (2)扩充(1)的属性文法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该注意使用一元运算符inttoreal把整型数转换成实型数，以便使后缀形如加法运算符的两个操作数具有相同的类型。【解】解题思路确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文法，使之把表达式翻译成后缀形式。我们将不在name或num.num向T归约的时候输出该运算对象，而是把运算对象的输出放在T或ET向E归约的时候。这是因为考虑输出类型转换算符inttoreal的动作可能在ET归约的时候进行，如果这时两个运算对象都在前面name或num.num向T归约的时候已输出，需要为第1个运算对象输出类型转换算符时就已经为时太晚。还要注意的是，在ET向E归约时，该加法运算的第1个运算对象已经输出。所以EET的语义规则不需要有输出E运算对象的动作。解答（1）为文法符号E和T配以综合属性type,用来表示它们的类型。类型值分别用int和real来表示。确定每个子表达式结果类型的属性文法如下：产生式语义规则EE1TT.type:=if E1.type=int and T.type=int then int else realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=int(2)下面属性文法将表达式的后缀表示打印输出，其中lexeme属性表示单词的拼写。产生式语义规则EE1Tif E1.type=real and T.type=int then begin E.type:=real; print(T.lexeme); print(inttoreal); endelse if E1.type=int and T.type=real then begin E.type:=real; print(inttoreal); print(T.lexeme); endelse beginE.type:=E1.type;print(T.lexeme);endprint(+);ETE.type:=T.type;print(T.lexeme);Tnum.numT.type:=real;T.lexeme:=num1.lexeme|“.”|num2.lexemeTnumT.type:=int;T.lexeme:=num.lexeme;例9 将下列语句翻译为逆波兰表示(后缀式)、三元式和四元表示： a:=(b+c)*e+(b+c)/f【解】解题思路把中缀式转换为后缀式的简单方法：按中缀式中各运算符的优先规则，从最先执行的部分开始写，一层层套。如ab+cada+be，先把b+c写为bc+；然后把a套上去，成为abc+；再把ad表示为ad；然后把套上去，成为abc+ad，依此类推。四元式由4个部分组成：算符op、第1和第2运算量arg1和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)四元式序列为：(1)(+ ，b，c，T1)(2)(* ，T1，e，T2)(3)(+ ，b，c，T3)(4)(/ ，T3，f，T4)(5)(+ ，T2，T4，T5)(6)(:= ，T5，-，a)例10 利用回填技术把语句while a0 or b0 doif c0 and d0 or b0将被翻译为：if a0 goto Ltruegoto L1L1: if b0 goto Ltruegoto Lfalse而c0 and d0 goto L3goto LfalseL3: if d0 goto L2 goto L1L1：if b0 goto L2 goto LnextL2：if c0 goto L3 goto L0L3：if d0 goto L4 Goto L0L4：T1:=y+1 x:=T1 goto L0Lnext：例11 C语言中的for语句的一般形式为：for(E1;E2;E3) s 其意义如下：E1；while(E2) do beginS;E3;end试构造一个属性文法和翻译模式，把C语言的for语句翻译成三地址代码。【解】解题思路本题既要求构造属性文法，也要求构造相应的翻译模式。因此，有必要回忆一下属性文法和翻译模式的区别。我们知道，属性文法(有时也称语法制导定义)可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来；而翻译模式(也称为翻译方案)是一种适合语法制导翻译的描述形式，它给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来。为了明确翻译目标，我们首先给出for语句的中间代码结构如图1所示。根据C语言的for语句的语义和以上中间代码结构可以构造出属性文法。为了构造属性文法相应的翻译模式，通常可采用两种方法：一种方法是在原有产生式中引入必要的标记非终结符；另一种方法是对文法进行分解和改造。两种方法的目的都是为了便于语法制导翻译。翻译把C语言的for语句翻译成三地址代码的属性文法如下：产生式语义动作Sfor(E1;E2;E3) S1E2.lable:=newlable;E3.lable:=newlable;E2.true:=newlable;E2.false:=S.next;S1.next:=E3.lable;S.code:=E1.code|gen(E2.lable:)|E2.code|gen(E3.lable:)|E3.code|gen(gotoE2.lable)|gen(E2.true:)|S1.code|gen(gotoE3.lable)下面我们用两种方法构造相应上述属性文法的翻译模式。方法一：引入M1、M2和N这3个标记非终结符。M1用来记住E2的开始地址，M2用来记住M3的开始地址。N是用来产生E3后面的goto语句，从上面的中间代码结构来看，产生这个goto语句时，转移地址应该是已知的了，但语句是在N归约时产生的，这时不能访问M1的属性，因此这个转移的目标地址是回填。所求的翻译模式如下：Sfor(E1;M1E2;M2E3) N S1 emit(gotoM2.next); backpatch(E2.truelist,N.next); backpatch(S1.nextlist,M2.next); backpatch(N.nextlist,M1.next); S.nextlist:=E2.falselist;M M.next:=nextquadN N.nextlist:=makelist(nextquad); emit(goto_); N.ne