编译原理第8章

1、第八章第八章 符号表符号表 第八章第八章 符号表符号表 n符号表的作用和地位符号表的作用和地位n符号的主要属性及作用符号的主要属性及作用n符号表的组织符号表的组织第八章第八章 符号表符号表 一、符号表的作用和地位一、本章主要内容：一、本章主要内容： 静态语义检查和翻译中间代码；静态语义检查和翻译中间代码； 二、静态语义检查的内容：二、静态语义检查的内容： 类型检查、控制流检查、一致性检查、相关名字检查、类型检查、控制流检查、一致性检查、相关名字检查、 名字的作用域分析等；名字的作用域分析等； 三、翻译产生中间代码的优点：三、翻译产生中间代码的优点： 便于进行与机器无关的代码优化工作、使编译程序

2、改变目标便于进行与机器无关的代码优化工作、使编译程序改变目标 机更容易、使编译程序的结构在逻辑上更为简单明确；机更容易、使编译程序的结构在逻辑上更为简单明确； 四、静态语义检查和中间代码产生在编译程序中的地位：四、静态语义检查和中间代码产生在编译程序中的地位： 第八章第八章 符号表符号表 7.1 中间语言中间语言(中间代码的种类中间代码的种类)一、后缀式一、后缀式( (逆波兰逆波兰) ) 1 1、表达式、表达式E E的后缀式形式的后缀式形式E E的定义：的定义： 若若E E是变量或常量：是变量或常量：E E为为E E； 若若E E是是E E1 1 op Eop E2 2：E E为为E E1 1

3、E E2 2opop； 若若E E是（是（E1E1）：）：E E为为E E1 1； 2 2、中缀形式的表达式翻译为后缀式的语义规则：、中缀形式的表达式翻译为后缀式的语义规则： （E.CodeE.Code: :构成构成E E后缀式；后缀式；| | ：捻接后缀式；：捻接后缀式；op :op :二元算符）二元算符） EE1 op E2 E.Code := E1.Code|E2 .Code|opEE1 op E2 E.Code := E1.Code|E2 .Code|op E( E1 ) E.Code E( E1 ) E.Code := E1.Code := E1.Code E id E.Code E

4、 id E.Code :=id :=id 3 3、例：、例：a+ba+b ： abab+ , a+ , a* *b b ： abab* *, abc, abc+ +* * ：a a* *(b+c(b+c) , ) , ab+cd ab+cd+ +* * ：(a+b) (a+b) * * (c+d (c+d) ) 第八章第八章 符号表符号表 二、图表示法二、图表示法 1 1、抽象语法树。、抽象语法树。 2 2、有向无环图（、有向无环图（DAGDAG）：）： (1)(1)构造：表达式的每个子表达式对应构造：表达式的每个子表达式对应DAGDAG中一个结点，内部结中一个结点，内部结 点代表操作符，其孩

5、子代表操作数；点代表操作符，其孩子代表操作数； (2)(2)与抽象语法树区别：抽象语法树描述源程序的自然层次结与抽象语法树区别：抽象语法树描述源程序的自然层次结 构，构，DAGDAG也可以，但可标识出公共子表达式；也可以，但可标识出公共子表达式； 例例: :第八章第八章 符号表符号表 3 3、与后缀式的关系：表达式的抽象语法树形式的中间代码与后、与后缀式的关系：表达式的抽象语法树形式的中间代码与后 缀式等价，后缀式是抽象语法树的线性表现形式，是树的结点缀式等价，后缀式是抽象语法树的线性表现形式，是树的结点序列序列( (每个结点都在其所有子结点之后立即出现每个结点都在其所有子结点之后立即出现 )

6、 )。第八章第八章 符号表符号表 4 4、产生赋值语句抽象语法树的属性文法：、产生赋值语句抽象语法树的属性文法： S id:=E S id:=E S.nptr:= mknode(:=,mkleaf(id ,id.place),E.nptr S.nptr:= mknode(:=,mkleaf(id ,id.place),E.nptr) E E E E1 1+E+E2 2 E.nptr E.nptr:=mknode(+,E:=mknode(+,E1 1.nptr ,E.nptr ,E2 2.nptr) .nptr) E E E E1 1* *E E2 2 E.nptr:=mknodeE.nptr:

7、=mknode(* *,E,E1 1.nptr ,E.nptr ,E2 2.nptr) .nptr) E -E E -E1 1 E.nptrE.nptr:=mknode(:=mknode(,E,E1 1.nptr) .nptr) E (E E (E1 1) ) E.nptr E.nptr:=E:=E1 1.nptr.nptr E id E id E.nptr:=mkleaf(id ,id.place E.nptr:=mkleaf(id ,id.place) ) 第八章第八章 符号表符号表 5 5、抽象语法树表示、抽象语法树表示( (存储结构存储结构) )： 法法1:1:每个结点用一个记录，每记

