第6章 语法制导翻译和语义分析

编译原理第6章语法制导翻译和语义分析安庆师范学院计算机与信息学院本章目标定义相关概念：属性、属性文法、S——属性文法和L——属性文法解释基于属性文法的语法制导翻译技术的基本思想介绍常见的中间代码的描述方法介绍不同语法结构的语法制导翻译技术教学内容6.1属性文法与语法制导翻译6.2语义分析和中间代码的产生6.3简单算术表达式及赋值语句的翻译6.4布尔表达式的翻译6.5控制结构的翻译教学内容6.6说明语句的翻译6.7数组的翻译6.8过程调用语句的翻译6.9本章小结6.1属性文法与语法制导翻译属性及属性文法

1综合属性与继承属性

2S—属性文法与L—属性文法

3基于属性文法的语法制导翻译

41、属性及属性文法（1）文法的属性

属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。 随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来。对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号X，该X可以是终结符或非终结符。根据语义处理的需要，在用产生式A→αXβ进行归约或推导时，应能准确而恰当地表达文法符号X在归约或推导时的不同特征。 例如，判断变量X的类型是否匹配，要用X的数据类型来描述；判断变量X是否存在，要用X的存储位置来描述；而对X的运算，则要用X的值来描述；因此，语义分析阶段引入X的属性，如X.type、X.place、X.val等来分别描述变量X的类型、存储位置以及值等不同的特征。1、属性及属性文法（2）属性文法

属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了属性的文法，它将文法符号的语义以“属性”的形式附加到各个文法的符号上(如上述与变量X相关联的属性X.type、X.place和X.val等)，再根据产生式所包含的含义，给出每个文法符号属性的求值规则，从而形成一种带有语义属性的上下文无关文法，即属性文法。属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作。属性文法=上下文无关文法+属性+语义规则返回2、综合属性与继承属性（1）属性分类

属性文法中的属性可分为继承属性与综合属性两类。继承属性 用于“自上而下”地传递信息。综合属性

用于“自下而上”地传递信息。（2）语义规则 属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程。对于文法的每一个产生式都配备了一组属性的计算规则，称为语义规则。2、综合属性与继承属性（3）语义规则的表示 在一个属性文法中，对应于每个产生式A→α都有一套与之相关联的语义规则，每条规则形式为 其中f是一个函数，而且或者 ①b是A的一个综合属性，并且c1,c2,…,ck是α中文法符号的属性；或者 ②b是α中某个文法符号的一个继承属性并且c1,c2,….,ck是A或α中任何文法符号的属性。 在上述两种情况下，我们都说属性b依赖于属性c1,c2,…,ck。2、综合属性与继承属性（3）语义规则的表示 【注意】 ①终结符号只有综合属性，由词法分析器提供。 ②非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。 ③对出现在产生式右边的继承属性和产生式左边的综合属性都必须提供一个计算规则。 ④属性计算规则中只能使用相应产生式的文法符号的属性，这有利于在产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供。返回3、S—属性文法与L—属性文法（1）S—属性文法

仅仅使用综合属性的属性文法，称为S—属性文法。（2）L—属性文法 一个属性文法称为L—属性文法，如果对于每个产生式A→x1x2,…xn，其每个语义规则中的每个属性或者是综合属性，或者是xj(1≤j≤n)的一个继承属性且这个继承属性仅依赖于： ①产生式中xj的左边符号x1,x2,…xj-1的属性； ②A的继承属性 L—属性文法的最大特点是产生式右部符号的继承属性不依赖于该符号右边符号的任何属性。3、S—属性文法与L—属性文法 【注意】

①S—属性文法一定是L-属性文法②S—属性文法适合于一遍扫描的自下而上分析③L—属性文法可用于一遍扫描的自上而下分析返回4、基于属性文法的语法制导翻译（1）语法制导翻译

所谓语法制导翻译就是指为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。语法制导翻译法的基本思想是对文法中的每个产生式都附加上一个语义动作（或语义子程序），在执行语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式对应的语义动作（或语义子程序）。这些语义动作不仅指明了该产生式所产生符号串的意义，而且还根据这种意义规定了对应的加工动作（如查填各类表格、更新变量的值、提示出错信息、生成中间代码等），从而完成预定的翻译工作。

