第十一章语义分析和中间代码生成

第十一章语义分析和中间代码生成第o节符号表在程序中,用户用标识符定义了不少名字来代表不同的数据对象,编译程序将这些名字保存在符号表中。符号表除了记录名字本身而外,还记录了与名字关联的各种属性信息。一.符号表的一般形式每个名字对应一个表项,一个表项包括名字域和信息域。名字信息其中,信息域通常设若干子域及标志位，其内容可以是和名字有关的任何信息：类型,种属,长度,相对地址,数组的内情向量,记录与分量的联系,形参标志,说明标志,赋值标志等。因名字的长度、信息域的组成及长度可能是各不相同的,一般采用间接表技术。二.常用的符号表结构1.线性表:用N个数组A1,A2,…,AN来存放符号表的N个子域2.HASH表第一节语义分析概论一.语义分析的主要工作(1)语义检查:如类型是否一致,数组维数是否正确。(2)语义处理:对说明语句,登记信息;对可执行语句,生成中间代码。二.语法制导翻译为每个产生式配上一个语义子程序,在语法分析过程中,当用一个产生式进行匹配或归约时,就调用相应的语义程序。上述语义子程序既可能包含了语义检查,也可能包含了语义处理,其核心是为了生成相应的中间代码。例：语法分析采用自底向上的LR分析法XABYCDZXY状态栈符号栈语义栈BA

B的语义值A的语义值

状态栈符号栈语义栈X

X的语义值

状态栈符号栈语义栈DCX

D的语义值C的语义值X的语义值

状态栈符号栈语义栈YX

Y的语义值X的语义值

状态栈符号栈语义栈Z

Z的语义值

语义可以是：“值”、“类型”、“种属”、“地址”等。可见：在分析过程中必须保存语义值。三.四元式形式:(op,ARG1,ARG2,RESULT)op—运算符,ARG1—第一运算量,ARG2—第二运算量,RESULT—结果如:A:=-B*(C+D)翻译成

(@,B,_,t1)(+,C,D,t2)(*,t1,t2,t3)(:=,t3,_,A)由此可见:四元式出现顺序和表达式计值顺序一致;四元式之间的联系是通过临时变量实现的。第二节简单赋值语句的翻译一.语义变量及过程(1)E.place:语义变量，它和非终结符E相关联，表示存放E值的变量名在符号表的入口或其整数编码(2)newtemp:语义函数,每调用一次就返回一个可用的临时变量地址。在后面的使用中，将其表示为t1,t2,…(3)entry(i):语义函数，对变量查符号表返回i在符号表中的入口(4)gen（OP,ARG1,ARG2,RESULT):语义过程,产生四元式并填入四元式表中，同时ip:=ip+1（四元式编号增加1）二.翻译方案E→E1opE2{E.place:=newtemp;gen(op,E1.place,E2.place,E.place)}E→-E1

{E.place:=newtemp;gen(@,E1.place,_,E.place)}E→(E1){E.place:=E1.place}E→i{E.place:=entry(i)}A→i:=E{gen(:=,E.place,_,entry(i))}举例:a:=-b*(c+d)的移进-归约过程a:=-b*(c+d)a:=-E1*(c+d)a:=E2*(c+d)a:=E2*(E3+d)a:=E2*(E3+E4)a:=E2*(E5)a:=E2*E6a:=E7Aii:=i:=-i:=-ii:=-E1i:=E2i:=E2*i:=E2*(i:=E2*(ii:=E2*(E3i:=E2*(E3+i:=E2*(E3+ii:=E2*(E3+E4i:=E2*(E5i:=E2*(E5)i:=E2*E6i:=E7A

aa_a__a___a__ba_t1a_t1_a_t1__a_t1___a_t1__ca_t1__c_a_t1__c__a_t1__c_da_t1__t2a_t1__t2_a_t1_t2a_t3

a:=-b*(c+d):=-b*(c+d)-b*(c+d)b*(c+d)*(c+d)*(c+d)*(c+d)(c+d)c+d)+d)+d)d))))

(@,b,_,t1)(+,c,d,t2)(*,t1,t2,t3)(:=,t3,_,a)

符号栈PLACE输入四元式a:=-b*(c+d)的翻译过程3.类型转换对表达式E增加类型属性E.type;引进类型转换指令(itr,x,_,t)E→E1opE2的语义子程序如后三.类型转换对表达式E增加类型属性E.type;引进类型转换指令(itr,x,_,t)E→E1opE2的语义子程序如后t:=newtemp;ifE1.type=integerandE2.type=integerthenbegingen(opi,E1.place,E2,place,t);

E.type:=integerendelseifE1.type=realandE2.type=realthenbegingen(opr,E1.place,E2.place,t);

E.type:=realendelseifE1.type=integerthenbegint1:=newtemp;gen(itr,E1.place,_,t1);gen(opr,t1,E2.place,t);

