编译原理课件 第7章 语义分析和中间代码产生

1、本章在编译程序中的地位本章在编译程序中的地位 表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理语义分析和中间代码的产生语义分析和中间代码的产生n语义分析的概念语义分析的概念: 源程序经过词法分析、语法分析后，表明该源源程序经过词法分析、语法分析后，表明该源程序书写正确、符合程序语言所规定的语法，但语程序书写正确、符合程序语言所规定的语法，但语法分析并未对程序内部的逻辑含义加以分析，因此法分析并未对程序内部的逻辑含义加以分析，因此编译程序接着进行编译程序接着进行语义分析语义分析，即审查每个语法成分即审查每个语法成分的静态

2、语义。如果静态语义正确，则生成与该语言的静态语义。如果静态语义正确，则生成与该语言成分等效的中间代码，或直接生成目标代码。成分等效的中间代码，或直接生成目标代码。 直接生成机器语言或汇编语言形式的目标代直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的优点是编译时间短且无需中间代码到目标代码的翻译，而码的翻译，而生成中间代码的优点生成中间代码的优点是使编译结构是使编译结构在逻辑上更为简单明确，特别是使目标代码的优在逻辑上更为简单明确，特别是使目标代码的优化较易实现。化较易实现。 语义分析进行的语义分析进行的语义检查有两类语义检查有两类：动态语义：动态语义检查和

3、静态语义检查。检查和静态语义检查。动态语义检查动态语义检查需生成相应需生成相应的目标代码，在运行时进行；的目标代码，在运行时进行；静态语义检查静态语义检查在编在编译时进行。译时进行。语义分析和中间代码的产生语义分析和中间代码的产生静态语义检查静态语义检查涉及以下几个方面：涉及以下几个方面：(1)(1)类型检查类型检查，如运算操作数的类型应相容。，如运算操作数的类型应相容。(2)(2)控制流检查控制流检查，用以保证控制语句有合法的，用以保证控制语句有合法的 转向点。如转向点。如C C语言中不允许语言中不允许gotogoto语句转入语句转入casecase语语句流；句流；breakbreak语句需

4、寻找包含它的最小语句需寻找包含它的最小switchswitch、whilewhile或或forfor语句方可找到转向点。语句方可找到转向点。(3)(3)一致性检查一致性检查，如在相同作用域中标识符只，如在相同作用域中标识符只 能说明一次、能说明一次、casecase语句的标号不能相同等。语句的标号不能相同等。语义分析和中间代码的产生语义分析和中间代码的产生语法分语法分析器析器中间代码中间代码产生器产生器静态检静态检查器查器中间代码中间代码优化器优化器 语义分析阶段语义分析阶段只产生只产生中间代码中间代码而不生成目而不生成目标标代码代码的方法使编译程序的开发变得较为容易，但的方法使编译程序的开发

5、变得较为容易，但由于语义是上下文有关的，因此语义的形式化描由于语义是上下文有关的，因此语义的形式化描述非常困难，目前较常见的是用述非常困难，目前较常见的是用属性文法属性文法作为描作为描述语义的工具，并采用述语义的工具，并采用语法制导翻译法语法制导翻译法完成对语完成对语法成分的翻译。法成分的翻译。语义分析和中间代码的产生语义分析和中间代码的产生语法制导翻译：语法制导翻译： 在语法分析的基础上进行边分析边翻译。在语法分析的基础上进行边分析边翻译。 教学要求教学要求n掌握掌握：n1. 1. 逆波兰式逆波兰式, , DAGDAG图图, , 抽象语法树抽象语法树, , 三地址三地址代码代码, , 三元式

6、三元式, , 四元式等中间代码表示四元式等中间代码表示; ;n2. 2. 简单赋值语句的翻译简单赋值语句的翻译, , 带数组元素引用带数组元素引用的赋值句的翻译的赋值句的翻译; ;n3. 3. 布尔表达式的翻译布尔表达式的翻译, , 控制语句中布尔表控制语句中布尔表达式的翻译达式的翻译; ;n4. 4. 控制语句的翻译。控制语句的翻译。n了解理解了解理解：说明语句的翻译，过程调用和参：说明语句的翻译，过程调用和参数的处理。数的处理。教学内容教学内容n7.1 中间语言中间语言n 后缀式，后缀式，DAG，三地址码三地址码(四元式，三元式，间四元式，三元式，间接三元式接三元式)n*7.2 说明语句的

7、翻译说明语句的翻译n7.3 赋值语句的翻译，数组元素引用的翻译赋值语句的翻译，数组元素引用的翻译n7.4 布尔表达式的翻译布尔表达式的翻译n求求布尔式布尔式值的翻译，作为控制条件的翻译值的翻译，作为控制条件的翻译n7.5 控制语句的翻译控制语句的翻译nif ， while ， goto ， casen7.6 过程调用的处理过程调用的处理, 参数传递的处理参数传递的处理n*7.7 类型检查类型检查（不作要求，不讲）（不作要求，不讲） 7.1 7.1 中间语言中间语言 n要掌握几种中间语言的基本结构：要掌握几种中间语言的基本结构：n逆波兰表示即后缀式逆波兰表示即后缀式n抽象语法树抽象语法树nDAG