4、基于属性文法的语法制导翻译（2）举例【例6.1】描述简单算术表达式求值的属性文法。产生式语义规则（1）L→E{print(E.val);}（2）E→E1+T{E.val=E1.val+T.val;}（3）E→T{E.val=T.val；}（4）T→T1*F{T.val=T1.val*F.val;}（5）T→F{T.val=F.val;}（6）F→(E){F.val=E.val;}（7）F→digit{F.val=digit.lexval;}val：综合属性，表示E、T、F的值lexval：综合属性，由词法分析器提供print：打印由E产生的表达式值4、基于属性文法的语法制导翻译LEE+TTT*FFdigitdigitFdigit.lexval=3.lexval=5.lexval=4.val=3.val=3.val=5.val=15.val=15.val=4.val=4.val=19计算表达式3*5+4的值print(19)4、基于属性文法的语法制导翻译【例6.2】描述说明语句中变量类型信息的属性文法。产生式语义规则（1）D→TL{L.in=T.type;}（2）T→int{T.type=int;}（3）T→float{T.type=float;}（4）L→L1,id{L1.in=L.in;addtype(id.entry,L.in);}（5）L→id{addtype(id.entry,L.in);}type：综合属性，其值由说明中的关键字确定in：继承属性，addtype：把每个标识的类型信息登记到符号表中相关项（id.entry）中4、基于属性文法的语法制导翻译DTLintL,id2id1intid1,id2.type=int.in=int.in=intaddtype(id1.entry,int)addtype(id2.entry,int)返回6.2语义分析和中间代码的产生语义分析的任务

1常见的中间代码形式

21、语义分析的任务

语义分析与处理的主要任务： （1）审查每个语法结构的静态语义，即验证语法结构合法的源程序是否真正有意义。有时把这个工作称为静态语义分析或静态语义审查。 （2）若静态语义正确，则要执行语义翻译，即用另一种语言形式（比源语言更接近于目标语言的一种中间代码或直接用目标代码）来描述这种语义。返回2、常见的中间代码形式（1）中间代码

源程序的一种内部表达，不依赖于目标机的结构，易于机械生成目标代码的中间表示，称为中间代码。（2）为什么要此阶段 使用中间代码主要有以下几点好处： ①使逻辑结构清楚 ②有利于不同目标机上实现同一种语言 ③有利于进行与机器无关的优化 ④这些内部形式也能用于解释2、常见的中间代码形式（3）常见的中间代码形式 ①后缀式（逆波兰表示式） ②图表示法抽象语法树DAG图 ③三地址代码四元式三元式间接三元式2、常见的中间代码形式（4）后缀式（逆波兰式）①定义 后缀式表示法（逆波兰表示法），由波兰逻辑学家卢卡西维奇（Lukasiewicz）发明，它把运算量（操作数）写在前面，把运算符写在后面（后缀）的一种表达式表示方法。其归纳定义如下：如果E是一个变量或常数，则E的后缀式是E自身。如果E是E1opE2形式的表达式，op是二元操作符，则E的后缀式为E1´E2´op，其中E1´，E2´分别是E1和E2的后缀式。若E是（E1）形式的表达式，则E的后缀式就是E1的后缀式。2、常见的中间代码形式（4）后缀式（逆波兰式）②举例

