编译原理8.ppt

1、语法制导翻译和中间代码生成,第8章,属性文法和语法制导翻译,编译程序的作用是：将源程序转换为具有相同效果的可运行程序。 所谓相同效果就是程序的语义。 并不是所有满足语法规则的程序都是有意义的。 所谓语义分析，就是确定程序是有意义的，分析程序的含义，并做出相应的处理。 程序的含义包括： 数据结构的含义：和标识符相关联的数据对象。 控制结构的含义：由语言定义。规定了每个语句的执行效果。,语义分析和中间代码的产生,在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。静态语义检查通常包括： 1。类型检查。 2。控制流检查。 3。一致性检查。 4。相关名字检查。 翻译为中间语言的好处：

2、 （1）便于进行与机器无关的代码优化； （2）使编译程序改变目标机更容易； （3）使编译程序的结构在逻辑上更为简单明确， 以中间语言为界面，编译前端和后端的接口更清晰。,语义分析的基本功能,确定类型：确定标识符所关联的数据对象的数据类型。 类型检查：按照语言的类型规则，对运算及分量进行类型检查，必要时做出相应类型转换。 识别含义：根据程序设计语言的语义定义，确定各个构造部分组合后的含义，做出相应处理（生成中间代码或者目标代码）。 其它静态语义检查：比如控制流检查，嵌套层数检查。,语义分析的输入输出,输入为前面语法分析的结果。 输出为中间表示代码(抽象语法树，三元式)。 对中间代码的分析比较容易

3、，便于进行优化。 可以把编译程序分成机器独立部分和机器相关部分。 便于任务的分解，和开发人员的分组开发。,例:简单台式计算器的语法制导定义,属性文法,对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把重写规则附加以语义规则的时候，就得到属性文法。 语法制导的翻译过程：由于属性文法的规则和重写规则是一一对应的关系。所以，由属性文法的确定的语义分析可以在语法分析的过程中进行。这个过程成为语法制导的翻译。,属性文法,属性文法(attribute grammar)是一个三元组: A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这

4、些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等 .属性与变量一样，可以进行计算和传递。 F:关于属性的属性断言或一组属性的计算规则(称为语义规则) . 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.,属性文法,语义规则描述的动作包括：属性计算、静态语义检查、符号表操作、代码生成等。 如果对于G中的某一个输入串而言， F中的所有断言对该输入串的语法树结点的属性都为真，则该输入串也是A语言中的句子。 编译程序的静态语义审查就是验证所编译的程序的断言是否全部为真。 例：类型检查的属性文法 P170 图8.2 属性一般分为两类：综合属性和

5、继承属性 综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。,设表达式为35+4，则语义动作打印数值19, 语义规则见P171例8.1,3*5+4的带注释的分析树,例：说明语句,说明语句的文法 D T L T int T real L L1,id L id,要解决的问题： 纪录标识符的类型 类型信息传递,说明语句类型信息传递,方法 编写说明语句的文法 将类型信息作为类型描述 T 的属性 type 和变量表 L 的属性 in。 目的 分析说明语句 D，为变量指定类型,语法制导定义(属性文法),entry 单词 id 的属性 addtype 在符号表中为变量填加类型信息,Rea

6、l id1,id2,id3,语义规则,在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为： b:=f(c1,c2,ck) 这里f是一个函数 综合属性：b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性； 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S属性文法。 继承属性：b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck是A或产生式右边任何文法符号的属性 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些

7、属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。,强调： （1）终结符只有综合属性，它由词法分析器提供 （2）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。 一般，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供。,基于属性文法的处理方法 输入串语法树依赖图语义规则计算次序 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。 语义规则计算结果：可

8、能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行计算得出结果。,S属性文法的自下而上计算,S属性文法：只含有综合属性。 下面我们讨论分析栈中的综合属性。 在自下而上的分析法中。我们使用一个栈来存放已经分析过的子树的信息。现在我们可以在分析栈中使用一个附域来存放综合属性值。右图表示的是一个带有一个属性值空间的分析栈的例子。,State val X X.x Y Y.y Z Z.z ,top,设栈是由一对数组state和val来实现的。 每一个state元素都是一个指向LR(1)分析表的指针然而，如果第i个state对应的符号为A时，vali中就存