8、DAG图图n三地址代码三地址代码( (四元式、三元式、间接三元式四元式、三元式、间接三元式) )7.1.1 后缀式后缀式n波兰逻辑学家卢卡西维奇（波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示法，又称逆波兰式表示法。发明的一种表示法，又称逆波兰式表示法。n后缀式后缀式这种方法是，把运算量这种方法是，把运算量( (操作数操作数) )写在写在算符的前面，把算符写在运算量的后面算符的前面，把算符写在运算量的后面( (后后缀缀) )。 后缀式的定义后缀式的定义( (P167.)P167.)n一个一个表达式的后缀式表达式的后缀式可以如下定义：可以如下定义：1. 如果如果E是一个变量或常量

9、，则是一个变量或常量，则E的后缀式是的后缀式是E自身自身。2. 如果如果E是是 E1 op E2 形式的表达式，这里形式的表达式，这里op是是任何二元操作符，则任何二元操作符，则E的后缀式为的后缀式为 E1E2op,这里这里E1 和和E2分别为分别为E1和和E2的后缀式。的后缀式。3. 如果如果E是是(E1)形式的表达式，则形式的表达式，则E1的后缀式的后缀式就是就是E的后缀式。的后缀式。n要求会正确写出表达式的后缀式要求会正确写出表达式的后缀式。 后缀式求值后缀式求值n可以使用一个栈来求值可以使用一个栈来求值n求值过程：求值过程： 从左到右扫描后缀式，每碰到运算量就把它从左到右扫描后缀式，每

10、碰到运算量就把它推进栈，每碰到推进栈，每碰到k目运算符就把它作用于栈顶目运算符就把它作用于栈顶的的k个项，弹出这个项，弹出这k项，并用运算结果来代替这项，并用运算结果来代替这k个项个项 后缀式：例后缀式：例n写表达式的后缀式写表达式的后缀式要点：要点：1.后缀式中后缀式中运算量运算量的顺序与中缀式的相同；的顺序与中缀式的相同；2.算符算符出现的次序即表达式的出现的次序即表达式的运算次序运算次序；3.不使用括号。不使用括号。n例：例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) -a+b*c a bc*+ a/b*c-d*e x := a-b/(c+d)n 用用 表示取负算

11、符表示取负算符(uminus) n := 表示赋值算符表示赋值算符(assign) ab+cd+*ab/c*de*-x a b c d + / - :=7.1.2 抽象语法树抽象语法树n语法制导翻译以语法树作基础语法制导翻译以语法树作基础, , 实际上实际上, , 语法树可语法树可以作为一种合适的中间语言形式。以作为一种合适的中间语言形式。n现在对语法树进行改造，去掉那些对翻译不必要的现在对语法树进行改造，去掉那些对翻译不必要的信息，将语法树进行抽象信息，将语法树进行抽象 - - 抽象语法树抽象语法树。n在表达式的抽象语法树中，在表达式的抽象语法树中，运算符运算符、关键字不作叶、关键字不作叶子

12、结点而作为子结点而作为内部结点内部结点，叶子结点只是运算量叶子结点只是运算量。n抽象语法树也可以属性化抽象语法树也可以属性化，给结点加上属性变成带，给结点加上属性变成带附注的抽象语法树。附注的抽象语法树。n语法制导翻译既可以基于语法分析树也可以基于抽语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行象语法树进行，采用的基本方法是一样的。，采用的基本方法是一样的。抽象语法树：简例抽象语法树：简例n例，为下面文法的句子例，为下面文法的句子 a-4+ca-4+c 建立抽象语法树。建立抽象语法树。 E E+T | ET | T T (E) T id | numn为每个为每个运算量运算量或或运算符

13、号运算符号都建立一个结点。都建立一个结点。n可以可以根据表达式的运算顺序自下而上的构造根据表达式的运算顺序自下而上的构造 - 手工手工构造。构造。a+c4抽象语法树抽象语法树运算符作内运算符作内部结点部结点id(a)E E TE + TTnum(4)id(c )语法树语法树 7.1.3 DAG图表示法：图表示法：n无循环有向图无循环有向图（DAG DAG ) ) 与与语法树语法树一样，对于表达式中的每个子表达式，一样，对于表达式中的每个子表达式，DAGDAG图中都有一个结点：图中都有一个结点：n一个内部结点代表一个操作符，它的孩子代表操作一个内部结点代表一个操作符，它的孩子代表操作数；数；n两

14、者不同两者不同的是的是n在在DAGDAG图中代表图中代表公共子表达式公共子表达式的结点具有多个父结点；的结点具有多个父结点；n在一棵抽象语法树中公共子表达式被表示为重复的子树；在一棵抽象语法树中公共子表达式被表示为重复的子树；例如赋值语句的语法树与例如赋值语句的语法树与DAGDAG图：图：a:=b a:=b * * - c+b - c+b * * -c -c 抽象抽象语法树语法树公共子表达式公共子表达式重复出现重复出现assigna+*bcuminus*uminuscb图图7.37.3抽象语法树例抽象语法树例： a:=b * - c+b * -c (b) DAG公共子表达式只出现一公共子表达式

