第六章语法制导译 在前面已经介绍了编译程序构造的二个重要阶段,即词 法分析和语法分析。现在再来介绍编译程序的另一个重要阶 段 中间代码生成。虽然在实际应用中,是否采用中间代 码形式是根据实际情况而定的。但事实上,为了使编译程序 的结构清晰、简单、明确,多数编译程序采用了中间代码的 形式。尤其是使用了中间代码的形式,使目标代码优化比较 容易实现。通常以中间代码生成这一阶段来划分编译程序的 前端和后端。对于不同的高级语言只要翻译成相同的中间代 码,再接上一个相同的把中间代码翻译成目标代码的后端」 就可以形成不同的编译程序。同一种高级语言只要翻译成相 同的中间代码就可以共用一个前端,接上后端可以在不同机 型上实现同一语言的编译程序。虽然中间代码的形式很多, 但常见的中间代码有逆波兰式、三元式、四元式、树形表示 等。本章讨论如何将高级语言翻译成中间代码
第六章 语法制导译 在前面已经介绍了编译程序构造的二个重要阶段，即词 法分析和语法分析。现在再来介绍编译程序的另一个重要阶 段——中间代码生成。虽然在实际应用中，是否采用中间代 码形式是根据实际情况而定的。但事实上，为了使编译程序 的结构清晰、简单、明确，多数编译程序采用了中间代码的 形式。尤其是使用了中间代码的形式，使目标代码优化比较 容易实现。通常以中间代码生成这一阶段来划分编译程序的 前端和后端。对于不同的高级语言只要翻译成相同的中间代 码，再接上一个相同的把中间代码翻译成目标代码的后端， 就可以形成不同的编译程序。同一种高级语言只要翻译成相 同的中间代码就可以共用一个前端，接上后端可以在不同机 型上实现同一语言的编译程序。虽然中间代码的形式很多， 但常见的中间代码有逆波兰式、三元式、四元式、树形表示 等。本章讨论如何将高级语言翻译成中间代码
61中间代码的形式 中间代码的形式虽然很多,但组成中间代码的原则是: (1)形式比较简单,容易翻译成相应的目标机器代码 (2)能充分反映源程序的特点 比较常用有逆波兰式、三元式、四元式和树型表示。 6.11逆波兰式 逆波兰式是由波兰数学家卢卡西维奇发明的一种表示算 术表达式或逻辑表达式的方法,它是一种能表示运算符的计 算顺序,但没有括号的表达式。在这种表示法中,把运算符 直接跟在运算对象后面,因此逆波兰表示法又称后缀表示法
6.1 中间代码的形式 中间代码的形式虽然很多，但组成中间代码的原则是： (1) 形式比较简单，容易翻译成相应的目标机器代码 (2) 能充分反映源程序的特点 比较常用有逆波兰式、三元式、四元式和树型表示。 6.1.1 逆波兰式 逆波兰式是由波兰数学家卢卡西维奇发明的一种表示算 术表达式或逻辑表达式的方法，它是一种能表示运算符的计 算顺序，但没有括号的表达式。在这种表示法中，把运算符 直接跟在运算对象后面，因此逆波兰表示法又称后缀表示法
逆波兰表示法的格式为: 例如:表达式(a+b*c/()e-f的逆波兰式为 abcd/ te*f 从上可以看出,逆波兰式具有下列性质: 1)在中缀式和逆波兰式中,运算对象是按相同的顺序出现 2)在逆波兰式中,运算符是按计算顺序(从左到右)出现 3)运算符紧跟在其运算对象后面出现的
逆波兰表示法的格式为： 例如：表达式(a+b*c/d)*e-f的逆波兰式为： abc*d/+e*f- 从上可以看出，逆波兰式具有下列性质： (1) 在中缀式和逆波兰式中，运算对象是按相同的顺序出现 的 (2) 在逆波兰式中，运算符是按计算顺序（从左到右）出现 的 (3) 运算符紧跟在其运算对象后面出现的
当逆波兰式允许单目运算符(仅允许一个运算对象的运 算符)出现时,会产生一些问题。如写出表达式a+(-bcd)*e 的逆波兰式为ab-cd/e*,此时很难区分运算符-是单目的还是 双目的。即先计算a-b还是-b。解决上述问题的方法有二种: (1)把单目运算符改成双目,如改写成:a0b-cd/e* (2)引进新的运算符为@,如:ab@cd/"e* 其它单元目的运算符可参照上述方法处理。对于第一种方法 把单目运算符处理成双目运算符增加了运算的时间,降低 工作效率。对于第二种方法,要解决的问题是如何把符号 处理成不同的符号。处理的时机可以放在词法分析中解决, 如在表达式的起始位(如赋值号后、逗号后、左括号后等) 设置标记19为1,即单元且运算符,在遇到运算对象后设置 标记fag为0,即双目运算符
当逆波兰式允许单目运算符（仅允许一个运算对象的运 算符）出现时，会产生一些问题。如写出表达式a+(-b*c/d)*e 的逆波兰式为ab-cd/*e*,此时很难区分运算符-是单目的还是 双目的。即先计算a-b还是-b。解决上述问题的方法有二种： (1) 把单目运算符改成双目，如改写成：a0b-cd/*e* (2) 引进新的运算符为@，如：ab@cd/*e* 其它单元目的运算符可参照上述方法处理。对于第一种方法， 把单目运算符处理成双目运算符增加了运算的时间，降低了 工作效率。对于第二种方法，要解决的问题是如何把符号‘- ’处理成不同的符号。处理的时机可以放在词法分析中解决， 如在表达式的起始位（如赋值号后、逗号后、左括号后等） 设置标记flag为1，即单元目运算符，在遇到运算对象后设置 标记flag为0，即双目运算符
计算逆波兰式表示的算术或逻辑表达式比计算中缀式要 简单。这是因为计算逆波兰式不要比较运算符的优先级,只 要一遇到运算符就立即可以计算。具体实现中只要用一个栈 来存放运算对象,故该栈又称运算对象栈或运算分量栈。在 栈中存放未被计算的运算对象 旦扫描到运算符时,就 从栈中取出运算符所需的运算对象个数进行计算。然后再将 计算结果放入栈中,当全部扫描完逆波兰式后栈顶元素即为 最后的计算结果。 般算法语言除了算术表达式和逻辑表达式外,还有其 它如赋值语句、条件语句、循环语句等,但只要遵守运算对 象后直接紧跟计算它们的运算符这一规则,就可以很方便地 将逆波兰式扩充到整个算法语言。 例如,赋值语句:三可改写为:三; GOTO L改写成Lmp(其中jmp表示转移的运算符, L表示逆波兰式的编号或地址)
计算逆波兰式表示的算术或逻辑表达式比计算中缀式要 简单。这是因为计算逆波兰式不要比较运算符的优先级，只 要一遇到运算符就立即可以计算。具体实现中只要用一个栈 来存放运算对象，故该栈又称运算对象栈或运算分量栈。在 栈中存放未被计算的运算对象，当一旦扫描到运算符时，就 从栈中取出运算符所需的运算对象个数进行计算。然后再将 计算结果放入栈中，当全部扫描完逆波兰式后栈顶元素即为 最后的计算结果。 一般算法语言除了算术表达式和逻辑表达式外，还有其 它如赋值语句、条件语句、循环语句等，但只要遵守运算对 象后直接紧跟计算它们的运算符这一规则，就可以很方便地 将逆波兰式扩充到整个算法语言。 例如，赋值语句 :=可改写为:= ；GOTO L 改写成L jmp （其中jmp 表示转移的运算符， L表示逆波兰式的编号或地址）
对于条件语句: E then s1,ese,S2可以考虑三目运 算符,如ES1S2f但这种表示方法当执行到运算符i时,E S1、S2三个运算对象已经全部计算过可或执行了,由于构造 的逆波兰式都是从左到右执行的,此时很难再回到前面去重 新执行或跳过相应的逆波兰式。为此可以用二目条件转移来 表 Esop S1分别 天S2的开始位置和跟在之后那个号的位置。利mp分 别为条件和无条件转运算符。类似可以引进条件转移的逆波 其中是算术值或逻辑值,是逆波兰 的某个编号或位置;可以是、j、je、ige、j、 jnz等,分别表示小于、大于、小于等于、大于、等于、不等 于等转移的运算符
对于条件语句：if E then S1 else S2 可以考虑三目运 算符if，如ES1S2 if。但这种表示方法当执行到运算符if时，E、 S1、S2三个运算对象已经全部计算过可或执行了，由于构造 的逆波兰式都是从左到右执行的，此时很难再回到前面去重 新执行或跳过相应的逆波兰式。为此可以用二目条件转移来 表示：Ejz S1jmpS2，其中，、分别 为S2的开始位置和跟在S2之后那个符号的位置。jz和jmp分 别为条件和无条件转运算符。类似可以引进条件转移的逆波 兰式为： 其中是算术值或逻辑值，是逆波兰 的某个编号或位置；可以是jl、jg、jle、jge、jz、 jnz等，分别表示小于、大于、小于等于、大于、等于、不等 于等转移的运算符
当然用同样的方式,还可以将逆波兰式扩充至数组、记录或 其它数据类型,也可将fo语句、 While语句、case语句扩充 至逆波兰式。另外需要指出的是:赋值运算符和其它逆波兰 式不一样,它要把的值放入,在栈中只需要 变量的地址,而不是值,计算赋值运算符后不要将结果入栈 例:写出语句ia> b and bbc< and 21 jz x53 d *4 /+:=28 202122232425262728 jmp y 6 y 8
当然用同样的方式，还可以将逆波兰式扩充至数组、记录或 其它数据类型，也可将for语句、while语句、case语句扩充 至逆波兰式。另外需要指出的是：赋值运算符和其它逆波兰 式不一样，它要把的值放入，在栈中只需要 变量的地址，而不是值，计算赋值运算符后不要将结果入栈。 例:写出语句 if a>b and b b c < and 21 jz x 5 3 d * 4 / + := 28 20 21 22 23 24 25 26 27 28 jmp y 6 y 8 * - :=
6.1.2三元式和树 中间代码的另一种表示法为三元式,三元式的形式为 (,) 其中:分别表示变量、常量或三元 式的结果等。 例如,表达式a+(-b*c+d)e的三元式序列为: 运算符运算对象运算对象 (2)( (3)(+,(2),d ))) (4)(*,(3) (5)(+ a 其中:(1)、(2)、(3)、(4)分别为第1、第2、第3、 第4条三元式的结果。整个表达式的结果可用(5)表示
6.1.2 三元式和树 中间代码的另一种表示法为三元式，三元式的形式为： （ , , ） 其中： 分别表示变量、常量或三元 式的结果等。 例如，表达式a+(-b*c+d)*e的三元式序列为： 运算符 运算对象 运算对象 （1）（ - , b , _ ） （2）（ * , (1) , c ） （3）（ + , (2) , d ） （4）（ * , (3) , e ） （5）（ + , a , (4) ） 其中：（1）、（2）、（3）、（4）分别为第1、第2、第3、 第4条三元式的结果。整个表达式的结果可用（5）表示
下面把三元式扩充到其它表示 〔imp,,p)表示无条件转向第p条三元式执行 表示当a小于0时转向第p条三元式执行,否则执行 三元式 9ap),表示当a大于0时转向第p条三元式执行,否则执 行下一条三元式 ile, a 执 侣下 表示当a小于等于0时转向第p条三元式执行,否 条三元式 好得一素至大于等于0时转向第D条三元式行,否 华已 表示当a等于0时转向第p条三元式执行,否则执行 三元式 (nz 表示当a不等于0时转向第p条三元式执行,否则 为行 条三元式
下面把三元式扩充到其它表示。 (jmp,_,p) 表示无条件转向第p条三元式执行 (jl,a,p) 表示当a小于0时转向第p条三元式执行，否则执行 下一条三元式 (jg,a,p) 表示当a大于0时转向第p条三元式执行，否则执 行下一条三元式 (jle,a,p) 表示当a小于等于0时转向第p条三元式执行，否 则执行下一条三元式 (jge,a,p) 表示当a大于等于0时转向第p条三元式执行，否 则执行下一条三元式 (jz,a,p) 表示当a等于0时转向第p条三元式执行，否则执行 下一条三元式 (jnz,a,p) 表示当a不等于0时转向第p条三元式执行，否则 执行下一条三元式
下面介绍用树来表示算术表达式。用树来表示中间代 码需要用两个指针分别指向它的左子树和右子树。如果e1 和e2是表达式,其相应的树用T1和T2表示,则e1+e2、e e2、e1e2、e1e2和-e1的树如图 T T2 T, T x e
下面介绍用树来表示算术表达式。用树来表示中间代 码需要用两个指针分别指向它的左子树和右子树。如果e1 和e2是表达式，其相应的树用T1和T2表示，则e1+e2、e1 - e2、e1*e2、e1 /e2和-e1的树如图