8、录含运算符域和算量指针域；每个结点用一个记录，每记录含运算符域和算量指针域； 法法2:2:所有结点信息安排在一个记录数组中，结点的索引为指针。所有结点信息安排在一个记录数组中，结点的索引为指针。第八章第八章 符号表符号表 三、三地址代码三、三地址代码 1 1、含义：每条代码最多可以有三个操作数，是抽象语法树或、含义：每条代码最多可以有三个操作数，是抽象语法树或DAGDAG 的一种线性表示，为中间代码的一种抽象形式的一种线性表示，为中间代码的一种抽象形式 2 2、基本格式：、基本格式：x := y op zx := y op z 3 3、代码种类：、代码种类： (1)(1)计算、赋值：计算、赋值

9、：x:=y op z x:=y op z 、x:=op y x:=op y 、x:=y x:=y ； (2)(2)流程控制：流程控制：gotogoto L L、if x relop y gotoif x relop y goto L L、if a gotoif a goto L L ； (3)(3)过程调用：过程调用：paramparam x x 、call p ,ncall p ,n； (4)(4)数组元素引用：数组元素引用：x:=yix:=yi 、xixi:=y :=y ； (5)(5)地址、指针：地址、指针：x:=&y x:=&y 、x:=x:=* *y y 、* *x:

