编译原理-第七章

1、2022-5-1TJNU-COCIE-WJW1编译原理编译原理第七章第七章 语义分析和中间代码产生语义分析和中间代码产生王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW22022-5-1第七章第七章 语义分析和中间代码产生语义分析和中间代码产生l在词法分析和语法分析之后的阶段就是语义分析在词法分析和语法分析之后的阶段就是语义分析和中间代码生成和中间代码生成l本章把第六章介绍的有关语法制导翻译的相关方本章把第六章介绍的有关语法制导翻译的相关方法和技术用在中间代码生成和语义分析上法和技术用在中间代码生成和语义分析上l主要工作主要工作l静态语义检查静态语义检查l翻译翻译TJNU-C

2、OCIE-WJW32022-5-1l静态语义检查静态语义检查l类型检查类型检查: :如果操作符作用于不相容的操作数，如果操作符作用于不相容的操作数，编译程序必须报告出错信息。编译程序必须报告出错信息。，在，在C C语言中语言中”.”.”因该作用与结构体变量，因该作用与结构体变量，若作用于指针变量应用若作用于指针变量应用“-”-”l控制流检查控制流检查: :控制流语句必须使控制转移到合控制流语句必须使控制转移到合法的地方。法的地方。，在，在C C语言中语言中breakbreak语句使控制跳离包括语语句使控制跳离包括语句的最小句的最小whilewhile、forfor或或switchswitch语

3、句。如果不存语句。如果不存在包括它的这样的语句应该报错。在包括它的这样的语句应该报错。TJNU-COCIE-WJW42022-5-1l静态语义检查静态语义检查l一致性检查一致性检查: :很多场合要求对象只能被定义一次很多场合要求对象只能被定义一次，PascalPascal语言规定同一标识符在一个分程序语言规定同一标识符在一个分程序中只能被说明一次，同一中只能被说明一次，同一casecase语句的标号不能相语句的标号不能相同，枚举类型的元素不能重复出现等等。同，枚举类型的元素不能重复出现等等。l相关名字检查相关名字检查: :有时，同一名字必须出现两次或有时，同一名字必须出现两次或多次。多次。，A

4、daAda语言程序中，循环或程序块可以有一语言程序中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，编译个名字，它出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。程序必须检查这两个地方用的名字是相同的。l其他其他: :如名字的作用域分析等。如名字的作用域分析等。TJNU-COCIE-WJW52022-5-1l翻译（产生中间代码）翻译（产生中间代码）l采用独立于机器的中间代码的好处：采用独立于机器的中间代码的好处：l便于进行与机器无关的代码优化工作便于进行与机器无关的代码优化工作l使编译程序改变目标机更容易使编译程序改变目标机更容易l使编译程序的结构在逻辑上更

5、为简单明确。以中间语使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰言为界面，编译前端和后端的接口更清晰静态语义检查和中间代码生成器的位置静态语义检查和中间代码生成器的位置语法语法分析器分析器静静 态态检查器检查器中间代码中间代码生成器生成器中间中间代码代码符号流符号流中间代码中间代码优化器优化器TJNU-COCIE-WJW62022-5-1第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n7.1 中间语言中间语言n7.2 说明语句说明语句n7.3 赋值语句的翻译赋值语句的翻译n7.4 分情况语句分情况语句n7.5 回填技术回填技术n7.6 类型检查

6、类型检查TJNU-COCIE-WJW72022-5-17.1中间语言中间语言n中间语言中间语言 源程序的中间表示方法源程序的中间表示方法n中间语言的形式中间语言的形式后缀式后缀式图表示法图表示法 三地址代码三地址代码TJNU-COCIE-WJW82022-5-1把运算量把运算量( (操作数操作数) )写在前面，把算符写在后面。写在前面，把算符写在后面。：原式原式后缀式后缀式a+ba+b，ab+ab+a a* *b b，abab* *一、一、后缀式后缀式TJNU-COCIE-WJW92022-5-11.表达式表达式E的后缀表示递归定义的后缀表示递归定义n如果如果E是变量和常数，则是变量和常数，则

7、E的后缀表示是的后缀表示是E本身本身n如果如果E是形如是形如E1 op E2的表达式，其中的表达式，其中op是任是任意的二元算符，则意的二元算符，则E的后缀表示是的后缀表示是E1 E2 op，其中其中E1和和E2分别是分别是E1和和E2的后缀表示的后缀表示n如果如果E是形如是形如op E1的表达式，其中的表达式，其中op是一元是一元算符，则算符，则E的后缀表示是的后缀表示是E1 op，其中，其中E1 是是E1的后缀表示的后缀表示n如果如果E是形如是形如(E1)的表达式，则的表达式，则E1的后缀表示的后缀表示也是也是E的后缀表示的后缀表示：后缀式不需要括号：后缀式不需要括号TJNU-COCIE-

