编译原理课件chapter5.pptVIP

1,2,翻译的任务：首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。 使用的方法称作语法制导翻译。基本思想是，1.根据翻译的需要设置文法符号的属性，以描述语法结构的语义。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。2.属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。,3,属性值根据计算的依赖关系分成不相交的两类：综合属性(synthesized attribute)和继承属性(inherited attribute)。在分析树中，一个结点的综合属性值是从其子结点的属性值计算出来的；而一个结点的继承属性值是由该结点兄第结点和父结点的属性值计算出来的。 一般来说，语义翻译可按图5.1 的流程处理。实际上，编译中语义翻译的实现并不是按图5.1 的流程处理的；而是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。,4,要求：随着语法分析，分析树逐步被构造出来，每构造一个子树，和这棵子树结点相联系的文法符号的属性值都可以根据已有结点属性值的计算出来的。一个重要的属性定义类称作“L属性”定义，满足上述要求。,5,输 入 符 号 串,分 析 树,依 赖 图,语 义 属 性 的 计 算,图5.1 语法制导翻译概观,6,5.1 语法制导定义(Syntax-directed definitions) 语法制导定义是对上下文无关文法的推广 综合属性 继承属性 依赖图 语义规则建立了属性之间的依赖关系，这些关系可以用图来表示，这样的图称为依赖图。,属性,7,5.1.1 语法制导定义的形式 在一个语法制导定义中，AP都有与 之相关联的一套语义规则，规则形式为 b：= f（c1，c2，ck）， f是一个函数，而且或者 1b是A的一个综合属性并且c1，c2，ck是 中的符号的属性，或者 2b是中的符号的一个继承属性并且c1， c2，ck是A或中的任何文法符号的属性。 在两种情况下，都说属性b依赖于属性c1，c2，ck。,8,例5.1 台式计算器程序的语法制导定义（表5.1),产生式 语义规则 LEn print(Eval) E E1+T E val := E1 val+T val E T E val := T val T T1*F T val := T1 val+F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,9,每个文法符号和一个属性值val 联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。例如，把例5.1中的类型扩充到 int和real。 5.1.2 综合属性 S-属性定义 唯独只使用综合属性的语法制导定义。 结点属性值的计算正好和自底向上分析建立分析树结点同步进行。 例 5 .2 输入：3*5+4n,10,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,n,11,综合属性值的计算方法 对于s-属性定义，通常使用自底向上的分析方法，在建立每一个结点处使用语义规则来计算综合属性值，即在 用哪个产生式进行归约后，就执行那个产生式的s-属性定义计算属性的值，从叶结点到根结点进行计算。 5.1.3 继承属性 继承属性值是由此结点的父结点和或兄弟结点的某些属性值来决定的。 例5 . 3 变量说明的类性定义 int a,b,c,12,表5.2 带有继承属性L.in的语法制导定义,产生式 语义规则 DTL Lin:=T type T int T type :=integer T real T type :=real L L1,id L1 in :=L in addtype(id entry,L in) L id addtype(id entry,L in),13,T,L,L,id3,L,id2,D,id1,real,1 entry,2 entry,3 entry,4 type,in 5,6,in 7,8,in 9,10,14,5.1.4 依赖图 依赖图的构造方法 for 分析树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 分析树中每一个结点n do for 结点n所用产生式对应的每一条 语义规则 b:f（c1，c2，ck ) do for i:=1 to k do 从结点ci到结点b构造一条有向边；,15,5.1.5 计算顺序 拓扑排序 一个有向非循环图的拓扑排序是图中结点的任何顺序m1，m2，mk，使得 边必须是从序列中前面的结点指向后面的结点，也就是说，如果mimj是mi到mj的一条边,那么在序列中mi必须出现在mj的前面。 若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。,16,例5 . 6 图5 . 5的拓扑排序是： 1， 2， 3，4，5，6，7，8，9，10 a4:=real; a5:=a4; addtype(id3entry,a5); a7:=a5; addtype(id2entry,a7); a9:=a7; addtype(id1entry,a9);,17,计算语义规则的方法 1 .分析树法: 输入串 分析树 依赖图 计算次序 2.基于规则的方法： 在构造编译器时，用手 工或专门的工具来分析语义规则,确定属性 值的计算顺序。 3.忽略语义规则的方法：在分析过程中翻译， 那么计算顺序由分析方法来确定而表面上与 语义规则无关。实际上，限制语法制导定义， 使属性值的计算顺序能和语法分析过程同步 进行。,18,5.2 语法树（syntax tree）的构造 抽象语法（abstract syntax） 从具体语法中抽象出语言结构的本质性的东西，而不考虑语言的具体符号表示，从而可简化语义的形式描述。 在不同的语言中赋值语句有不同的写法： x=y; x:=y; yx 等等，可以用抽象形式 assignment(variable,expression) 把前面各种具体形式统一起来。,19,语法树 表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形 式 ,也称作语法结构树，或结构树。 语法树是常用的一种中间表示形式。 C SAGE+ 语法分析过程中完成翻译有许多优点，但也有一些不足： 1.适于语法分析的文法可能不完全反映语言成分的自然层次结构； 2. 受语法分析方法限制，对分析树结点的访问序和翻译需要的访问序不一致。,20,5.2.1 语法树 产生式Sif B then S1 else S2的语法树 if-then-else | B S1 S2 赋值语句的语法树 assignment variable expression 在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。,21,5.2.2 建立表达式的语法树 建立表达式的语法树使用的函数: 1. mknode(op,left,right) 建立一个运算符号结 点，标号是op,两个域left和right指向运算分 量结点的指针。 2mkleaf(id,entry) 建立一个标识符结点,由 标号id标识，一个域entry指向标识符符号 表中相应的项。 3. mkleaf(num,val) 建立一个数结点，标号为 num ，域val用于存放数的值。 返回新建立结点的指针。,22,id,to entry a,num 4,id,to entry c,+,图5.6 a-4+c的语法树,23,5.2.3 建立语法树的语法制导定义,产生式 语义规则 EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val),24,id,to entry a,num 4,id,to entry c,+,图5.6 a-4+c的语法树,25,1 .每个非终结符号有一个语法树结点的指针 属性。 2 .非终结符号归约未建立结点。 5.2.4 关于表达式的有向非循环图 有向非循环图 （Directed Acyclic Graph，简称dag) 用途：提取表达式中的公共子表达式，以取得 目标程序的局部优化。 方法：执行mknode和mkleaf时，检查是否已有 相同的结点，若有，则返回相应结点的 指针。,26,例5.9 表达式 aa*(b-c)+(b-c)*d 的dag,+,*,d,+,*,a,c,b,27,5.3 S-属性定义及其自底向上的计算 在分析栈中使用一个附加的域来存放综 合属性值。 下图为一个带有综合属性值域的分析栈：,state,val,.,X,X.x,Y,.,Y.y,.,.,Z,Z.z,top,28,A b:=f(c1,c2,ck) b是A的综合属性，ci(1 ik)是中符号的属性。综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。 AXYZ Aa:=f(X x, Y y,Z z),A a,X x Y y Z z,29,top,state,val,.,.,X,X.x,Y,Y.y,Z,Z.z,state,val,.,.,A,A .a,top,定义式 A .a:=f(X.x, Y.y, Z.z)（抽象）变成 valntop:=f(valtop-2,valtop-1,valtop) （具体可执行代码）。 在执行代码段之前执行： ntop:=top-r+1 执行代码段后执行： top:=ntop; r是句柄的长度.,30,产生式 代码段(和表5.1对比） LEn printf(valntop) E E+T valntop:=valtop-2+valtop E T T T*F valntop:=valtop-2*valtop T F F (E) valntop:=valtop-1 F digit,例5.10 用LR分析器实现台式计算器(表5.4）,31,表5.5 翻译输入3*5+4n所做的移动,输入 state val 使用的产生式,3*5+4n - -,*5+4n 3 3,*5+4n F 3 Fdigit,*5+4n T 3 TF,5+4n T* 3-,+4n T* 5 3-5,+4n T* F 3-5 F digit,32,+4n T 15 T T*F,+4n E 15 E T,4n E+ 15-,n E+4 15-4,n E+F 15-4 F digit,n E+T 15-4 T F,n E 19 E E+T,En 19 -,L 19 L En,33,总结： 采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成相应的翻译任务。,34,5.4 L-属性定义 在语法分析过程中进行语义分析和翻译，属 性的计算顺序受到语法分析建立分析树结点顺序的限制。 一种自然的计算属性的顺序是按深度优先 访问分析树结点的顺序，它适应多种自底向上 和自顶向下的翻译方法。 L-属性定义 可用于按深度优先顺序计算属性值。,35,深度优先顺序计算属性 PROCEDURE dfvisit(n:node); BEGIN FOR n 的每个子结点m,从左至右 DO BEGIN 计算m的继承属性； dfvisit(m) END; 计算n的综合属性 END;,36,5.4.1 L-属性定义 定义 一个语法制导定义是L-属性定义，如果AX1X2XnP,其每一个语义规则中的每一个属性或是一个综合属性，或是Xj (1j n)的一个继承属性， 这个继承属性仅依赖于 1. 产生式中Xj的左边符号X1，X2，Xj-1的属性； 2A的继承属性。 每一个S-属性定义都是L-属性定义。,37,表5.6 非L-属性的语法制导定义,产生式,语义规则,ALM A QR,L.i:=l(A.i) M.i:=m(L.s) A.s:=f(M.s) R.i:=r(A.i) Q.i:=q(R.s) A.s:=f(Q.s),表5.6的语法制导定义不是L-属性定义。文法符号Q的继承属性依赖于它右边文法符号R的属性。,38,5.4.2 翻译模式 定义 翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号 括起来，可被插入到产生式右部的任何合适的位置上。 这是一种语法分析和语义动作交错的表示法，他表达在按深度优先遍历分析树的过程中何时执行语义动作。 翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,39,例5.12 一个简单的翻译模式 ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把语义动作看成终结符号，输入9-5+2,其分析树如图5. 10，当按深度优先遍历它，执行遍历中访问的语义动作，将输出 9 5 - 2 + 它是输入表达式9-5+2的后缀式。,40,E,T,9,T,Pt(9),R,Pt(-),Pt(+),R,-,5,Pt(5),+,T,2,Pt(2),R,图5.10 9-5+2的带语义动作的分析树,41,设计翻译模式（根据语法制导定义） 条件：语法制导定义是L-属性定义 保证语义动作不会引用还没有计算的属性值。 1. 只需要综合属性的情况： 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。 例如：TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val,42,2. 既有综合属性又有继承属性 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 一个动作不能引用这个动作右边符号的综合属性。 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。,43,下面的翻译模式不满足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) 例5.13 从L-属性制导定义建立一个满足上面要求 的翻译模式。 使用文法产生的语言是数学排版语言EQN，里如， E sub 1val 编排结果,E,1,val,44,B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) B1.ps:=B.ps B2.ps:=shrink(B.ps) B.ht:=disp(B1.ht,B2.ht) B.ht:=text.h*B.ps,SB B B1 B2 B B1 sub B2 B text,产生式,语义规则,表5.7 盒子的大小和高度的语法制导定义,45,B是编排单元； BBB表示俩个编排单元的并置； BBsubB表示第二个编排单元是第一个编 排 单元的下标； ps是继承属性，影响编排单元的位置； texth可根据text的性质查表得到； shrink把B2的尺寸缩小30%； disp把B2向下偏置。,46,SB.ps:=10 BS.ht:=B.ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2B.ht:=disp(B1.ht,B2.ht) BtextB.ht:=text.h*Bps 图5.12 从表5.7构造的翻译模式,47,5.5 自顶向下的翻译 用翻译模式构造自顶向下翻译。 5.5.1 从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。 例5.14 图5.13的带左递归的文法的翻译模式被转 换成图5.14的带右递归的文法的翻译模式。,48,EE1+T E val:=E1val+T val E E1-T E val:=E1 val-T val E T E.val:=T val T (E) T val:=E val T num T val:=num val 图5.13 带左递归的文法的翻译模式,49,ET Ri:=T val RE val:=R s R TR1i:=R.i+T. val R1R s:=R1 s R- TR1 i:=R i-Tval R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val 图5.14 经过转换的带有右递归文法的翻译模式,50,E val=6,Tval=9,R i=9; R s= 6,9,T val=5,5,R i=4; R s= 6,+,T val=2,R i=6; R s= 6,2,图5.15 表达式9-5+2的计算,51,关于左递归翻译模式的一般化讨论 左递归翻译模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （5.2） 每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。 消除左递归，文法转换成 AX R RY R| （5.3）,52,再考虑语义动作，翻译模式变为： AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i,Y y） R1 R s:=R1 s RR s:=R i （5.4） 经过转换的翻译模式与图5.14中一样,使用R的继承属性i和综合属性s。 （5.2）和（5.4）的结果是一样的, 为什么？,53,A a=g(g(f(X x),Y1 y),Y2 y),A a=g(f(X x),Y1 y),A a=f(X x),Y2,Y1,X,(a),输入：XY1Y2,54,A,Ri=f(X x),R i=g(f(X x),Y1 y),R i=g(g(f(X x),Y1 y),Y2 y),Y2,Y1,X,(b),55,例5. 15 表达式建立语法树的翻译模式： EE1+T Enptr :=mknode(+,E1 nptr,T nptr) EE1-T Enptr :=mknode(-,E1 nptr,T nptr) ET Enptr :=T nptr 从翻译模式中消除左递归，变成图5.17的翻译模式。,56,ET Ri:=T nptr R E nptr:=R s R T R1 i:=mknode(+,R i,T nptr) R1 R s:=R1 s R- T R1 i:=mknode(-,R i,T nptr) R1 R s:=R1 s R R s:=R i T( E ) T nptr:=E nptr Tid T nptr:=mkleaf(id, id entry) Tnum T nptr:=mkleaf(num,num val),57,使用继承属性构造语法树,E,i,R,s,T,id,R,-,T,num,i,R,T,+,id,id,num 4,id,-,+,to entry for a,to entry for c,nptr,nptr,nptr,58,5.5.2 预测翻译器的设计 算法5.1 预测语法制导翻译器的建立 输入：一个带有适合预测分析的基础文法的 语法制导翻译模式。 输出：一个语法制导翻译器的代码。 方法：在预测分析器中加入语义动作代码。 1AVN,建立一个可递归调用的函数过程 A。为A的每一个继承属性都设置 一个形 式参数，函数的返回值是A的综合属性值。 2. 函数过程A的代码（指用符号形式表示的 数据和程序）要根据当前的输入符号来决 定使用哪一个产生式。,59,3. 与每一个产生式有关的代码，从左到右根椐产 生 式右部是单词符号、非终结符号还是语义动作， 分别是： （a）对于带有综合属性x的单词符号X，x存放在 X.x中，Match(X)。 （b）对于BVN，编写一个赋值语句 c:= B（b1, b2, ，bk) 其中， b1, b2, ，bk是继承属性，c是综合属 性。 （c）对于每个动作，把动作的代码抄进翻译器中， 用代表属性的变量来代替对属性的每一次引用。,60,例5.16 ： Raddop TR1i:=mknode（addop lexeme， R i， T nptr） R1R.s:=R1.s R R.s:=R.i （55） 递归下降构造语法树 function R（in: syntax-tree-node）： syntaX-tree-node； var nptr,i1,s1,s： syntax-tree-node; addoplexeme:char；,61, IF lookahead=addop THEN /*产生式Raddop T R*/ addoplexeme:=lexval; match(addop); nptr:=T; i1:=mknode(addoplexeme,in,nptr); s1:=R(i1); s:=s1 ; ELSE s:=in; /*产生式R*/ return (s); ,62,5.8 类型分析 每个程序设计语言都有自己的类型机制，包括类型说明和使用。 类型分析是编译器语义分析的重要组成部分 。编译器首先根据类型说明，确定每一个变量和常量的类型 ，计算其使用存储空间的大小，从而建立其到存储空间的映射。进而，编译器要确定每个语言结构的类型，以完成下面的主要任务： （1） 判定重载算符（函数）在程序中代表是 那一个运算； （2） 进行类型转换； （3） 对语言结构进行类型检查。,63,5.8.1 类型表达式 5.8.1.1 类型表达式定义 语言结构的类型由类型表达式指称，类型表达式依赖于程序语言的类型体制。类型表达式或者是简单类型表达式，或者是构造符作用在类型表达式上得到的类型表达式。类型表达式的定义如下： （1）类型名和基本类型是类型表达式。 integer、char、real、boolean是基本类型， 所以它们是类型表达式。另外，void表示 “无类型”，type_error表示“出错类型”，它 们也是类型表达式。,64,（2）类型构造符作用于类型表达式的结果仍然是 类型表达式。类型构造符包括： （a）数组构造符ARRAY：若T是类型表达式， 则ARRAY（I,T）是类型表达式； （b）笛卡儿乘积：若T1、T2是类型表达式，则 T1 T2是类型表达式，且是左结合。 （c）记录类型构造符RECORD：若有标识符N1、 N2、Nn与类型表达式T1、T2、Tn， 则RECORD（N1 T1） （N2 T2） （Nn Tn）是一个类型表达式，它 指称一个记录类型。,65,（d）指针类型构造符POINTER：若T是类型 表达式，则POINTER（T）是类型表达式， 它指称一个指针类型。 （e）函数类型构造符：若D1、D2、Dn和 R是类型表达式，则D1D2 DnR 是类型表达式，其中优先于，它指称从 定义域类型D1 D2 Dn到值域类型R 的映射。 （3) 类型表达式中可出现类型变量，变量值是类 型表达式。,66,例5.23 设有Pascal 程序片段： TYPE stype=RECORD name:ARRAY 18 OF char; score:integer END; VAR table:ARRAY 150 OF stype; p: stype; 则stype绑定的类型表达式 RECORD(nameARRAY(18,char) (score integer) 和table绑定的类型表达式 ARRAY(150,stype) 和P绑定的类型表达式 POINTER(stype),67,例5.24 设有下面的函数定义 FUNCTION f(P1:T1;P2:T2;Pn:Tn):T; BEGIN END; 和f绑定的类型表达式 T1T2 TnT 例5.25 在函数式语言中可如下定义恒等函数 fun f(x)=x x可以是任何类型的语言结构。因此x可以是任何类型。f的类型表达式为 为类型变量，其值是任何类型表达式。,68,类型表达式的表达方法 1.树:内部结点是类型构造符，叶结点是基本类 型，类型名或类型变量。例如， FUNCTION f (a,b:char):integer: charcharpointer(integer),pointer,integer,char,char,69,2. 位串(对类型表达式作某些限制) 例如，考虑由POINTER、和ARRAY 作为构 造符的类型表达式。Pointer(t)表示指向类型为 t的指针，freturns(t)表示若干变元的函 数, 其 中t为函数返回对象的类型, 而函数变元的类型 则存放在其它地方。ARRAY(t) 表示元素类型 为t 的数组，而数组元素的个数保存在其它地 方。这样，构造符都成为一元算符，它们作用 于基本类型形成的类型表达式有非常统一的结 构。,70,类型构造符 编码 pointer 01 array 10 freturns 11 基本 类型 编码 boolean 0000 char 0001 integer 0010 real 0011 类型 表达式 编码 char 000000 0001 freturns(char) 000011 0001 pointer(freturns(char) 000111 0001 array(pointer(freturns(char) 100111 0001,71,5.8.1.2 类型表达式的等价 根据语言的类型体制和类型表达式的表示方法，分结构等价和名字等价。 结构等价 两个类型表达式结构等价，当且仅当它们完全相同。图5.30是测试两个类型表达式结构等价的算法，假设类型构造符仅有 数组、笛卡儿积、指针和函数，这个算法递归地比较两个类型表达式的结构。 FUNCTION eq(s,t):boolean; BEGIN IF s 和 t 是相同的基本类型 THEN return(true),72,ELSE IF (s=ARRAY(s1,s2) and (t=ARRAY(t1,t2) THEN return(eq(s1,t1) and eq(s2,t2) ELSE IF (s=s1s2) and (t=t1 t2) THEN return(eq(s1,t1) and (eq(s2,t2) ELSE IF (s=POINTER(s1) and(t=POINTER(t1) THEN return(eq(s1,t1) ELSE IF (s=s1s2) and (t=t1t2) THEN return(eq(s1,t1) and eq(s2,t2) ELSE return(false) END ；,73,类型表达式中的名字 类型可以命名。例如， TYPE Link=cell; VAR next: Link; (5.9） Last: Link; P: cell; q,r: cell; 所谓名字等价，是指两个等价类型有同一个名字，也就是说，两个类型名表示不同的类型。在结构等价中，在类型表达式中的所有名字被它们代表的类型表达式替换后，两个类型表达式等价即是结构等价。,74,例5.26 下面给出和声明（5.9）中的5个变量相 联系的类型表达式。 变 量 类 型表 达 式 next Link last Link p Pointer(cell) q Pointer(cell) r Pointer(cell) 在名字等价下，变量next和last有同样的类型; next和p的类型不相同。在结构等价下，所有五个变量都有同样的类型。,75,不同的语言中，通过声明变量标识符和类型联系的规则是不同的，在解释这些规则时，结构等价和名字等价是两个有用的概念。 例5.27 在一些Pascal的实现中，用隐含的类型 名和每个声明的变量标识符相联系，如果说 明中出现没有名字的类型表达式，就建立一 个隐含的类型名。 TYPE VAR Link=cell; next : link; np=cell; last : link; nqr=cell; p : np; q,r : nqr;,76,典型的实现是构造一张类型图，每当遇到类型构造符和基本类型，就建立一个新结点，但要记住类型名所命名的类型表达式。在这种方法中，如果两个类型表达式用类型图中同样的结点表示，那么，它们等价。,link,=,pointer,pointer,pointer,cell,next,last,p,q,r,图5.31,77,类型表示中的环 链表和树结构经常是递归定义的。它们的结点通常定义成一个记录，记录中含有指向同类型记录的指针。 设链表中的结点含有一个整型信息和一个指向下一个结点的指针，实现链表的类型定义： TYPE link=node; node=RECORD info:integer; next: link END;,78,类型表达式用图表示如下：,Node=record,info integer,next pointer,node,Node=record,next,info integer,pointer,a. 无环,b. 有环,79,5.8.2 类型分析 5.8.2.1 变量标识符和类型表达式的绑定 程序说明部分建立计算环境,其中说明了每个变量标识符以及与之绑定的类型。语法(5.10)是一个简单的程序语言语法，假设数组的下标从1开始。 文法GP，产生式如下： (5 . 10) PD；E DD；D | id:T Tchar | integer | ARRAYnum OF T | T Enum | id | E mode | EE | E（E）| E,80,语义分析程序首先处理类型说明，建立类型 表达式，然后处理变量说明，建立变量和类型 表达式的绑定。具体实现是把变量标识符的类 型信息记录在其符号表的表项中，过程 addtype（id.enery,T.type）完成这个任务，其 翻译模式由图5.32给出,81,PD；E DD；D Did:T addtype（id.enery，T.TYPE） Tchar T.type:=char Tinteger T.type:=integer TT1 T.type:=POINTER(T1.type) TARRAYnum OF T1 T.type:=ARRAY(num.val,T1.type) 图5.32 建立变量标识符和类型属性绑定 的翻译模式,82,5.8.2.2 类型检查 借助于符号表中变量和类型属性的绑定信息，分析确定每个语言结构的类型表达式。类型检查是在编译时做的静态类型检查。 表达式的类型检查 检查对象之间类型是否满足相容条件,函数lookup（e）取符号表中保存在条目e中的类型。 Enum E.type:=integer Eid E.type:=lookup(id.entry) EE1 MOD E2 E.type:= IF (E1.type=integer)AND(E2.type=integer) THEN integer ELSE type_error ,83,EE1E2 E.type:= IF(E2.type=integer)AND(E1.type=ARRAY(s,t) THEN t ELSE type_error EE1 E.type:=IF E1.type=POINTER(t) THEN t ELSE type_error 图5.33 表达式的类型检查的翻译模式 语句的类型检查 指派给语句的类型是基本类型void，如果在语句中发现类型错误， 指派给语句的类型是type_error。,84,Sid:=E S.type:=IF id.type=E.type THEN void ELSE type_error SIF E THEN S1 S.type:=IF E.type=boolean THEN S1.type ELSE type_error SWHILE E DO S1 S.type:=IF E.type=boolean THEN S1.type ELSE type_error SS1;S2 S.type:=IF (S1.type=void)AND(S2.type=void) THEN void ELSE type_error 图5.34 检查语句类型的翻译模式,85,函数引用的类型检查 对说