9、放语法树中与结点A对应的属性值。 设栈顶指针top。语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的。在把XYZ归约成A以前，属性Z.z的值放在valtop中，Y.y的值放在valtop-1中，X.x的值放在valtop-2中。归约后，top值减2，A的状态存放在statetop中（也就是X的位置）综合属性A.a的值存放在valtop中。 如果一个符号没有综合属性，那么数组val中相应的元素就不定义。,S属性定义的自下而上计算,将LR分析器增加一个域来保存综合属性值。,栈 state val,top,若产生式A XYZ的语义规则是 A.a := f (X.x, Y.y,

10、Z.z)， 那么归约后：,top,S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,L属性文法和自顶向下翻译,一个属性文法称为L属性文法：如果对于每个产生式AX1X2Xn其每个语义规则中的每个属性或者是综合属性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖于： （1）产生式Xj的左边符号X1,X2,Xj-1的属性 （2）A的继承属性。,翻译模式,在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号 括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。 如果既有综合属性又有继承

11、属性，在建立翻译模式时： （1）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 （2）一个动作不能引用这个动作右边符号的综合属性。 （3）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,例1 某程序设计语言说明部分的语法制导定义如下： DTL Tint Treal LL1, id Lid 给出语法制导定义及自底向上的翻译模式，并比较两者的不同。 解：语法制导定义为： DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id

12、 L1.in := L.in, addtype(id.entry , L.in ) Lid addtype (id.entry, L.in) ,自底向上分析的翻译模式为： DT L.in := T.type L Tint T.type := integer Treal T.type := real L L1.in := L.in L1, id addtype(id.entry , L.in ) Lid addtype (id.entry, L.in) 从上述定义看两者的区别仅在于在翻译模式中把语义动作插入在规则右部的任意位置。而语法制导中把语义动作都放在产生式的最后。,例2 在一个移入归约的分

13、析中采用以下的语法制导的翻译模式，在某产生式归约时，立即执行括号中的动作。 AaB print “0” Ac print “1” BAb print “2” 当分析器输入为aacbb时，打印的字符串是什么? 解： 分析器的分析过程如右图： 由于分析器采用移入归约的方式进行分析，符号串aacbb的分析过程将按标号进行，而按一产生式归约时立即执行括号中的动作所以分析器打印的字符为： 12020,设有文法GS： S(L)|a LL，S|S 写出一个属性翻译文法，它输出配对括号的个数。 答案： S(L) S.n:=L.n+1 Sa S.n:=0 LL，S L.n:=L.n+S.n LS L.n:=S.

14、n,中间语言,几种中间语言的基本结构： 逆波兰表示 图表示法（DAG 和抽象语法树） 三地址代码（四元式、三元式、间接三元式）,逆波兰式(后缀式表示),把运算量（操作数）写在前面，把算符写在后面（后缀）。 一个表达式的后缀式可以如下定义： （1）如果E是一个变量或常量，则E的后缀式是E自身。 （2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为 E1 E2 op,这里E1 和E2分别为E1和E2的后缀式。 （3）如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。,例：对中缀式a+b+c*d有四种不同的理解，对应后缀式四种表示： 结合性 优先级 中缀式