表达式后缀式（逆波兰式）a+bab+(a+b)*(c+d)ab+cd+*A+B*(C-D)+E/(C-D)∧NABCD-*+ECD-N∧/+a=b*c+b*dabc*bd*+=2、常见的中间代码形式（4）后缀式（逆波兰式）③后缀式的计算机处理 后缀式的最大优点是易于计算机处理，其处理过程如下： 利用一个栈，从左至右扫描逆波兰式，若当前符号是运算对象则进栈，若当前符号是运算符（假定该运算符号是k元运算符），则将栈顶k个元素依次弹出，同时进行k元运算，并将运算结果进栈，表达式处理完毕时，最后的结果留在栈顶。2、常见的中间代码形式（5）图表示法①抽象语法树 在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。抽象语法树不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的层次结构。 例如，表达式x=a-b*c的语法树和抽象语法树如下图所示：S→V=EV→xE→E-E|E*E|a|b|c2、常见的中间代码形式（5）图表示法②DAG图（DirectedAcyclicGraph，有向无环图） 对表达式的每个子表达式，DAG都有一个结点，一个内部结点代表一个操作符，它的孩子代表操作数，在一个DAG中代表公共子表达式的结点具有多个父结点。而在抽象语法树中公共子表达式被表示为重复的子树。 例如，表达式a+a*(b-c)+(b-c)*d的DAG图和抽象语法树如下图所示：2、常见的中间代码形式（6）三地址代码 三地址代码可以看成是抽象语法树或ＤＡＧ的一种线性表示。①三地址代码的形式 三地址代码语句的一般形式为x=yopz其中，x、y和z为名字、常量或编译时产生的临时变量，op为运算符。三地址代码的每条语句通常包含三个地址，两个用来存放运算对象，一个用来存放运算结果。 实际中用户定义的名字由指向符号表中该名字项的指针所取代。由于三地址语句只含一个运算符，因此多个运算符组成的表达式需用三地址语句序列来表示。2、常见的中间代码形式（6）三地址代码 例如，表达式x+y*z的三地址代码为：t1=y*zt2=x+t1②三地址语句的种类 三地址语句类似于汇编代码，它可以有符号标号和各种控制流语句。常用的三地址语句有以下几种：x=yopz，其中op为二目算术或逻辑运算符。x=opy，其中op为一目运算符，如一目减uminus、逻辑否定not、移位运算符、将定点数转换成浮点数的类型转换符。2、常见的中间代码形式（6）三地址代码赋值语句：x=y无条件转移语句：gotoL条件转移语句：ifxrelopygotoL，ifagotoL过程调用语句paramX和callP,n及过程返回语句returny变址赋值语句：x=y[i]，x[i]=y地址和指针赋值语句：x=&y，x=*y，*x=y2、常见的中间代码形式（6）三地址代码③三地址代码的具体实现

编译程序中，三地址代码的具体实现通常有三种表示方法：四元式、三元式

和间接三元式。四元式 四元式是具有四个域的记录结构，即(op，arg1，arg2，result)其中，op为运算符，arg1、arg2及result为指针，它们可指向有关名字在符号表中的登记项或临时变量（也可为空）。2、常见的中间代码形式（6）三地址代码常用的三地址语句与相应四元式对应如下：

三地址语句四元式x=yopz(op,y,z,x)x=-y(uminus,y,_,x)x=y(=,y,_,x)paramx1(param,x1,_,_)callP(call,_,_,P)gotoL(j,_,_,L)ifxrelopygotoL(jrelop,x,y,L)relop为：>、>=、<、<=、!=、==2、常见的中间代码形式（6）三地址代码 例如，赋值语句a=b*(c+d)的四元式代码为： ①(+,c,d,t1) ②(*,b,t1,t2) ③(:=,t2,_,a)

约定：一个运算量的算符使用arg1。 此外，若op是一个算术或逻辑运算符，则result为新引进的临时变量，用来存放运算结果。可见，四元式出现的顺序与表达式计值的顺序一致，四元式之间的联系通过临时变量实现。2、常见的中间代码形式（6）三地址代码三元式 三元式是具有三个域的记录结构，即(op，arg1，arg2) 其中，op为运算符，arg1、arg2既可指向有关名字在符号表中的登记项或临时变量，也可指向三元式表中的某个三元式。 例如，表达式a=(b+c)*(b+c)的三元式代码为：①(+,b,c)②(+,b,c)③(*,①,②)④(:=,a,③) 由上例可知，三元式出现的先后顺序和表达式各部分的计值顺序一致。2、常见的中间代码形式（6）三地址代码间接三元式 在三元式代码表的基础上另设一张表，该表按运算的次序列出相应三元式在三元式表中的位置，这张表称为间接码表。 三元式表只记录不同的三元式，间接码表表示由这些语句组成的运算次序。 例如，表达式a=(b+c)*(b+c)的三元式表和间接码表为：三元式表： ①(+,b,c) ②(*,①,①) ③(:=,a,②)间接码表： ①①②③返回6.3简单算术表达式及赋值语句的翻译（1）文法

（2）语义 赋值语句，简单算术表达式（3）目标结构 翻译成四元式 （=,E,_，i）A表示赋值语句E表示表达式6.3简单算术表达式及赋值语句的翻译（4）语义子程序 语义子程序涉及的语义变量、语义过程及语义函数如下：①语义变量（属性）E.place：表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码。：表示存放标识符i的变量名②语义过程emit(op,arg1,arg2,result)：功能是产生一个四元式并填入四元式表中。③语义函数newtemp()：返回一个代表新临时变量的整数码，临时变量名按产生的顺序可设为T1、T2、……、。lookup()：审查是否出现在符号表中。若是，则返回在符号表的入口指针，否则返回NULL。6.3简单算术表达式及赋值语句的翻译（4）语义子程序