15、只出现一次，一个结点可以有多次，一个结点可以有多个父结点个父结点图图7.3 7.3 DAGDAG例例： a:=b * - c+b * -c assigna+bcuminus* 后缀式与抽象语法树后缀式与抽象语法树(DAG)的关的关系系n后缀式是抽象语法树的后缀式是抽象语法树的线性表示形式线性表示形式。是树的。是树的后序遍历后序遍历的一个序列。的一个序列。n例如例如: 抽象语法树抽象语法树assigna+*bcuminus*uminuscb后缀式后缀式: : a b c uminus a b c uminus * * b c uminus b c uminus * * + assign + as

16、sign后序遍历：后序遍历： (1)(1)遍历左子树；遍历左子树； (2)(2)遍历右子树；遍历右子树； (3)(3)访问根结点。访问根结点。 7.1.4 三地址代码三地址代码n三地址代码是由下面一般形式的语句构成的三地址代码是由下面一般形式的语句构成的序列序列: x := y op zn其中，其中，x、y、z为名字、常数或编译时产生为名字、常数或编译时产生的临时变量；的临时变量；op代表运算符号。代表运算符号。n每个三地址语句的每个三地址语句的右边只能有一个运算符。右边只能有一个运算符。n例例, 表达式表达式x+y*z翻译为三地址代码翻译为三地址代码: T1:=y*z T2:=x+T1nT1

17、, T2是编译时产生的临时变量。是编译时产生的临时变量。三地址代码：说明三地址代码：说明n1. 之所以称为三地址代码，是因为三地址代码之所以称为三地址代码，是因为三地址代码语句类似与汇编指令语句类似与汇编指令, 涉及三个地址涉及三个地址 x、y和和z，其中其中y、z表示操作数，表示操作数，x存放结果。存放结果。地址常用地址常用属性属性place表示表示。n名字名字.place：指向符号表名字入口的指针指向符号表名字入口的指针n临时变量临时变量.place：临时变量值存放的单元地址临时变量值存放的单元地址n常数常数.place：指向常数表中常数入口的指针指向常数表中常数入口的指针n2. 三地址语

18、句可以带符号标号三地址语句可以带符号标号, 标号代表存放标号代表存放中间代码的数组中三地址代码语句的下标。中间代码的数组中三地址代码语句的下标。n3. 三地址代码是抽象语法树或三地址代码是抽象语法树或DAG的线性化的线性化表示表示 - 每个内部结点对应一个三地址语句。每个内部结点对应一个三地址语句。 n例例, P170.图图7.5，是相应于，是相应于P168.图图7.3的抽象语法树的抽象语法树和和DAG的三地址代码：的三地址代码： (a) 对应抽象语法树的代码对应抽象语法树的代码 (b) 对应对应DAG的代码的代码 T1 : -c T1 : -c T2 : b* T1 T2 : b*T1 T3

19、 : -c T5 : T2+T2 T4 : b* T3 a : T5 T5 : T2+T4 a : T5 n注：注： 临时变量的名字对应抽象语法树的内部结点临时变量的名字对应抽象语法树的内部结点(算符结点算符结点), 表达式中的每个运算都要引入一个新的表达式中的每个运算都要引入一个新的临时变量存放计算结果临时变量存放计算结果, 要多少引入多少。要多少引入多少。抽象语法树与三地址代码的关系抽象语法树与三地址代码的关系n(1) 赋值语句赋值语句 x : y op z ; op是二元算术或逻辑运算符是二元算术或逻辑运算符n(2) 赋值语句赋值语句 x : op y ; op是一元算符，如取负是一元算

20、符，如取负、逻辑非逻辑非、移位及类型转换移位及类型转换n(3) 复制语句复制语句 x : y;n(4) 无条件转移语句无条件转移语句 goto L; 符号标号符号标号 L 代表存放中间代码的数组中三地址代码代表存放中间代码的数组中三地址代码语句的下标语句的下标n(5) 条件转移语句条件转移语句 if x relop y goto L ; if a goto L ; relop是关系运算符是关系运算符; a是布尔量是布尔量*三地址代码语句的种类三地址代码语句的种类(P170.)n(6) 过程调用语句过程调用语句 param x; x是实参数是实参数 call p, n ; p过程名过程名, n实

21、参个数实参个数 过程返回语句过程返回语句 return y; y返回值返回值, 可有可无可有可无n(7) 索引赋值索引赋值 x := yi; = 变址取数变址取数 xi := y ; =变址存数变址存数n(8) 地址和指针赋值地址和指针赋值 x : y; x : * y; * x : y;n注：注：选择适当的算符集合是中间代码设计的重要问选择适当的算符集合是中间代码设计的重要问题，应该不大不小，足以实现源语言的操作运算。题，应该不大不小，足以实现源语言的操作运算。*三地址代码语句的种类三地址代码语句的种类(续续P170.) 四元式四元式 用了四个域（用了四个域（ op, arg1, arg2,