10、=y x:=y ；例例 为如下定义赋值语句和简单算术表达式的文法设计属性文为如下定义赋值语句和简单算术表达式的文法设计属性文 法，将赋值语句翻译成三地址代码法，将赋值语句翻译成三地址代码 SidSid:=E:=E EE+E|E EE+E|E* *E|-E|(E)|idE|-E|(E)|id第八章第八章 符号表符号表 例例( (续续):(1):(1)属性：属性：codecode对应语法单位对应语法单位( (非终结符非终结符) )的三地址代码的三地址代码; ; E.place E.placeEE的值的值( (存放位置存放位置: :临时变量或符号表入口临时变量或符号表入口);); id.place

11、id.placeidid的值的值( (存放位置存放位置:id:id的符号表入口的符号表入口); ); (2)(2)子程序：子程序：NewTempNewTemp分配一个新的临时变量分配一个新的临时变量 GenGen生成一个新的三地址代码生成一个新的三地址代码(3)(3)产生三地址代码的属性文法产生三地址代码的属性文法 Eid EidE.place:=id.place;E.codeE.place:=id.place;E.code:=; :=; E(E E(E1 1) )E.placeE.place:=E:=E1 1.place;E.code:=E.place;E.code:=E1 1.code;.

12、code; E- E E- E1 1E.place:=NewTempE.place:=NewTemp; ;E.codeE.code:=E:=E1 1.code|gen(E.place ,:=,.code|gen(E.place ,:=, ,E,E1 1.place); .place); EEEE1 1* *+E+E2 2E.place:=NewTempE.place:=NewTemp; ;E.codeE.code:=E:=E1 1.code|E.code|E2 2.code|.code|gen(E.palcegen(E.palce ,:= ,E ,:= ,E1 1.palce ,.palce

13、,* *+,E+,E2 2.palce);.palce); Sid:=ESid:=ES.code:=E.code|gen(id.place ,:=,E.placeS.code:=E.code|gen(id.place ,:=,E.place); ); 第八章第八章 符号表符号表 4、三地址代码的三地址代码的具体实现形式具体实现形式 第八章第八章 符号表符号表 7.2 说明语句的翻译说明语句的翻译一、过程中一、过程中( (函数内函数内) )的说明语句的说明语句的翻译的翻译 1 1、任务、任务: :在符号表中建立相应表项并填入类型、相对地址等在符号表中建立相应表项并填入类型、相对地址等; ; 2

14、2、相对地址：相对内存数据区基地址的偏移量；、相对地址：相对内存数据区基地址的偏移量； 3 3、翻译模式中的属性、翻译模式中的属性 type:type:类型类型 ; width:; width:存储单元长度存储单元长度 ; val; val: :常量的值常量的值 ; ; name: name:标识符名字标识符名字 ; pointer:; pointer:指针类型构造符指针类型构造符 ; ; array: array:数组类型构造符数组类型构造符 4 4、变量与子程序：、变量与子程序： offset:offset:全局变量全局变量, ,跟踪下一个相对地址值跟踪下一个相对地址值 ; ; Enter

15、: Enter:填表子程序填表子程序 5 5、基础文法：、基础文法：PDPD Did:T|D;D Did:T|D;D Tinteger|real|T|arraynum Tinteger|real|T|arraynum of T of T 第八章第八章 符号表符号表 6 6、翻译模式、翻译模式第八章第八章 符号表符号表 7 7、翻译过程、翻译过程( (语法制导翻译语法制导翻译) )第八章第八章 符号表符号表 二、保留作用域信息二、保留作用域信息( (不同过程中的说明语句的翻译不同过程中的说明语句的翻译) ) 1 1、方法：为每个过程建立一个独立的符号表，各表通过指针、方法：为每个过程建立一个独立

16、的符号表，各表通过指针 链接。链接。 2 2、基础文法：、基础文法： P M DP M D M M D id:T|D;D|proc id;ND id:T|D;D|proc id;N D;S D;S N N Tinteger|real|T|arraynumTinteger|real|T|arraynum of T of T ( (注注:_:_产生式产生式M M 与与N N 的作用是使语义子程序都添的作用是使语义子程序都添 加在产生式最后而不影响属性计算顺序加在产生式最后而不影响属性计算顺序) )第八章第八章 符号表符号表 例：例：pascalpascal快速排序程序中的说明语句与翻译结果快速排序

17、程序中的说明语句与翻译结果( (符号表符号表) )第八章第八章 符号表符号表 3 3、变量与子程序、变量与子程序 栈栈tblptrtblptr：保存各外层过程的符号表指针；：保存各外层过程的符号表指针； 栈栈offsetoffset：栈顶元素为当前过程的下一个局部名相对地址；：栈顶元素为当前过程的下一个局部名相对地址； mktablemktable：建新表；：建新表；enterenter：填表：填表( (名字名字) )； addwidthaddwidth：填宽度；：填宽度；enterprocenterproc：填表：填表( (过程名过程名) )； 4 4、翻译模式、翻译模式 (1) PMD(1

18、) PMD addwidth(top(tblptr),top(offset addwidth(top(tblptr),top(offset);); pop(tblptr pop(tblptr);); pop(offset pop(offset) (2) M (2) M t:=mktable(nil);push(t,tblptr);push(0,offset) t:=mktable(nil);push(t,tblptr);push(0,offset) (3) DD (3) DD1 1;D;D2 2第八章第八章 符号表符号表 (4) D proc id;N(4) D proc id;N D D1

19、1;S;S t:=top(tblptr t:=top(tblptr);); addwidth(t,top(offset addwidth(t,top(offset);); pop(tblptr pop(tblptr); ); pop(offset pop(offset) ;) ; enterproc(top(tblptr),,t enterproc(top(tblptr),,t) ) (5) D id: T(5) D id: T enter(top(tblptr),,T.type,top(offset enter(top(tblptr),

20、,T.type,top(offset);); top(offset):=top(offset)+T.width top(offset):=top(offset)+T.width (6) N (6) N t:=mktable(top(tblptr t:=mktable(top(tblptr);); push(t,tblptr push(t,tblptr);); push(0,offset) push(0,offset) 第八章第八章 符号表符号表 三、记录中的域名三、记录中的域名 1 1、方法：为记录类型建立符号表；、方法：为记录类型建立符号表； 2 2、基础文法：、基础文法：T record

21、D end T record D end 3 3、翻译模式：（记录类型构造符）、翻译模式：（记录类型构造符） (1) T record L D end(1) T record L D end T.type:=record(top(tblptr T.type:=record(top(tblptr); ); T.width:=top(offset T.width:=top(offset);); pop(tblptr pop(tblptr);); pop(offset pop(offset) ) (2) L (2) L t:=mktable(nil t:=mktable(nil);); push(t

22、,tblptr push(t,tblptr);); push(0,offset) push(0,offset)第八章第八章 符号表符号表 7.3 赋值语句的翻译赋值语句的翻译 一、简单算术表达式及赋值语句一、简单算术表达式及赋值语句 1 1、基础文法、基础文法 S id := ES id := E E id | E + E | E E id | E + E | E * * E | - E | ( E ) E | - E | ( E ) 2 2、属性、属性 place:place:值值( (存放位置存放位置);); name: name:标识符名标识符名( (变量名变量名) ) 3 3、子程序、

23、子程序 lookup:lookup:查符号表，返回标识符得表入口，若返回查符号表，返回标识符得表入口，若返回nil(nil(空空 值值) )，表示不在符号表中；，表示不在符号表中； emit:emit:产生三地址代码并输出产生三地址代码并输出( (到文件到文件) )； error:error:错误处理程序错误处理程序第八章第八章 符号表符号表 4 4、翻译模式、翻译模式第八章第八章 符号表符号表 二、包含数组元素的引用的赋值语句的翻译二、包含数组元素的引用的赋值语句的翻译 1 1、数组元素相对地址的计算、数组元素相对地址的计算( (按行存放方式按行存放方式) )(1)A:(1)A:数组名；数组

24、名；base:base:首地址；首地址；w:w:单元长度；单元长度；i:i:下标；下标；l:l:下标下届；下标下届； h:h:下标上届；下标上届；n:n:下标的长度；下标的长度；&:&:元素的相对地址元素的相对地址( (相对首地址相对首地址) )(2)(2)一维数组一维数组:&Ai=base+(il)w = iw+(baselw:&Ai=base+(il)w = iw+(baselw) ) (3)(3)二维数组二维数组: : &Ai &Ai1 1,i,i2 2 =base+ =base+ (i (i1 1-l-l1 1)n)n2 2+i+i2 2

25、-l-l2 2)w)w =(i =(i1 1n n2 2+i+i2 2)w)w +(base-(l +(base-(l1 1n n2 2+l+l2 2)w) )w) 第八章第八章 符号表符号表 (4)k(4)k维数组维数组: : &Ai &Ai1 1 ,i,i2 2 , ,i, ,ik k=(i(i1 1n n2 2+i+i2 2)n)n3 3+i+i3 3)n)nk k+i+ik k)w)w +base-(l+base-(l1 1n n2 2+l+l2 2)n)n3 3+l+l3 3)n)nk k+l+lk k)w)w 令令(i(i1 1n n2 2+i+i2 2)n)n3

26、3+i+i3 3)n)nk k+i+ik k)w)w = V = V (l (l1 1n n2 2+l+l2 2)n)n3 3+l+l3 3)n)nk k+l+lk k)w)w = C = C 则则 &Ai&Ai1 1,i,i2 2,i,ik k = V + base C = V + base C ( (其中，其中，basebase、C C与与i i1 1 ,i,i2 2 ,i,ik k无关，可在翻译说明语句时计无关，可在翻译说明语句时计 算出并填入符号表算出并填入符号表) )2 2、基础文法、基础文法第八章第八章 符号表符号表 (3)(3)包含数组元素的赋值语句文法：包含数组