产生式语义子程序A→i=Ep=lookup();if(p==NULL)error();elseemit(=,E.place,_,p);E→E1+E2E.place=newtemp();emit(+,E1.place,E2.place,E.place);E→E1*E2E.place=newtemp();emit(*,E1.place,E2.place,E.place);E→−E1E.place=newtemp();emit(uminus,E1.place,_,E.place);E→（E1）E.place=E1.place;E→ip=lookup();if(p!=NULL)E.place=p;elseerror();返回6.4布尔表达式的翻译布尔表达式的翻译方法

1控制语句中布尔表达式的翻译

21、布尔表达式的翻译方法（1）布尔表达式

用布尔运算符号（and,or,not）作用到布尔变量或关系表达式上而组成的。关系表达式形如E1relopE2,其中E1，E2是算术表达式。relop为<，≤，>，≥，=，≠。布尔运算符的运算顺序从高到低为not、and、or，且or和and服从左结合规则。（2）布尔表达式的作用 ①用作计算逻辑值。 ②用作控制流语句（如if…then,if…then…else,while…do等）之中的条件表达式。（3）布尔表达式的文法描述 E→EorE|EandE|notE|(E)|idrelopid|true|false|id

relop→=|≠|>|≥|<|≤1、布尔表达式的翻译方法（4）布尔表达式的计值

①同算术表达式的计算 一步不差地从表达式各部分的值计算出整个表达式的值。 例如，用1表示true,用0表示false。1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1 ②采取某种优化措施 用if-then-else来解释or，and，not，即：AorBifAthentrueelseBAandBifAthenBelsefalsenotAifAthenfalseelsetrue1、布尔表达式的翻译方法（5）数值表示法的翻译方案①语义规则 按数值方式计算布尔表达式的值。②目标结构id1relopid2 (jrelop,id1.place,id2.place,nextstat+3);(:=,‘0’,_,E.place);(j,_,_,nextstat+2)(:=,‘1’,_,E.place) 1、布尔表达式的翻译方法（5）数值表示法的翻译方案③运算符not，and，or翻译为四元式：T:=notx(not,x,_,T)T:=xory(or,x,y,T)T:=xandy(and,x,y,T)④一个形如arelopb的关系表达式可等价的写成:ifarelopbthen1else0,并将它翻译成如下三地址语句及四元式序列：（我们假定语句序号从p开始。）三地址 四元式p：ifarelopbgotop+3 p：(jrelop,a,b,p+3)p+1：T:=0 p+1：(:=,0,_,T)p+2：gotop+4 p+2：(j,_,_,p+4)p+3：T:=1 p+3：(:=,1,_,T)p+4： p+4：

1、布尔表达式的翻译方法（5）数值表示法的翻译方案

例如，a<b的关系表达式可等价地写成:ifa<bthen1else0,并将它翻译成如下三地址语句及四元式序列：（我们假定语句序号从100开始。）

三地址 四元式100：ifa<bgoto103 100：(j<,a,b,103)101：T:=0 101：(:=,0,_,T)102：goto104 102：(j,_,_,104)103：T:=1 103：(:=,1,_,T)104： 104：

1、布尔表达式的翻译方法（6）语义子程序①相关函数和变量说明：emit函数：生成四元式，并将其插入到四元式列表中。nextstat:给出四元式序列中下一条四元式语句的地址索引，每调用一次emit函数，便把nextstat加1。

1、布尔表达式的翻译方法② 语义规则