22、 result ）四元式式要要用用多的临时单元，四元式式间的四元式式要要用用多的临时单元，四元式式间的联系通过联系通过临时变量临时变量实现实现三地址语句：三地址语句：z :=x op y可表示为：可表示为： (op，x，y，T1) (=，T1， z )对于一元运算可只只用对于一元运算可只只用arg1四元式中的四元式中的arg1, arg2, result其实都是指针，它指其实都是指针，它指向相关符号表中的名字的入口向相关符号表中的名字的入口,临时变量也要要临时变量也要要入符号表。入符号表。三地址代码的实现三地址代码的实现算符算符操作数操作数1(指针指针) 操作数操作数2(指针指针)结果结果(临

23、变临变)n三地址代码的具体实现三地址代码的具体实现: 用记录结构用记录结构, 含四个域含四个域 n赋值语句赋值语句a:=ba:=b* *-c+b-c+b* *-c -c 的三地址代码实现的三地址代码实现(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbT2T5arg1T1T3T4arg2resultT1T2T3T4T5aopP172. 表表7.4(a) 三地址语句的四元式表示三地址语句的四元式表示三地址代码实现：四元式表示三地址代码实现：四元式表示n四元式之间四元式之间 的联系通过的联系通过临时变量临时变量实现实现 三元式三元式 (op, arg1, arg

24、2 ）为只有三个域，以为三元式为只有三个域，以为三元式是为了了避免临时变量要入符号表表是为了了避免临时变量要入符号表表而是通过计算算个个个临时变量的值值而是通过计算算个个个临时变量的值值语句语句的位置的位置来引用该临时变量表来引用该临时变量表三地址代码的实现三地址代码的实现(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2opP172. 表表7.4(b) 三地址语句的三元式表示三地址语句的三元式表示三元式中使用了指向三元式语句的指针三元式中使用了指向三元式语句的指针( (序号序号) )，序号也表示该三元式计算的

25、结果值序号也表示该三元式计算的结果值, , 三元式之间三元式之间 的联系通过的联系通过指针指针实现。实现。三地址代码实现：三元式三地址代码实现：三元式 a:=ba:=b* *-c+b-c+b* *-c -c 三地址代码实现：三地址代码实现：(0)(1)(2)(3)uminus*+assigncb(1)aarg1(0)(1)(2)arg2op三元式表三元式表(0)(1)(0)(1)(2)(3)间接代码间接代码三元式表中没有了重复的三元式，语句的移三元式表中没有了重复的三元式，语句的移动仅改变左边的间接码表。动仅改变左边的间接码表。另外的例见另外的例见P173.表表7.6。间接三元式（三元式的指针

26、表）间接三元式（三元式的指针表）不直接只用三元式表，而是另外设一张指示器表不直接只用三元式表，而是另外设一张指示器表(间接码表间接码表)间接三元式间接三元式a:=b*-c+b*-c 写中间语言：练习写中间语言：练习n写出表达式：写出表达式：A+B*(C-D)-E/(F-G) 的逆波兰表示、三元式表示、四元式表示。的逆波兰表示、三元式表示、四元式表示。n解解: 四元式表示四元式表示：( - , C , D , T1 ) (* , B , T1, T2 ) ( + , A , T2, T3 ) (- ,F , G , T4 ) ( / , E, T4, T5 ) ( - , T3, T5, T6

27、)n解解: 三元式表示三元式表示：( - , C , D )(* , B , )( + , A , ) (- ,F , G ) ( / , E, ) ( - , , )n解：解：逆波兰表示逆波兰表示： ABCD -*+EFG-/ -* * 7.2 说明语句说明语句n当考察一个过程或分程序的一系列说明语句时，当考察一个过程或分程序的一系列说明语句时，便可便可为局部于该过程的名字分配存储空间为局部于该过程的名字分配存储空间。n对每个局部名字，将对每个局部名字，将在符号表中建立相应的表在符号表中建立相应的表项项，并填入相应的信息如类型、嵌套深度、相，并填入相应的信息如类型、嵌套深度、相对地址等。对地

28、址等。n说明语句的翻译目的就是说明语句的翻译目的就是建立符号表建立符号表。局部变量局部变量地址增加地址增加相对地址相对地址基地址基地址 相对地址相对地址是指相是指相对数据区基地址对数据区基地址的一个偏移量。的一个偏移量。如图所示：如图所示：符号表的结构和组织符号表的结构和组织(参见参见CH.8)n符号表结构例符号表结构例, P235. FORTRAN语言的语言的SD表结构。表结构。 名 字 属 性 地 址种属维数/形参个数类型 数据区号 相对地址 a局部变量算型 1 20 b数组 2实型 2 100 p过程 1n符号表的组织符号表的组织: 指各表项的安排指各表项的安排n线性表线性表: 顺序要、

29、查表顺序要、查表n二叉树：按序要表，对折查找二叉树：按序要表，对折查找n杂凑技术：根据杂凑技术：根据HASH( )函数值要、查表函数值要、查表sortnilheaderaxreadarrayexchangequicksortheaderexchangeheaderkvpartitionquicksortheaderijpartitioniheaderreadarrayto readarrayto exchangeP176. 嵌套过程的程序例子嵌套过程的程序例子P176. 图图7.7 嵌套过程的符号表嵌套过程的符号表(5个个过程过程, 5张表张表, 表式间的联系表式间的联系)P177. 图图7.

30、8 处理嵌套过程中的说处理嵌套过程中的说明语句的翻译模式明语句的翻译模式说明语句翻译的例子说明语句翻译的例子7.3 赋值语句的翻译赋值语句的翻译n本节讨论的赋值语句，其表达式类型可以是整本节讨论的赋值语句，其表达式类型可以是整型、实型、数组和记录。型、实型、数组和记录。n赋值语句的翻译将讨论赋值语句的翻译将讨论如何在符号表中查找名如何在符号表中查找名字字及及如何存取数组和记录的元素如何存取数组和记录的元素。n本节只介绍本节只介绍7.3.1和和7.3.2小节。小节。n7.3.1 简单算术表达式及赋值语句的翻译简单算术表达式及赋值语句的翻译n图图7.10的翻译模式表的翻译模式表赋值语句翻译为三地址

31、代码赋值语句翻译为三地址代码n7.3.2 数组元素引用的翻译数组元素引用的翻译n一维、二维数组元素地址计算一维、二维数组元素地址计算n含有数组元素引用的赋值语句的翻译含有数组元素引用的赋值语句的翻译n含简单变量的赋值语句，如含简单变量的赋值语句，如id := E，其中，其中，id为普为普通变量，而通变量，而E是简单的算术表达式。是简单的算术表达式。 7.3.1 简单算术表达式及赋值语句简单算术表达式及赋值语句文法定义如下：文法定义如下：S id := EE E1 + E2E E1 * E2E - E1E ( E1 )E id式要的语义过程式要的语义过程 1. E的属性定义：的属性定义： E.p

32、lace : 存放表达式存放表达式E“值值”2. newtemp ： 获取临时变量以存获取临时变量以存 放中间结果放中间结果3. emit 产生三地址码的过程表产生三地址码的过程表4. lookup( name ) 检查检查name是是否在符号表中有定义（条目）否在符号表中有定义（条目）n式要的语义变量式要的语义变量 E EPLACEPLACE：与非终结符：与非终结符E E相联系的语义变量相联系的语义变量n值为某变量的符号表入口地址或临时变量序号。值为某变量的符号表入口地址或临时变量序号。 n它与文法的非终结符相联，分析过程需要就建立，它与文法的非终结符相联，分析过程需要就建立，不需要就消亡。

33、不需要就消亡。n例例. 翻译赋值语句翻译赋值语句 x := -a+b*c 为三地址代码为三地址代码n自下而上语法制导翻译，结合自下而上语法制导翻译，结合图图7.10 理解理解赋值语句和算术表达式翻译：例赋值语句和算术表达式翻译：例n三地址语句三地址语句: 查表查表查表查表id(x) := E.placeSE.place + E.place id(a )E.place * E.place E. placeid(c )id(b) 查表查表生成生成生成生成生成生成查表查表, 生成生成 T1:=uminus a T2:=b*c T3:=T1+T2 x:=T3n翻译赋值语句翻译赋值语句 x := -a+

34、b*(-c+d)/e 为三地址代为三地址代码。掌握码。掌握手工生成赋值句的三地址代码手工生成赋值句的三地址代码的方的方法：按运算顺序写出三地址语句。法：按运算顺序写出三地址语句。赋值语句和算术表达式翻译：练习赋值语句和算术表达式翻译：练习n三地址语句序列三地址语句序列: T1:=uminus a T2:=uminus c T3:=T2+d T4:=b*T3 T5:=T3/e T6:=T1+T2x:=T67.3.2 数组元素的引用数组元素的引用n一数组及其下标变量地址的计算一数组及其下标变量地址的计算n1. 数组分类数组分类： 一维数组、二维数组、多维数组；一维数组、二维数组、多维数组；n2.

35、多维数组的存放多维数组的存放n 按行存放按行存放n 按列存放按列存放(FORTRAN)n 只要知道数组的首地址，及每个数组元素占多只要知道数组的首地址，及每个数组元素占多少少内存单元，就可计算出任一数组元素的地址；内存单元，就可计算出任一数组元素的地址； 7.3.2 数组元素的引用数组元素的引用n数组元素引用的关键问题数组元素引用的关键问题: 数组元素地址的计算数组元素地址的计算，由数组的存放方式决定，由数组的存放方式决定n翻译时要产生翻译时要产生计算数组元素地址的中间代码。计算数组元素地址的中间代码。n以后都假定：数组的元素存放在一片连续存储以后都假定：数组的元素存放在一片连续存储单元中，按

36、行存放，数组的每个元素宽度为单元中，按行存放，数组的每个元素宽度为w。一维数组元素地址计算一维数组元素地址计算-牢记牢记n设一维数组：设一维数组：A low : high n一维数组元素一维数组元素Ai 的相对地址为：的相对地址为： base + (i low)*w (7.4) 其中：其中：low为数组下标的下界，为数组下标的下界， high为数组下标的上为数组下标的上界，界， base是数组的起始地址，即是数组的起始地址，即base为为A的第一个元的第一个元素素Alow的相对地址。的相对地址。n(7.4)式可以算理为：式可以算理为： i*w + (base low*w) 其中：其中：i*w

37、是随数组下标变量是随数组下标变量 i 而变化的部分表而变化的部分表 base low*w 是在数组元素地址计算公式中不是在数组元素地址计算公式中不变化的常数变化的常数, 常记常记 C = base low*w。 二维数组元素地址计算二维数组元素地址计算-牢记牢记n设二维数组：设二维数组：A low1 : high1low2 : high2 每维每维 的长度的长度( n1、n2) ni = highilowi +1 P180. n二维二维数组元素数组元素A i1i2 的相对地址计算公式：的相对地址计算公式： base( i1 low1 )* n2 (i2 low2)*w 可整理为：可整理为： b

38、ase(low1 *n2low2)*w ( i1*n2 i2)* w (7.5) n(7.5)分出地址不变部分和地址变化部分。常记分出地址不变部分和地址变化部分。常记 C=(low1 *n2low2)*wnC值值在处理数组说明时即可以计算出来在处理数组说明时即可以计算出来, 与数组元素与数组元素的下标无关的下标无关, 是一个定数是一个定数, C值可放在符号表数组值可放在符号表数组A的的表项中表项中, 或或数组内情向量数组内情向量中。中。k维数组元素地址计算维数组元素地址计算n一般一般, 对于一个对于一个 k维数组维数组 P180. A low1 : high1 , lowk : highk 若

39、按行存放，数组的每个元素的宽度为若按行存放，数组的每个元素的宽度为 w 各维的长度各维的长度 ni = highilowi +1 则数组元素则数组元素 A i1, i2 , , ik 的相对地址计算：的相对地址计算： D = base C + 变化部分变化部分 (7.6) 变化部分变化部分 =(.(i1*n2+ i2)* n3+ i3 ).)* nk + ik )*w C=(.(low1* n2 + low2)* n3 + low3 ).)* nk + lowk) * w (7.7) 静态数组静态数组, 动态数组动态数组n静态数组：静态数组：n数组说明中各维的上下界是确定的数组说明中各维的上下