E.type:=realendelsebegint1:=newtemp;gen(itr,E2.place,_,t1);gen(opr,E1.place,t1,t);

E.type:=realend;E.place:=t;一.文法D→D1;D2│i:TT→real│integer│array[num]ofT1│↑T1可见,非终结符D产生一系列i:T形式的说明语句。第三节说明语句的翻译二.主要工作不产生可执行指令,仅负责填表,将被说明对象的类型及相对存储位置记入各自的符号表中。三.语义变量及过程(1)offset:相对位移量,初值为0,是一个全局变量(2)T.type:数据类型(3)T.width:数据宽度(4)enter:语义过程,将变量名及其类型和相对存储位置记入符号表中。四.翻译方案对一个程序来说，offset的初值为0，针对这个赋初值的语义动作，引进了标记非终结符M及空字产生式M→ε的归约。M→ε{offset:=0}D→D1;D2D→i:T{enter(,T.type,offset);offset:=offset+T.width}T→integer{T.type:=integer;T.width:=4}T→real{T.type:=real;T.width:=4}T→array[num]ofT1{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}T→↑T1

{T.type:=pointer(T1.type);T.width:=4}五.其它说明语句(1)说明语句可能为如下形式D→integernamelist│real

namelistnamelist→namelist,i│i先改写为D→D,i│integeri│reali(2)说明语句也可为如下形式D→namelistinteger|namelistrealnamelist→namelist,i|i翻译时需引进队列namelist.QUEUE用以存放变量名

(3)对数组说明的翻译：分配内情向量表区,产生在运行时动态地建立内情向量和分配数组空间的目标指令。第四节控制语句的翻译一.布尔表达式的翻译1.文法及其分析B→iB→i1

ropi2作为控制条件的布尔表达式，它为真或假时，要转移到不同的地方。2.语义变量（1）B.T:真出口，记录B为真的转移语句的地址；（2）B.F:假出口，记录B为假的转移语句的地址。3.转移语句的四元式条件转移(jrop,P1,P2,0)(jnz,P1,-,0)无条件转移(j,-,-,0)4.翻译方案B→i{B.T:=ip;gen(jnz,entry(i),-,0);B.F:=ip;gen(j,-,-,0)}B→i1

ropi2{B.T:=ip;

gen(jrop,entry(i1),entry(i2),0);B.F:=ip;gen(j,-,-,0)}二.无条件转移语句的翻译1.gotoL的两种情形（1）L已经定义…L:.../*此时，将L登记入符号表*/…gotoL;/*查表，发现L已定义，生成四元式*/…（2）L未定义…gotoL;/*将L记入符号表，定义否标记为“否”*/…gotoL;/*拉链*/…L:…/*定义否标记改为“是”，回填*/…名字类型…定义否地址L标号未r……(p)(j,_,_,0)……(q)(j,_,_,p)……(r)(j,_,_,q)……………2.带标号语句的处理方法设文法：S→labelSlabel→i:当用label→i:进行归约时(1)若i（假定为L）不在符号表中，则把它填入，置“类型”栏为“标号”，“定义否”栏为“已”，“地址”栏为ip的当前值；(2)若L已在符号表中，但“类型”不为“标号”，或“定义否”为“已”，则“名字重定义”；(3)若L已在符号表中，但“类型”为“标号”，则把标志“未”改为“已”，然后把“地址栏”中的链首取出，同时把ip当前值填入其中，最后执行backpatch（q，ip）语义过程进行回填。其中，backpatch（q，ip）为语义过程：把q为链首的链上所有四元式的第四区段都填为ip。三.条件语句的翻译1.文法及其分析S→ifBthenS1│ifBthenS1elseS2L→S│L;SBS1?ifBthenS1B为假B为真S1的第一条四元式用以“回填BS1S2?ifBthenS1elseS2B为假B为真S1、S2的第一条四元式用以“回填”此处产生一无条件转移语句由上面几个图可见：

(1)B具有真假出口B为真假时的转向不同在翻译B时其真假出口有待“回填”

(2)因if语句的嵌套,必须记录不确定转移目标的四元式的地址—拉链技术2.改写文法M→ifBthenN→MS1elseS→MS1|NS1L→SL→XSX→L;

3.语句变量及过程

(1)N.CHAIN:记录不确定转移目标的四元式形成的链；

如：S.CHAIN记录了S中不确定转移目标的且转向地址均相同的四元式（这些四元式形成一个链,S.CHAIN为链头）如:(p)(j,-,-,0)……(q)(j,-,-,p)……(r)(j,-,-,q)S.CHAIN=r

