【教学课件】第7章语义分析与中间代码生成.ppt

《【教学课件】第7章语义分析与中间代码生成.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第7章语义分析与中间代码生成.ppt（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 语义分析与中间语义分析与中间代码生成代码生成School of Computer Science&Technology Harbin Institute of Technology重点：重点：三地址码，各种语句的目标代码结构、三地址码，各种语句的目标代码结构、语法制导定义与翻译模式。语法制导定义与翻译模式。难点：难点：布尔表达式的翻译，对各种语句的目标布尔表达式的翻译，对各种语句的目标 代码结构、语法制导定义与翻译模式的代码结构、语法制导定义与翻译模式的 理解。理解。2023/1/92第第7章章语义分析与中间代码生成语义分析与中间代码生成 7.1 中间代码的形式中间代码的形式7.2

2、 声明语句的翻译声明语句的翻译7.3 赋值语句的翻译赋值语句的翻译7.4 类型检查类型检查7.5 控制结构的翻译控制结构的翻译7.6 回填回填7.7 switch语句的翻译语句的翻译7.8 过程调用和返回语句的翻译过程调用和返回语句的翻译7.9 输入输出语句的翻译输入输出语句的翻译7.10 本章小结本章小结2023/1/937.1 中间代码的形式中间代码的形式n中间代码的作用中间代码的作用n过渡：经过语义分析被译成中间代码序列过渡：经过语义分析被译成中间代码序列n中间代码的形式中间代码的形式n中间语言的语句中间语言的语句n中间代码的优点中间代码的优点n形式简单、语义明确、独立于目标语言形式简单

3、、语义明确、独立于目标语言n便于编译系统的实现、移植、代码优化便于编译系统的实现、移植、代码优化n常用的中间代码常用的中间代码n语法树语法树(6.3.5节节)n逆波兰表示、三地址码逆波兰表示、三地址码(三元式和四元式三元式和四元式)、DAG图表示图表示2023/1/947.1.1 逆波兰表示逆波兰表示 n中缀表达式的计算顺序不是运算符出现的自中缀表达式的计算顺序不是运算符出现的自然顺序，而是根据运算符间的优先关系来确然顺序，而是根据运算符间的优先关系来确定的，因此，从中缀表达式直接生成目标代定的，因此，从中缀表达式直接生成目标代码一般比较麻烦。码一般比较麻烦。n波兰逻辑学家波兰逻辑学家J.Lu

4、kasiewicz于于1929年提出了年提出了后缀表示法，其优点为：表达式的运算顺序后缀表示法，其优点为：表达式的运算顺序就是运算符出现的顺序，它不需要使用括号就是运算符出现的顺序，它不需要使用括号来指示运算顺序。来指示运算顺序。2023/1/957.1.1 逆波兰表示逆波兰表示 n例例7.1 下面给出的是一些表达式的中缀、前缀下面给出的是一些表达式的中缀、前缀和后缀表示。和后缀表示。中缀表示中缀表示前缀表示前缀表示后缀表示后缀表示a+b+abab+a*(b+c)*a+bcabc+*(a+b)*(c+d)*+ab+cd ab+cd+*a:=a*b+c*d:=a+*ab*cd abc*bd*+:

5、=2023/1/967.1.2 三地址码三地址码 n所谓三地址码，是指这种代码的每条指令最多所谓三地址码，是指这种代码的每条指令最多只能包含三个地址，即两个操作数地址和一个只能包含三个地址，即两个操作数地址和一个结果地址。结果地址。n如如x+y*z三地址码为：三地址码为：t1:=y*z t2:=x+t1n三地址码中地址的形式：三地址码中地址的形式：n名字、常量、编译器生成的临时变量。名字、常量、编译器生成的临时变量。2023/1/977.1.2 三地址码三地址码 n例例7.2 赋值语句赋值语句a:=(-b)*(c+d)-(c+d)的三地址码的三地址码如图如图7.1所示所示 t1:=minus

