编译原理分知识点习题 语法制导和翻译.doc

1. 一般情况下，为什么语义分析部分仅产生中间代码？解答：一般情况下，语义分析部分仅产生中间代码，其原因是：可使难点分解，分别解决。可对语义分析产生的中间代码进行优化，以产生高效率的目标代码。语义分析通常与机器无关，目标代码往往与机器有关。把语义分析与目标代码生成分开，可让一个语义分析程序适用于多个目标代码生成程序。2.（湖北省高等教育自学考试）什么是语法制导翻译？为什么把这种方法叫语法制导翻译？解答：所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成对输入符号串的翻译。由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或规约的同时又使用这些语义规则来知道翻译与最终产生目标代码，所以称为语法制导翻译。3. 给出将附值语句翻译成四元式的语法制导定义，允许右部表达式含有加法、乘法、取负、括号运算。生成赋值语句X:=B*(C+D)+A的四元式。解答：赋值语句的自下而上的语法制导翻译过程描述为：规则 语义动作（1）A:=i:=E GEN (:=,E.PLACE,ENTRY(i) ) （2）E:=E1+E2 E.PLACE:=NEWTEMP; GEN(+,E1.PLACE, E2.PLACE,E.PLACE)（3）E:= E1*E2 E.PLACE:=NEWTEMP; GEN(*,E1.PLACE, E2.PLACE,E.PLACE)（4）E:=-E1 E.PLACE:=NEWTEMP; GEN(,E1.PLACE,E.PLACE)(5)E:=(E1) E.PLACE:= E1.PLACE (6)E:=i E.PLACE:= ENTRY(i) 生成的赋值语句X:=B*(C+D)+A的四元式为：(+，C,D,T1)(*,B,T1,T2)(+,T2,A,T3)(:=,T3,X)4. 给出将布尔表达式翻译成四元式的语法制导定义。解答：布尔表达式的语义子程序为：规则 语义动作(1) E:=I E.TC:=null;E.FC:=NXQ; GEN (Jez , ENTRY(i), ,0) (2) E:= i1 rop i2 E.TC:=null;E.FC:=NXQ; GEN (Jnrop,ENTRY(i1), ENTRY(i2),0)(3) E:= (E1) E.TC:=E1.TC, E.TC:=E1.TC; (4) E:= ¬ E1 E.TC:=NXQ; GEN ( J, , , 0); BP (E1.FC, NXQ);(5) EA:=E1 if E1.FC=nullthen begin E1.TC:=NXQ; GEN ( J, , , 0) End;BP ( E1.TC , NXQ );EA.TC:=null; EA.FC:=E1.FC (6) E := EAE2 if E2.FCnullthen begin BP (EA.FC, NXQ); E.FC:=nullEndE.TC:=E2.TC; (7) E0:=E1 if E1.TC:=nullthen begin E1.TC:=NXQ; GEN ( J, , , 0)End;E0.TC:=E1.TC;BP (E1.TC,NXG);(8) E:=E0E2 if E2.TCnullthen E.TC:=MERG(E0.TC,E2.TC)Else begin BP (E0.TC ,NXQ); E.FC:=E2.FCEnd;E.FC:=E2.FC其中：l NXQ指示器指向下一个将要形成但尚未形成的四元式的地址（编号），初值为1，每当执行GEN一次，NXQ自动加1。l GEN是一个语义过程，该过程把四元式加入四元式表区中。l E.TC和E.FC分别表示E所对应的四元式需回填“真”、“假”出口的四元式地址所构成的链。l MERG（P1,P2）为一函数，把以P1和P2为链首的两个链合二为一作为函数值，回送合并后的链首。l BP（P，t）为一语义过程，BP是BACKPATCH的缩写。这是一“回填”过程，它把以P为链首所链接的每个四元式的第四区段都填为t。l Jrop是根据关系运算符rop定义的条件转移。5. 试写出PASCAL循环语句for I:=1 to N do S 的语义程序，假定该语句的文法为F1:= for i:= 1 to NS:= F1 do S1解答：根据题设文法，for语句的语义子程序为：F1:= for i:= 1 to N F1.place:=entry (i); GEN(:=, 1 , ,F1.place); Final:=newtemp; GEN( :=,N.place, ,final); F1.chain:=NXQ; F1.quad:=NXQ ;GEN( J>,F1.place ,final,0)S:= F1 do S1 BACKPATCH (S1.chain,NXQ); GEN (+,F1.place, 1,F1.place); GEN (J, , ,F1.quad); BACKPATCH (S.chain,NXQ)6. 写出条件赋值语句i :=if B then E1 else E2的语义子程序。其中B是布尔表达式，E1和E2是算术表达式，i代表与E1、E2类型相同的左部变量。按写出的语义子程序生成条件赋值语句Z:=if A>C then x+y else x-y+0.5的四元式序列。解答：按条件赋值语句的语义给出该语句的文法如下：A1:=i:=A2:=A1 if B then A3:=A2 E1 elseS:=A3 E2相应的语义子程序为:(1) A1:=i:= A1.place:=entry (i) (2) A2:=A1 if B then BP (B.TC, NXQ); A2.chain:=B.FC; A2.place:=A1.place(3) A3:=A2 E1 else GEN (:=,E1.place, ,A2.place); A3.chain:=NXQ; GEN ( J, , ,0 );BP(A2.chain,NXQ);A3.place:=A2.place(4) S:=A3E2 GEN (:=,E2.place, ,A3.place);BP(A3.chain,NXQ) 按上述语义子程序,条件赋值语句Z:=if A>C then x+y else x-y+0.5的四元式序列为:(1) ( J>,A,C, (3)(2) ( J , , ,(6)(3) (+,X,Y,T1)(4) (:=,T1, ,Z)(5) ( J, , ,(9)(6) (-,X,Y,T2)(7) (+,T2,0.5,T3)(8) (:=,T3, ,Z)(9)7. 写出编译PASCAL语言repeat语句 repeat S1; S2; ; Sn until E;的语义子程序.其中E是条件表达式.解答:PASCAL的repeat语句的文法为:R1repeatLS|LsSLsL;R2R1L untilSR2E于是repeat语句各产生式的语义子程序为:R1repeat R1.QUAD:=NXQLS L.CHAIN:=S.CHAINLsL; BACKPATCH (L.CHAIN,NXQ)LLsS1 L.CHAIN:=S1.CHAINR2R1L until R2.QUAD:=R1.QUAD; BACKPATCH (L.CHAIN,NXQ) SR2E BACKPATCH (E.FC, R2.QUAD); S.CHAIN:=E.TC8. 为便于填写被说明的名字的性质,试修改下面关于变量类型说明的文法,并给出相应的语义动作。待修改的类型说明文法为：Dnamelist integer|namelistnamelisti,namelist|i解答：(1) 为便于填写名字的属性，将上述文法修改为：Dnamelist，D1Di integerDi realnamelistnamelist1,inamelisti于是，相应的语义动作为：Di integer FILL (ENTRY (i) , int ); D.ATT:=int Di real FILL (ENTRY (i) ,real ); D.ATT:=real Dnamelist，D1 for 队列 namelist.QUEUE 的每一项 P do FILL (P,D1.ATT);D.ATT:=D1.ATT namelisti 建立一个队列namelist.QUEUE, 它只包含一项ENTRY（i） namelistnamelist1,i 把ENTRY(i)排在namelist1.QUEUE的末端； namelist.QUEUE:=namelist1.QUEUE 注意：其中FILL（P，A）是一语义过程，其功能是把属性A添进P所指向的符号表入口的有关区段。语义变量D.ATT用以记录说明语句所规定的属性。（2）若类型说明的文法为：Dnamelist integerDnamelist realnamelistnamelist1,inamelisti相应的语义动作为：Dnamelist integer for 队列 namelist.QUEUE的每一项P do FILL (P,int);Dnamelist real for 队列 namelist.QUEUE的每一项P do FILL (P,real);namelisti 建立一个队列namelist.QUEUE它只包含一项ENTRY(i) namelistnamelist1,i 把ENTRY(i)排在namelist.QUEUE的末端；namelist.QUEUE:=namelist1.QUEUE 9. (中国科学院计算所1996年)某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题：D attrlist namelist|attrlist(D) Namelistid,namelist|id AttrlistA attrlist|AA decimal|fixed|float|realD attrlist (D) 的含义是：在括号中的声明提到的所有名字有attrlist中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性添入符号表。解答：相应的翻译方案为：D D.num=0; DD attrlistnamelist.num=D.num+attrlist.num; namelistD attrlistD1.num=D.num+attrlist.num; (D1)Namelist idaddattr(id.entry ,namelist.num); Namelist id,namelist1.num=namelist.num; namelist1addattr (id.entry,namelist.num); attrlist A attrlist1 attrlist.num=attrlist1.num +1; attrlist A attrlist.num=1; 10. 写出翻译过程调用语句的语义子程序。要求生成的四元式序列在转子指令之前的参数四元式par按反序出现（即和实在参数的顺序相反），在此情况下翻译过程调用语句时是否需要语义变量（队列）QUEUE呢？解答：为使过程调用语句的语义子程序产生的参数四元式par按反序出现，过程调用语句的文法为：S call i (arglist)Arglist EArglist arglist1,E按照该文法，语法制导翻译程序将不需要语义变量队列QUEUE，但需要一个语义变量栈STACK，用以实现按反序记录每个实在参数的地址。翻译过程调用语句的语义子程序为：arglist E 建立一个arglist.STACK栈，它只包含一个项E.PLACE arglist arglist1,E 把E.PLACE压入栈arglist1.STACK; arglist.STACK:=arglist1.STACK S call i (arglist) WHILE arglist.STACKnull doBegin 把arglist.STACK栈顶上托出去，并放入P元中；GEN（par, , ,P）End;GEN(call, , ,ENTRY(i) 11. (中国科学院计算所1994)设有文法GS：S:=(L)|aL:=L,S|S给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出配对括号的个数，如对于句子（a,(a,)）,输出是2。解答：加入新的开始符号S和规则S:=S,得到增广文法。语法制导定义如下：S:=S print (S.num); S:=(L) S.num:=L.num+1; S:=a S.num:=0; L:=L1,S L.num:=L1.num+S.num; L:=S L.num:=S.num; 12. (中国科学院软件所1999)文法GS的产生式如下：S:= (L)|aL:= L,S|S试写出一个语法制导定义，它输出配对括号个数。写出一个翻译方案，打印每个a的嵌套深度。如（a,a）,a）,打印2，1。解答：加入新的开始符号S和规则S :=S,得到增广文法：S :=SS:= (L)S:= AL:=L1,SL:=S1 为S，L引入属性h，语法制导定义为： S :=S print (S.h) S:= (L) S.h:=L.h+1 S:= a S.h:=0 L：=L1，S L.h:=L1.h+S.h L：=S L.h:=S.h2 引入属性d，翻译方案定义为： S :=S.d:=0; S S := ( L.d:=S.d +1; L1 , S.d:=L.d; SL:=S.d=L.d; S13. (中国科学院软件所2000年)程序的文法如下：PDDD; D|id ; T|proc id ; D ; S(1) 写一个语法制订定义，打印该程序一共声明了多少个id.(2) 写一个翻译方案，打印该程序每个变量id的嵌套深度。解答：（1） 引进属性i,得到语法制导定义如下：PD print (D,i); DD1;D2 D.i:=D1.i+D2.i;Did : T D.i:=1; Dproc id ;D1 ; S D.i:=D1.i+1; (3) 引进属性l和name,得到翻译方案如下：PD.l:=1; DDD1.l:=D.l; D1 ; D2.l:=D.l; D2Did : T print (id.name ,D.l); Dproc Id : D1.l:=D.l+1; D1 : S14. (中国科学院计算所1995年) 设有文法GS：S;:=L.L|LL:=LB|BB:=0|1给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出S产生的二进制数的值，例如101.101时，输出5.625。解答： 加入新的开始符号S和规则S ：=S，得到增广文法。语法制导定义如下：S :=S print (S.val); S:=L1.L2 S.val:=L1.val+L2.val/2L2.length; S:=L S.val:=L.val; L:=L1B L.val:=L1.val*2+B.val; L.length:=L1.length+1; L:=B L.val:=B.val; L.length:=1; B:=0 B.val:=0; B:=1 B.val:=1; 15. (中国科学院计算所1993年) 请按语法制导的定义将后缀表达式翻译成中缀表达式。注意：不允许出现冗余括号，后缀表达式的文法如下： E:=E1E2+ E:=E1E2* E:=id解答：加入新的饿开始符号S和规则S:=E, 得到增广文法。语法制导定义如下：S:=E print (E.code) E:=E1E2+ E.code:=E1.code| + |E2.code; E.op=+ ; E:=E1E2* if E1.op= + and E2.op= + Then E1.code:= ( |E1.code| ) * | ( | E1.code| ) ; Else If E1.op=+ Then E.code:= ( | E1.code| ) | * |E2.code; Else If E2.op=+ Then E.code:=E1.code| * | ( |E2.code| ); Else E.code:=E1.code| * |E2.code; E.op:= * ; E:=id E.code:=id.lexval; E.op:=$ ; 16. 某程序设计语言说明部分的语法制导定义如下所示：D:=TLT:=intT:=realL:=L1,idL:=id给出其语法制导定义及自底向上分析的翻译方案，并比较两者的不同。解答： 语法制导定义为： D:=TL L.in:=T.typeT:=int T.type:=integerT:=real T.type:=realL:=L1,id L.in:=L.in addtype (id.entry,L.in) L:=id addtype (id.entry, L.in ) 自底向上分析的翻译方案为：D:=T L.in:=T.typeLT:=int T.type:=integerT:=real T.type:=realL:= L.in:=L.inL1,id addtype (id.entry, L.in ) L:=id addtype (id.entry, L.in ) 从上述定义可见，两者的区别仅在于翻译方案中，把语义操作插入在规则右部的任意位置。17. 给出PASCAL语言常量定义的翻译方案。解答： PASCAL语言常量定义的翻译方案为： CONSTDP:=CONST CDT CDT:=CDT: CD CD:=id=num num.ord:=lookCT (num.lexval); id.ord:=num.ord; id.type:=integer ; id.kind:=CONSTANT; add (id.entry, id.kind,id.type,id.ord) CD:=id=id1 id.kind:=CONSTANT; id.type:=id1.typel id.ord:=id1.ord; add (id.entry ,id,kind,id.type,id,ord) 函数lookCT（c）将在常量表中查找常量c。若查不到，则把该常量值录入常量表。不论查到与否，最终将回送常量c之值在常量表中的序号。CONSTANT是表示标识符种类为常量的一个枚举值。过程add是对过程addtype的扩充，它把种类、类型与序号三者填入符号表相应条目中。18. 将 PASCAL语言的饿变量说明简化为：变量说明部分由变量说明组成，不再保留字VAL标志，且每个变量说明中仅包含一个标识符；可允许的类型仅整型、实型数组类型与指针类型；数组规定为一维，且下界恒为1。给出这样的变量说明文法，并给出其翻译方案。解答：按上述规定，变量说明文法为：P:=D;S D:=D; D D:=id; TT:=integer T:=real T:=TT:=ARRAYnumOF T每个类型说明id：T的处理大致如下：确定类型T；确定分配存储地址，让相应变量有相应大小存储区域；为标识符id创建符号表新条目，并在该条目中土如相应类型及所分配的存储地址（通常为相对地址），还可填入标识符的变量标志。基于上述考虑，变量说明的翻译方案如下： P:= offset:=0 D;S D:=D; D D:=id; T enter (id.name,T.type,offset); offset:=offset+T.width T:=integer T.type:=integer; T.width:=4 T:=real T.type:=real; T.width:=8 T:=ARRAYnumOF T1 T.type:=array (num.lexval, T1.type); T.width:=num.lexval*T1.width T:=T1 T.type:=pointer (T1.type); T.width:=4 19. (浙江大学1997年)在一个移入-归约的分析中采用以下的语法制导的翻译模式，在按一产生式归约时，立即执行括号中的动作。 AaB print “0”; Ac print “1”; BAb print “2” ; 当分析器的输入aacbb时，打印的在字符串是什么？解答：分析器的分析过程入图8.1所示.A 5a B 4A b 3a B 2A b 1c由于分析器采用移入-归约的方式进行分析，符号串aacbb的分析过程将按图8.1中所标的归约顺序进行，而在按一产生式归约时，立即执行括号中的动作，所以分析器答应的字符为12020