15、后缀式 左 * + (a+b)+(c*d) ab+cd*+ 右 * + a+(b+(c*d) abcd*+ 左 + * (a+b)+c)*d ab+c+d* 右 + * (a+(b+c)*d abc+d* 后缀式的推广：遵守广义运算符在运算量后面的原则。 例：x=a+b 后缀式为：xab+= = 作为广义运算符，其优先级低于运算符+,例： 表达式：a*b+c 后缀式：ab*c+ 表达式：a*(b+c) 后缀式：abc+* 表达式：(a+b)*(c+d) 后缀式：ab+cd+* 表达式：a := b *（- c）+ b *（- 34） 后缀式: a b c - * b 34 - * + :=,后

16、缀式的最大优点是利用栈可以很方便地处理表达式。,例： if e then X else Y,j：无条件转移运算符 juz：条件e为真(非0)转移运算符 jez：条件e为假(0)转移运算符 将形成后缀式存放在一维数组POSTN中，数组的每一个元素存放一个运算符或运算量。 后缀式 pi j 表示无条件转移到pi所指那个元素，即POSTpi。 后缀式 e pi jez 表示条件 e 为假(0)转移到 POSTpi。 if e then X else Y 的后缀式： ep1 jez Xp2 j Y 例如： if a+bc then a=a-1; else b=b+1; POST,生成后缀式的属性文法,

17、三地址代码,三地址代码 三地址代码是由下面一般形式的语句构成的序列: x:=y op z 其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。每个语句的右边只能有一个运算符。,三地址代码,一般形式 x := y op z 其中 x, y, z 为变量名、常数或编译产生的临时变量 四元式（op, y, z, x） 三元式、间接三元式（p178-179),种类：x := y op z 双目运算 x := op y 单目运算 x := y 复制语句 if x relop y goto l 条件转移语句,其它语句的三地址代码,goto l 无条件

18、转移 param x 实在参数 call p, n 过程调用 return x 过程返回 x := yi数组运算 xi := y x := 产生新的临时变量 newtemp 属性设置 Id名字 中间代码序列 code 存储位置 place,四元式形式: (op ,arg1,arg2,result) 或 Result:= arg1 op arg2,S id := E P :=lookup(); if P nil then emit( P “:=“E.place) else error (2) EE1+E2 E.place:= newtemp; emit(E.plac

19、e“:=” E1.place“+”E2.place) (3) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place) (4) E( E1) E.place:= E1.place (5) Eid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error,例:翻译 a:= -c+b*34,T1:=uminus c T2:=b*34 T3:=T1+T2 a:=T3,布尔表达式的翻译,布尔表达式有两个基本作用： 用作计算逻辑值； 用作控制流语句如 if

20、-then、if-then-else和 while-do等之中的条件表达式。 布尔表达式是用布尔运算符号（and、 or、not )作用到布尔变量或关系表达式上而组成的。 EE or E | E and E | not E | (E) | id relop id |id 设：or和and 是左结合的，并且规定or 的优先级最低，其次是and, not的优先级最高 relop为关系运算符 （ , , =, ）,数值表示法,三种逻辑运算的等价解释: A or B: if A then true else B A and B: if A then B else false Not A: if A t

21、hen false else true 因此二种作用都可以归纳成统一的条件翻译方式,布尔式翻译,出现条件语句： if E then S1 else S2,E.false,E,的代码,E,.true,E,.true:,S,1,的代码,goto out,E.false:,S,2,的代码,out:,.,把条件转移的布尔表达式翻译成仅含条件真转和 无条件转的四元式 E： a rop b If a rop b goto E.true goto E.false,如,：,ab or cd and ef 希望翻译成如下三地址代码：,(1)if ab goto E.true (2)goto (3) (3)if

22、cd goto (5) (4)goto E.false (5)if ef goto E.true (6)goto E.false,产生布尔表达式三地址代码的语义规则,E E1 or E2 E1.true := E.true; E1.false := newlabel; E2.true := E.true; E2.false := E.false; E.code:=E1.code| gen(E1.false, :) | E2.code ,if a b goto E.true goto L1 L1:if c d goto E.true goto E.false E.true：。 E.false:

23、。,ab: if a b goto E1.true goto E1.false cd: if c d goto E2.true goto E2.false,表达式a b or c d的代码是：,产生布尔表达式三地址代码的语义规则,E E1 and E2 E1. false := E. false; E1. true := newlabel; E2.true := E.true; E2.false := E.false; E.code:=E1.code| gen(E1. true, :) | E2.code ,if a b goto L1 goto E.false L1:if c d goto