6、bt2:=c+dt3:=t1*t2t4:=c+dt5:=t3-t4a:=t5图图7.1 a:=(-b)*(c+d)-(c+d)的三地址码的三地址码2023/1/987.1.2 三地址码三地址码 1形如形如x:=y op z的赋值指令；的赋值指令；2形如形如x:=op y的赋值指令；的赋值指令；3形如形如 x:=y的复制指令；的复制指令；4无条件跳转指令无条件跳转指令goto L；5形如形如 if x goto L(或或if false x goto L)的条件跳转指令；的条件跳转指令；6形如形如if x relop y goto L的条件跳转指令；的条件跳转指令；7过程调用和返回使用如下的指令

7、来实现：过程调用和返回使用如下的指令来实现：param x用来指明参数；用来指明参数；call p,n和和y=call p,n用来表示过程调用和函数调用；用来表示过程调用和函数调用；return y表示过程返回；表示过程返回；8形如形如x:=yi和和xi:=y的变址复制指令；的变址复制指令；9形如形如x:=&y、x:=*y和和*x:=y的地址和指针赋值指令。的地址和指针赋值指令。2023/1/99四元式四元式 n四元式是一种比较常用的中间代码形式，它由四个域四元式是一种比较常用的中间代码形式，它由四个域组成，分别称为组成，分别称为op、arg1、arg2和和result。op是一个是一个一元或

8、二元运算符，一元或二元运算符，arg1和和arg2分别是分别是op的两个运算的两个运算对象，它们可以是变量、常量或编译器生成的临时变对象，它们可以是变量、常量或编译器生成的临时变量，运算结果则放入量，运算结果则放入result中。中。图图7.2(a)图图7.1中三地址码的四元式表示中三地址码的四元式表示2023/1/910三元式三元式 n为了节省临时变量的开销，有时也可以使用只有三个域的三元为了节省临时变量的开销，有时也可以使用只有三个域的三元式来表示三地址码。三元式的三个域分别称为式来表示三地址码。三元式的三个域分别称为op，arg1和和arg2，op，arg1和和arg2的含义与四元式类似

9、，区别只是的含义与四元式类似，区别只是arg1和和arg2可以是某个三元式的编号可以是某个三元式的编号(图图7.2(b)中用圆括号括起来的数字中用圆括号括起来的数字)，表示用该三元式的运算结果作为运算对象。，表示用该三元式的运算结果作为运算对象。图图7.2(b)图图7.1中三地址码的三元式表示中三地址码的三元式表示2023/1/911生成三地址码的语法制导定义生成三地址码的语法制导定义2023/1/9127.1.3 图表示图表示 n类似于表达式的抽象语法树一样，在类似于表达式的抽象语法树一样，在dag(directed acyclic graph)中，每个节点对应一个运算符，代表表达式的一个子

10、表中，每个节点对应一个运算符，代表表达式的一个子表达式，其子节点则与该运算符的运算对象相对应，叶节点对应达式，其子节点则与该运算符的运算对象相对应，叶节点对应的是变量或者常量，可以看成是原子运算。的是变量或者常量，可以看成是原子运算。n利用利用dag可以很容易地消除公共子表达式可以很容易地消除公共子表达式n例例7.3 表达式表达式a+a*(b-c)-(b-c)/d的的dag如图如图7.5所示。所示。图图7.5 a+a*(b-c)-(b-c)/d的的dag图图2023/1/913生成生成dag的语法制导定义的语法制导定义产生式产生式语义规则语义规则 E E1+TE.node:=mknode(+,

11、E1.node,T.node)E E1-TE.node:=mknode(-,E1.node,T.node)E TE.node:=T.node T T1*FT.node:=mknode(*,T1.node,F.node)T T1/FT.node:=mknode(/,T1.node,F.node)T FT.node:=F.node F (E)F.node:=E.node F idF.node:=mkleaf(id,id.entry)F numF.node:=mkleaf(num,num.val)2023/1/9147.2 声明语句的翻译声明语句的翻译n声明语句的作用声明语句的作用n为程序中用到的变

