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

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

2、来知道翻译与最终产生目标代码，所以称为语法制导翻译。3. 给出将附值语句翻译成四元式的语法制导定义，允许右部表达式含有加法、乘法、取负、 括号运算。生成赋值语句X=E*(C+D)+A的四元式。解答：赋值语句的自卜而上的语法制导翻译过程描述为：规则语义动作(1) A:=i:=EGEN (:=E.PLACE.,ENTRY(i) ) (2) E:=E1+E2 E .PLACE =NEWTEMP;GEN(+，E】.PLACE, E2.PLACE.E.PLACE)(3) E:= EE2 E.PLACE:=NEWTEMP;GEN(凭E】.PLACE, EMPLACE,E.PLACE)(4) E:=.EA

3、EPLACE:=NEWTEMP;GEN(E】PLACE.EPLACE)(5)E:=(艮)E.PLACE:= EMPLACE(6)E 二=1E.PLACE:= ENTRY(i) 生成的赋值语句X:=B*(C+D)+A的四元式为:什，CQJ4)(*BT1,T2)(+.T2.AJ3)(:=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 (JmopJEN

4、TRYg), ENTRY(F) E：=Q)(4)E:=-E1ETC=EiTC,ETC=ELTC; E.TC:=NXQ;GEN (J.0): BP (ELFU NXQ);(5) EA:=E!A if EFCnullthen beginE1.TC:=NXQ;GEN (J.,0)End;BPtETCNXQ );EA.TC:=null; EdFC严E】FC (6) E := EAE2if E2.FCiiull then beginBP (EA.FC, NXQ); E.FC:=nuUEndE.TC:=E2.TC; (7) EO:=EXV if E】TC=iiullthen begm E】TC:=NXQ;

5、GEN (I 0)End;EO.TCWTC;BP (E】TC,NXG);(8)E:=E°E2 if E2.TCxnullthenE.TC:=MERG(E°.TC.E2.TC)Else beginBP (EMC ,NXQ);E.FC:=E2.FCEnd;E.FC:=E2.FC其中： NXQ指示器指向下一个将要形成但尚未形成的四元式的地址(编号)，初值为1,每当 执行GEN次，NXQ自动加U GEN是一个语义过程，该过程把四元式加入四元式表区中。 E.TC和E.FC分别表示E所对应的四元式需回填“真”、“假”出I的四元式地址所构 成的链。 MERG (P1,P2)为一函数，把以

6、P1和P2为链首的两个链合二为一作为函数值，回送 合并后的链首。 BP (P, t)为一语义过程，EP是BACKPATCH的缩写。这是一 “回填”过程，它把以 P为链首所链接的每个四元式的第四区段都填为to Jrop是根据关系运算符rop定义的条件转移。5. 试写出PASCAL循环语句foi 1=1 to Ndo S的语义程序，假定该语句的文法为 Ff：= for i:= 1 toNS:= Fi doS1解答：根据题设文法，f&语句的语义子程序为：Fi：:= for i:= 1 toNFi.place:=entry (1); GEN(:=, T,Fi.place);Fmal:=nele

7、mp; GEN( :=.N.place,filial);Fi.chain:=NXQ; Fi.quad:=NXQ ;GEN(place .finaLO)S:=Fi doS1BACKPATCH (Scham.NXQ); GEN j+R place, 4Fi.place); GEN (J,_，巧.quad); BACKPATCH (S.chaukNXQ)6.写出条件赋值语句i :=if B then Ei elseE：的语义子程序。其中E是布尔表达式，E】和氏是算术表达式，1代表与E】、氏类型相同的 左部变量。按写出的语义子程序生成条件赋值语句Z:=if A>C then x+v else x

8、v+05的四元式序列。解答：按条件赋值语句的语义给出该语句的文法如F:Ai：:=i:=A2:=Ai if B thenA3：:=Az Ei elseS:=A$ Er相应的语义子程序为：(1) A】二=1】=Al.place:=entiy (i) (2) A2：:=Ai if B then(3) A3：:=A： Ei elseBP (E.TC, NXQ); A2.chaiii:=B.FC; A：.place :=Ai .place GEN (:=,Ei.place, _ ,A：.place); A3.cham:=NXQ;GEN ( J, _、_,0 );BP(A2.chaiii,NXQ);A3.