24、E.true goto E.false E.true：。 E.false: 。,ab: if a b goto E1.true goto E1.false cd: if c d goto E2.true goto E2.false,表达式a b and c d的代码是：,如何用一遍扫描完成翻译？ 假设实现三地址代码时采用四元式形式实现，并且假定： （jnz , a ,- , p ) 表示 if a goto p (jrop, x , y, p ) 表示 if x rop y goto p (j , -, - , p ) 表示 goto p 有时,四元式转移地址无法立即知道,我们只好把这个未完成

25、的四元式地址作为E的语义值保存,待机回填。,回填技术,if (ab) max=b; else max = a; (j, a, b, ? ) 可以使用回填技术解决： 先生成一个指令坯，不填入转移目标；把这个指令的相关信息保存好，把需回填True的四元式拉成一链，把需回填False的四元式拉成一链，分别称做“真”链和“假”链当可以得到转移目标的时候,在把目标填入这个位置。,为非终结符E赋予两个综合属性E.true和E.false。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填真出口的p，q，r三个四元式，则E.true为下列

26、链: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),链尾,E. true =r,为了处理E.true和E.false ，引入下列语义变量和过程: 变量nextstat，它指向下一条将要产生但尚未形成的四元式的地址(标号)。 每当执行一次emit之后， nextstat将自动增1。 变量codebegin，一段代码开始的四元式的地址(标号) 。 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。,布尔表达式的