27、元素的赋值语句文法： SL:=ESL:=EEE+E|(E)|LEE+E|(E)|L LElist|id LElist|idElistElist,E|idEElistElist,E|idE 3 3、数组元素引用的三地址代码、数组元素引用的三地址代码 &Ai&Ai1 1 ,i,i2 2 , ,i, ,ik k=(i=(i1 1n n2 2+i+i2 2)n)n3 3+i+i3 3)n)nk k+i+ik k)w)w +base-(l +base-(l1 1n n2 2+l+l2 2)n)n3 3+l+l3 3)n)nk k+l+lk k)w)w = V + base C = V +

28、 base C 令令B=base CB=base C (1)Ai (1)Ai1 1 ,i,i2 2 , ,i, ,ik k=E=E译成译成:BV=E ,( = ,B ,V ,E):BV=E ,( = ,B ,V ,E) (2)x=Ai (2)x=Ai1 1 ,i,i2 2 , ,i, ,ik k 译成译成:x=BV ,(= ,B ,V ,x):x=BV ,(= ,B ,V ,x) 第八章第八章 符号表符号表 4 4、属性、属性 数组每维下标的下界、长度，数组元素存储单元长度，相对地数组每维下标的下界、长度，数组元素存储单元长度，相对地 址计算公式中的址计算公式中的basebase、C C等可查