40、界是确定的nC值在编译的时候就能计算出来值在编译的时候就能计算出来n动态数组：动态数组：n数组说明中各维的上下界有不确定的数组说明中各维的上下界有不确定的nC值在编译的时候不能计算出来值在编译的时候不能计算出来, 运行时才运行时才能计算能计算n计算动态数组元素地址的公式与静态数组是同计算动态数组元素地址的公式与静态数组是同样的，只是上、下界在编译时是未知的。样的，只是上、下界在编译时是未知的。n数组元素引用的文法数组元素引用的文法: P181. L id Elist | id L表示简单变量或数组元素表示简单变量或数组元素 Elist Elist,E | E Elist表示下标列表表示下标列表

41、 Elist + i1, i2, , inn数组元素地址变化部分数组元素地址变化部分: (i1*n2+i2)*n3+i3)*n4+ nj := highj lowj + 1 (7.8) 递归公式递归公式 em = em-1 * nm + im (7.9)n为了从符号表获值有关数组各维长度为了从符号表获值有关数组各维长度 nj 的信息，改的信息，改写文法为：写文法为： LElist | id ElistElist , E | id E 让数组名与第一个下标联系让数组名与第一个下标联系设计数组元素引用的文法设计数组元素引用的文法n P181. 数组元素引用的文法数组元素引用的文法: (1) SL