8、WJW102022-5-1：赋值语句：赋值语句 a := b *（- c）+ b *（ - 34）的后缀式的后缀式：a b c-*b 34-*+ :=TJNU-COCIE-WJW112022-5-11.1.特点和形式特点和形式描述了源程序的自然层次结构描述了源程序的自然层次结构n语法树语法树(抽象语法树抽象语法树)n有向无环图有向无环图(DAG)二、二、图表示法图表示法TJNU-COCIE-WJW122022-5-1：a := b * - c + b * - c后缀式是抽象语法树的线性表示后缀式是抽象语法树的线性表示后根序遍历后根序遍历 a b c uminus * b c uminus *

9、+ :=assigna+*bcuminus(a)抽象语法树抽象语法树*uminuscbTJNU-COCIE-WJW132022-5-1assigna+*bcuminus(b) DAG：a:=b * - c+b * -c其中，其中，b*-c是公共子表达式是公共子表达式TJNU-COCIE-WJW142022-5-12.产生赋值语句抽象语法树的属性文法产生赋值语句抽象语法树的属性文法产生式产生式语义规则语义规则S id := E S.nptr := mknode(:=, mkleaf(id, id.place), E.nptr )E E1 + E2E.nptr := mknode(+, E1.np

10、tr, E2.nptr )E E1 * E2E.nptr := mknode(*, E1.nptr, E2.nptr )E -E1E.nptr := mknode(uminus, E1.nptr )E ( E1 ) E.nptr := E1.nptrE idE.nptr := mkleaf(id , id.place )TJNU-COCIE-WJW152022-5-1：赋值语句：赋值语句：a:=b*-c+b*-c 抽象语法树的表示方法抽象语法树的表示方法后缀式：后缀式：a b c uminus * b c uminus * + assignassign + * uminus id a id c

11、 id b * uminus id c id b id b id c unimus 1 * 0 2 id b id c unimus 5 * 4 6 + 3 7 id a assign 9 8 . 01234567891011TJNU-COCIE-WJW162022-5-11.一般形式一般形式包含三个地址：两个操作数，一个结果包含三个地址：两个操作数，一个结果x := y op z一系列的上述形式一系列的上述形式x, y, z是名字、常数和编译器产生的临时变量是名字、常数和编译器产生的临时变量op是算符，定点、浮点、逻辑，只能有一个是算符，定点、浮点、逻辑，只能有一个：x + y * z翻译成

12、翻译成t1 := y * zt2 := x + t1三、三、三地址代码三地址代码TJNU-COCIE-WJW172022-5-11.一般形式（续）一般形式（续）三地址代码是三地址代码是AST或或DAG的线性化表示的线性化表示nDAG图对应的三地址代码可能比相应的图对应的三地址代码可能比相应的AST对应的三地址代码要优化，因为可以复用中对应的三地址代码要优化，因为可以复用中间结果间结果TJNU-COCIE-WJW182022-5-1：相应于相应于a:=b * - c+b * -c的的AST和和DAG的三地址代码的三地址代码 t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t

13、3 t5 ： t2+t4 a ： t5 （a）对于）对于AST的代码的代码 t1：-c t2：b*t1 t5：t2+t2 a：= t5 （b）对于）对于DAG的代码的代码 TJNU-COCIE-WJW192022-5-12.三地址代码的种类三地址代码的种类(1)赋值语句：赋值语句：x := y op z，op是二元算术算符或逻辑算符是二元算术算符或逻辑算符(2)赋值语句：赋值语句：x := op z，op是一元算符，如：负号，逻辑非是一元算符，如：负号，逻辑非not等等(3)复写语句：复写语句：x := yTJNU-COCIE-WJW202022-5-12.三地址代码的种类三地址代码的种类(续

14、续1)(4)无条件转移：无条件转移：goto L，L是下一步要执行的三地址语句的标号是下一步要执行的三地址语句的标号(5)条件转移语句：条件转移语句：if x relop y goto L根据逻辑运算的结果决定是否执行转移根据逻辑运算的结果决定是否执行转移if a goto La为真跳到为真跳到L执行，否则执行执行，否则执行if后边的语句后边的语句TJNU-COCIE-WJW212022-5-12.三地址代码的种类三地址代码的种类(续续2)(6)过程调用语句：过程调用语句：param x和和call p, nn表示实参个数表示实参个数：call p(x1 , x2 , , xn )，表示成三地