产生式语义子程序E→E1orE2E.place:=newtemp;emit(or,E1.place,E2.place,E.place);E→E1andE2E.place:=newtemp;emit(and,E1.place,E2.place,E.place);E→notE1E.place:=newtemp;emit(not,E1.place,_,E.place);E→(E1)E.place:=E1.place;E→id1relopid2E.place:=newtemp;emit(jrelop,id1.place,id2.place,nextstat+3);emit(:=,0,_,E.place);emit(j,_,_,nextstat+2);emit(:=,1,_,E.place);E→idE.place:=id.place;E→trueE.place:=newtemp;emit(:=,1,_,E.place)E→falseE.place:=newtemp;emit(:=,0,_,E.place)1、布尔表达式的翻译方法（7）举例：将布尔表达式a<borc<dande<f翻译为四元式序列。100：(j<,a,b,103)101：(:=,0,_,T1)102：(j,_,_,104)103：(:=,1,_,T1)104：(j<,c,d,107)105：(:=,0,_,T2)106：(j,_,_,108)107：(:=,1,_,T2)108：(j<,e,f,111)109：(:=,0,_,T3)110：(j,_,_,112)111：(:=,1,_,T3)112：(and,T2,T3,T4)113：(or,T1,T4,T5)返回2、控制语句中布尔表达式的翻译（1）语义规则

按优化方式计算布尔表达式的值。（2）目标结构

P(:=,‘1’,_,T)P+1(j,_,_,P+3)P+2(:=,‘0’,_,T)P+3后继四元式2、控制语句中布尔表达式的翻译（3）翻译方案

对于出现在条件语句：ifEthenS1elseS2中的布尔表达式E，它的作用仅在于控制对S1和S2的选择。只要能完成这一使命，E的值就无需最终保留在某个临时单元中。因此，作为转移条件的布尔式E，我们可以赋予它两种“出口”。一个是“真”出口，出向S1；一个是“假”出口，出向S2。于是，上述语句可翻译成如图所示的形式。2、控制语句中布尔表达式的翻译（3）翻译方案

ifEthenS1elseS2

E.codeS1.codegotoS.nextS2.codeE.true:E.false:S.next:...........E.true:E.false:2、控制语句中布尔表达式的翻译（4）优化方式

①E1orT的优化：只要E为真，后面的表达式就不必计算，只有当E为假时才读取T，目标结构为2、控制语句中布尔表达式的翻译（4）优化方式

②E1andT的优化：只要E为假，后面的表达式就不必计算，只有当E为真时才读取T，目标结构为③notE1：E的真假出口与E1的真假出口相反。2、控制语句中布尔表达式的翻译 在这种翻译中，对于作为转移条件的布尔式，我们可以把它翻译成为一串跳转指令。 如：ifa>corb<dthenS1elseS2可以翻译为以下三地址代码：

ifa>cgotoL2gotoL1L1:ifb<dgotoL2gotoL3L2:关于S1的三地址代码序列gotoLnextL3:关于S2的三地址代码序列Lnext：2、控制语句中布尔表达式的翻译布尔量的目标结构应由两条四元式组成：(jnz,A,_,P):真出口，当A为真时跳转到四元式P，ifAgotoP(j,_,_,q):假出口，无条件跳转到四元式qgotoq关系表达式的目标结构可以写成两条四元式：(jrop,x,y,P):真出口，当xropy为真时转四元式PifxropygotoP(j,_,_,q):假出口，无条件跳转到四元式qgotoq2、控制语句中布尔表达式的翻译（5）如何确定一个表达式的真假出口呢？

考虑表达式E(1)orE(2)。若E(1)为真，则E为真，因此，E(1)的真出口就是E的真出口；若E(1)为假，则E(2)必须被计值，此时E(2)的第一个四元式就是E(1)的假出口，同时，E(2)的真假出口就是E的真假出口。 考虑E(1)andE(2)，与上类似。 对notE(1),只需调换E(1)的真假出口为E的假真出口。 E(1)orE(2)和E(1)andE(2)的翻译如下图:2、控制语句中布尔表达式的翻译（5）如何确定一个表达式的真假出口呢？

2、控制语句中布尔表达式的翻译（5）如何确定一个表达式的真假出口呢？

在自下而上分析过程中，一个布尔式的真假出口往往不能在产生四元式时填上，故把未完成四元式的地址(编号)作为E的语义值暂存，等到整个表达式的四元式产生完毕后，再填写这个未填入的转移目标。 对于每个非终结符E，需为它赋两个语义值E.truelist和E.falselist，分别用以记录E所对应的四元式需要回填“真”、“假”出口的四元式地址所构成的链。这是因为在翻译过程中常会出现若干四元式转向同一目标但目标位置又未确定的情况，此时将这些四元式链接起来，待获得目标四元式地址时再返填。2、控制语句中布尔表达式的翻译（5）如何确定一个表达式的真假出口呢？

