[高等教育]第七章语义分析和中间代码生成.pdf

《[高等教育]第七章语义分析和中间代码生成.pdf》由会员分享，可在线阅读，更多相关《[高等教育]第七章语义分析和中间代码生成.pdf（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、*第七章第七章语义分析和中间代码生成语义分析和中间代码生成知识结构：知识结构：语义分析语义分析语法分析概述语法分析概述语法制导翻译语法制导翻译逆波兰式表示逆波兰式表示三元式表示三元式表示语义分析和中语义分析和中中间语言中间语言图型表示图型表示间代码生成四元式表示间代码生成四元式表示三地址语句表示三地址语句表示赋值语句的翻译赋值语句的翻译布尔表达式的翻译布尔表达式的翻译中间代码生成中间代码生成控制语句的翻译控制语句的翻译说明语句的翻译说明语句的翻译过程语句的翻译过程语句的翻译第一节第一节语法制导翻译概述语法制导翻译概述一、语义分析的任务一、语义分析的任务在词法分析和语法分析的基础上进一步分析其含

2、义，主要在词法分析和语法分析的基础上进一步分析其含义，主要的工作是进行静态语义检查和翻译。的工作是进行静态语义检查和翻译。二、语义分析的功能语义分析的功能1 1、类型检查、类型检查检查运算的合法性（运算对象的一致性）检查运算的合法性（运算对象的一致性）。/筱*2 2、一致性检查、一致性检查一个对象（标识符等）在一个分程序中只能被定义一次。一个对象（标识符等）在一个分程序中只能被定义一次。3 3、相关名字检查、相关名字检查如果一个名字必须出现多次，如果一个名字必须出现多次，检查使用的名字是否相同的。检查使用的名字是否相同的。4 4、控制流检查、控制流检查控制流语句必须使控制转移到合法的地方。控制

3、流语句必须使控制转移到合法的地方。5 5、确定类型、确定类型确定标识符所关联得数据类型。确定标识符所关联得数据类型。6 6、识别含义、识别含义确认程序中各种成分组合到一起的含义，并作相应的语义确认程序中各种成分组合到一起的含义，并作相应的语义处理，对可执行的语句生成中间语言或目标语言。处理，对可执行的语句生成中间语言或目标语言。三、生成的语言三、生成的语言1 1、直接生成目标语言、直接生成目标语言根据源程序中各语法成分的语义，直接生成机器语言或汇根据源程序中各语法成分的语义，直接生成机器语言或汇编语言。其特点：编语言。其特点：编译时间较短；编译时间较短；存储空间较大；存储空间较大；目标语言的质

4、量较差。目标语言的质量较差。2 2、生成中间语言、生成中间语言介于源程序语言和机器语言之间的机内表示形式。介于源程序语言和机器语言之间的机内表示形式。其特点：其特点：编译程序的逻辑结构简单；编译程序的逻辑结构简单；有利于编译程序的移植；有利于编译程序的移植；/筱*便于目标语言的优化。便于目标语言的优化。四、语义分析方法四、语义分析方法1 1、语法制导翻译方法、语法制导翻译方法在语法分析过程中，使用语法规则进行归约的同时，根据在语法分析过程中，使用语法规则进行归约的同时，根据每个产生式的语义动作进行翻译（在语法规则的制导下，通过每个产生式的语义动作进行翻译（在语法规则的制导下，通过对语义规则的计

5、算，完成对输入字符串的翻译）的方法。对语义规则的计算，完成对输入字符串的翻译）的方法。2 2、属性翻译方法、属性翻译方法指明语义规则的计算次序，陈述一些实现细节，以表达语指明语义规则的计算次序，陈述一些实现细节，以表达语义动作在语法分析过程中的执行时刻。义动作在语法分析过程中的执行时刻。五、语义规则五、语义规则为文法中的每一条产生式配置计算属性的计算规则。为文法中的每一条产生式配置计算属性的计算规则。六、语法制导翻译六、语法制导翻译为文法中每个产生式配备一组语义规则。为文法中每个产生式配备一组语义规则。1 1、语义规则、语义规则语义规则计算包括：产生代码、在符号表中存放信息、在语义规则计算包括