(2)merge(t1,t2):语义函数,将t1、t2合并，返回合并后的链头t2;(3)backpatch(t1,code):语义过程,用code回填t1;如:(p)(j,-,-,0)(u)(j,-,-,0)………...(q)(j,-,-,p)(v)(j,-,-,u)………...(r)(j,-,-,q)(w)(j,-,-,v)t1=rt2=w执行merge(t1,t2)后得(p)(j,-,-,0)(u)(j,-,-,r)………...(q)(j,-,-,p)(v)(j,-,-,u)………...(r)(j,-,-,q)(w)(j,-,-,v)链头t2=w执行backpatch(t2,120)后:(p)(j,-,-,120)(u)(j,-,-,120)………...(q)(j,-,-,120)(v)(j,-,-,120)………...(r)(j,-,-,120)(w)(j,-,-,120)4.翻译方案M→ifBthen{backpatch(B.T,ip);M.CHAIN:=B.F}N→MS1else{q:=ip;gen(j,-,-,0);

backpatch(M.CHAIN,ip);N.CHAIN:=merge(S1.CHAIN,q)}S→MS1{S.CHAIN:=merge(M.CHAIN,S1.CHAIN)}S→NS1{S.CHAIN:=merge(N.CHAIN,S1.CHAIN)}L→S{L.CHAIN:=S.CHAIN}L→XS{L.CHAIN:=S.CHAIN}X→L;{backpatch(L.CHAIN,ip)}例1:ifa<bthena:=a+b的翻译ifa<bifBB.T=100100:(j<,a,b,0)B.F=101101:(j,-,-,0)ifBthenMM.CHAIN=101backpatch(100,102)Ma:=a+b

MA102:(+,a,b,t1)103:(:=,t1,-,a)MS1S1.CHAIN=0SS.CHAIN=merge(M.CHAIN,S1.CHAIN)=101102例2:ifa<bthena:=a+belsea:=a-b的翻译ifa<bifBB.T=100100:(j<,a,b,0)B.F=101101:(j,-,-,0)ifBthenMM.CHAIN=101backpatch(100,102)Ma:=a+b

MS1S1.CHAIN=0102:(+,a,b,t1)103:(:=,t1,-,a)MS1elseNq=ip=104104:(j,-,-,0)backpatch(M.CHAIN,105)N.CHAIN=merge(S1.CHAIN,q)=104Na:=a-bNS2S2.CHAIN=0105:(-,a,b,t2)106:(:=,t2,-,a)SS.CHAIN=merge(N.CHAIN,S2.CHAIN)=104102105四.while语句的翻译1.文法及其分析S→whileBdoS1BS1?B为假B为真whileBdoS1B的第一条四元式需记录、S1的第一条四元式用以“回填”此处产生一无条件转移语句2.改写文法W→whileD→WBdoS→DS13.翻译方案W→while{W.code:=ip}D→WBdo{backpatch(B.T,ip);D.CHAIN:=B.F;D.code:=W.code}S→DS1{backpatch(S1.CHAIN,D.code);

gen(j,-,-,D.code);S.CHAIN:=D.CHAIN}例3:whilea>bdoifc<dthene:=f+g;的翻译whileWW.code=100Wa>b

WB1B1.T=100100(j>,a,b,0)B1.F=101101(j,-,-,0)WB1doDbackpatch(100,102)D.CHAIN=101D.code=W.code=100Difc<dDifB2B2.T=102102(j<,c,d,0)B2.F=103103(j,-,-,0)102107104100DifB2thenDMbackpatch(102,104)M.CHAIN=103DMe:=f+gDMS1S1.CHAIN=0104(+,f,g,t1)105(:=,t1,-,E)DS2S2.CHAIN=merge(103,0)=103Sbackpatch(103,100)S.CHAIN=101106(j,-,-,100)LL.CHAIN=S.CHAIN=101L;Xbackpatch(101,107)五．循环语句的翻译1.文法及其语义

S→fori:=1toNdoS1其语义为

i:=1;again:ifi

NthenbeginS1;i:=i+1;

gotoagainend代码结构可为：F+0:（:＝，’1’，－，i）F+1:(j<=,i,N,F+3)F+2:(j,-,-,S.CHAIN)F+3:(S1的四元式序列)…...D+0:(+,i,‘1’,i)D+1:(j,-,-,F+1)2.翻译方案(1)为了在生成S1的代码之前生成i:=1等三个语句,必须改写文法F→fori:=1toNdoS→FS1(2)F具有三个语义值

F.CHAIN:记录前述F+2的地址

F.place:记录i在符号表入口

F.again:记录F+1(3)语义子程序F→fori:=1toNdo{gen(:=,’1’,-,entry(i));F.again:=ip;gen(j

,entry(i),N,F.again+2);F.CHAIN:=ip;gen(j,-,-,0);F.place:=entry(i)}S→FS1{backpatch(S1.CHAIN,ip);

gen(+,F.place,’1’,F.place);

gen(j,-,-,F.again);S.CHAIN:=F.CHAIN}例4:forI:=1toNdoM:=M+I的翻译forI:=1to