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

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::=i1ropi2{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∧{ifE1.FC=nullthenbeginE1.TC::=NXQ;GEN(J,＿＿,＿＿,0)End;BP(E1.TC,NXQ);EA.TC:=null;EA.FC:=E1.FC}(6)E::=EAE2{ifE2.FC≠nullthenbeginBP(EA.FC,NXQ);E.FC:=nullEndE.TC:=E2.TC;}(7)E0::=E1∨{ifE1.TC:=nullthenbeginE1.TC:=NXQ;GEN(J,＿＿,＿＿,0)End;E0.TC:=E1.TC;BP(E1.TC,NXG);}(8)E::=E0E2{ifE2.TC≠nullthenE.TC:=MERG(E0.TC,E2.TC)ElsebeginBP(E0.TC,NXQ);E.FC:=E2.FCEnd;E.FC:=E2.FC}其中：NXQ指示器指向下一个将要形成但尚未形成的四元式的地址（编号），初值为1，每当执行GEN一次，NXQ自动加1。GEN是一个语义过程，该过程把四元式加入四元式表区中。E.TC和E.FC分别表示E所对应的四元式需回填“真”、“假”出口的四元式地址所构成的链。MERG（P1,P2）为一函数，把以P1和P2为链首的两个链合二为一作为函数值，回送合并后的链首。BP（P，t）为一语义过程，BP是BACKPATCH的缩写。这是一“回填”过程，它把以P为链首所链接的每个四元式的第四区段都填为t。Jrop是根据关系运算符rop定义的条件转移。5.试写出PASCAL循环语句forI:=1toNdoS的语义程序，假定该语句的文法为F1::=fori:=1toNS::=F1doS1解答：根据题设文法，for语句的语义子程序为：F1::=fori:=1toN{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::=F1doS1{BACKPATCH(S1.chain,NXQ);GEN(+,F1.place,‘1’,F1.place);GEN(J,＿,＿,F1.quad);BACKPATCH(S.chain,NXQ)}6.写出条件赋值语句i:=ifBthenE1elseE2的语义子程序。其中B是布尔表达式，E1和E2是算术表达式，i代表与E1、E2类型相同的左部变量。按写出的语义子程序生成条件赋值语句Z:=ifACthenx+yelsex-y+0.5的四元式序列。解答：按条件赋值语句的语义给出该语句的文法如下：A1::=i:=A2::=A1ifBthenA3::=A2E1elseS::=A3E2相应的语义子程序为:(1)A1::=i:={A1.place:=entry(i)}(2)A2::=A1ifBthen{BP(B.TC,NXQ);A2.chain:=B.FC;A2.place:=A1.place}(3)A3::=A2E1else{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:=ifACthenx+yelsex-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语句repeatS1;S2;…;SnuntilE;的语义子程序.其中E是条件表达式.解答:PASCAL的repeat语句的文法为:R1→repeatL→S|LsSLs→L;R2→R1LuntilS→R2E于是repeat语句各产生式的语义子程序为:R1→repeat{R1.QUAD:=NXQ}L→S{L.CHAIN:=S.CHAIN}Ls→L;{BACKPATCH(L.CHAIN,NXQ)}L→LsS1{L.CHAIN:=S1.CHAIN}R2→R1Luntil{R2.QUAD:=R1.QUAD;BACKPATCH(L.CHAIN,NXQ)}S→R2E{BACKPATCH(E.FC,R2.QUAD);S.CHAIN:=E.TC}8.为便于填写被说明的名字的性质,试修改下面关于变量类型说明的文法,并给出相应的语义动作。待修改的类型说明文法为：D→namelistinteger|namelistnamelist→i,namelist|i解答：(1)为便于填写名字的属性，将上述文法修改为：D→namelist，D1D→iintegerD→irealnamelist→namelist1,inamelist→i于是，相应的语义动作为：D→iinteger{FILL(ENTRY(i),int);D.ATT:=int}D→ireal{FILL(ENTRY(i),real);D.ATT:=real}D→namelist，D1{for队列namelist.QUEUE的每一项PdoFILL(P,D1.ATT);D.ATT:=D1.ATT}namelist→i{建立一个队列namelist.QUEUE,它只包含一项ENTRY（i）}namelist→namelist1,i{把ENTRY(i)排在namelist1.QUEUE的末端；namelist.QUEUE:=namelist1.QUEUE}注意：其中FILL（P，A）是一语义过程，其功能是把属性A添进P所指向的符号表入口的有关区段。语义变量D.ATT用以记录说明语句所规定的属性。（2）若类型说明的文法为：D→namelistintegerD→namelistrealnamelist→namelist1,inamelist→i相应的语义动作为：D→namelistinteger{for队列namelist.QUEUE的每一项PdoFILL(P,int);}D→namelistreal{for队列namelist.QUEUE的每一项PdoFILL(P,real);}namelist→i{建立一个队列namelist.QUEUE它只包含一项ENTRY(i)}namelist→namelist1,i{把ENTRY(i)排在namelist.QUEUE的末端；namelist.QUEUE:=namelist1.QUEUE}9.(中国科学院计算所1996年)某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题：D→attrlistnamelist|attrlist(D)Namelist→id,namelist|idAttrlist→Aattrlist|AA→decimal|fixed|float|realD→attrlist(D)的含义是：在括号中的声明提到的所有名字有attrlist中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性添入符号表。解答：相应的翻译方案为：D’→{D.num=0;}DD→attrlist{namelist.num=D.num+attrlist.num;}namelistD→attrlist{D1.num=D.num+attrlist.num;}(D1)Namelist→id{addattr(id.entry,namelist.num);}Namelist→id,{namelist1.num=namelist.num;}namelist1{addattr(id.entry,namelist.num);}attrlist→Aattrlist1{attrlist.num=attrlist1.num+1;}attrlist→A{attrlist.num=1;}10.写出翻译过程调用语句的语义子程序。要求生成的四元式序列在转子指令之前的参数四元式par按反序出现（即和实在参数的顺序相反），在此情况下翻译过程调用语句时是否需要语义变量（队列）QUEUE呢？解答：为使过程调用语句的语义子程序产生的参数四元式par按反序出现，过程调用语句的文法为：S→calli(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→calli(arglist){WHILEarglist.STACK≠nulldoBegin把arglist.STACK栈顶上托出去，并放入P元中；GEN（par,＿,＿,P）End;GEN(call,＿,＿,ENTRY(i))}11.(中国科学院计算所1994)设有文法G[S]：S::=(L)|aL::=L,S|S给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出