42、: E S 赋值赋值 语句语句 (2) EEE E 表达式表达式, 可含数组元素可含数组元素 (3) E(E) (4) EL (5) LElist L 数组元素数组元素 (6) Lid L 简单变量简单变量 (7) ElistElist , E Elist 带数组名的下标表带数组名的下标表 (8) Elistid E n参见参见P181.183. 包含数组元素引用的赋值语包含数组元素引用的赋值语句的翻译模式句的翻译模式。数组元素引用的文法及翻译模式数组元素引用的文法及翻译模式n有关变量与函数的说明：有关变量与函数的说明：Elist.ndim 综合属性综合属性：记录：记录Elist中的下标表中的

43、下标表达式的个数，即维数达式的个数，即维数;函数函数limit(array, j)：返回返回nj ，即由即由array所指所指示的数组的第示的数组的第j维长度维长度;Elist.place：临时变量，用来临时存放由临时变量，用来临时存放由Elist 中的下标表达式计算出来的值中的下标表达式计算出来的值: em=em-1*nmElist. Array 综合属性综合属性：数组名数组名的符号表地址的符号表地址;过程过程 emit( ) 产生一条三地址语句产生一条三地址语句;数组元素引用的翻译模式：说明数组元素引用的翻译模式：说明(1)L.place, L.offset : 描述描述 L的左值的情况。

44、的左值的情况。n若若 L 为简单变量为简单变量, 则则 L.place为符号表指为符号表指针针, 而而L.offset 为为 null; n若若L为数组为数组, 则则 L.place 存放数组元素地存放数组元素地址的不变部分的值址的不变部分的值, L.offset 存放地址的存放地址的变化部分的值变化部分的值, L表示的数组元素的地址表示的数组元素的地址为为: L.placeL.offset。 相应相应语义动作语义动作: 若若L是一个简单变量的名字，是一个简单变量的名字，则生成一般的赋值则生成一般的赋值; 若若L为数组元素引用，则为数组元素引用，则生成对生成对L所指示的数组元素地址的索引赋值。