例如，假定E的四元式需要回填“真”出口的有p、q、r这三个四元式，则它们可链接成如下图所示的一条真值链(记作truelist)。2、控制语句中布尔表达式的翻译（6）举例

对输入串a<borc<dande>f翻译成四元式，100：（j<,a,b,）101：(j,_,_,102)102：（j<,c,d,104）103：(j,_,_,)104：（j>,e,f,106）105：(j,_,_,)106：(:=,‘1’,_,T)107：(j,_,_,109)108：(:=,‘0’,_,T)109：后续四元式返回1061081086.5控制结构的翻译if语句的翻译

1while语句的翻译

2for语句的翻译

31、if语句的翻译（1）文法

S→ifEthenS1∣ifEthenS1elseS2（2）语义 条件分支转移语句。条件成立执行S1，不成立不执行任何操作或执行S2，然后继续执行if语句后面的语句。（3）目标结构TE的代码S1

的代码S2

的代码F1、if语句的翻译（4）举例

将ifa<borc<dande>fthenx=y+zelsex=y-z翻译成四元式。100：(j<,a,b,)101：(j,_,_,102)102：(j<,c,d,104)103：(j,_,_,)104：(j>,e,f,106)105：(j,_，_,)106：(+,y,z,x)107：(j,_,_,109)108：(-,y,z,x)109：(后续四元式序列)返回1081061082、while语句的翻译（1）文法

S→whileEdoS1（2）语义 当E为真，反复执行S1;否则执行while语句后面的语句。（3）目标结构TE

的代码S(1)

的代码F2、while语句的翻译（4）举例

将while(A>B)do if(C<D)thenX:=Y+Z翻译成四元式序列。100：（j>,A,B,102）101：(j,_,_,)102：(j<,C,D,104)103：(j,_,_,)104：(+,Y,Z,X)105：(j,_,_,100)106：

返回1061053、for语句的翻译（1）文法

S→fori:=E1stepE2untilE3doS1（2）语义begini:=E1gotooveragain:i:=i+E2over:ifi≤E3thenbeginS1;gotoagainendend3、for语句的翻译（3）目标结构

3、for语句的翻译（4）举例

将forI:=1step1untilNdoM:=M+I翻译成四元式

100（:=,1,_,I）101(j,_,_,103)102(+,I,1,I)103(j≤,I,N,105)104(j,_,_,)105(+,M,I,T)

