语法制导翻译和中间代码生成实用教案

1、会计学1语法制导语法制导(zhdo)翻译和中间代码生成翻译和中间代码生成第一页，共111页。第1页/共111页第二页，共111页。what types are allowable in the various language constructs.第2页/共111页第三页，共111页。第3页/共111页第四页，共111页。第4页/共111页第五页，共111页。法主要是属性文法和语法制导翻法主要是属性文法和语法制导翻译译第5页/共111页第六页，共111页。第6页/共111页第七页，共111页。(chnshng)式相联，只引用该式相联，只引用该产生产生(chnshng)式相联的属性。式相联的属

2、性。第7页/共111页第八页，共111页。第8页/共111页第九页，共111页。n T falseT.t := bool 第9页/共111页第十页，共111页。第10页/共111页第十一页，共111页。n终结符只有综合属性。终结符只有综合属性。第11页/共111页第十二页，共111页。(wnf)A性，则称性，则称b是是A的综合属性。的综合属性。第12页/共111页第十三页，共111页。第13页/共111页第十四页，共111页。F(E) F.val:=E.valFdigit F.val:=digit.lexval第14页/共111页第十五页，共111页。n某些非终结符加下标是为了区分某些非终结符

3、加下标是为了区分一个产生式中同一非终结符多次一个产生式中同一非终结符多次出现出现属性属性(shxng)文法的例文法的例第15页/共111页第十六页，共111页。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树设表达式为设表达式为 35+4，则语义动作则语义动作打印打印(d yn)数值数值19第16页/共111页第十七页，共111页。产产 生生 式式语语 义义 规规 则则D TLT intT re

4、alL L1,idL idL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)第17页/共111页第十八页，共111页。n 一个结点的继承一个结点的继承属性值是由此结点属性值是由此结点的父结点和的父结点和/或兄或兄弟弟(xingd)结点结点的某些属性来决定的某些属性来决定的。的。继承继承(jchng)属性属性Real id1,id2,id3DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，第18页/

5、共111页第十九页，共111页。第19页/共111页第二十页，共111页。(ch r)部的合适位置上。部的合适位置上。第20页/共111页第二十一页，共111页。第21页/共111页第二十二页，共111页。第22页/共111页第二十三页，共111页。到计算出所有属性。到计算出所有属性。n一遍扫描一遍扫描在语法分析的同时计在语法分析的同时计算属性值算属性值第23页/共111页第二十四页，共111页。从从ci结点到结点到b结点构造一条有结点构造一条有向边向边第24页/共111页第二十五页，共111页。第25页/共111页第二十六页，共111页。第26页/共111页第二十七页，共111页。第27页/

6、共111页第二十八页，共111页。nL-属性文法允许一次遍历就计算属性文法允许一次遍历就计算出所有属性值出所有属性值第28页/共111页第二十九页，共111页。第29页/共111页第三十页，共111页。n 中间代码中间代码(Intermediate code)n 源程序的一种内部表示源程序的一种内部表示n 不依赖目标机的结构；易于机械生成目标代码；逻不依赖目标机的结构；易于机械生成目标代码；逻辑结构清楚；利于不同目标机上实现同一种语言；辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化。利于进行与机器无关的优化。n 中间代码的几种形式中间代码的几种形式(xngsh)：n 逆波

7、兰、四元式、三元式、间接三元式、树逆波兰、四元式、三元式、间接三元式、树第30页/共111页第三十一页，共111页。tuple code.第31页/共111页第三十二页，共111页。8.3.1 逆波兰逆波兰(b ln)记号记号语言中的表示形式语言中的表示形式逆波兰表示逆波兰表示 a+b a+b*c (a+b)*c a:=b*c+b*d ab+ abc*+ ab+c* abc*bd*+:=第32页/共111页第三十三页，共111页。逆波兰逆波兰(b ln)记号记号n栈顶两元素栈顶两元素C、D相乘并退栈，相乘并退栈，结果进栈结果进栈n栈顶两元素相加，退栈，结果栈顶两元素相加，退栈，结果进栈进栈第3

