编译原理分知识点习题-语法制导和翻译(共8页).doc

《编译原理分知识点习题-语法制导和翻译(共8页).doc》由会员分享，可在线阅读，更多相关《编译原理分知识点习题-语法制导和翻译(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上1. 一般情况下，为什么语义分析部分仅产生中间代码？解答：一般情况下，语义分析部分仅产生中间代码，其原因是：可使难点分解，分别解决。可对语义分析产生的中间代码进行优化，以产生高效率的目标代码。语义分析通常与机器无关，目标代码往往与机器有关。把语义分析与目标代码生成分开，可让一个语义分析程序适用于多个目标代码生成程序。2.（湖北省高等教育自学考试）什么是语法制导翻译？为什么把这种方法叫语法制导翻译？解答：所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成对输入符号串的翻译。由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或规约的同时又使

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)

3、（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:

4、=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

5、.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

6、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解

7、答：根据题设文法，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. 写

8、出条件赋值语句i :=if B then E1 else E2的语义子程序。其中B是布尔表达式，E1和E2是算术表达式，i代表与E1、E2类型相同的左部变量。按写出的语义子程序生成条件赋值语句Z:=if AC 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

9、.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 AC then x+y else x-y+0.5的四元式序列为:(1) ( J,A,C, (3)(2) ( J , , ,(6)(3) (+,X,Y,T1)(4) (:=,T1,

10、,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.

11、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于是，相应的语义

12、动作为：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

13、 注意：其中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.QU

14、EUE它只包含一项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) 的含义是：在括号中的声明提到的所有名字有att

15、rlist中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性添入符号表。解答：相应的翻译方案为：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 a

16、ttrlist1 attrlist.num=attrlist1.num +1; attrlist A attrlist.num=1; 10. 写出翻译过程调用语句的语义子程序。要求生成的四元式序列在转子指令之前的参数四元式par按反序出现（即和实在参数的顺序相反），在此情况下翻译过程调用语句时是否需要语义变量（队列）QUEUE呢？解答：为使过程调用语句的语义子程序产生的参数四元式par按反序出现，过程调用语句的文法为：S call i (arglist)Arglist EArglist arglist1,E按照该文法，语法制导翻译程序将不需要语义变量队列QUEUE，但需要一个语义变量栈STAC

17、K，用以实现按反序记录每个实在参数的地址。翻译过程调用语句的语义子程序为：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

18、：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试写出一个语法制导定义，它输出配对括号个数。写出一个翻译方案，打

19、印每个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;

20、 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.

21、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+

22、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

23、 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

24、给出其语法制导定义及自底向上分析的翻译方案，并比较两者的不同。解答： 语法制导定义为： 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

25、:=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.

26、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标志，且每个变量说明中仅包含一个标识符；可允许的类型仅整

27、型、实型数组类型与指针类型；数组规定为一维，且下界恒为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.

28、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专心-专注-专业