45、所指示的数组元素地址的索引赋值。数组元素引用的翻译模式：说明数组元素引用的翻译模式：说明(2)手工生成数组元素引用的代码手工生成数组元素引用的代码n1. 先确定先确定: 数组维数数组维数k; 宽度宽度w; 各维的下界各维的下界Lowj, 上上界界highj, 计算各维长度计算各维长度nj; 数组首地址数组首地址(不同的数组不同的数组用不同的符号用不同的符号, 比如比如A数组用数组用A表示表示); 计算出常数计算出常数Cn一维数组一维数组 C=Low*wn二维数组二维数组 C=(low1*n2+low2)*wn2. 对一维数组元素对一维数组元素Ai产生产生2个地址计算的三地址语个地址计算的三地址

46、语句句: T1 := w*i T2 := AC 地址表示地址表示T2T1 n3. 对二维数组元素对二维数组元素Ai,j产生产生4个地址计算的三地址个地址计算的三地址语句语句: T1 := i* n2 T2 := AC T1 := T1+j T3 := w*T1 地址表示地址表示T2T3 数组元素引用的代码结构数组元素引用的代码结构n例例, 赋值语句赋值语句 x := Ai1, i2的的 三地址代码结构：三地址代码结构： T1 := Ai1, i2的地址变化部分的计算值的地址变化部分的计算值 T2 := base-C Ai1, i2地址的不变部分值地址的不变部分值 T3 := T2T1 x :=

47、 T3n例例, 赋值语句赋值语句Ai1, i2 := E 的的 三地址代码结构：三地址代码结构： T1 := Ai1, i2的地址变化部分的计算值的地址变化部分的计算值 T2 := base-C Ai1, i2地址的不变部分值地址的不变部分值 T3 := 表达式表达式E的值的值 T2T1 := T3 n例例7.1 设设A为一个为一个10*20的二维数组的二维数组 P183. 即设即设 A1:10, 1:20, n1= 10, n2= 20; w4； 数组第一个元素数组第一个元素 为为 A1, 1 则计算则计算C值值 = (low1*n2low2)*w=(1*201)*484n使用使用P1811

48、83.的翻译模式的翻译模式, 对赋值语句对赋值语句 x := Ay,z 进行翻译，带注释的分析树如进行翻译，带注释的分析树如 P183.图图7.12所所示。考虑结合自下而上分析的一遍扫描语法示。考虑结合自下而上分析的一遍扫描语法制导翻译。制导翻译。带数组元素引用的赋值语句的翻译例带数组元素引用的赋值语句的翻译例例例7.1 7.1 x := Ay, zx := Ay, z的带注释的分析树的带注释的分析树L.place = xL.offset = nullL.place = T2L.offset = T3E.place = T4Elist.place = T1Elist.ndim = 2Elist