8、3页/共111页第三十四页，共111页。逆波兰逆波兰(b ln)记号记号 产产 生生 式式 翻翻 译译 规规 则则 EE+T E T T T F T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a第34页/共111页第三十五页，共111页。第35页/共111页第三十六页，共111页。第36页/共111页第三十七页，共111页。:=* *a+cb* *bd第37页/共111页第三十八页，共111页。 (7) ( + (3) (6) ) 第38页/共111页第三十九页，共111页。间接间接(jin ji)三元式三元式 间接间接(jin ji)码表码表(1) ( - C

9、 D ) (1)(2) ( * B (1) ) (2) (3) ( + A (2) ) (3)(4) ( (1) N ) (1)(5) ( / E (4) ) (4)( + (3) (5) ) (3)(5) 三元三元(sn yun)式和树形表示式和树形表示第39页/共111页第四十页，共111页。运算对象及运算结果运算对象及运算结果(ji gu)是是程序中定义的变量，必要时可使程序中定义的变量，必要时可使用编译程序引进的临时变量。用编译程序引进的临时变量。第40页/共111页第四十一页，共111页。第41页/共111页第四十二页，共111页。第42页/共111页第四十三页，共111页。第43页

10、/共111页第四十四页，共111页。第44页/共111页第四十五页，共111页。(1) S id:=E p:= lookup() if p nil then emit(p := E.place) else error(2) EE1+E2 E.place:= newtemp; emit(E.place:=E1.place+E2.place)(3) E E1* *E2 E.place:= newtemp; emit(E.place:=E1.place* *E2.place)产生产生(chnshng)式和语义动作描式和语义动作描述述第45页/共111页第四十六页，共111页。(4) E

11、 - -E1 E.place:=newtemp; emit(E.place:=uminus E1.place)(5) E( E1) E.place:= E1.place(6) Eid E.place:=newtemp; P:=lookup(); if P nil then E.place:=P else error产生产生(chnshng)式和语义动作描述式和语义动作描述第46页/共111页第四十七页，共111页。*n +i *i +r *rn一目运算符一目运算符 itr 将整型转换成实将整型转换成实型型第47页/共111页第四十八页，共111页。 end else 第48页/共

12、111页第四十九页，共111页。第49页/共111页第五十页，共111页。E2.type=int */ 第50页/共111页第五十一页，共111页。第51页/共111页第五十二页，共111页。n | true| false第52页/共111页第五十三页，共111页。第53页/共111页第五十四页，共111页。关系式关系式 a b 等价等价(dngji)的条件的条件语句：语句：if ab then 1 else 0 if ab goto (4) t:=0 goto (5) t:=1 第54页/共111页第五十五页，共111页。emit(E.place,:= notE1.place);E (E1)

13、 E.place:= E1.place);第55页/共111页第五十六页，共111页。其中其中nextstat给出了在输出序列给出了在输出序列(xli)中下一四元式序号。调用中下一四元式序号。调用emit过程，每次加过程，每次加1。第56页/共111页第五十七页，共111页。第57页/共111页第五十八页，共111页。E的代码的代码 S1的代码的代码if E then S1的代码结构的代码结构truefalse第58页/共111页第五十九页，共111页。E.falseE的代码的代码E.true S1的代码的代码jump out S2的代码的代码out:if E then S1 else S2的

14、代码结构的代码结构E的代码的代码 S1的代码的代码jump beginbeginWhile E do S1 代码结构代码结构第59页/共111页第六十页，共111页。n 把条件转移把条件转移(zhuny)的布尔表达式的布尔表达式 E 翻翻译成仅含：条件真译成仅含：条件真转和无条件转和无条件转的四转的四元式。元式。n E：a rop bn if a rop b goto E.truen goto E.false控制语句控制语句(yj)(yj)中布尔表达式的翻译中布尔表达式的翻译第60页/共111页第六十一页，共111页。第61页/共111页第六十二页，共111页。例：语句例：语句 if ab o