6、：产生代码、在符号表中存放信息、在分析工作栈中填写语义值（属性值）分析工作栈中填写语义值（属性值）,并生成相应的中间代码。并生成相应的中间代码。2 2、自上而下分析、自上而下分析用一条产生式与输入符号匹配成功时用一条产生式与输入符号匹配成功时,执行相应语义子程执行相应语义子程序生成中间代码。序生成中间代码。3 3、自下而上分析、自下而上分析用一条产生式进行的归约时用一条产生式进行的归约时,执行相应语义子程序生成中执行相应语义子程序生成中间代码。间代码。/筱*七、翻译简例七、翻译简例表达式文法和相应的翻译模式：表达式文法和相应的翻译模式：（P179P179）S Sid:=Eid:=E p:=Lo

7、okup(id.name);p:=Lookup(id.name);if p if p nil thennil thenemit(pemit(p:=:=E.place)E.place)else errorelse errorE.placeE.place 为属性值为属性值(语义变量语义变量)，代表存放，代表存放 E E 值的变量名在值的变量名在符号表的入口地址或指向代表符号表的入口地址或指向代表 E E 值的临时变量的整数值。值的临时变量的整数值。E EE E1 1+E+E2 2 E.place:=newtemp;E.place:=newtemp;emit(E.placeemit(E.place:

8、=:=E E1 1.place.place+E E2 2.place).place)语法分析工作栈进行扩充语法分析工作栈进行扩充,增加相应的语义值，增加相应的语义值，语法分析同语法分析同时时(如归约时如归约时)，执行语义规则，执行语义规则(语义子程序语义子程序)。例：例：x:=y+zx:=y+z 的语法制导翻译的语法制导翻译用用 E EE E1 1+E+E2 2归约归约执行语义规则执行语义规则E2 E2.place E.place:=T1;+-归约后归约后 E E.placeemit(T1:=y+z)E1E1.place 符号符号 语义值语义值生成一条中间代码生成一条中间代码符号符号 语义值语

9、义值用用 S Sid:=Eid:=E 归约归约执行语义规则执行语义规则E E.place p:=Lookup(x);:=-归约后归约后 s E.placeemit(x:=T1)id id.place符号符号 语义值语义值生成一条中间代码。生成一条中间代码。/筱*符号符号语义值语义值这样语法分析结束时也就生成了中间代码：这样语法分析结束时也就生成了中间代码：（0 0）T T1 1:=y+z:=y+z（1 1）x:=T x:=T1 1注意：注意：语义工作栈中的值与状态工作栈中的值一一对应，某些符语义工作栈中的值与状态工作栈中的值一一对应，某些符号可能无相应的语义值，如上例“号可能无相应的语义值，如

10、上例“+”，保留语义栈位是用“”，保留语义栈位是用“”表示。表示。归约时符号和语义值同时退出工作栈，归约时符号和语义值同时退出工作栈，同时进入工作栈。同时进入工作栈。例例 A A XYZXYZZ Z.zZ Z.z Y Y.y Y Y.y归约后归约后A A.aA A.aX X.xX X.x 符号符号 语义值语义值符号符号 语义值语义值八、语义值（属性）和语义规则（语义子程序）八、语义值（属性）和语义规则（语义子程序）1 1、语义值、语义值代表文法符号的类型、值、符号表地址等语义子程序需要代表文法符号的类型、值、符号表地址等语义子程序需要的信息。如的信息。如 E.place E.place（符号表

11、指针）（符号表指针）。2 2、语义规则、语义规则对语义值（属性）进行计算，或其它加工处理过程。对语义值（属性）进行计算，或其它加工处理过程。属性文法翻译属性文法翻译使用语义规则进行属性值的计算。使用语义规则进行属性值的计算。语法制导翻译语法制导翻译给出使用语义规则进行计算的顺序（用给出使用语义规则进行计算的顺序（用 括号起来）括号起来）。九、理解语法制导翻译的若干关键问题九、理解语法制导翻译的若干关键问题/筱*1 1、语义值（属性）代表的含义、语义值（属性）代表的含义2 2、语义子程序（语义规则）、语义子程序（语义规则）3 3、语法制导翻译过程、语法制导翻译过程翻译的顺序与语义子程序执行的顺序