29、符号表得到；等可查符号表得到； array:array:数组名的符号表入口；数组名的符号表入口； ndimndim: :记录下标个数记录下标个数( (维数维数) )； 5 5、子程序、子程序(1)limit(1)limit：查符号表，返回每维长度；：查符号表，返回每维长度； (2)emit:(2)emit:生成并输出中间代码生成并输出中间代码( (三地址代码三地址代码););(3)NewTemp:(3)NewTemp:分配临时存储单元；分配临时存储单元；第八章第八章 符号表符号表 6 6、翻译模式、翻译模式第八章第八章 符号表符号表 第八章第八章 符号表符号表 第八章第八章 符号表符号表 第八

30、章第八章 符号表符号表 第八章第八章 符号表符号表 三、表达式中的类型问题：三、表达式中的类型问题： 1 1、属性：、属性：typetype属性表示类型信息，属性表示类型信息， inttorealinttoreal表示类型转换，表示类型转换， 2 2、产生式、产生式EEEE1 1+E+E2 2的语义规则如下的语义规则如下 E.place := newtempE.place := newtemp; ; if E if E1 1.type=integer and E.type=integer and E2 2.type=integer then .type=integer then emit(E.

31、place emit(E.place:=E:=E1 1.place ,int+,E2,place); .place ,int+,E2,place); E.type E.type:=integer:=integer else if E else if E1 1.type=real and E.type=real and E2 2.type=real then.type=real then emit(E.place emit(E.place:=E:=E1 1.place ,real+,E.place ,real+,E2 2.place); .place); E.type E.type:= real

32、:= real else if E else if E1 1.type=integer and E.type=integer and E2 2.type=real then.type=real then u:=newtemp; emit(u u:=newtemp; emit(u:= ,inttoreal,E:= ,inttoreal,E1 1.place);.place); emit( E.place emit( E.place:=u ,real+,E:=u ,real+,E2 2.place);.place); E.type E.type:=real:=real else if E else

33、 if E1 1.type=real and E.type=real and E2 2.type=integer then.type=integer then u:=newtemp u:=newtemp; emit( u:=,inttoreal,E; emit( u:=,inttoreal,E2 2.place);.place); emit(E.place emit(E.place:=E:=E1 1.place,real+,u );.place,real+,u ); E.type E.type:=real:=real else E.type:=type_error else E.type:=t