12、量或常量名指定类型为程序中用到的变量或常量名指定类型 n类型的作用类型的作用 n类型检查：类型检查的任务是验证程序运行时的行为是否遵守语言的类型检查：类型检查的任务是验证程序运行时的行为是否遵守语言的类型的规定，也就是是否符合该语言关于类型的相关规则。类型的规定，也就是是否符合该语言关于类型的相关规则。n辅助翻译：编译器从名字的类型可以确定该名字在运行时所需要的存辅助翻译：编译器从名字的类型可以确定该名字在运行时所需要的存储空间。在计算数组引用的地址、加入显式的类型转换、选择正确版储空间。在计算数组引用的地址、加入显式的类型转换、选择正确版本的算术运算符以及其它一些翻译工作时同样需要用到类型信

13、息。本的算术运算符以及其它一些翻译工作时同样需要用到类型信息。n编译的任务编译的任务n在符号表中记录被说明对象的属性在符号表中记录被说明对象的属性(种别、类型、相对地址、作用域种别、类型、相对地址、作用域等等)，为执行做准备，为执行做准备2023/1/9157.2.1 类型表达式类型表达式 n类型可以具有一定的层次结构，因此用类型表达式类型可以具有一定的层次结构，因此用类型表达式来表示。类型表达式的定义如下：来表示。类型表达式的定义如下：1基本类型是类型表达式。基本类型是类型表达式。典型的基本类型包括典型的基本类型包括boolean、char、integer、real及及void等。等。2类型

14、名是类型表达式。类型名是类型表达式。3将类型构造符将类型构造符array应用于数字和类型表达式所形成的表应用于数字和类型表达式所形成的表达式是类型表达式。达式是类型表达式。如果如果T是类型表达式，那么是类型表达式，那么array(I,T)就是元素类型为就是元素类型为T、下标集为下标集为I的数组类型表达式。的数组类型表达式。4如果如果T1和和T2是类型表达式，则其笛卡尔乘积是类型表达式，则其笛卡尔乘积T1T2也是也是类型表达式。类型表达式。2023/1/9167.2.1 类型表达式类型表达式 5类型构造符类型构造符record作用于由域名和域类型所形成的作用于由域名和域类型所形成的表达式也是类型