15、r cf then S1 else S2 的四元式序列的四元式序列(xli)为为 if ab goto (7) 转移至转移至(E.true) goto (3) if cf goto (7) 转移至转移至(E.true)(6) goto (p+1) 转移至转移至(E.false) 控制控制(kngzh)(kngzh)语句中布尔表达式的翻语句中布尔表达式的翻译译第62页/共111页第六十三页，共111页。(7) S1的四元的四元(s yun)式式 (E.true ) 入口入口 (p) goto (q) (E.false)入口入口(p+1) (S2的四元的四元(s yun)式式) (q)控制语句控制

16、语句(yj)(yj)中布尔表达式的翻译中布尔表达式的翻译第63页/共111页第六十四页，共111页。四元式拉成的链四元式拉成的链第64页/共111页第六十五页，共111页。则链成则链成(10) goto (0) (20) goto (10) (30) goto (20)第65页/共111页第六十六页，共111页。表示表达式表示表达式E的第一个四元式语的第一个四元式语句序号。句序号。第66页/共111页第六十七页，共111页。第67页/共111页第六十八页，共111页。第68页/共111页第六十九页，共111页。第69页/共111页第七十页，共111页。nextstat初值为初值为100E.co

17、debegin为为100E.true的值为的值为100E.false的值为的值为101第70页/共111页第七十一页，共111页。E.codebegin为为104E.true的值为的值为102E.false的值为的值为103第71页/共111页第七十二页，共111页。第72页/共111页第七十三页，共111页。第73页/共111页第七十四页，共111页。第74页/共111页第七十五页，共111页。第75页/共111页第七十六页，共111页。其中其中(qzhng)：S 语句语句L 语句串语句串A 赋值语句赋值语句E 布尔表达式布尔表达式第76页/共111页第七十七页，共111页。元元(s yun

18、)式形成一条链，在转式形成一条链，在转移目标的四元移目标的四元(s yun)式形成后式形成后回填。回填。第77页/共111页第七十八页，共111页。第78页/共111页第七十九页，共111页。n endn 计算表达式计算表达式E，测试，测试(csh)符合哪一个符合哪一个case，相当于多个条件，相当于多个条件转移语句。转移语句。第79页/共111页第八十页，共111页。n next：n Li为与为与case Vi对应对应(duyng)的语句序列的语句序列Si的标号的标号第80页/共111页第八十一页，共111页。第81页/共111页第八十二页，共111页。第82页/共111页第八十三页，共11

19、1页。105 T:=M+I106 M:=T107 goto 102108 第83页/共111页第八十四页，共111页。n对应的产生对应的产生(chnshng)式如式如下：下：n F1 E1n F2 F1;E2n F3 F2;E3n F4 for(F3) n S F4 S1n四元四元(s yun)式序列：式序列：n100 i=1n101 if i=n goto 103n102 goto 107n103 t=s+in104 s=tn105 i=i+1n106 goto 101n107第84页/共111页第八十五页，共111页。第85页/共111页第八十六页，共111页。第86页/共111页第八十七

20、页，共111页。第87页/共111页第八十八页，共111页。第88页/共111页第八十九页，共111页。nextstat然后，产生四元然后，产生四元(s yun)式式(goto q)。第89页/共111页第九十页，共111页。第90页/共111页第九十一页，共111页。第91页/共111页第九十二页，共111页。n(5) L：n(6) endn(7)end第92页/共111页第九十三页，共111页。n处理到第处理到第(n)行行后，第后，第(4)行的行的goto目标目标(mbio)得以得以解决。而第解决。而第(2)行的行的goto L是非是非法的，但只有当法的，但只有当循环关闭时才能循环关闭时才能确定。确定。第93页/共111页第九十四页，共111页。第94页/共111页第九十五页，共111页。指令的前面指令的前面n统计统计par的个数记录实在参数个的个数记录实在参数个数数第95页/共111页第九十六页，共111页。第96页/共111页第九十七页，共111页。第97页/共111页第九十八页，共111页。和性质登记在符号表中。和性质登记在符号表中。第98页/共111页第九十九页，共111页。改写为：改写为：DD1，idn | integer id | real id第99页