15、址语句：，表示成三地址语句：param x1param x2 param xncall p , n过程返回：过程返回：return yy表示返回值表示返回值TJNU-COCIE-WJW222022-5-12.三地址代码的种类三地址代码的种类(续续3)(7)数组引用赋值数组引用赋值x := y i x i := y(8)地址和指针的使用地址和指针的使用x := &yx := *y*x := yTJNU-COCIE-WJW232022-5-13.对赋值语句产生对赋值语句产生三地址代码的属性文法三地址代码的属性文法产生式产生式语义规则语义规则Sid:=ES.code:=E.codegen(i

16、d.place:=E.place)EE1+E2E.place:=newtemp; E.code:=E1.codeE2.codegen(E.place:=E1.place +E2.place)EE1*E2E.place:=newtemp; E.code:=E1.codeE2.codegen(E.place:=E1.place*E2.place)E-E1E.place:=newtemp;E.code:=E1.codegen(E.place:=uminusE1.place)E(E1)E.place:=E1.place; E.code:=E1.codeEidE.place:=id.place; E.c

17、ode:=TJNU-COCIE-WJW242022-5-1其中：其中：(1)E.place表示存放表示存放E值的名字。值的名字。 (2)E.code表示对表示对E求值的三地址语句序列。求值的三地址语句序列。 (3)newtemp是个函数，对它的调用将产生一个新的是个函数，对它的调用将产生一个新的临时变量临时变量： 三地址语句序列是语法树的线性表示，用临时变三地址语句序列是语法树的线性表示，用临时变量代替语法树中的结点量代替语法树中的结点实际实现中，三地址语句序列往往是被存放到一实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地址语句序列置入个输出文件中，而不是将三地址语句序列

18、置入code属属性之中性之中TJNU-COCIE-WJW252022-5-14. 三地址代码的具体实现三地址代码的具体实现三地址代码是一种抽象形式，其具体实现可用结构三地址代码是一种抽象形式，其具体实现可用结构体来表示，有以下几种表示方法：体来表示，有以下几种表示方法： 四元式四元式 ：op, arg1, arg2, result三元式三元式 ：op, arg1, arg2 间接三元式：间接码表间接三元式：间接码表+三元式表三元式表TJNU-COCIE-WJW262022-5-1(1)四元式四元式op, arg1, arg2, resultnop：算符的内部编码：算符的内部编码narg1和和a

19、rg2分别表示两个操作数分别表示两个操作数nresult表示计算结果表示计算结果narg1、arg2和和result的内容通常是符号表条目指针的内容通常是符号表条目指针：n一元运算不需要使用一元运算不需要使用arg2的域的域nparam不使用不使用arg2和和result域域n条件和无条件转移把目标语句的标号放在条件和无条件转移把目标语句的标号放在result中中TJNU-COCIE-WJW272022-5-1：语句：语句a:=b*-c+b*-c 的的四元式表示四元式表示arg1arg2resultop(0)uminusct1(1)*bt1t2(2)uminusct3(3)*bt3t4(4)+

20、t2t4t5(5)Assignt5aTJNU-COCIE-WJW282022-5-1(2)三元式三元式op, arg1, arg2避免四元式引入临时变量，可以用三地址语句的避免四元式引入临时变量，可以用三地址语句的序号表示临时变量序号表示临时变量有有3个域的记录结构个域的记录结构nop：算符的内部编码：算符的内部编码narg1和和arg2分别表示操作数分别表示操作数n语句的结果通过语句的序号引用语句的结果通过语句的序号引用narg1、arg2的内容通常是符号表条目指针或的内容通常是符号表条目指针或三地址语句的序号三地址语句的序号(对于临时变量对于临时变量)TJNU-COCIE-WJW29202