15、表达式。记录表达式也是类型表达式。记录record是一种带有命是一种带有命名域的数据结构，可以用来构成类型表达式。例如，名域的数据结构，可以用来构成类型表达式。例如，下面是一段下面是一段Pascal程序段：程序段：ntype row=recordnaddress:integer;nlexeme:array1.15 of charnend;nvar table:array 1.10 of row;n该程序段声明了表示下列类型表达式的类型名该程序段声明了表示下列类型表达式的类型名row：nrecord(addressinteger)(lexemearray(1.15,char)2023/1/917

16、7.2.1 类型表达式类型表达式 6如果如果T是类型表达式，那么是类型表达式，那么pointer(T)也是类型表达也是类型表达式，表示式，表示“指向类型为指向类型为T的对象的指针的对象的指针”。n函数的类型可以用类型表达式函数的类型可以用类型表达式DR来表示。考虑如来表示。考虑如下的下的Pascal声明：声明：nfunction f(a,b:char):integer；n其定义域类型为其定义域类型为charchar，值域类型为，值域类型为pointer(integer)。所以函数。所以函数f的类型可以表示为如下的类型可以表示为如下的类型表达式：的类型表达式：ncharcharpointer(i

17、nteger)7类型表达式可以包含其值为类型表达式的变量。类型表达式可以包含其值为类型表达式的变量。2023/1/9187.2.2 类型等价类型等价 n许多许多类型检查的规则类型检查的规则都具有如下的形式：都具有如下的形式：nif两个类型表达式等价两个类型表达式等价then返回一种特定类型返回一种特定类型else返回返回type_error。n如果用图来表示类型表达式，当且仅当下列条件之一如果用图来表示类型表达式，当且仅当下列条件之一成立时，称两个类型成立时，称两个类型T1和和T2是是结构等价结构等价的：的：nT1和和T2是相同的基本类型；是相同的基本类型；nT1和和T2是将同一类型构造符应用

18、于结构等价的类型上形成是将同一类型构造符应用于结构等价的类型上形成的；的；nT1是表示是表示T2的类型名。的类型名。n如果将类型名看作只代表它们自己的话，则上述条件如果将类型名看作只代表它们自己的话，则上述条件中的前两个将导致类型表达式的中的前两个将导致类型表达式的名字等价名字等价n两个类型表达式名字等价当且仅当它们完全相同两个类型表达式名字等价当且仅当它们完全相同 2023/1/9197.2.3 声明语句的文法声明语句的文法 nP prog id(input,output)D;SnD D;D|List:T|proc id D;SnList List1,id|idnT integer|real

19、|array C of T1|T1|record DnC num C|nD 程序说明部分的抽象程序说明部分的抽象nS 程序体部分的抽象程序体部分的抽象nT 类型的抽象，需要表示成类型表达式类型的抽象，需要表示成类型表达式nC 数组下标的抽象数组下标的抽象2023/1/920语义属性、辅助过程与全局变量的设置语义属性、辅助过程与全局变量的设置n文法变量文法变量T(类型类型)的语义属性的语义属性ntype：类型类型(表达式表达式)nwidth：类型所占用的字节数：类型所占用的字节数n辅助子程序辅助子程序nenter：将变量的类型和地址填入符号表中：将变量的类型和地址填入符号表中narray：数组类

20、型处理子程序：数组类型处理子程序n全局变量全局变量noffset：已分配空间字节数，用于计算相对地址：已分配空间字节数，用于计算相对地址2023/1/9217.2.4 过程内声明语句的翻译过程内声明语句的翻译P offset:=0 DDD;DDid:T enter(id.name,T.type,offset);offset:=offset+T.widthTinteger T.type:=integer;T.width:=4Treal T.type:=real;T.width:=8Tarray num of T1 T.type:=array(num.val,T1.type);T.width:=n

21、um.val*T1.widthTT1 T.type:=pointer(T1.type);T.width:=4PMDM offset:=0 2023/1/922例例 x:real;i:integer 的翻译的翻译enter(x,real,0)offset=0offset=0offset=8offset=8T.type=realT.type=realT.width=8T.width=8offset=12offset=12T.type=integerT.type=integerT.width=4T.width=4enter(i,integer,8)Did:TDid:T enter(id.name,T

22、.type,offset);offset:=offset+T.widthenter(id.name,T.type,offset);offset:=offset+T.width2023/1/923例例 x:real;i:integer 的翻译的翻译Poffset:=0Doffset:=0D;Doffset:=0 x:Tenter(x,T.type,offset);offset:=offset+T.width;Doffset:=0 x:realT.type:=real;T.width:=8 enter(x,T.type,offset);offset:=offset+T.width;Dx:real(

23、x,real,0);offset:=8;Dx:real(x,real,0);offset:=8;i:T enter(id.name,T.type,offset);offset:=offset+T.widthx:real(x,real,0);offset:=8;i:integerT.type:=integer;T.width:=4enter(i,T.type,offset);offset:=offset+T.widthx:real(x,real,0);i:integer(i,integer,8);offset:=122023/1/9247.2.5 嵌套过程中声明语句的翻译嵌套过程中声明语句的翻译

24、n所讨论语言的文法所讨论语言的文法P prog id(input,output)D;S D D;D|id:T|proc id D;S n语义动作用到的函数语义动作用到的函数nmktable(previous)：创建一个新的符号表；：创建一个新的符号表；nenter(table,name,type,offset)naddwidth(table,width)：符号表的大小；：符号表的大小；nenterproc(table,name,newtable)在在table指向的符号表中为指向的符号表中为name建立一个新表项；建立一个新表项；2023/1/925P prog id(input,output

25、)M D;S addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t:=mktable(nil);push(t,tblptr);push(0,offset)D D1;D2D proc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)Did:T enter(top(tblptr),id.name,T.type,top(offset);top(offset)：=top（offs

26、et）+T.widthN t:=mktable(top(tblptr);push(t,tblptr);push(0,offset)7.2.5 嵌套过程中声明语句的翻译嵌套过程中声明语句的翻译2023/1/926program sort(input,output);var a:array0.10 of integer;x:integer;procedure readarray;var i:integer;begin aend；procedure exchange(i,j:integer);begin x:=ai;ai:=aj;aj:=x;end；procedure quicksort(m,n:i

27、nteger);var k,v:integer;function partition(y,z:integer):integer;var i,j:integer;begin a v exchange(i,j)end;begin end；begin end；例例 一个带有嵌套的一个带有嵌套的pascal程序程序(图图7.11)2023/1/927表表 头头空空sortoffsettblptrtoptop02023/1/928表表 头头空空sortoffsettblptrtoptop 40a array 02023/1/929x integer 40a array 0表表 头头空空sortoffse

28、ttblptrtoptop442023/1/930表表 头头空空sortreadarrary表表 头头offsettblptrtoptop440a array 0 x integer 402023/1/931表表 头头空空sortreadarrary表表 头头 offsettblptrtoptop444a array 0 x integer 40i integer 02023/1/932表表 头头空空sortreadarrary表表 头头 4 offsettblptrtoptop44a array 0 x integer 40i integer 0readarray指向指向readarray2

29、023/1/933表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头toptop02023/1/934表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange2023/1/935表表 头头空空sortrea

30、darrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicksort02023/1/936表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicks

31、ort4k integer 02023/1/937表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicksort8k integer 0v integer 42023/1/938表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向

32、readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicksort8k integer 0v integer 4表表 头头partition02023/1/939表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicksort8k integer 0v integer 4表表 头头partiti

33、on4i integer 02023/1/940表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicksort8k integer 0v integer 4表表 头头partition8i integer 0j integer 42023/1/941表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0

34、x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头quicksort8k integer 0v integer 4表表 头头 8partitioni integer 0j integer 4partition2023/1/942表表 头头空空sortreadarrary表表 头头 4 offsettblptr44a array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptope

35、xchange指向指向exchange表表 头头 8quicksortk integer 0v integer 4表表 头头 8partitioni integer 0j integer 4partitionquicksort2023/1/943表表 头头 44空空sortreadarrary表表 头头 4 offsettblptra array 0 x integer 40i integer 0readarray指向指向readarrayexchange表表 头头 0toptopexchange指向指向exchange表表 头头 8quicksortk integer 0v integer

36、4表表 头头 8partitioni integer 0j integer 4partitionquicksort2023/1/9447.2.6 记录的翻译记录的翻译n空间分配空间分配n设置首地址和各元素的相对地址设置首地址和各元素的相对地址n大于所需的空间大于所需的空间(对齐对齐)n例：例：struct Node float x,y;struct node*next;node;0482023/1/9457.2.6 记录的翻译记录的翻译n符号表及有关表格处理符号表及有关表格处理n为每个记录类型单独构造一张符号表为每个记录类型单独构造一张符号表n将域名将域名id的信息的信息(名字、类型、字节数名

37、字、类型、字节数)填入到该填入到该记录的符号表中记录的符号表中n所有域都处理完后，所有域都处理完后，offset将保存记录中所有数将保存记录中所有数据对象的宽度总和据对象的宽度总和nT.type通过将类型构造器通过将类型构造器record应用于指向该记应用于指向该记录符号表的指针获得录符号表的指针获得2023/1/9467.2.6 记录的翻译记录的翻译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

38、(t,tblprt);push(0,offset)2023/1/9477.3 赋值语句的翻译赋值语句的翻译翻译的需求翻译的需求n充分了解各种语言现象的语义充分了解各种语言现象的语义n包括：控制结构、数据结构、单词包括：控制结构、数据结构、单词n充分了解它们的实现方法充分了解它们的实现方法n目标语言的语义目标语言的语义n了解中间代码的语义了解中间代码的语义n了解运行环境了解运行环境2023/1/948辅助子程序与语义属性设置辅助子程序与语义属性设置n辅助子程序辅助子程序ngencode(code)，emit(code)：产生一条中间代码：产生一条中间代码nnewtemp：产生新的临时变量：产生新

39、的临时变量nlookup：检查符号表中是否出现某名字：检查符号表中是否出现某名字n语义属性设置语义属性设置n中间代码序列：中间代码序列：coden地址：地址：addrn下一条四元式序号：下一条四元式序号：nextquad2023/1/9497.3.1 简单赋值语句的翻译简单赋值语句的翻译S id:=E p:=lookup(id.name);if p nil thengencode(p,:=,E.addr)else error E E1+E2E.addr:=newtemp;emit(E.addr,:=,E1.addr,+,E2.addr)E E1 E.addr:=newtemp;emit(E.a

40、ddr,:=,uminus,E1.addr)E (E1)E.addr:=E1.addr E id p:=lookup(id.name);if p nil then E.addr:=p else error 2023/1/950临时名字的重用临时名字的重用n大量临时变量的使用对优化有利大量临时变量的使用对优化有利n大量临时变量会增加符号表管理的负担大量临时变量会增加符号表管理的负担n也会增加运行时临时数据占的空间也会增加运行时临时数据占的空间E E1+E2的动作产生的代码的一般形式为的动作产生的代码的一般形式为计算计算E1到到t1计算计算E2到到t2t3:=t1+t2()()()()临时变量的生

41、存期像配对括号那样嵌套或并列临时变量的生存期像配对括号那样嵌套或并列2023/1/951基于临时变量生存期特征的三地址代码基于临时变量生存期特征的三地址代码x:=a b+c d e f语语 句句 计数器计数器c的值的值 0$0:=a b 1$1:=c d 2$0:=$0+$1 1$1:=e f 2$0:=$0$1 1 x:=$0 0引入一个计数引入一个计数器器c，它的初，它的初值为值为0。每当。每当临时变量仅作临时变量仅作为运算对象使为运算对象使用时，用时，c减去减去1；每当要求产；每当要求产生新的临时名生新的临时名字时，使用字时，使用$c并把并把c增加增加1。2023/1/9527.3.2

42、数组元素的寻址数组元素的寻址n数组元素引用的翻译数组元素引用的翻译n完成上下界检查完成上下界检查n生成完成相对地址计算的代码生成完成相对地址计算的代码n目标目标nx:=yi 和和 yi:=xny为数组地址的固定部分为数组地址的固定部分相当于第相当于第1个元素个元素的地址，的地址，i是相对地址，不是数组下标是相对地址，不是数组下标数组说明的翻译数组说明的翻译符号表及有关表格符号表及有关表格(内情内情向量向量)的处理的处理维数、下标上界、下标下维数、下标上界、下标下界、类型等界、类型等首地址、需用空间计算首地址、需用空间计算按行存放、按列存放按行存放、按列存放影响具体元素地址的计算影响具体元素地址

43、的计算2023/1/953数组元素地址计算数组元素地址计算行优先行优先n一维数组一维数组Alow1:up1 (nk=upk-lowk+1)addr(Ai)=base+(i-low1)*w=(base-low1*w)+i*w=c+i*wn二维数组二维数组Alow1:up1,low2:up2；Ai1,i2addr(Ai1,i2)=base+(i1-low1)*n2+(i2-low2)*w=base+(i1-low1)*n2*w+(i2-low2)*w=base-low1*n2*w-low2*w+i1*n2*w+i2*w=base-(low1*n2-low2)*w+(i1*n2+i2)*w=c+(i

44、1*n2+i2)*wA1,1,A1,2,A1,3 A2,1,A2,2,A2,32023/1/954数组元素地址计算的翻译方案设计数组元素地址计算的翻译方案设计下标变量访问的产生式下标变量访问的产生式L idElist|idElist Elist,E|E为了使数组各维的长度为了使数组各维的长度n在我们将下标表达式合在我们将下标表达式合并到并到Elist时是可用的，需将产生式改写为：时是可用的，需将产生式改写为：L Elist|idElist Elist,E|idE2023/1/955数组元素地址计算的翻译方案设计数组元素地址计算的翻译方案设计 L Elist|id Elist Elist,E|i

45、dEn目的目的n使我们在整个下标表达式列表使我们在整个下标表达式列表Elist的翻译过程中随的翻译过程中随时都能知道符号表中相应于数组名时都能知道符号表中相应于数组名id的表项，从而的表项，从而能够了解登记在符号表中的有关数组能够了解登记在符号表中的有关数组id的全部信息。的全部信息。n于是我们就可以为非终结符于是我们就可以为非终结符Elist引进一个综合属性引进一个综合属性Elist.array，用来记录指向符号表中相应数组名字，用来记录指向符号表中相应数组名字表项的指针。表项的指针。2023/1/956数组元素地址计算的翻译方案设计数组元素地址计算的翻译方案设计n属性属性nElist.ar

46、ray，用来记录指向符号表中相应数组名字，用来记录指向符号表中相应数组名字表项的指针。表项的指针。nElist.ndim，用来记录，用来记录Elist中下标表达式的个数，即中下标表达式的个数，即数组的维数。数组的维数。nElist.addr，用来临时存放，用来临时存放Elist的下标表达式计算出的下标表达式计算出来的值。来的值。n函数函数nlimit(array,j)，返回，返回nj2023/1/9577.3.3 带有数组引用的赋值语句的翻译带有数组引用的赋值语句的翻译S Left:=EE E+EE (E)E LeftLeft ElistLeft idElist Elist,EElist id

47、E2023/1/958赋值语句的翻译模式赋值语句的翻译模式Leftid Left.addr:=id.addr;Left.offset:=null ElistidE Elist.addr:=E.addr;Elist.ndim:=1;Elist.array:=id.addr ElistElist1,E t:=newtemp;m:=Elist1.ndim+1;gencode(t,:=,Elist1.addr,limit(Elist1.array,m);gencode(t,:=,t,+,E.addr);Elist.array:=Elist1.array;Elist.addr:=t;Elist.ndim

48、:=mLeft Elist Left.addr:=newtemp;Left.offset:=newtemp;gencode(Left.addr,:=,base(Elist.array),invariant(Elist.array);gencode(Left.offset,:=,Elist.addr,w)i1*n2(i1*n2)+i2(i1*n2)+i2)*wbase-(low1*n2-low2)*w2023/1/959赋值语句的翻译模式赋值语句的翻译模式E Left if Left.offset=null then/Left是是简简单单变变量量 /E.addr:=Left.addr else

49、begin E.addr:=newtemp;gencode(E.addr,:=,Left.addr,Left.offset,)endE E1+E2 E.addr:=newtemp;gencode(E.addr,:=,E1.place,+,E2.addr)E (E1)E.addr:=E1.addr S Left:=E if Left.offset=null then/Left是简单变量是简单变量/gencode(Left.addr,:=,E.addr)else gencode(Left.addr,Left.offset,:=,E.addr)(i1*n2)+i2)*w+(base-(low1*n2

50、-low2)*w)(i1*n2)+i2)*w+(base-(low1*n2-low2)*w)2023/1/960例：设例：设A是一个是一个1020的整型数组的整型数组 w=4 S:=Left.place:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=