9、place:=A2.place(4) S:=A3E2GEN (:= Ez.place, ,A3.place);BP(A3.chain.NXQ) 按上述语义子程序,条件赋值语句Z:=if A>C thenx+y else x-y+0.5的四元式序列为:JZ JZ JZ JZ JZ JZ JZ JZ JZ 123456789 ( /(X /lx /(X /(X /(V z(x /(J>,AG )(J , 一 一(6) (+：XTi) v c=g 一z)(人 _，_，(刃) CXXTJ (+,T2,O.5J3) (：=, 一Z)7.写出编译PASCAL语言repeat语句repeatSi

10、； S2；Sn until E;的语义子程序其中E是条件表达式.解答:PASCAL的“peat语句的文法为:Ri- repeatL->S|LsSlT；R：f R1L untilS-R：E于是repeat语句各产生式的语义子程序为:Ri- repeat L SLT;L->LsSlR：-*R1L untilRi.QUAD:=NXQL.CHAIN:=S.CHAINBACKPATCH (L.CHAIN.NXQ)L.CHAIN:=Si.CHAINR2.QUAD-R1.QUAD; BACKPATCH (L.CHAIN,NXQ) Sf R：EBACKPATCH (E.FC, Rz.QUAD);

11、S.CHAIN:=E.TC8为便于填写被说明的名字的性质，试修改下面关于变量类型说明的文法，并给出相应的语义动作。待修改的类型说明文法为：D-namelist integEt namelistnamelist-* i, name 1 i st i解答：(1为便于填写名字的属性，将上述文法修改为:Dfnamelist, DIDf i integerD i realnamelist-* name 1 i s 11, i namelist- i于是，相应的语义动作为: Df i integerD i realDfnamelist, DInamelist-* inamelist-* name list

12、1, iFILL (ENTRY (1)，mt); D.ATT:=int FILL (ENTRY (i) ,real )； D.ATT:=realfor 队列 namelist.QUEUE 的每一项 P do FILL (RD】.ATT); DArr=D】ATT 建立一个队列namelist.QUEUE.它只包含一项ENTRY (i) 把 ENTRY(i)排在 nainelistQUEUE 的末端； namelist.QUEUE: lamelist1 .QUEUE 注意：其中FILL (P, A)是一语义过程，其功能是把属性A添进P所指向的符号表入I I的 有关区段。语义变量D.ATT用以记录说

13、明语句所规定的属性。(2)若类型说明的文法为：D-namelis t int egerD-namelis t real namelist-* name list1, inamelisti相应的语义动作为：Df namelis t integerfor 队列 namelist.QUEUE 的每一项 P do FILL (Emt);Df namelis t realfor 队列 namelist.QUEUE 的每一项 P do FILL (Pjeal);namelisti建立一个队列namelist.QUEUE它只包 含一项 ENTRY(i) namelist- name list1, i把 EN

14、TRY(i)排在 namelist.QUEUE 的末端；nainelist.QUEUEnainelist1 .QUEUE 9.(中国科学院计算所1996年)某些语言允许给出名字表的一个属性表，也允许声明嵌在另 一个声明里面，下面文法抽彖这个问题：D>attrlistnamelist|attilist(D)Name list>id,namelist id Attrlist>A attrlist|AA>decinial|fixed|float|realD - attrlist (D)的含义是：在括号中的声明提到的所有名字有attrlist中给出的属 性，而不管声明嵌套多少层

15、。写一个翻译方案，它将每个名字的属性添入符号表。解答：相应的翻译方案为：DJ ->D.num=O; DD attrlistnamelist.num=D.num+attilist.num; namelistD attrlist D).num=D .niun-rattrlist.num; (D JNamelist -ldfaddattrd.entiy aiamelist.num); Namelist -ldnamelisti.nunnamelist.num; namelistiaddatti (list.num); attrlist A attrlisti attr

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

17、反序记录每个实在参数的地址。翻译过程调用语句的语义子程序为：aiglist Eaiglist aiglist1、E建立一个arglist.STACK栈，它只包含一个项E.PLACE 把 E.PLACE 压入栈 arglistSTACK;aiglist. STACK:=arghst1. STACK S call i (aiglist)WHILE aighst.STACKnull doBegin把arglist.STACK栈顶上托出去，并放入P元中；GEN (par,一P)End;GEN(call, 一 一ENTRY(i) 11. 仲国科学院计算所1994)设有文法GS：S 二=(L)|aL:=L

18、.S|S给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对拾 号的个数,如对于句子(a,(a,)，输出是2。解答：加入新的开始符号S和规则S*S,得到增广文法。语法制导定义如下：print (S.num);S.num:=L.num+l;S.num:=O; L.num:=L i .num+S.num; L.num:=S.num; st=sS 二=(L)S:=aL:=LbSL:=S12. (中国科学院软件所1999)文法GS的产生式如2S 二=(L)|aL:= L、S|S 试写出一个语法制导定义，它输出配对括号个数。写出一个翻译方案，打印每个a的嵌套深度。如(a,a) ,a

19、)，打印2, 1。 解答：加入新的开始符号S，和规则S，aS,得到增广文法：s=sSx(L)S:=AL:=LbSL；：=S1为s； L引入属性h,语法制导定义为：S=Spnnt (S.h)S 二=(L)S.h:=L.h+lS:= aS.h:=OL：: =Li, SL.h:=Li.h+S.hL：: =SL.h:=S.h2引入属性d,翻译方案定义为：S：=S.d:=O; SS :='C L.d:=S.d+l; Li Sd:=Ld; S，L:=S.d=L.d; S13. (中国科学院软件所2000年)程序的文法如下：Pf DDD; D|id ; T|proc id ; D ; S(1) 写一

20、个语法制订定义，打印该程序一共声明了多少个id.(2) 写一个翻译方案，打印该程序每个变量id的嵌套深度。 解答：(1)引进属性b得到语法制导定义如下：PDprint (D,i); DDi；D?D.i:=Di.i+D2.i；D->id :TD.i:=l; D-proc id :DI ; S引进属性1和得到翻译方案如卞:D->Di.l:=D.l; DiDz.l-D.l; d2DidTprint （ Ql）； DprocIdDi.l:=D.l+l;D）s14. （中国科学院计算所1995年）设有文法GS：S;:=L.L|LL:=LB|BE:=0|l给此文法配上语义动作子程

21、序（或者说为此文法写一个语法制导定义），它输出S产生 的二进制数的值，例如101.101时，输出5.625。解答：加入新的开始符号9和规则9 : =S,得到增广文法。s=spimt (S.val); S:=Li.LzS.val:=Li.val+L2.vaV2L2 kngth;S:=LS.val:=L.val; L:=LiBL.val:=Li.val*2+B.val; L.length:=Li.lengths 1;L:=BL.val:=B.val; L.length:=l; B:=0B.val:=0;B:=lB.val:=l; 语法制导定义如下：15. (中国科学院计算所1993年)请按语法制导

22、的定义将后缀表达式翻译成中缀表达式。注 意：不允许出现冗余拾号，后缀表达式的文法如下：E：=E1E2+E:=EiE2*E:=id解答：加入新的饿开始符号S和规则S:=E,得到增广文法。语法制导定义如下：S:=Eprint (E.code) E：=EiE2+E.code:=Ei.code|p |Ez.code; E.op=>+> E:=E1E2*if Ei.op= + and E：.op=ThenEi.code:= X c |Ei.code| 0 ' * MP Cll Ei.code| 4 ) c;ElseIf El .op=,+JThen E.codeh C | Ei.co

23、de| ')' |4 * 'HEz.code; ElseIf E2.op=5+,Then E.code:=Ei.code|c c |p (4 |E2.code| y ； ElseE.code:=Ei.code|c* ' |E2.code;E.oph *；E:=idE.code:=id.lexval; E.op='$，;16.某程序设计语言说明部分的语法制导定义如下所示：D:=TL T:=mt T:=real L:=LijdL:=id给出其语法制导定义及自底向上分析的翻译方案，并比较两者的不同解答：语法制导定义为：D:=TLL.in:=T.typeT:=i

24、iitT.type:=iiitegerT:=realT.type:=realL:=LljdL.m:=L.m addtvpe (id.entryX.iii) L:=idaddtype (id.entiy, L.m) 自底向上分析的翻译方案为：D:=TL T:=mtL.iii:=T.typeT.type:=integerT:=realT.type:=realL:=L.in:=L.inLbidaddtvpe (id.entiy. L.m) L:=idaddtype (id.entry, L.iii)从上述定义可见，两者的区别仅在于翻译方案中，把语义操作插入在规则右部的任意位置。17. 给出PASCAL语言常量定义的翻译方案。解答：PASCAL语言常量定义的翻译方案为：CONSTDP:=CONST CDTCDT:=CDT: CDCD:=id=num num.ord: =lookCT (num.lexval);id.ord:=num.oid;ld.type :=iiiteger ;id .kind :=CONSTANT;add (id.entry; 1d.kind4d.typejd.01d) CD:=id=id i id .kind :=CONSTANT; ld.type:=id 1 .typelid.ord:=idi.ord;add (id.