34、ype_error 第八章第八章 符号表符号表 7.4 布尔表达式的翻译布尔表达式的翻译一、布尔表达式的文法一、布尔表达式的文法 1 1、基础文法：、基础文法： EE or E|E and E|not E|( E )|id relop id|idEE or E|E and E|not E|( E )|id relop id|id 2 2、关系运算符、关系运算符reloprelop的的opop属性值为：、属性值为：、 3 3、语义处理方法、语义处理方法 (1)(1)求值求值: : 法一：同算术表达式；法一：同算术表达式； 法二：优化办法，即法二：优化办法，即 A or BA or B解释为解释为

35、 If A Then TRUE Else B If A Then TRUE Else B A and B A and B解释为解释为 If A Then B Else FALSE If A Then B Else FALSE not A not A解释为解释为 If A Then FALSE Else TRUE If A Then FALSE Else TRUE (2) (2)做条件控制做条件控制: :控制选择语句和循环语句的执行。控制选择语句和循环语句的执行。第八章第八章 符号表符号表 二、对布尔表达式求值的语义处理二、对布尔表达式求值的语义处理 1 1、数值表示法：用、数值表示法：用1 1

36、表示表示TRUETRUE，0 0表示表示FALSEFALSE； 2 2、语义处理方法：、语义处理方法： (1)(1)布尔表达式直接翻译为能表示布尔运算的中间代码；类似布尔表达式直接翻译为能表示布尔运算的中间代码；类似 算术表达式的处理方法。算术表达式的处理方法。 (2)(2)关系表达式根据关系是否成立确定值为关系表达式根据关系是否成立确定值为1 1或或0 0。 例：例：第八章第八章 符号表符号表 3 3、翻译模式、翻译模式( (属性文法属性文法) )第八章第八章 符号表符号表 例：对布尔表达式例：对布尔表达式a b or c d and e fa b or c d and e c or bc

37、or bd then S1 1 else S else S2 2 三地址代码序列为三地址代码序列为 第八章第八章 符号表符号表 2 2、基础文法、基础文法( (变形以后变形以后) )EE or ME|E and ME|not E|(E)|id relopEE or ME|E and ME|not E|(E)|id relop id| id id| idM M 3 3、完成转移操作的四元式、完成转移操作的四元式(1) (jnz(1) (jnz , a , _ , p) , a , _ , p) 表示表示 if a gotoif a goto p p (2) (jrop(2) (jrop , x

38、, y , p) , x , y , p) 表示表示 if x rop y gotoif x rop y goto p p (3) (j , _ , _ , p) (3) (j , _ , _ , p) 表示表示 gotogoto p p 4 4、回填操作、回填操作 (1)(1) 转移操作转移操作(goto(goto L) L)要转移到要转移到 的位置的位置(L)(L)尚未确定，当位尚未确定，当位 置置(L)(L)确定后再填上；确定后再填上； (2)(2) 需回填同一位置的转移需回填同一位置的转移 操作多于一个，用链表链接。操作多于一个，用链表链接。第八章第八章 符号表符号表 5 5、相关属性

39、、全局变量、子程序、相关属性、全局变量、子程序第八章第八章 符号表符号表 6 6、翻译模式、翻译模式第八章第八章 符号表符号表 第八章第八章 符号表符号表 第八章第八章 符号表符号表 例例( (续续) )：ab or cd and efab or cd and ef的带注释的语法树及翻译结果的带注释的语法树及翻译结果第八章第八章 符号表符号表 7.5 控制语句的翻译控制语句的翻译 一、控制流语句一、控制流语句 1 1、语句种类及对应中间代码的结构：、语句种类及对应中间代码的结构：第八章第八章 符号表符号表 2 2、基础文法及其变换、基础文法及其变换第八章第八章 符号表符号表 3 3、翻译模式、翻译模式属性属性S.nextS.next( (或或L.next):SL.next):S( (或或L)L)的四元式组中需回填同一个出的四元式组中需回填同一个出口的四元式链接成的链表表头。口的四元式链接成的链表表头。第八章第八章 符号表符号表 第八章第八章 符号表符号表 第八章第八章 符号表符号表 二、标号与二、标号与gotogoto语句语句 1 1、基础文法、基础文法: S goto label|label: S goto label|label S label i: S