12、相关；翻译的顺序与语义子程序执行的顺序相关；子程序执行的顺序与应用产生式进行归约的顺序相关；子程序执行的顺序与应用产生式进行归约的顺序相关；归约的顺序与中间代码的顺序相关；归约的顺序与中间代码的顺序相关；第二节中间语言第二节中间语言一、中间语言的表示形式一、中间语言的表示形式1 1、后缀式（逆波兰表示）、后缀式（逆波兰表示）（P167P167 定义）定义）2 2、图表示法（、图表示法（DAGDAG 无环路有向图，抽象语法树）无环路有向图，抽象语法树）3 3、三地址代码、三地址代码三地址语句三地址语句四元式四元式三元式三元式间接三元式间接三元式二、后缀式（逆波兰表示）二、后缀式（逆波兰表示）1

13、1、表达式表示形式、表达式表示形式中缀形式中缀形式二目运算的运算符总是置于两个运算对象之间。二目运算的运算符总是置于两个运算对象之间。例：例：a*a*（b+cb+c）后缀形式后缀形式把运算符置于运算对象之后，将中缀式中的算符，按优先把运算符置于运算对象之后，将中缀式中的算符，按优先/筱*级或结合律重新排序。级或结合律重新排序。后缀形式表达式后缀形式表达式 E E 的定义的定义如果如果 E E 是一个变量或常量，则是一个变量或常量，则 E E 的后缀形式是的后缀形式是 E E 自身。自身。如果如果 E E 是是 E E1 1OPOP E E2 2形式的表达式，这里的形式的表达式，这里的 OPOP

14、 是任何二元是任何二元操作符，则操作符，则 E E 的后缀形式是的后缀形式是 E E1 1 E E2 2 OP OP，这里，这里 E E1 1 和和 E E2 2 分别为分别为 E E1 1和和 E E2 2的后缀形式。的后缀形式。如果如果 E E 是（是（E E1 1）形式的表达式，则）形式的表达式，则E E1 1 的后缀形式就是的后缀形式就是 E E的后缀形式。的后缀形式。例：中缀形式：例：中缀形式：a*a*（b+cb+c），而后缀形式：，而后缀形式：abc+*abc+*2 2、中缀形式转换后缀形式的算法、中缀形式转换后缀形式的算法建立两个工作栈，存放运算对象和经处理后的运算符（逆建立两个

15、工作栈，存放运算对象和经处理后的运算符（逆波兰区）波兰区）；另一个存放运算符，首先将“；另一个存放运算符，首先将“#”压入工作栈顶。”压入工作栈顶。若输入的符号是运算对象，送入波兰区。若输入的符号是运算对象，送入波兰区。若输入的符号是运算符，若输入的符号是运算符，送入运算符工作栈，送入运算符工作栈，操作过程：操作过程：工作栈顶运算符的优先级高于当前输入的运算符，将工工作栈顶运算符的优先级高于当前输入的运算符，将工作栈顶运算符弹出，送入逆波兰区，并把当前输入的运算符压作栈顶运算符弹出，送入逆波兰区，并把当前输入的运算符压入运算符工作栈；入运算符工作栈；工作栈顶运算符的优先级低于当前输入的运算符，

16、将当工作栈顶运算符的优先级低于当前输入的运算符，将当前输入的运算符压入运算符工作栈；前输入的运算符压入运算符工作栈；若当前输入的符号是“若当前输入的符号是“#”，将运算符工作栈的符号依次，将运算符工作栈的符号依次弹出，送入逆波兰区。弹出，送入逆波兰区。3 3、转换的语义规则、转换的语义规则/筱*属性定义（语义变量）属性定义（语义变量）E Ecodecode：表示：表示E E 的后缀式，定义了识别的标识符（指针）的后缀式，定义了识别的标识符（指针）。OPOP 表示任意的二元操作符。表示任意的二元操作符。“”表示后缀形式的连接。“”表示后缀形式的连接。语义规则的描述（语义规则的描述（P167P16