21、2-5-1arg1arg2op：语句语句a:=b*-c+b*-c 的的三元式表示三元式表示(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+ (1) (3)(5)Assigna(4)TJNU-COCIE-WJW302022-5-1：有些三地址语句要多个三元式表示有些三地址语句要多个三元式表示： xi := y op arg1 arg2(0) = x i (1) := (0) yy := xi op arg1 arg2(0) = x i(1) := y (0)TJNU-COCIE-WJW312022-5-1(3)间接三元式间接三元式在三元式基础上，增加一个间接码表在

22、三元式基础上，增加一个间接码表.该表按运算的先后顺序列出有关三元式在三元表该表按运算的先后顺序列出有关三元式在三元表中的位置。中的位置。TJNU-COCIE-WJW322022-5-1arg1arg2op间接代码间接代码：X:=(A+B)*C; Y:=D(A+B) 的间接的间接三元式表示三元式表示(1)+ A B(2)* (1) C(3)assign X (2)(4) D (1)(5)assign Y (4)(1)(2)(3)(1)(4)(5)TJNU-COCIE-WJW332022-5-1总结：总结：3种三地址代码的表示形式的比较种三地址代码的表示形式的比较式子之间的联系式子之间的联系所占空

23、间所占空间优化优化四元式四元式 临时变量临时变量较大较大易于调整次序，便易于调整次序，便于优化的实施于优化的实施三元式三元式 三元式的序号三元式的序号较小较小不易于调整次序，不易于调整次序，牵一发而动全身牵一发而动全身间接间接三元式三元式三元式的序号三元式的序号间接码表间接码表和四元式类似，和四元式类似，但如果临时值但如果临时值引用不止一次，引用不止一次，间接三元式的间接三元式的空间要节省一空间要节省一些些通过重排间接代码通过重排间接代码来实现来实现TJNU-COCIE-WJW342022-5-17.2 说明语句说明语句n说明语句的翻译说明语句的翻译：当翻译一个过程或分程序的一系列说明语句时，

24、当翻译一个过程或分程序的一系列说明语句时，便可为该过程的中的每个局部名字便可为该过程的中的每个局部名字(局部变量局部变量)分分配存储空间，并在符号表中建立相应的表项，填配存储空间，并在符号表中建立相应的表项，填写该名字的有关信息，如：类型、在存储器中的写该名字的有关信息，如：类型、在存储器中的相对地址等相对地址等n相对地址相对地址：相对静态数据区基址或活动记录中局部数据区基相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。址的一个偏移值。TJNU-COCIE-WJW352022-5-1nC，Java，Pascal和和Fortran这些语言的语法允许这些语言的语法允许一个过程中的所有声明

25、集中在一起处理，把它们安一个过程中的所有声明集中在一起处理，把它们安排在一个数据区中排在一个数据区中n在这种情况下，我们可用全局变量，例如在这种情况下，我们可用全局变量，例如offset，来记住下一个可用的相对地址。来记住下一个可用的相对地址。一、一、过程中的说明语句过程中的说明语句 TJNU-COCIE-WJW362022-5-1n声明语句的翻译模式声明语句的翻译模式计算名字的类型和相对地址计算名字的类型和相对地址P offset := 0 DDD ; DDid : T enter( , T.type , offset ); offset := offset + T.widt

26、h Tinteger T.type := integer; T.width := 4 Treal T.type := real; T.width := 8 Tarray num of T1 T.type := array( num.val , T1.type ); T.width := num.val * T1.width TT1 T.type := pointer( T1.type ); T.width := 4 TJNU-COCIE-WJW372022-5-1综合属性综合属性type和和width表示非终结符的类型和宽度表示非终结符的类型和宽度初始化的工作由第一个产生式完成初始化的工作由第

27、一个产生式完成P offset := 0 D改写上述产生式，使得所有动作出现在产生式的改写上述产生式，使得所有动作出现在产生式的右部的末端右部的末端P M DM offset := 0 TJNU-COCIE-WJW382022-5-11 .问题的提出问题的提出n 一般的语言中，标识符的作用在程序正文中有一一般的语言中，标识符的作用在程序正文中有一个确定的范围。因此，同一个标识符在不同的程序个确定的范围。因此，同一个标识符在不同的程序正文中可能标识不同的对象，具有不同的性质，要正文中可能标识不同的对象，具有不同的性质，要求分配不同的存储空间。求分配不同的存储空间。n于是提出下面的问题：于是提出下

28、面的问题：如何组织符号表，使得同一个标识符在不同的作用如何组织符号表，使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。域中得到正确的引用而不产生混乱。n编译程序分析说明语句时建立符号表，编译执行编译程序分析说明语句时建立符号表，编译执行语句时查找符号表。语句时查找符号表。Lookup(id)返回正返回正确的确的 id.entry。二、二、作用域信息的保存作用域信息的保存TJNU-COCIE-WJW392022-5-12.嵌套过程的声明嵌套过程的声明当遇到一个嵌入的过程说明时，应当暂停包围当遇到一个嵌入的过程说明时，应当暂停包围此过程的外围过程说明语句处理，而转去处理此过程的外围过程

29、说明语句处理，而转去处理嵌套过程，等被嵌套过程处理完后再继续。嵌套过程，等被嵌套过程处理完后再继续。 可以采用以下的产生式描述嵌套过程可以采用以下的产生式描述嵌套过程P DD D ; D | id : T | proc id ; D1 ; STJNU-COCIE-WJW402022-5-12.嵌套过程的声明（续）嵌套过程的声明（续）符号表的处理符号表的处理n为每个过程建立一个独立的符号表，可用链表实现为每个过程建立一个独立的符号表，可用链表实现n当遇到过程说明当遇到过程说明D proc id ; D1 ; S时，就创建一时，就创建一张新符号表，把张新符号表，把D1中的所有说明的局部名字都填入中

30、的所有说明的局部名字都填入该符号表该符号表n新表有一个指向其最近外围过程的符号表的指针新表有一个指向其最近外围过程的符号表的指针nid表示的过程名作为其外围过程的一个局部名字。表示的过程名作为其外围过程的一个局部名字。TJNU-COCIE-WJW412022-5-1program sort(input, output) var a: array0.10 of integer;x:integer;procedure readarray;var i:integer;begin a end readarrayprocedure exchange(i, j:integer);beginx:=ai;ai

31、:=aj;aj:=xend exchange;procedure quicksort(m,n:integer);var k,v: integer;function partition(y,z:integer):integer;var i,j: integer;begin avexchange(i, j); end partition ;beginend quicksort ;beginend sort .TJNU-COCIE-WJW422022-5-1：P176TJNU-COCIE-WJW432022-5-13.嵌套过程的翻译模式嵌套过程的翻译模式(1)定义一些操作定义一些操作mktable(

32、previous)n建立新的符号表，并返回新符号表的指针。参建立新的符号表，并返回新符号表的指针。参数数previous指向直接外围过程的符号表。指向直接外围过程的符号表。previous放在新建符号表的表头。放在新建符号表的表头。enter(table, name, type, offset)n在在table指向的符号表中为变量名指向的符号表中为变量名name建立新建立新项，项，enter把类型把类型type和相对地址和相对地址offset置于该置于该项的域中。项的域中。TJNU-COCIE-WJW442022-5-13.嵌套过程的翻译模式嵌套过程的翻译模式(1)定义一些操作定义一些操作(续

33、续)addwidth(table, width)n把符号表把符号表table所有名字占用的总宽度记录在该所有名字占用的总宽度记录在该符号表的表头。符号表的表头。enterproc(table, name, newtable)n在在table指向的符号表中为过程名指向的符号表中为过程名name建立新建立新项。参数项。参数newtable指向过程指向过程name的符号表。的符号表。 TJNU-COCIE-WJW452022-5-1(2)定义两个栈定义两个栈tblptr栈：栈：用于保存各过程的符号表指针用于保存各过程的符号表指针栈顶的指针指向当过程的前符号表栈顶的指针指向当过程的前符号表offset

34、栈：栈：用于存放各嵌套过程的当前相对地址用于存放各嵌套过程的当前相对地址栈顶元素为当前被处理过程的下一个局部名字的栈顶元素为当前被处理过程的下一个局部名字的相对地址相对地址相应操作有：相应操作有：push(栈名栈名)：压栈：压栈pop(值，栈名值，栈名)：出栈：出栈top(栈名栈名)：返回栈顶：返回栈顶TJNU-COCIE-WJW462022-5-1P M D addwidth( top( tblptr ) , top( offset ) ); pop( tblptr ); pop( offset ) M t := mktable( nil ); push( t , tblprt ); pus

35、h( 0 , offset ) DD1 ; D2Dproc id ; N D1 ; S t := top( tblptr ); addwidth( t , top( offset ) ); pop( tblptr ); pop( offset ); enterproc( top( tblptr ), , t ) Did : T enter( top(tblptr), , T.type ,top( offset ) ); top( offset ) := top( offset ) + T.width N t := mktable( top( tblptr ) );

36、 push( t , tblprt ); push( 0 , offset ) TJNU-COCIE-WJW472022-5-1n非终结符非终结符M的语义动作最先完成的语义动作最先完成建立最外层作用域的符号表建立最外层作用域的符号表用最外层符号表初始栈用最外层符号表初始栈tblptr用用0初始化初始化offset栈栈n非终结符非终结符N的语义动作的语义动作建立一个新的作用域的符号表建立一个新的作用域的符号表在符号表栈中压入新的符号表指针在符号表栈中压入新的符号表指针用用0作为作为offset栈顶栈顶TJNU-COCIE-WJW482022-5-1n变量声明变量声明id : T不改变符号表栈不改

37、变符号表栈建立新的符号条目建立新的符号条目累加符号的宽度累加符号的宽度n过程的声明处理结束时过程的声明处理结束时addwidth记录该符号表的所有名字的宽度记录该符号表的所有名字的宽度更改符号表栈和更改符号表栈和offset栈栈过程名进入外围符号表过程名进入外围符号表TJNU-COCIE-WJW492022-5-14.记录声明的产生式记录声明的产生式T record D end为记录的域名建立符号表为记录的域名建立符号表T record L D end T.type := record( top ( tblptr ) ); T.width := top( offset ); pop( tblp

38、tr ); pop( offset ) L t := mktable( nil ); push( t , tblprt ); push( 0 , offset ) 看见关键字看见关键字record后，标记非终结符后，标记非终结符L为域名建立一个新的符号表为域名建立一个新的符号表Did : T的语义动作将域名的语义动作将域名id的信息填入该纪录的符号表中的信息填入该纪录的符号表中纪录的域分析完后，纪录的域分析完后，offset栈顶保存纪录中所有数据对象的总宽度栈顶保存纪录中所有数据对象的总宽度end后的动作将总宽度作为综合属性后的动作将总宽度作为综合属性T.width返回。把构造器返回。把构造器

39、record作用于该记录的符号表指针，得到作用于该记录的符号表指针，得到T.type，用于恢复记录中的域名，用于恢复记录中的域名的名字、类型和宽度的名字、类型和宽度TJNU-COCIE-WJW502022-5-17.3赋值语句的翻译赋值语句的翻译一、简单算术表达式及赋值语句一、简单算术表达式及赋值语句1.符号表中的名字符号表中的名字三地址代码中用标识符对应的符号表条目指针三地址代码中用标识符对应的符号表条目指针表示表示id的名字本身的名字本身nlookup()检查是否在符号表中存在相应该检查是否在符号表中存在相应该名字的入口名字的入口如果找到，则返回该名字对应表项

40、的指针如果找到，则返回该名字对应表项的指针如果找不到，则返回如果找不到，则返回nil表示没有找到表示没有找到2.赋值语句的翻译方案赋值语句的翻译方案生成三地址代码生成三地址代码TJNU-COCIE-WJW512022-5-1Sid := E p := lookup( ); if p nil then emit( p := E.place) else error EE1 + E2 E.place := newtemp; emit( E.place := E1.place + E2.place ) EE1 * E2 E.place := newtemp; emit( E.place

41、 := E1.place * E2.place ) E -E1 E.place := newtemp; emit( E.place := uminus E1.place ) E ( E1 ) E.place := E1.place Eid p := lookup( ); if p nil then E.place := p else error 移进规约过程移进规约过程A:=B+(-C)AA:=A:=BA:=EA:=E+A:=E+(A:=E+(-A:=E+(-CA:=E+(-EA:=E+(ET1=uminus CA:=E+(E)A:=E+EA:=ET2=B+T1SA=T2TJN

42、U-COCIE-WJW522022-5-1二、二、数组元素的翻译数组元素的翻译数组元素的定址数组元素的定址：对于一个数组，确定某个元素相对于数：对于一个数组，确定某个元素相对于数组首地址的偏移组首地址的偏移假设数组存储在连续的存储块中假设数组存储在连续的存储块中假设每个数组元素的宽度为假设每个数组元素的宽度为w，数组的首地址为，数组的首地址为base1.一维数组元素的定址一维数组元素的定址：A i n假设数组下标的下界为假设数组下标的下界为low，此时：，此时：base=&Alow A i 的相对地址是：的相对地址是：base + ( i low ) * w优化的计算方式：优化的计算方

43、式：i * w + (base low * w)后一部分可以在处理数组的说明语句时就计算出后一部分可以在处理数组的说明语句时就计算出来，存到数组来，存到数组A对应的符号表项中去，然后在分对应的符号表项中去，然后在分析析A i 时只需计算出时只需计算出i*w的值的值TJNU-COCIE-WJW532022-5-1二维数组A2,3的存储布局二维数组A2,3的存储布局第一行第一行A1,1A1,1A1,2A1,2A1,3A1,3A2,1A2,1A2,2A2,2A2,3A2,3A1,1A1,1A2,1A2,1A1,2A1,2A2,2A2,2A1,3A1,3A2,3A2,3第二行第二行行为主，如C、Pas

44、cal行为主，如C、Pascal列为主，如Fortran列为主，如Fortran第一列第一列第二列第二列第三列第三列2.多维数组的定址多维数组的定址存储方式有两种：数组元组的定址计算方式是不一样的存储方式有两种：数组元组的定址计算方式是不一样的 l行为主（一行接一行的存放）行为主（一行接一行的存放）l列为主（一列接一列的存放）列为主（一列接一列的存放）TJNU-COCIE-WJW542022-5-1(1)行为主的二维数组行为主的二维数组n元素的定址公式元素的定址公式A i1，i2 的相对地址：的相对地址：base + ( ( i1 low1 ) * n2 + ( i2 low2 ) ) * w

45、Low1和和low2分别是两维的下界分别是两维的下界n2是数组第二维的维展，即是数组第二维的维展，即i2可取值的个数，如果可取值的个数，如果high2是是i2值的上界，且这一维的步长为值的上界，且这一维的步长为1，则，则n2=high2 - low2 +1n地址计算的优化公式：地址计算的优化公式： ( ( i1 * n2 ) + i2 ) * w + (base - ( ( low1 * n2 ) + low2 ) * w)(2)列为主的二维数组的元素定址列为主的二维数组的元素定址n类似于行为主的二维数组：类似于行为主的二维数组： base + ( ( i1 low1 ) + ( i2 low

46、2 ) * n1 ) * wTJNU-COCIE-WJW552022-5-1(3)多维数组的定址计算多维数组的定址计算n行为主的数组，最右边的下标变化最快行为主的数组，最右边的下标变化最快A i1，i2，ik 的相对地址：的相对地址：( ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )* w+base( ( low1 * n2 + low2 ) * n3 + low3 ) * nk + lowk ) * w由于在大多数情况下数组各维的维展是一个固定值，由于在大多数情况下数组各维的维展是一个固定值，所以上述公式的第二行可以在编译时刻计算，并存所以上述公

47、式的第二行可以在编译时刻计算，并存放在符号表中放在符号表中A的条目中的条目中n列为主的数组，最左边的下标变化最快，其地址计算列为主的数组，最左边的下标变化最快，其地址计算公式可以参照上述公式公式可以参照上述公式TJNU-COCIE-WJW562022-5-13.数组引用的描述数组引用的描述(1) 产生式描述产生式描述L id Elist | idElist Elist , E | E其中，其中，Elist代表下标表达式的列表，表达式中间用代表下标表达式的列表，表达式中间用，号分隔。号分隔。改写上述产生式，使数组名字改写上述产生式，使数组名字id和最左下标表达式和最左下标表达式E相相联系：联系：

48、L Elist | idElist Elist , E | id En目的是在对目的是在对Elist进行翻译时，随时知道符号表中数进行翻译时，随时知道符号表中数组组id的全部信息。的全部信息。n为为Elist配备一个综合属性配备一个综合属性array，用它来传递符号表，用它来传递符号表中数组中数组id项的指针。项的指针。TJNU-COCIE-WJW572022-5-1(2)几个定义几个定义：属性属性Elist.ndim表示表示Elist中的下标表达式的个数中的下标表达式的个数函数函数Limit( array， j )返回数组返回数组(array指向的符号表项所记指向的符号表项所记录的数组录的数

49、组)第第j维的元素个数维的元素个数(维展维展)函数函数Invariant( array )取得数组的地址计算的不变部分，取得数组的地址计算的不变部分，即地址计算公式第二行中除即地址计算公式第二行中除base外的其它部分的值外的其它部分的值( ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )* w+base( ( low1 * n2 + low2 ) * n3 + low3 ) * nk + lowk ) * w属性属性Elist.place存储临时变量在符号表中的表项地址存储临时变量在符号表中的表项地址(3)采用递推计算方法实现采用递推计算方法实现E

50、list的计算的计算(上式中的第一项上式中的第一项)：e1 = i1em = em-1 * nm + im当当m=k时，时， ek = ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )TJNU-COCIE-WJW582022-5-14.数组定址的翻译模式数组定址的翻译模式(1)在赋值语句中引用数组的文法在赋值语句中引用数组的文法(1) S L := E(2) E E + E(3) E ( E )(4) E L(5) L Elist (6) L id(7) Elist Elist , E(8) Elist id ETJNU-COCIE-WJW59202

51、2-5-1(2)各个产生式的三地址代码生成各个产生式的三地址代码生成(1) S L := E if L.offset = null then /* L是简单名字是简单名字*/ emit( L.place := E.place ); else emit( L.place L.offset :=E.place ) 如果如果L是简单名字，产生正常的赋值；否则产生对由是简单名字，产生正常的赋值；否则产生对由L的两的两个属性确定的存储单元的索引赋值。个属性确定的存储单元的索引赋值。(2) EE1 +E2 E.place := newtemp; emit( E.place := E1.place + E2

52、.place) (3) E ( E ) E.place := E1.place TJNU-COCIE-WJW602022-5-1(4) E L if L.offset = null then/* L是简单名字是简单名字*/ E.place := L.place; else begin E.place := newtemp; emit( E.place := L.place L.offset ) end 如果如果E产生数组元素产生数组元素L，则需要，则需要L的右值，可用索引得到存储的右值，可用索引得到存储单元单元L.place L.offset的内容的内容TJNU-COCIE-WJW612022

53、-5-1(5) L Elist L.place := newtemp; emit( L.place := Elist.array - invariant(Elist.array); L.offset := newtemp; emit( L.offset := w * Elist.place ) (6) L id L.place := id.place; L.offset := null ( ( ( (i1 n2 + i2 ) n3 + i3 ) ) nk + ik) w+ base ( ( ( (low1 n2 + low2) n3 + low3) ) nk + lowk ) w L.plac

54、e和和L.offset都是新的临时变量，都是新的临时变量，L.place对应第二项；对应第二项；L.offset保存保存w乘以乘以Elist.place的值，对应第一项的值，对应第一项 TJNU-COCIE-WJW622022-5-1(7) Elist Elist1 , E t := newtemp; m := Elist1.ndim + 1; emit( t := Elist1.place * limit( Elist1.array , m ); emit( t := t + E.place); Elist.array := Elist1.array; Elist.place := t; E

55、list.ndim := m 当看见下一个下标表达式时，使用递推公式当看见下一个下标表达式时，使用递推公式e1 = i1em = em-1 * nm + imElist1.place对应对应em-1 ，Elist.place对应对应em如果如果Elist1有有m 1个成分。那么产生式左边的个成分。那么产生式左边的Elist有有m个成分个成分TJNU-COCIE-WJW632022-5-1(8) Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place E.place保存表达式保存表达式E的值的值也是递

56、推公式也是递推公式e1 = i1em = em-1 * nm + imm = 1时的值时的值TJNU-COCIE-WJW642022-5-1：A是是10*20的数组，即的数组，即n1=10，n2=20，取，取w=4，假设数组的第一个元素是假设数组的第一个元素是A 1 , 1 求赋值语句求赋值语句x:=Ay , z的三地址代码。的三地址代码。(其中每个变量，用它们的名字来代替其中每个变量，用它们的名字来代替id.place)解：不变量：解：不变量：Base - ( ( low1 * n2 ) + low2 ) * w = A - ( 1 * 20 + 1 ) * 4 =A - 84可变量：可变量

57、：( i1 * n2 + i2 ) * w = (y * 20 + z ) * 4t1 := y * 20t1 := t1 + z Elist Elist1 , E t2 := A 84t3 := 4 * t1 L Elist t4 := t2 t3 E Lx := t4 S L := ETJNU-COCIE-WJW652022-5-1S S: := =L L. .p pl la ac ce e = = x xL L. .o of ff fs se et t = = n nu ul ll lE E. .p pl la ac ce e = = t t 4 4L L. .p pl la ac ce

58、 e = = t t 2 2L L. .o of ff fs se et t = = t t 3 3E El li is st t. .p pl la ac ce e = = t t 1 1E El li is st t. .n nd di im m = = 2 2E El li is st t. .a ar rr ra ay y = = A A E El li is st t. .p pl la ac ce e = = y yE El li is st t. .n nd di im m = = 1 1E El li is st t. .a ar rr ra ay y = = A A, ,E

59、E. .p pl la ac ce e = = z zL L. .p pl la ac ce e = = z zL L. .o of ff fs se et t = = n nu ul ll lz zE E. .p pl la ac ce e = = y yL L. .p pl la ac ce e = = y yL L. .o of ff fs se et t = = n nu ul ll ly y A ATJNU-COCIE-WJW662022-5-17.4布尔表达式的翻译布尔表达式的翻译一、一、概述概述1.布尔表达式的作用布尔表达式的作用计算逻辑值计算逻辑值在改变控制流的语句中作为条件表

60、达式在改变控制流的语句中作为条件表达式n条件语句：条件语句：if then或或if then elsen循环：循环：while do，for等等2.布尔表达式的文法布尔表达式的文法E E or E | E and E | not E | ( E ) | id relop id | true | false用用relop.op属性确定属性确定relop是是,=,=,!=中的哪个中的哪个算符的结合性和优先性算符的结合性和优先性nor和和and都是左结合的都是左结合的nor的优先级最低，其次是的优先级最低，其次是and，not的优先级最高的优先级最高TJNU-COCIE-WJW672022-5-13. 表示布尔表达