27、文法,(1) EE1 or E2 (2) | E1 and E2 (3)| not E1 (4)| (E1) (5)| id1 relop id2 (6)| id | ture |false,布尔表达式的翻译模式,(1) EE1 or E2 backpatch(E1.false, E2.codebegin); E.codebegin:=E1. codebegin; E.true:=merge(E1.true, E2.true); E.false:=E2.false (2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.codebegin:=E1.

28、 codebegin; E.true:=E2.true; E.false:=merge(E1.false,E2.false) Page 185,布尔表达式的翻译模式,(3) Enot E1 E.true:=E1.false; E.codebegin:=E1. codebegin; E.false:=E1.true (4) E(E1) E.true:=E1.true; E.codebegin:=E1. codebegin; E.false:=E1. false,布尔表达式的翻译模式,(5) Eid1 relop id2 E.true:=nextstat; E.codebegin:= nextst

29、at; E.false:= nextstat +1; emit(j rop , id 1.place , id 2.place,0); emit(j, , , 0) (6) Etrue E.true:= nextstat; E.codebegin:= nextstat; emit( j, -, -, 0) (7) E false E.false:= nextstat; E.codebegin:= nextstat; emit( j, -, -, 0) ,布尔表达式的翻译模式,作为整个布尔表达式的真假出口(转移目标)仍待回填.,回填的例子,ad AND ef,100 (j,a,b,0) 101(

30、j,_,_,0),102 (j,c,d,0) 103(j,_,_,0),104 (j,e,f,0) 105(j,_,_,0),回填的例子,ad AND ef,100 (j,a,b,0) 101(j,_,_,0),102 (j,c,d,104) 103(j,_,_,0),104 (j,e,f,0) 105(j,_,_,0),回填的例子,ad AND ef,100 (j,a,b,0) 101(j,_,_,102),102 (j,c,d,104) 103(j,_,_,0),104 (j,e,f,0) 105(j,_,_,0),控制语句的翻译（参考国防工业出版社陈火旺编译原理书的这一部分）,控制流语句

31、 考虑文法： S if E then S1 | if E then S1 else S2 | while E do S1 其中E 布尔表达式。 先对这些语句进行翻译的一般语义规则。然后讨论如何通过一遍扫描产生上述语句的代码，给出相应的翻译模式。,S if E then S1,E.true:=newlabel; E.false:=S.next; S1.next:=S.next; S.code:=E.code| gen(E.true:)|S1.code;,Sif E then S1 else S2,E.true:=newlabel; E.false:= newlabel; S1.next:=S.n

32、ext; S2.next:=S.next; S.code:=E.code| gen(E.true:)|S1.code |gen(goto S.next)| gen(E.false:)|S2.code;,例：翻译IF ab THEN a=y+z ELSE b=x+y 成四元式序列,If ab goto L1 (1) (j,a,b,(3) goto L2 (2) (j,_,_,(6) L1: T1:=y+z (3) (+,y,z,T1) a:=T1 (4) (:=,T1,_,a) goto S.next (5) (j,_,_,(8) L2:T2:=x+y (6) (+,x,y,T2) b:=T2

33、(7) (:=,T2,_,b) S.next (8),S while E do S1,S.begin:= newlabel; E.true:=newlabel; E.false:= S.next; S1.next:= S.begin; S.code:= gen(S. begin :)|E.code|gen(E.true:)|S1.code |gen(goto S. begin );,例 ：翻译下列语句,while a y do z := x + 1; else S12 x := y,S,while a y do C2 z := x + 1; else S12 x := y,L1: C.code

34、 L2: S.code goto L1 Lnext:,S,while,while a y do C2 z := x + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: S.code goto L1 Lnext:,S,while a y do C2 z := x + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: C1.code L3: S11.code goto L5 L4: S12.code L5: goto L1 Lnext:,S,while a y do C2 z := x

35、 + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: if c 5 goto L3 goto L4 L3: S11.code goto L5 L4: S12.code L5: goto L1 Lnext:,S,while a y do C2 z := x + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: if c 5 goto L3 goto L4 L3: C2.code L6: z:=x+1 goto L3 goto L5 L4: S12.code L5: goto L1 L

36、next:,S1,while a y do C2 z := x + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: if c 5 goto L3 goto L4 L3: if x y goto L6 goto L7 L6: z:=x+1 goto L3 L7: goto L5 L4: S12.code L5: goto L1 Lnext:,S1,while a y do C2 z := x + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: if c 5 goto L3 goto

37、 L4 L3: if x y goto L6 goto L7 L6: z:=x+1 goto L3 L7: goto L5 L4: x:=y L5: goto L1 Lnext:,S1,while a y do C2 z := x + 1; else S12 x := y,L1: if a b goto L2 goto Lnext L2: if c 5 goto L3 goto L4 L3: if x y goto L6 goto L1 L6: z:=x+1 goto L3 L4: x:=y goto L1 Lnext:,S1,生成的三地址代码序列,L1: if a b goto L2 got

38、o Lnext L2: if c 5 goto L3 goto L4 L3: if x y goto L6 goto L1 L6: z:=x+1 goto L3 L4: x:=y goto L1 Lnext:,C.code,C1.code,S11.code,S12.code,S1.code,For语句,Pascal语言的标准将for语句 for v := initial to final do stmt 定义成和下面的代码序列有同样的含义： begin v := initial; do while v= final begin stmt; v := succ(v); end end,Pasca

39、l语言for语句 for v := initial to final do S,的中间代码结构如下: v := initial L2: if v final goto L1 S v := v + 1 goto L2 L1:,C语言的for语句有下列形式 for (e1;e2;e3) stmt 它和 e1; while (e2)do begin stmt; e3; end 意义相同,C语言的for语句for (e1;e2;e3) stmt的中间代码 结构如下 e1的代码 L1: e2的代码 L2: stmt的代码 e3的代码 goto L1,翻译C语言：for (I=0;I10;I+) for(

40、j=0;jI;j+) AI,j=0;,三地址代码: I:=0 L1:if I10 goto L2 goto S.next L2: j:=0 L3:if jI goto L4 goto L5 L4:T1:=I*5 T1:=T1+j,A为10 x5的整型数组,T2:=A-C T3:=4*T1 T2T3:=0 j:=j+1 goto L3 L5: I:=I+1 goto L1 S.next:,四元式： (1) (:=, 0, , I) (j, I,10,(4) (j, , , (16) (:=, 0, , j) (j, j,i,(6) (j, , , (14) (*, I , 5, T1) (+,T

41、1,j, T1),(-,A,C, T2) (:=,4,T1,T3) (=,0,T2T3) (:=, j ,1 , j) (j , , ,(5) (:=, I , 1 , I) (j, , , (2),GOTO语句的翻译,L: S; GOTO L,L已定义，查找符号表，取得L所定义地址P，（J，-，-，P）,GOTO L L: S;,L尚未定义，先将L加入符号表，地址标明未定义，等处理L：S时再填入地址。 GOTO到L的所有四元式结链，以后回填。,CASE语句的翻译,switch E case C1: S1 case C2: S2 . . . case Cn - 1: Sn 1 default:

42、 Sn ,CASE语句的翻译,CASE语句的实现方法： 1。转化成条件转移语句 2。表格法 分二栏：Ci的值，对应语句Si的地址。 3。数组法 适用于值变化范围较小的的情况，数组下标作为Ci，数组值为Si的地址。,转化成条件转移语句,分支数较少时 t := E的代码 | Ln-2: if t Cn-1 goto Ln-1 if t C1 goto L1 | Sn -1的代码 S1的代码 | goto next goto next | Ln-1: Sn的代码 L1:if t C2 goto L2 | next: S2的代码 goto next L2:. . . . . .,表格法,分支较多时，将

43、分支测试的代码集中在一起， 便于生成较好的分支测试代码。 t := E的代码| Ln:Sn的代码 goto test | goto next L1:S1的代码 |test: if t = C1 goto L1 goto next| if t = C2 goto L2 L2:S2的代码 | . . . goto next|if t = Cn-1 goto Ln-1 . . . |goto Ln Ln-1:Sn -1的代码 | next: goto next,数组元素的引用,一维数组元素Alow:up ,Ai 的起始地址为： base + (i low)*w Low：为数组下标的下界； w：每个元

44、素的宽度； Base：是分配给数组的相对起始地址，即base为A的第一个元素Alow的相对地址。 上式可以整理为： i*w + (base low*w) 其中：i*w 是随数组下标变量而变化的部分 （base low*w)是在编译中可确定的常数记为C 上式改为： i*w +C C= base low*w,base,w,up,low,二维数组-按行存放,二维数组Alow1:up1 , low2:up2Ai1,i2 ： Addr(Ai1,i2)=base+(i1- low1)*n2+ (i2-low2)*w = base+(i1- low1)*n2*w+(i2-low2)*w = base- lo

45、w1* n2*w-low2*w +i1 * n2*w+ i2*w = base-(low1* n2 +low2)*w +(i1 * n2 + i2)*w =C+(i1*n2+ i2)*w 其中，low1、low2分别为i1、i2的下界；n2是i2可取值得个数。即若up2为i2的上界，则n2= up2 low2 +1. 特别是当low=1 时有：V=(i1*n2+i2)*w C= base (n2+1)*w 应该牢记。 推广计算公式,K维数组-按行存放,Ai1,i2,ik ： （ ( ( i1*n2 +i2)n3)nk + ik)*w+ base-(low1* n2 +low2)*n3+low3

46、)nk+lowk)*w =V+C,数组元素引用,如下数组文法： Lid Elist | id ElistElist, E | E 为语义处理上的方便改写为： LElist | id Elist Elist, E | id E 描述L的左值用两个属性L.place和L.offset. 如果L仅为一个简单名字，L.place就为指向符号表中相应此名字表项的指针，而offset为null，表示这个左值只是一个简单名字而非数组的引用。若offset不是null，则为数组的引用， L.place指向符号表中该数组名。,数组元素引用,一个Elist可以产生一个k- 维数组引用Ai1,i2,ik的前m维下标

47、，并将生成计算下面式子的三地址代码。 （ ( ( i1*n2 +i2)*n3)nm + im 利用如下的递归公式进行计算： e1 = i1, em = em-1* nm + im V=（ ( ( i1*n2 +i2)n3)nm + im)*w 于是 当m=k时将ek乘以元素的宽度w便可计算出 V。,数组元素引用,Elist.array:纪录指向符号表中相应数组名字表项的指针。 Elist.dim:纪录Elist中的下表表达式的个数，即维数。 函数Limit(array, j) 返回nj ，即由array所指示的数组的第j 维的长度。 Elist.place:临时变量，临时存放由Elist中的下

48、标表达式计算的值。,SL:=E if L.offset=null then gen(L.place:=E.place) else gen(L.placeL.offset:=E.place EL if L.offset=null then E.place:=L.place else E.place:=newtemp; gen(E.place:=L.placeL.offset Lid L.place:=id.place; L.offset:=null LElist L.place:=newtemp;L.offset:=newtemp; gen(L.place:= C); gen(L.offset:

49、=Elist.place*w),ElistElist1,E t:=newtemp;m:=Elist1.dim+1; Elist.array:=Elist1.array; gen(t:=Elist1.place*limit(Elist.array,m); gen(t:=t+E.place); Elist.place:=t;Elist.dim:=m ElistidEElist.place:=E.place;Elist.dim:=1; Elist.array:=id.place,例:设A为一个10X20的数组，即n1=10, n2=20并设w=4。对付值语句X:=Ay,z （1） 写出该赋值语句被翻

50、译成三地址代码语句系列。 （2）画出该赋值语句的代注释语法分析树。 解： 三地址代码： T1:=y*20 T1:=T1 + z T2:= A-84 为：A-(n2 +1 )*w T3:= 4* T1 T4:= T2 T3 x:= T4,带注释的语法树：其中每个变量，用其名字代替id.place.,说明语句,说明语句： 1。分配存储空间。 2。在符号表中建立相应的表项，填入相应的信息，如类型、在存储器中的相对地址（指对静态数据区基地址的一个偏移量）。 过程中的说明语句 在一般高级语言中，一个过程中的所有说明语句可作为一个组分配在同一数据区中。可用全程变量offset来跟踪下一个可用的相对地址的位

51、置。,文法描述,P D D D ; D D id : T T integer T real T arraynum of T1 T T1,例如： a:integer; b:real; c:array10of real,变量说明的翻译,在符号表中填写变量的属性 种别、类型、相对地址、作用域等 相对地址 全局变量表示为静态数据区的偏移值(offset) 局部变量表示为局部数据域(活动记录的部分）的偏移值,例:相对地址举例,名字 相对地址 x 0 i64 j68,0 8 56 64 68,Begin real x8; integer i, j; end,属性、过程、与全局量,类型T的属性 type 类

52、型 width 占用的字节数 基本子程序 inter：在符号表中设置变量的类型和地址 array：数组类型处理 pointer: 指针类型的处理 全局量 offset：已分配空间字节数,说明语句的翻译模式,P offset := 0 D D D ; D D id : T enter( id.entry, T.type, offset ); offset := offset + T.width T integer T.type := integer; T.width := 4 T real T.type := real; T.width := 8 T array num of T1 T.type

53、 := array( num.val, T1.type); T.width := num.val * T1.width T T1 T.type := pointer( T1.type); T.width := 4,例：x:real; i:integer 的翻译,enter(x,real,0),offset=0,offset=8,T.type=real T.width=8,offset=12,T.type=integer T.width=4,enter(i,integer,8),例：C说明语句,最简单的说明句的语法： integernamelist;realnamelist; namelistn

54、amelist，idid 文法可改写为： P D D T L; T int T real L L1 ,id L id,P offset:=0D D T LL.type := T.type; L.width:= T.width T intT.type := integer;T.width:=4 T realT.type := real;T.width:=8 L L1 ,id L1.type:= L.type; L1.width:= L.width enter(, L.type,offset); offset:=offset+ L.width L identer(,L.type,offset); offset:=offset+ L.width,其中： P offset:=0 D 改写为： PMD M offset:= 0 ,组合数据说明的翻译,分类 同结构的组合数据(同质数据结构) 数组、集合 异结构的组合数据(异质数据结构) 记录、结构、联合 抽象数据类型 类、模块,记录的域名,T record D end 改写成: T record L D end T.