17、7）对同一产生式重复出现的文法符号用角标进行区分。对同一产生式重复出现的文法符号用角标进行区分。例例 a+b*a+b*（c+d*bc+d*b）+d+d 4 3 2 1 5 4 3 2 1 5后缀式：后缀式：abcdb*+*+d+abcdb*+*+d+产生式产生式语义动作语义动作 E Eid E.codeid E.code idid E EE E1 1OP EOP E2 2 E.code E.code E1.codeE1.codeE2.codeE2.codeopop三、图表示法三、图表示法1 1、抽象语法树、抽象语法树语法树可以作为一种合适的中间语言形式。在语法树中去语法树可以作为一种合适的中间

18、语言形式。在语法树中去掉那些对翻译无效的信息，掉那些对翻译无效的信息，从而获得更有效的源程序中间表示。从而获得更有效的源程序中间表示。这种变换后的语法树为抽象语法树。这种变换后的语法树为抽象语法树。抽象语法树的表示形式：抽象语法树的表示形式：操作符和关键字作为内部结点。操作符和关键字作为内部结点。运算对象作为叶子结点。运算对象作为叶子结点。例：例：3 35 54 4 的抽象语法树的抽象语法树/筱*4 4 3 5 3 52 2、DAGDAG 图（无环路有向图）图（无环路有向图）与抽象语法树一样，对表达式的每个子表达式，与抽象语法树一样，对表达式的每个子表达式，DAGDAG 都有都有一个结点。一个

19、结点。DAGDAG 图的结构：图的结构：内部结点为运算符。内部结点为运算符。子结点为操作对象。子结点为操作对象。3 3、DAGDAG 与抽象语法树的区别（与抽象语法树的区别（P168P168）DAGDAG 图的公共子表达式的结点具有多个父结点。图的公共子表达式的结点具有多个父结点。抽象语法树的公共子表达式对应重复子树。抽象语法树的公共子表达式对应重复子树。四、三地址代码四、三地址代码1 1、三地址代码一般形式、三地址代码一般形式X :=Yop ZX :=Yop Z结果结果操作数操作数操作符操作符 操作数操作数例：例：X+Y*ZX+Y*Z中间代码为：中间代码为：T T1 1:=Y*Z:=Y*ZT

20、 T2 2:=X+T:=X+T1 1 T T1 1,T,T2 2为临时变量（由编译生成）为临时变量（由编译生成）2 2、三地址语句的种类、三地址语句的种类(P170)(P170)：二目运算的赋值语句二目运算的赋值语句 x:=yopzx:=yopz。单目运算的赋值语句单目运算的赋值语句 x:=opyx:=opy。复制语句复制语句 x:=yx:=y。/筱*无条件转移语句无条件转移语句 goto Lgoto L（中间代码地址）（中间代码地址）。条件转移语句条件转移语句 ifx relopy gotoLifx relopy gotoL 或或 ifa goto Lifa goto L。调用语句调用语句