106(:=,T,_,M）107(j,_,_,102)108100（:=,1,_,I）101(j,_,_,103)102(+,I,1,I)103(j>,I,N,)104(+,M,I,T)105(:=,T,_,M）106(j,_,_,102)107或返回1081076.6说明语句的翻译简单说明语句的翻译

1过程中的说明

21、简单说明语句的翻译（1）文法

简单说明语句的文法G[D]为： D→intnamelist|floatnamelist namelist→namelist,i|i（2）语义 说明源程序中的简单变量的名字及其性质。（3）翻译方法 我们可以把文法G[D]改为G'[D]：G'[D]:D→D,i∣inti∣floati这样，就能把所说明的性质及时地告诉每个名字i；或者说，每当读进一个标识符时就可以把它的性质登记到符号表中，而无须到最后再集中登记了。1、简单说明语句的翻译①语义变量和语义过程语义变量D.att：用于传递名字的性质过程entry（id,A）：把名字id和性质A登记在符号表中②翻译方案产生式语义子程序D→D1，ientry(id,D1.att);D.att=D1.att;D→intientry(id,int);D.att=int;D→floatientry(id,float);D.att=float;返回2、过程中的说明

当考察一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。对每个局部名字，我们将在符号表中建立相应的表项，并填入相应的信息如类型、在存储器中的相对地址等。（1）相关术语活动记录：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这个连续的存储块称为活动记录。相对地址：指对静态数据区基址或活动记录中局部数据区基址的一个偏移量。2、过程中的说明（2）过程中的说明语句翻译 在C、Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把它们安排在一所数据区中。从而我们需要一个全程变量如offset来跟踪下一个可用的相对地址的位置。①语义变量和语义过程enter(name,type,offset):把名字name填入到符号表中，并给出此名字的类型type及在过程数据区中的相对地址offset。T.type:综合属性，名字的类型T.width:综合属性，名字的域宽2、过程中的说明②翻译方案产生式语义子程序P→Doffset:=0;D→D;D

D→id:Tenter(,T.type,offset);offset:=offset+T.width;T→integerT.type:=integer;T.width:=4;T→realT.type:=real;T.width:=8;T→array[num]ofT1T.type:=array(num.val,T1.type);T.width:=num.val*T1.width;T→↑T1T.type:=pointer(T1.type);T.width:=4;返回6.7数组的翻译数组元素的地址计算

1赋值语句中数组元素的翻译

21、数组元素的地址计算（1）数组的存储方式

在表达式或赋值语句中若出现数组元素，则翻译时将牵涉到数组元素的地址计算。数组在存储器中的存放方式决定了数组元素的地址计算方法，从而决定了该产生什么样的中间代码。数组在存储器中的存放通常有按行和按列两种方式。下面讨论以行为主序存放方式的数组元素地址计算法。1、数组元素的地址计算（2）数组元素的地址计算①一维数组

考虑一维数组A[low1...high1]，假定数组元素的存储长度为w，base是数组A的首地址，则数组元素A[i1]的起始地址为：base+(i1-low1)*w

即i1*w+(base-low1*w)

A[i1]basei1low1high1w1、数组元素的地址计算②二维数组

同理，二维数组元素A[i1,i2]的起始地址为base+[(i1-low1)*d2+i2-low2]*w

即(i1*d2+i2)*w+[base-(low1*d2+low2)*w]A[i1,i2]basei1low1high1low2high2i2d2d11、数组元素的地址计算③一般数组

数组的一般定义为：

arrayA[l1:u1，l2:u2，……，ln:un] 其中，A是数组名，lk是数组A第k维的下界，uk是第k维的上界。为简单起见，假定数组A中每个元素的存储长度为1，a是数组A的首地址，则数组元素A[i1,i2,…,in]的地址D的计算公式如下： 其中，di=ui-li+1（i=1,2,…,n）。将上述公式整理后得到：

与ik（1≤k≤n）无关的不变量与ik（1≤k≤n）有关的可变量a-C返回2、赋值语句中数组元素的翻译（1）翻译方法

CONSTPART中的各项(如li、di(i=1,2,…,n))在处理说明语句时就可以得到，因此CONSTPART值可在编译时计算出来后保存在数组A的相关符号表项里。此后，在计算数组A的元素地址时仅需计算VARPART值而直接引用CONSTPART值。 实现数组元素的地址计算时，将产生两组四元式序列：一组计算CONSTPART，其值存放在临时变量T中；另一组计算VARPART，其值存放在临时变量T1中，即用T1[T]表示数组元素的地址。这样，对数组元素的引用和赋值就有如下两种不同的四元式：变址存数：若有T1[T]=X，则可以用四元式([]=，X，_，T1[T])表示。变址取数：若有X=T1[T]，则可用四元式(=[]，T1[T]，_，X)表示。2、赋值语句中数组元素的翻译（2）举例

已知A是一个10×20的数组(每维下界均为1)且按行存放，求：(1)赋值语句X=A[I,J]的四元式序列；(2)赋值语句A[I+2，J+1]=M+N的四元式序列。解：由于A是10×20的数组，故d1=10，d2=20，C=d2+1=21。①X=A[I,J]的四元式序列为：100(*，I，20，T1) /*d2=20*/101(+，J，T1，T1) /*得到20I+J*/102(−，A，21，T2) /*得到A−21*/103(=[ ]，T2[T1]，_，T3) /*T2[T1]即为A[I, J]，即T3=T2[1]*/104(=，T3，_，X)2、赋值语句中数组元素的翻译（2）举例

已知A是一个10×20的数组(每维下界均为1)且按行存放，求：(1)赋值语句X=A[I,J]的四元式序列；(2)赋值语句A[I+2，J+1]=M+N的四元式序列。解：由于A是10×20的数组，故d1=10，d2=20，C=d2+1=21。②X=A[I,J]的四元式序列为：100(+，I，2，T1)101(+，J，1，T2)102(*，T1，20，T3)103(+，T2，T3，T3)104(−，A，21，T4)105(+，M，N，T5)106([ ]=，T5，_，T4[T3])/*T4[T3]=T5*/返回6.8过程调用语句的翻译参数传递的方式