编译原理 中间代码生成.ppt

《编译原理 中间代码生成.ppt》由会员分享，可在线阅读，更多相关《编译原理 中间代码生成.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中间代码生成1编译器的前端与后端 2 3语法树,DAG 后缀表达式可以看做语法树的一种线性表示 a b c uminus*b c uminus*+assign 4语法树能通过语法制导定义（SDD）生成.E.g:56三地址代码三地址代码形如:x:=y op z ;其它形式的三地址语句 7翻译时生成临时变量:x+y*z t1:=y*zt2:=x+t1 DAG8表达式的三地址代码表达式的三地址代码9newtemp()生成临时变量:t1,t2,gen()生成中间代码 10生成四元式生成四元式11E.g.关于数组 xi:=y 或者 x:=yi三元式12间接三元式13过程声明14Integers have

2、 width=4 and reals have the width=815跟踪记录过程中变量的作用域P DD D;D|id:T|proc id;D;S16嵌套过程的符号表嵌套过程的符号表exchangereadarrayxaheaderNill sortquicksortto readarraypartitionvkheaderquicksortreadarraryiheaderexchangeheaderto exchangepartition17过程:mktable(previous)-create a new symbol table and return a pointer to th

3、e new table(placed in the header)enter(table,name,type,offset)create a new entry name addwidth(table,width)enterproc(table,name,newtable)create a new entry for the procedure name in the symbol table pointed by table 18For each procedure generated by this grammar,the translation scheme sets up a sepa

4、rate symbol table 1920记录类型记录类型T record D endT record L D endT.type:=record(top(tblptr);T.width:=top(offset);pop(tblptr);pop(offset)L t:=mktable(nil);push(t,tblprt);push(0,offset)21赋值语句赋值语句22lookup()procedure is modified:23By modifying the lookup procedure,we can apply the translation scheme if the m

5、ost closely nested scope rule applies to nonlocal names(like Pascal)Fig.8.1524e.g.pp 479,last paragraph25数组的地址计算Arrays are stored normally in block of contiguous locations A 1-D array Alowhigh,with elements of size w,the ith element Ai begin at location:base+(i-low)w=i w+(base low w)=i w+cA 2-D arra

6、y is normally stored row-major(row-by-row)or column major(column-by-column).26For row-major form,Ai1,i2 is stored at:Some languages give the possibility to specify the size of the array dynamically,when a procedure is called run-time(see sect.7.3,pp.408).The formulas above remain valid,but the upper

7、 and lower limits are not known at compile time.Generalizations for row-major form for Ai1,i2,.,ik (i1n2+i2)n3+i3)nk+ik)w+base(low1n2+low2)n3+low3)nk+lowk)w In order to generate code for array reference we must do a connection of the computation above with the grammar for array reference 27 The key

8、problem in generating code for array references:relate the computation below to a grammar for array referencesA pointer to the symbol-table for array name is passed as synthesized attribute array of Elist28类型转换参与运算的数据类型必须一致 2930布尔表达式布尔表达式 E E or E|E and E|not E|(E)|id relop id|true|falserelop ,3132布

9、尔表达式的SDT:3334控制流语句文法:353637Control-Flow Translation of Boolean Expressions(E.code)E is translate into TAS that evaluate the E as sequence of conditional and unconditional jumps to one of the two locations:E.true and E.false The basic idea for translation:Remember(pp.468):E.place keep the name that h

10、old the value of E E.code keep the sequence of TAS that evaluate E 38(syntax directed definition to produce TAS code for Booleans)39例子:40Revisited:E E1+E2E.type:=arith;if E1.type=arith and E2.type=arith thenbegin /*normal arithmetic add*/E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place

11、+E2.place)endelse if E1.type:=arith and E2.type=bool thenbegin E2.place:=newtemp;E2.true:=newlabel;E2.flase:=newlabel;E.code:=E1.code|E2.code|gen(E2.true:E.place:=E1.place+1)|gen(goto nextstat+1)|gen(E2.false:E.place:=E1.place)else if 41Case 语句翻译syntax directed translation(next slide)4243回填技术The eas

12、iest way to implement the syntax directed definition is to use two passes:1.construct a syntax tree for input 2.walk on the tree in depth-first order and compute the translation that are given in definitions The main problem is that we will have jumps to a label temporary left unspecified.The fillin

13、g of these places with labels determined later is named backpatching These labels are generated according to a specific algorithm,the rest of the algorithm to generate code remains the same as in 8.4-8.5 Quadruples can be generate into an array with indices of the array as labels 44Three functions(f

14、or code generation in one pas):makelist(i)merge(p1,p2)bapckpatch(p,i)The marker M(nonterminal)is inserted to produce semantic action (pick-up the index of the next quadruple to be generated)Synthesized attributes E.truelist and E.falselist are used to generate jumping code for Boolean expressions Th

15、e incomplete jumps are placed on the lists pointed by these two attributes:E.truelist and E.falselist M.quad records the number of first statement in E2.code The variable nextquad store the index of the next quadruple that follows 45backpatch(p,i)46Example(Fig.8.29):a b or c d and e f(implementation

16、 in one pass by using backpatching)47控制流语句的文法S,L,A,E 分别代表语句、语句序列、赋值语句、布尔表达式S if E then S|if E then S else S|while E do S|begin L end|AL L;S|S48语义规则ProductionSemantic RulesM M.quad:=nextquadN N.nextlist:=makelist(nextquad);emit(goto _)S if E then M S1backpatch(E.truelist,M.quad);S.nextlist:=merge(E.f

17、alselist,S1.nextlist)S if E then M1 S1 N else M2 S2backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,merge(N.nextlist,S2.nextlist)49ProductionSemantic RulesS while M1 E do M2 S1backpatch(S1.next,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselist;e

18、mit(goto,M1.quad)S begin L endS.nextlist:=L.nextlistS AS.nextlist:=NULLL L1;M Sbackpatch(L1.nextlist,M.quad);L.nextlist:=S.nextlistL SL.nextlist:=S.nextlist50过程调用A grammar for a simple procedure call statementExample(parameters are passed by reference,and storage is statically allocated)param is use

19、d as place for arguments The values for E are saved in a queue,first-in,first out 51The param statement is replaced at code generation by code to push a parameter on the stack,e.g.E.dim attribute can be append to semantic action if we want to count the number of parameters in the procedure call 52使用

20、队列The code to evaluate arguments is emitted first,followed by param statements and then a callIf desired,could augment rules to count the number of parametersProductionSemantic RulesS call id(Elist)for each item p on queue do emit(param p);emit(call id.place)Elist Elist,Epush E.place to queueElist Einitialize queue to contain E53