21、param xparam x 和和 call p,ncall p,n，返回语句，返回语句 return yreturn y。索引赋值索引赋值 x:=yix:=yi和和 xi:=yxi:=y（数组元素）（数组元素）。地址和指针赋值地址和指针赋值 x:=&yx:=&y，x:=*yx:=*y 和和*x:=y*x:=y。3 3、三地址代码的几种表示、三地址代码的几种表示四元式四元式（opop，arg1arg1，arg2arg2，resultresult）例：例：x:=yopzx:=yopz 的四元式的四元式(op(op，y y，z z，x)x)例：例：a:=b*-c+b*-ca:=b*-c+b*-c(

22、，c c，_ _，T T1 1)(*(*，b b，T T1 1，T T2 2)(，c c，_ _，T T3 3)(*(*，b b，T T3 3，T T4 4)(+(+，T T2 2，T T4 4，T T5 5)(:=(:=，T T5 5，_ _，a)a)三元式三元式为了避免把临时变量填入符号表，为了避免把临时变量填入符号表，用中间代码地址用中间代码地址（指针）（指针）代表运算对象。代表运算对象。（opop，arg1arg1，arg2arg2）例：例：a:=b*-c+b*-ca:=b*-c+b*-c(0)(0)(，c c，_)_)(1)(*(1)(*，b b，(0)(0)(2)(2)(，c c，

23、_)_)(3)(*(3)(*，b b，(2)(2)(4)(+(4)(+，(1)(1)，(3)(3)/筱*(5)(:=(5)(:=，a a，(4)(4)例：例：xi:=yxi:=y(0)(=(0)(=，x x，i)i)(1)(:=(1)(:=，y,y,（0 0）)用两条三元式表示索引赋值。用两条三元式表示索引赋值。例：例：x:=yix:=yi(0)(=(0)(=，y y，i)i)(1)(:=(1)(:=，x x，(0)(0)(3)(3)间接三元式间接三元式(P173)(P173)为了便于代码优化处理，不直接使用三元式的指针，而是为了便于代码优化处理，不直接使用三元式的指针，而是另设一张间接代码表

24、，按先后顺序列出三元式在三元式代码表另设一张间接代码表，按先后顺序列出三元式在三元式代码表中的位置。中的位置。例：例：x:=(A+B)*cx:=(A+B)*cy:=Dy:=D(A+B)(A+B)三元式代码表三元式代码表间接代码表间接代码表OP ARG1 ARG2 (1)OP ARG1 ARG2 (1)(1)+A B (2)(1)+A B (2)(2)*(1)C (3)(2)*(1)C (3)(3)(3)X (2)(1)X (2)(1)(4)(4)D (1)(4)D (1)(4)(5)(5)Y (1)(5)Y (1)(5)比较几种形式的三地址代码比较几种形式的三地址代码a:=b*-c+b*-ca

25、:=b*-c+b*-c三地址码三地址码四元式四元式三元式三元式间接三元式间接三元式/筱*T T1 1:=-c:=-c(,c,-,T,c,-,T1 1)(,c,-)(,c,-)T T2 2:=b*T:=b*T1 1(*,b,T(*,b,T1 1,T,T2 2)(*,b,(0)(*,b,(0)T T3 3:=-c:=-c(,c,-,T,c,-,T3 3)(,c,-)(,c,-)T T4 4:=b*T:=b*T3 3(*,b,T(*,b,T3 3,T,T4 4)(*,b,(*,b,)(+,T(+,T2 2,T,T4 4,T,T5 5)(+,(+,)T T5 5:=T:=T2 2+T+T4 4(0)(

26、0)(1)(1)(2)(2)(3)(3)(4)(4)(,c,-)(,c,-)(0)(0)(*,b,(0)(*,b,(0)(1)(1)(+,(+,)(0)(0)(：=，a,a,)(1)(1)(2)(2)(3)(3)A:=T A:=T5 5(:=,T(:=,T5 5,-,a),-,a)(：=，a,a,)(5)(5)第三节第三节赋值语句的翻译赋值语句的翻译一、简单算术表达式及赋值语句一、简单算术表达式及赋值语句1 1、语义函数（子程序）、语义函数（子程序）P178P178Lookup(id.name)Lookup(id.name)：查找：查找 id.nameid.name 在符号表中的入口地址。在符

27、号表中的入口地址。emit()emit()：生成三地址语句（中间代码）发送到输出文件：生成三地址语句（中间代码）发送到输出文件中。中。例：例：emit(Xemit(X:=:=uminusuminusT)T)产生中间代码。产生中间代码。newtempnewtemp：产生一个新临时变量名的整数码。产生一个新临时变量名的整数码。如如 T T1 1，T T2 2，T T3 3。2 2、语义变量（属性）、语义变量（属性）E.placeE.place：代表存放：代表存放 E E 值在符号表的入口地址或临时变量。值在符号表的入口地址或临时变量。id.name id.name：以存在的变量名。：以存在的变量名

28、。赋值语句的翻译模式（赋值语句的翻译模式（P179P179）S Sid:=Eid:=E p:=Lookup(id.name);p:=Lookup(id.name);if pif p nil thenemit(pnil thenemit(p:=:=E.place)E.place)else errorelse errorE EE E1 1+E+E2 2 E.place:=newtemp;E.place:=newtemp;emit(E.placeemit(E.place:=:=E E1 1.place.place+E E2 2.place).place)E EE E1 1*E*E2 2E.place

29、:=newtemp;E.place:=newtemp;emit(E.placeemit(E.place:=:=E E1 1.place.place*E E2 2.place).place)/筱*E E-E-E1 1E.place:=newtemp;E.place:=newtemp;emit(E.placeemit(E.place:=:=uminusuminusE E1 1.place).place)E E(E(E1 1)E.place:=E E.place:=E1 1.place.placeE Eidid p:=lookup(id.name)p:=lookup(id.name)if pif p

30、 nil then E.place:=pnil then E.place:=pElse errorElse error例：例：X:=-B*(C+D)X:=-B*(C+D)的语法制导翻译过程的语法制导翻译过程输入栈PlaceX:=-B*(C+D)X_:=-B*(C+D)X:=_ _-B*(C+D)X:=-_ _ _B*(C+D)X:=-B_ _ _ _*(C+D)X:=-E_ _ _ B*(C+D)X:=E_ _ T1*(C+D)X:=E*_ _ T1_(C+D)X:=E*(_ _ T1_ _C+D)X:=E*(C_ _ T1_ _ _+D)X:=E*(E_ _ T1_ _C+D)X:=E*(E

31、+_ _ T1_ _C_D)X:=E*(E+D_ _ T1_ _ C _ _)X:=E*(E+E_ _T1 _ _ C _ D)X:=E*(E_ _ T1_ _T2)X:=E*(E)_ _ T1_ _ T2_X:=E*E_ _T1 _T2X:=E_ _ T3产生式三地址代码EidE-E1T1:=uminus BEidEidEE1+E2T2:=C+DE(E)EE1*E2T3:=T1*T2Sid:=EX:=T3二、不同类型运算的翻译（二、不同类型运算的翻译（P184P184）对不同类型运算，生成代码时首先进行类型转换。对不同类型运算，生成代码时首先进行类型转换。例：例：x:=y+i*jx:=y+i

32、*j其中其中 x,yx,y 为实型，为实型，i,j i,j 为整型；为整型；产生三地址代码为：产生三地址代码为：T T1 1:=iint*j:=iint*jT T2 2:=inttoreal T:=inttoreal T1 1T T3 3:=yreal+T:=yreal+T2 2X:=TX:=T3 3增加一个语义值（属性）类型属性增加一个语义值（属性）类型属性 E.type E.type 语义栈扩充语义栈扩充/筱*state place type state place typeE EE E1 1+E+E2 2的语义规则（的语义规则（P184P184）E.place:=newtemp;E.pl

33、ace:=newtemp;if Eif E1.1.type=integer and Etype=integer and E2.2.type=integertype=integerthen beginthen beginemit(E.place:emit(E.place:=EE1 1.place.placeint+int+EE2 2.place).place)E.type=integerE.type=integerendendelse if Eelse if E1.1.type=real and Etype=real and E2.2.type=realtype=realthen beginth

34、en beginemit(E.place:emit(E.place:=EE1 1.place.placereal+real+EE2 2.place).place)E E.type=realtype=realendendelse if Eelse if E1.1.type=integer and Etype=integer and E2.2.type=realtype=realthen beginthen beginu:=newtemp;u:=newtemp;emit(uemit(u:=int to realint to realEE1 1.place).place)emit(E.place:e

35、mit(E.place:=u urealreal+E+E2 2.place).place)E.type=realE.type=realendendelse if Eelse if E1.1.type=real and Etype=real and E2.2.type=integertype=integerthen beginthen beginu:=newtemp;u:=newtemp;emit(uemit(u:=inttorealinttorealEE2 2.place).place)emit(E.place:emit(E.place:=EE1 1.place.placerealreal+u

36、)u)E.type=realE.type=realendendelse Eelse E.type:=type_error type:=type_error 三、数组元素的引用三、数组元素的引用1 1、编译对变量、数组元素的处理、编译对变量、数组元素的处理为某过程的名字（变量、数组元素）分配空间，在中间代码为某过程的名字（变量、数组元素）分配空间，在中间代码中操作数用相对地址表示。中操作数用相对地址表示。2 2、符号表（实数域宽、符号表（实数域宽 8 8 字节字节,整数域宽整数域宽 4 4 字节）字节）某一过程有变量某一过程有变量 X,Y,i,jX,Y,i,j名字名字类型类型相对地址相对地址内存

37、的分布内存的分布0 0X RealX Real0 0X X8 8 字节字节/筱*1 1Y RealY Real2 2I IIntInt3 3J JIntInt8 8Y Y8 8 字节字节1616i i4 4 字节字节2020j j4 4 字节字节3 3、操作数在中间代码中表示：、操作数在中间代码中表示：如如 i i 的的 E.placeE.place 为为 2 2（符号表的指针（符号表的指针 2 2）;书面表达用名字书面表达用名字 i i（直观）（直观）;存储分配后相对地址存储分配后相对地址 16;16;4 4、数组元素地址的计算、数组元素地址的计算数组元素的存储方式：数组元素的存储方式：数组

38、元素存放在一片连续的单元中，数组元素存放在一片连续的单元中，地址用相对地址表示。地址用相对地址表示。例例 Var A Var A：array1array12 2，1 13of integer3of integer；a a1111，a a1212，a a1313a a2121，a a2222，a a2323行排序行排序列排序列排序A1A1，1 A11 A1，11A1A1，2 A22 A2，11A1A1，3 A13 A1，22A2A2，1 A21 A2，22A2A2，2 A12 A1，33A2A2，3 A23 A2，33数组下标：数组下标：沿着每一维的距离称为一个下标，每一维下标只能在上、沿着每一

39、维的距离称为一个下标，每一维下标只能在上、下限之内变动。下限之内变动。例：一维数组例：一维数组 AlowAlowhighhighlowlow 为下标的下限、为下标的下限、highhigh 为下标的上限。为下标的上限。例：数组说明为例：数组说明为 A1A15,low=1,high=55,low=1,high=5。/筱*lowlowi ihighhigh（i i 取值范围）其中：取值范围）其中：i i 为一个下标值。为一个下标值。数组下标变量数组下标变量:由数组名连同各维的下标值命名的，由数组名连同各维的下标值命名的，表示数组元素的地址。表示数组元素的地址。例：例：AiAi数组元素地址的计算：数组

40、元素地址的计算：一维数组元素地址的计算一维数组元素地址的计算D=base+(iD=base+(ilow)low)w=iw=iw+w+(base-low(base-loww)w)其中：其中：D D 表示数组元素表示数组元素 AiAi的相对地址；的相对地址；basebase 为为 A A 的第一个数据元素的第一个数据元素 A1A1的相对地址，的相对地址，w w 为域宽。为域宽。(base-low(base-loww)w)为相对地址为相对地址 D D 的常量用的常量用 CONSTPARTCONSTPART 表示。表示。i iw w 为相对地址为相对地址 D D 中的变量用中的变量用 VARPARTV

41、ARPART 表示。表示。地址计算公式：地址计算公式：D=CONSTPART+VARPARTD=CONSTPART+VARPART例：求例：求 A3A3的地址的地址A3A33 34 4(100(1001 14)4)=12+96=108=12+96=108A0 96A0 96A1 100A1 100 A2 104 A2 104 A3 108 A3 108例：一维数组例：一维数组 A2A25,5,low=2low=2、high=5high=5，basebase 为为 A A 的相对的相对地址为地址为 100100，w w 为为 4 4。相对地址偏移量：。相对地址偏移量：(base-low(base

42、-loww)w)=100=1002 24=924=92。例：求例：求 A4A4的地址的地址/筱*A4A4i iw w(base-low(base-loww)w)4 44 492=10892=108 A0 92 A0 92A1 96A1 96A2 100A2 100A3 104A3 104A4 108A4 108二维数元素地址的计算二维数元素地址的计算(按行存放按行存放)：二维数组二维数组 AlowAlow1 1highhigh1 1,low,low2 2highhigh2 2 例：例：AiAi1 1,i,i2 2 的地址的地址D D base+(ibase+(i1 1-low-low1 1)n

43、 n2 2+i+i2 2-low-low2 2)w wbase+(ibase+(i1 1n n2 2-low-low1 1n n2 2+i+i2 2-low-low2 2)w w（i i1 1n n2 2+i+i2 2）w+w+base-(lowbase-(low1 1n n2 2+low+low2 2)w w/*n/*n2 2为第二维的取值个数，为第二维的取值个数，n n2 2=high=high2 2-low-low2 2+1*/+1*/CONSTPART=CONSTPART=base-(low base-(low1 1n n2 2+low+low2 2)w wVARPART=VARPAR

44、T=（i i1 1n n2 2+i+i2 2）w w例：二维数组例：二维数组 A1A12 2，1 13,3,求数组元素求数组元素 A1,3A1,3的地址。的地址。其中：其中：lowlow1 11 1，lowlow2 21 1，highhigh2 23 3，n n2 23 31 11 13 3。CONSTPARTCONSTPART base-(lowbase-(low1 1n n2 2+low+low2 2)w w100100（1 13 31 1）4 48484VARPARTVARPART(i(i1 1n n2 2+i+i2 2)w w(1*3+3)*4=24(1*3+3)*4=24A1,3A1

45、,3 CONSTPART+VARPARTCONSTPART+VARPART84+24=10884+24=108数组元素数组元素 A1,3A1,3是第三个元素（按行存放）是第三个元素（按行存放）。A1A1，1 1001 100/筱*A1A1，2 1042 104A1A1，3 1083 108A2A2，1 1121 112A2A2，2 1162 116A2A2，3 1183 118多维数组元素地址的计算多维数组元素地址的计算D D（i i1 1n n2 2+i+i2 2）n n3 3+i+i3 3）n nk k+i+ik k)w w+base-(base-(（lowlow1 1n n2 2+low

46、+low2 2）n n3 3+low+low3 3）)n)nk k+low+lowk k)w wD DVARPARTVARPART+CONSTPARTCONSTPART数组内情向量：数组内情向量：下限值下限值上限值上限值每维界差每维界差 i i1 1 h h1 1 n n1 1 i in n h hn n n nn n n n（维数）（维数）C C（常量）（常量）TYPE TYPE（类型）（类型）A A（数组名称）（数组名称）数组元素在中间代码中的表示：数组元素在中间代码中的表示：用用 CONSTPART VARPATRCONSTPART VARPATR两部分表示数组元素。两部分表示数组元素。

47、例：例：A2A2，3:=E3:=E 中间代码为：中间代码为：T Tj j:=VARPATR;T:=VARPATR;Ti i:=CONSTPART:=CONSTPARTT Ti i保存语义值保存语义值 L.placeL.place 符号表指针；符号表指针；T Tj j保存语义值保存语义值 L.offsetL.offset 属性变量。属性变量。T Ti iTTj j:=E L.placeL.offset:=E:=E L.placeL.offset:=E例：例：X:=A2,3X:=A2,3的中间代码为：的中间代码为：X:=TX:=Ti iTTj j/筱*四、含数组元素的赋值语句的翻译模式（四、含数组

48、元素的赋值语句的翻译模式（P181P181）1 1、语义值和语义子程序、语义值和语义子程序L.placeL.place：简单变量：指此名字的符号表入口。简单变量：指此名字的符号表入口。数组元素：数组元素：指保存指保存 CONSTPARTCONSTPART 的临时变量整数码。的临时变量整数码。L.offsetL.offset：简单变量：简单变量：nullnull。数组元素：指保存数组元素：指保存VARPARTVARPART 的临时变量整数码。的临时变量整数码。Elist.arrayElist.array：表示数组名在符号表中的位置。：表示数组名在符号表中的位置。Elist.ndimElist.n

49、dim：下标个数（数组维数）计数器。：下标个数（数组维数）计数器。Elist.placeElist.place：保存保存 VARPARTVARPART 的中间结果的临时变量整数码。的中间结果的临时变量整数码。LimitLimit（array,marray,m）：给出数组：给出数组 arrayarray 第第 m m 维的长度维的长度。2 2、语义规则（翻译规则）、语义规则（翻译规则）：（P181-P182P181-P182）ElistElistidEidE Elist.place:=E.place;Elist.place:=E.place;Elist.ndim:=1;Elist.ndim:=1

50、;Elist.array:=id.placeElist.array:=id.placeElistElistElistElist1 1,E,Et:=newtemp;t:=newtemp;m:=Elistm:=Elist1 1.ndim+1;.ndim+1;emit(t:=Elistemit(t:=Elist1 1.place*limit(Elist.place*limit(Elist1 1.array.array,m),m)emit(temit(t:=:=t t+E.place)E.place)Elist.array:=ElistElist.array:=Elist1 1.array;.arra