49、.array = AS:=x 4 1 6 5 7图图7.127.12结合翻译模式理解结合翻译模式理解第第7步产生步产生2条条, 第第8步产生步产生2条条, 第第9步产步产生生1条条, 10步产生步产生1条条Elist.place = yElist.ndim = 1Elist.array = A,L.place = zL.offset = nullE.place = zAzyL.place = yL.offset = nullE.place = yElist(place=T1,ndim=2,array=A) 7 4 6 8 4 6(续上页）续上页）x := Ay, zx := Ay, z在第在第

50、7, 8, 9, 10步归步归约时产生计算数组元约时产生计算数组元素地址的代码素地址的代码数组元素的引用翻译数组元素的引用翻译: 例例7.1n赋值语句赋值语句 x := Ay, z 在自下而上的分析中被在自下而上的分析中被翻译成如下三地址语句序列：翻译成如下三地址语句序列：P183. T1 := y*20 T1 := T1z T2 := A-84 T3 : = 4*T1 T4 := T2T3 x : = T4 n 注意：注意：20(第第2维长度维长度)、84(C值值)、4(宽度宽度)都是都是编译中引入的常量编译中引入的常量, 用用A代表数组的首地址。代表数组的首地址。 7地址的变化部分计算地址

51、的变化部分计算: *,+ 5地址的不变部分地址的不变部分: base-C地址的变化部分地址的变化部分(乘宽度乘宽度w) 4从数组元素地址取数从数组元素地址取数 1赋值赋值手工生成数组元素引用的代码：例手工生成数组元素引用的代码：例n翻译翻译 Ai+2, j+1:=M+Bk 为三地址代码为三地址代码 设设 A数组数组 A1:10,1:20; w=4; 数组首地址数组首地址 A; CA=(1*20+1)*4=84 设设 B数组数组 B1:10; w=4; 数组首地址数组首地址B; CB=1*4=4n三地址语句三地址语句: T1:=i+2 T5:=4*k T2:=j+1 T6:=B4 T1:=T1*

52、20 T7:=T6T5 变址取数变址取数 T1:=T1+T2 T7:=M+T7 T3:=A84 T3T4:=T7 变址存数变址存数 T4:=4*T1计算下标值计算下标值一维一维 Bk二维二维Ai+2,j+1数组元素引用翻译数组元素引用翻译: 练习练习1n设二维数组设二维数组A1:10,1:20，则，则 n1=10, n2=20表表设设 W=2n(1) 赋值语句赋值语句 X:= AI, J 的三地址代码序列表的三地址代码序列表n(2) 赋值语句赋值语句AI+2, J+1 := M+N三地址代码。三地址代码。 ( (1) 1) 解：解：C = 42C = 42 T1 := IT1 := I* *2

53、020 T1 := T1+J T1 := T1+J T2 := A-42 T2 := A-42 T3 := T1 T3 := T1* *2 2 T4 := T2T3 T4 := T2T3 X := T4 X := T4(2) (2) 解：解： C = 42C = 42 T1 := I+2T1 := I+2 T2 := J+1 T2 := J+1 T3 := T1 T3 := T1* *20 20 T3 := T2+T3 T3 := T2+T3 T4 := A-42 T4 := A-42 T5 := T3 T5 := T3* *2 2 T6 := M+N T6 := M+N T4T5 := T6

54、 T4T5 := T6数组元素引用翻译数组元素引用翻译: 练习练习2n(3) 赋值语句赋值语句 X:= AI, J 的四元式序列表的四元式序列表n(4) 赋值语句赋值语句AI+2, J+1 := M+N四元式序列。四元式序列。(3) 解解 ： C = 42 ( *，I, 20, T1 ) ( +, J, T1, T1 ) ( - ,A, 42, T2 ) ( * ,T1, 2, T3) ( = , T2T3,_,T4 ) ( := , T4 ,_,X )(4) 解：解： C = 42 ( + , I , 2 , T1 ) ( + , J , 1 , T2 ) ( * , T1, 20 , T3

55、 ) ( + , T2 , T3 , T3 ) ( - , A, 42 , T4 ) ( * ,T3, 2, T5) ( + , M, N ,T6 ) ( =, T6, _,T4T5 )7.4 布尔表达式的翻译布尔表达式的翻译n布尔表达式是用布尔运算符号布尔表达式是用布尔运算符号and、 or、not 作用到布尔变量或关系表达式上而组成的。作用到布尔变量或关系表达式上而组成的。n关系表达式形式如关系表达式形式如 E1 relop E2 , 其中其中E1 和和E2是算术表达式，是算术表达式， relop为关系运算符为关系运算符: ,=, , =, 。n程序设计语言中程序设计语言中, 布尔表达式有

56、两个基本作用布尔表达式有两个基本作用： n一个是用作计算逻辑值一个是用作计算逻辑值(真真1, 假假0)n另一个是用作控制流语句如另一个是用作控制流语句如 if-then、if-then-else和和 while-do等中的条件表达式等中的条件表达式布尔表达式的文法布尔表达式的文法n本节中考虑由下列文法产生的布尔表达式：本节中考虑由下列文法产生的布尔表达式： EE or E | E and E | not E | (E) | id relop id | idn使用使用 relop 的的 属性属性relop.op 来确定来确定 relop 所指所指的的6种关系运算中的哪一个。种关系运算中的哪一个。

57、n假定按惯例确定假定按惯例确定and,、or 、not 的优先级和结的优先级和结合性。合性。注意: 此id表示布尔量布尔表达式的语义布尔表达式的语义n布尔式的语义布尔式的语义是指明计算一个逻辑值的规则是指明计算一个逻辑值的规则, 有两种计算规则有两种计算规则: n 1. 用数值用数值(1/0)表示真和假表示真和假, 同计算算术表达同计算算术表达式一样式一样, 一步不差地按序计算出整个布尔式一步不差地按序计算出整个布尔式的值。的值。 例如例如: 计算计算 1 or (not 0 and 0) or 0 =1n2. 优化优化(短路短路)方法，不一定一步不差的计算，方法，不一定一步不差的计算，可以由

58、某个子布尔式的值确定整个布尔式可以由某个子布尔式的值确定整个布尔式的值。的值。布尔表达式的计值规则布尔表达式的计值规则n规则规则2 2用于翻译控制流语句中的布尔表达式尤用于翻译控制流语句中的布尔表达式尤其方便其方便计算计算 E E1 E2 or = 真真 真真 真真 假假 假假 假假 计算计算 E E1 E2 and = 真真 真真 真真 假假 假假 假假 解释为解释为: if E1 then true else E2解释为解释为: if E1 then E2 else false7.4.1 数值表示法数值表示法n首先考虑用首先考虑用1表示真表示真，用，用0表示假表示假来实现布尔来实现布尔表达

59、式的翻译。表达式的翻译。n1. 类似算术表达式求值方法计算布尔式值类似算术表达式求值方法计算布尔式值 例例: a or b and not c 翻译为翻译为: T1 := not c T2 :=b and T1 T3 :=a or T2 n注意注意: 此布尔式中的此布尔式中的a, b, c是逻辑量是逻辑量(值值0/1)!数值表示法：数值表示法：第第2 2种方法求布尔式值种方法求布尔式值n一个形如一个形如 abab的关系表达式可等价的写成的关系表达式可等价的写成: : if ab then 1 else 0 if ab then 1 else 0 并将它翻译成如下三地址语句序列：并将它翻译成如下

60、三地址语句序列： 100 100 if if abab goto 103 goto 103 101 T:=0 101 T:=0 102 goto 104 102 goto 104 103 T:= 1 103 T:= 1 104 104n逻辑量逻辑量 a a也作同样翻译，只要将也作同样翻译，只要将 ab ab 换为换为 a a。nP186.图图7.13 7.13 布尔式的数值表示法的翻译模式布尔式的数值表示法的翻译模式 nP187.例例7.2 翻译布尔式翻译布尔式 ab or cd and ef 100 if ab goto 103 108 if ef goto 111 101 T1:=0 10