第8章 语法制导翻译和中间代码生成.ppt

第8章语法制导翻译和中间代码生成 8 1概述 一 语义处理的任务 根据语义规则对识别出的各种语法成分析其含义 进行初步翻译 生成相应的中间代码或直接生成目标代码 第一静态语义分析或静态审查 第二动态语义处理 编译中的语义处理是指两个功能 类型检查 控制流检查 确保控制语句有合法的转向点 一致性检查 相关名字检查 名字的作用域分析 第一 静态语义分析通常包括 如果静态语义正确 语义处理则要执行真正的翻译 即 或者将源程序翻译成程序的一种中间表示形式 中间代码 或者将源程序翻译成目标代码 第二动态语义处理 实际应用中比较流行的语义分析方法 基于属性文法的语法制导翻译方法 8 2属性文法 属性文法 属性 所谓属性 用以描述事物或人的特征 性质 品质等等 比如 谈到一个物体 可以用 颜色 描述它 谈起某人 可以使用 有幽默感 来形容他 对一个文法 文法中的每个符号都有属性 可以用 类型 值 或 存储位置 来描述它 附加了一组属性和运算 语义 规则的文法 属性文法 文法符号X的属性t常用X t来表示 语义规则用花括号 括起来 可被插入到产生式右部的任何合适的位置上 不同的产生式对应不同的语义规则不同的分析目标也对应不同的语义规则 语义信息 语义之间的关系 一个属性文法是一个三元组 A G V F G 是一个上下文无关文法V 有穷的属性集 每个属性与文法的一终结符或非终结符相连 F 关于属性的属性断言或谓词集 每个断言与一个产生式相联 一个断言就是一个语义规则 描述各属性的关系 用法 针对语义 为每个符号设置一个属性 终结符号用单词属性 为每个产生式设置语义规则 描述各属性的关系 属性文法的定义 属性分为两种 继承属性和综合属性 综合属性 在语法树中 一个结点的综合属性由该结点的子结点的属性值确定 它的计算规则由底向上 继承属性 在语法树中 一个结点的继承属性由该结点的父结点 兄弟结点的属性确定 例综合属性 计算3 5 4的值 3 5 4的分析树 只使用综合属性 3 5 4的分析树 一个结点的综合属性值是其子结点的某些属性来决定的 通常使用自底向上的分析方法在每个结点处使用语义规则来计算综合属性值当一个产生式获得匹配时 就调用相应的语义子程序从叶结点到根结点进行计算 继承属性 一个结点的继承属性值是由此结点的父结点和 或兄弟结点的某些属性来决定的 例 添加标识符类型的语义描述 继承属性 与L产生式相联的语义规则中有一个过程调用addtype 过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中 句子intid1 id2的语法树 使用表示属性的传递情况 1 文法非终结符既可有综合属性 也可有继承属性 2 开始符号没有继承属性 3 终结符只有综合属性 由词法分析器提供 几点说明 语法制导翻译 将语义规则与语法规则相结合 在语法分析的过程中通过执行语义动作 计算语义属性值 从而完成预定的翻译工作 8 3语法制导翻译 自底向上语法制导翻译 自顶向下语法制导翻译 语法制导翻译的实现 语法制导翻译分为两种处理方法 1 自底向上的翻译 只有综合属性 对每个产生式编制一个语义子程序 在进行语法分析的过程中 当一个产生式获得匹配时 就调用相应的语义子程序实现语义检查与翻译 这种实现方案隐藏了其中语义规则的计算次序等实现细节 不必规定翻译顺序 2 自顶向下翻译 含有继承属性 在产生式右部的适当位置 插入相应的语义动作 即语义规则或语义动作用花括号 括起来 可被插入到产生式右部的任何合适的位置上 按照分析的进程 执行遇到的语义动作 这是一种动作与分析交错的实现方案 语法制导定义 对每个产生式编制一个语义子程序在进行语法分析的过程中 当一个产生式获得匹配时 就调用相应的语义子程序实现语义检查与翻译 自底向上传递信息 自顶向下 自左向右 传递信息 仅包含综合属性的语法制导定义如 算术表达式求值的属性文法 属性定义 S 属性文法 属性定义 L 属性文法 既包括综合属性 又包括继承属性 即对于所有 1 2 n 每一个属性或者都是综合属性 或者 i属性计算仅使用 1 2 i 1的属性其属性可用深度优先的顺序从左至右计算 非L 属性的语法制导定义 产生式 语义规则 A LMA QR L i l A i M i m L s A s f M s R i r A i Q i q R s A s f Q s 表中的语法制导定义不是L 属性定义文法符号Q的继承属性依赖于它右边文法符号R的属性 例如 定义表达式的文法如下 E E EE E E n给出定义表达式值的属性文法 E E1 E2 E val E1 val E2 val E E1 E val E1 val E n E val n lex 属性文法的主要思想有两点 首先对于每个文法符号引进相关的属性符号 其次对于每个产生式写出属性值计算的规则 例一个简单的翻译模式E TRR addopT print addop lexeme R1 T num print num val 输入9 5 2 其分析树如下页图 当按深度优先遍历它 执行遍历中访问的语义动作 将输出 95 2 它是输出表达式9 5 2的后缀式 E T 9 T Pt 9 R Pt Pt R 5 Pt 5 T 2 Pt 2 R 9 5 2的带语义动作的分析树 E TR R addopT print addop lexeme R1 T num print num val 输出 95 2 设计翻译模式 分两种情况 1 只需要综合属性的情况2 既有综合属性又有继承属性 为每一个语义规则建立一个包含赋值的动作 并把这个动作放在相应的产生式右边的末尾 例如 T T1 F T val T1 val F val T T1 F T val T1 val F val 1 只需要综合属性的情况 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 一个动作不能引用这个动作右边符号的属性 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算 计算这种属性的动作通常可放在产生式右端的未尾 2 既有综合属性又有继承属性 下面的翻译模式不满足要求 不满足第1 个条件 S A1A2 A1 in 1 A2 in 2 A a print A in 可以看出 按深度优先遍历输入串aa的语法树 当要打印属性A in时 该属性还没有定义 也就是说 从S开始按深度优先遍历A1和A2子树之前 A1 in和A2 in的值还未赋值 A1 in 1 A2 in 2 Print A in Print A in 如果计算A1 in和A2 in的值的动作分别被嵌入在产生式S A1A2的右部A1和A2之前 而不是后面 那么A in在执行Print A in 时已有定义 S A1 in 1 A1 A2 in 2 A2A a print A in S A1 A2 a a A1 in 1 Print A in Print A in A2 in 2 常见的中间代码形式 后缀式三地址代码 四元式 三元式和间接三元式 图形 抽象语法树等 中间代码 一种介于源语言和目标语言之间的中间语言形式 中间代码 逆波兰记号 逆波兰记号是最简单的一种中间代码表示形式 这种表示法将运算对象写在前面 把运算符号写在后面 比如把a b写成ab 把a b写成ab 用这种表示法表示的表达式也称做后缀式 中缀表示后缀表示a bab a b cabc a b cab c a b c b dabc bd 特点 1 运算对象出现的顺序和原有顺序 从左到右 相同2 运算符按实际计算顺序 从左到右 出现3 运算符紧跟在运算对象的后面出现 且没有括号 优点 简明 便于计值 后缀表示法表示表达式 其最大的优点是易于计算机处理表达式 常用的算法是使用一个栈 自左至右扫描算术表达式 后缀表示 每扫描到运算对象 就把它推进栈 扫描到运算符 若该运算符是二目的 则对栈顶部的两个运算对象实施该运算 并将运算结果代替这两个运算对象而进栈 若是一目运算符 则对栈顶元素执行该运算 并以运算结果代替该元素进栈 最后的结果留在栈顶 例如B CD 它的中缀表示为 B C D 使用 表示一目减 的计值过程为 B进栈 对栈顶元素施行一目减运算 并将结果代替栈顶 即 B置于栈顶 C进栈 D进栈 栈顶两元素相乘 两元素退栈 相乘结果置栈顶 栈顶两元素相加 两元素退栈 相加结果进栈 现在栈顶存放的是整个表达式的值 逆波兰表示很容易扩充到表达式以外的范围 只要遵守运算对象后直接紧跟它们的运算符的规则即可 比如把转语句GOTOL写为 Ljump 运算对象L为语句标号 运算符jump表示转到某个标号L 再比如条件语句ifEthenS1elseS2可表示为 ES1S2 把ifthenelse看成三目运算符 用 来表示 生成后缀式的属性文法 注释 表示代码序列的连接 例 给出下列表达式的逆波兰式 1 a b c 2 a b c d e 解 1 ab c 2 abcde 练习 P2021 另一类中间代码形式是三元式 把表达式及各种语句表示成一组三元式 op ARG1 ARG2 分别是算符op 第一运算对象ARG1和第二运算对象ARG2 运算对象可能是源程序中的变量 也可能是某个三元式的结果 用三元式的编号表示 例如a b c b d的表示为 1 b c 2 b d 3 1 2 4 3 a 三元式和树形表示 例 A B C D E C D N 三元式 1 CD 2 B 1 3 A 2 4 CD 5 4 N 6 E 5 7 3 6 间接三元式 1 CD 2 B 1 3 A 2 4 1 N 5 E 4 6 3 5 间接码表 1 2 3 1 4 5 6 每生成一条指令 先检查已生成的间接三元式序列 若已有 不再生成 只把序号列入间接码表 间接码表明了间接三元式执行的顺序 树形表示是三元式表示的翻版 例 a b c b d可表示成下面的树表示 例表达式 A 12 B 6的语法结构树 将赋值语句变换为语法结构树 基本函数 结点构造Mknode op left right 建标记为op的算符结点 结点有两个域 分别为left和right Mkleaf id entry 建标记为id的叶结点 有一个entry域 它是指向符号表的入口 Mkleaf num val 建标记为id的叶结点 有一个val域 是表示该数的值 构造a 4 c的语法树 1 p1 mkleaf id entrya 2 p2 mkleaf num 4 3 p3 mknode p1 p2 4 p4 mkleaf id entryc 5 p5 mknode p3 p4 语法制导定义 属性文法 E p是语法结构树指针 四元式和三元式的主要不同在于 四元式对中间结果的引用必须通过给定的名字 而三元式是通过产生中间结果的三元式编号 也就是说 四元式之间的联系是通过临时变量实现的 有时 为了更直观 也把四元式的形式写成简单赋值形式或更易理解的形式 比如把a b c b d四元式序列写成 1 t1 b c 2 t2 b d 3 t3 t1 t2 4 a t3把 jump L 写成gotoL把 jrop B C L 写成ifBropCgotoL 请将表达式 a b c d a b 分别表示成三元式 间接三元式和四元式序列 三元式 1 a b 2 c d 3 1 2 4 3 5 a b 6 4 5 间接三元式间接三元式序列间接码表 1 a b 1 2 c d 2 3 1 2 3 4 3 4 5 4 1 1 5 四元式 1 a b t1 2 c d t2 3 t1 t2 t3 4 t3 t4 5 a b t5 6 t4 t5 t6 简单的赋值语句的 四元式 翻译 四元式形式 t arg1oparg2 语义属性 id name E place函数 lookup id name 过程 emit t arg1oparg2 生成一条指令 newtemp 分配一个临时工作单元 1 S id E p lookup id name ifp nilthenEmit p E place elseerror 2 E E1 E2 E place newtemp Emit E place E1 place E2 place 3 E E1 E2 E placeE newtemp Emit E place E1 place E2 place 4 E E1 E Place newtemp Emit E Place uminus E1 place 5 E E1 E Place E1 place 6 E id p lookup id name ifp nilthenE placeE pelseerror 赋值语句的四元式翻译 实际上 在一个表达式中可能出现各种不同类型的变量 而不象前面假定为同一类型 因此 上例应改为P181图8 13的形式 8 3布尔表达式的翻译 程序设计语言中的布尔表达式有两个作用 一是计算逻辑值更多的情况是二 用做改变控制流语句中的条件表达式 如在if then if then else 或是while do语句中那样 布尔表达式是由布尔算符and or和not或表示为 和 施于布尔变量或关系表达式而成 约定优先顺序为 遵循左结合 布尔表达式有两个作用 是计算逻辑值用来改变控制流语句中的条件表达式 布尔表达式的翻译方法 通常 计算布尔表达式的值有两种办法 第一种办法 如同计算算术表达式一样 步步计算出各部分的真假值 最后计算出整个表达式的值 那么布尔表达式1or not0and0 or0的计算过程是 1or not0and0 or0 1or 1and0 or0 1or0or0 1or0 1 用数值1表示true 用0表示false 另一种计算方法是采取某种优化措施 只计算部分表达式 例如要计算AorB 若计算出A的值为1 那么B的值就无需再计算了 因为不管B的值为何结果 AorB的值都为1 如计算AandB若A为假值0 则无需计算B 结果为0 这种计算方法 意味着可以用if then else来解释 和 即 把A B解释成 ifAthentrueelseB把A B解释成 ifAthenBelsefals 把 A解释成 ifAthenfalseelsetrue 控制语句中布尔表达式的翻译现在讨论出现在ifthen ifthenelse和whiledo等语句中的布尔表达式E的翻译 这三种语句的语法为 S ifEthenS1 ifEthenS1elseS2 whileEdoS1 控制语句的代码结构 a ifEthenS1 E的代码 S1的代码 Jumpout S2的代码 out b ifEthenS1elseS2 E的代码 S1的代码 真 假 begin E的代码 S1的代码 Jumpbegin c whileEdoS1 对于E为E1orE2的形式 1 E1为真 则E为真 即E的真出口为E1的真出口 2 E1为假 计算E2 即E1的假出口应为E2的第一个四元式标号 E2的真 假出口与E的真 假出口一样 翻译的基本思路 对于E为aropb 形成代码为 IfaropbgotoE truegotoE false 把条件转移的布尔表达式E翻译成仅含条件转移和无条件转移的四元式 E aropb ifaropbgotoE truegotoE false 如 a borc dande f可以翻成如下四元式 1 ifa bgoto 2 goto 3 ifc dgoto 4 goto 5 ife fgoto 6 goto E tue 3 5 E false E true E false 我们使用E true和E false分别表示整个表达式a borc dande f的真 假出口 而E true和E false的值并不能在产生四元式的同时就知道 为了看清这一点 我们把该表达式放在条件语句中考虑 如语句If a borc dande f thenS1elseS2的四元式序列见下页 1 ifa bgoto 2 goto 3 ifc dgoto 4 goto 5 ife fgoto 6 goto 7 关于S1的四元式 p goto p 1 关于S2的四元式 q If a borc dande f thenS1elseS2的四元式序列为 7 3 5 p 1 q 7 p 1 使用拉链回填翻译控制语句中的布尔表达式拉链 L1 gotoL L2 gotoL L3 gotoL L L2 L1 0 语义描述使用的量 E true 真 链 E false 假 链 E codebeginE 的第一个四元式 nextstat 下一四元式地址 过程 emit 输出一条四元式 merge p1 p2 例 merge p1 p2 p100 goto0 p1 链 p 10 gotop100 p1 gotop10 p200 goto0 p2 链 p20 gotop200 p2 gotop20 backpatch p t 把 p 所链接的每个四元式的第四区 段都填为 t 如 E1orE2E1有一个真出口 E2也有一个真出口 将两个链合并为一条链 p1 7 E true E true nextstat E codebegin nextstat emit goto 8 E false E false nextstat E codebegin nextstat emit goto 以表达式af为例 它的四元式序列 100 ifafgoto105 goto将分析产生语法树时的语义动作结果 真 假 链情况注释在相应结点处 见P185图8 17 E true 102 104 E false E true E false 控制语句的翻译 条件转移考虑ifthen ifthenelse和whiledo语句 在图8 12中已给出了它们的代码结构 这里我们使用下面文法G S 定义这些语句 G S 1 S ifEthenS 2 ifEthenSelseS 3 whileEdoS 4 beginLend 5 A 6 L L S 7 S其中各非终结符号的意义是 S 语句L 语句串A 赋值句E 布尔表达式 为了能使语义在程序置于每个产生式的最后 需对原文法的产生式拆分 对G S 进行拆分修改为G S 1 S CS1 8 C ifEthen 2 S TpS2 9 Tp CSelse 3 S WdS3 10 Wd WEdo 4 S beginLend 11 W while 5 S A 6 S LsS1 12 Ls L 7 L S 1 S CS1 S Chain merge C Chain S1 Chain 8 C ifEthen backpatch E true nextstat C chain E false 9 Tp CS1else q nextstatemit goto backpatch C Chain nextstat Tp Chain merge S1 chain q 2 S TpS2 S chain merge Tp Chain S2 Chain 11 W while W codebegin nextstat 10 Wd WEdo backpatch E true nextstat Wd chain E falseWd codebegin W codebegin S WdS3 backpatch S3 chain Wd codebegin emit goto Wd codebegin S chain Wd chain 4 S beginLend S chain L chain 5 S A S chain 0 空链 L S L chain S chain 12 Ls L backpatch L chain nextstat 6 L LsS1 L chain S1 chain 按照上述文法产生式相应的语义动作 加上前述关于赋值句和布尔表达式的翻译法 语句while A B doif C D thenX Y Z 将被翻译成如下的一串四元式 100ifA Bgoto101goto102ifC Dgoto103goto100104T Y Z105X T106goto100107 while A B doif C D thenX Y Z 102 107 104 for循环语句 fori E1stepE2untilE3doS1 为了简单起见 假定E2总是正的 在这种假定下 上述循环句的意义等价于 i E1 gotoOVER AGAIN i i E2 OVER ifi E3thenbeginS1 gotoAGAINend 翻译见P191 P192 开关语句 开关语句 case语句或switch语句 switchEofcaseV1 S1caseV2 S2 caseVn 1 Sn 1default Snend 如果分叉不太多 case语句翻译成如下的一连串条件转移语句 t E L1 ift V1gotoL2 S1 gotonext L2 ift V2gotoL3 S2gotonext Ln 1 ift Vn 1gotoLn Sn 1 gotonext Ln Sn next 另一种方法 P190图8 18 计算E值 并把结果放到临时变量t中gototestL1 S1的中间代码gotonextL2 S2的中间代码gotonext Ln Sn的中间代码gotonexttest ift v1gotoL1 ift v2gotoL2 ift vn 1gotoLn 1 gotoLnnext goto语句 多数程序语言中的转移是通过标号和goto语句实现的 带标号语句的形式是L S goto语句的形式是gotoL 当L S 语句被处理之后 标号L是 定义了 的 即在符号表中 将登记L的项的 地址 栏中登上语句S的第一个四元式的地址 如果gotoL是一个向上转移的语句 那么 当编译程序碰到这个语句时 L必是已定义了的 通过对L查找符号表获得它的定义地址p 编译程序可立即产生出相应于这个gotoL的四元式如 j p 如果gotoL是一个向下转移的语句 也就是说 标号L尚未定义 那么 若L是第一次出现 则把它填进符号表中并标志上 未定义 由于L尚未定义 对gotoL只能产生一个不完全的四元式 goto 它的转移目标须待L定义时再回填进去 在这种情况下 必须把所有那些以L为转移目标的四元式的地址全都记录下来 以便一旦L定义时就可对这些四元式进行回填 我们将采用如图8 20所示的拉链办法 把所有以L为转移目标的四元式串在一起 链的首地址放在符号表中L的 地址 栏中 建链的方法是 若gotoL中的标号L尚未在符号表中出现 则把L填入表中 置L的 定义否 标志为 未 把nextstat填进L的地址栏中作为新链首 然后 产生四元式 p goto0 其中0为链尾标志 若L已在符号表中出现 但 定义否 标志为 未 则把它的地址栏中的编号 记为p 取出 把nextstat填进该栏作新链首 然后 产生四元式 q gotop 一旦标号L定义时 我们将根据这条链回填那些待填转移目标的四元式 一般而言 假定用下面的产生式来定义标号语句 S labelSlabel i 1 若i所指的标识符 假定为L 不在符号表中 则把它填入 置 类型 为 标号 定义否 为 已 地址 为nextstat 2 若L已在符号表中但 类型 不为 标号 或 定义否 为 已 则报告出错 3 若L已在符号表中 则把标志 未 改为 已 然后 把地址栏中的链首 记为q 取出 同时把nextstat填在其中 最后 执行backpatch q nextstat 过程调用的四元式产生 过程调用的实质是把程序控制转移到子程序 在转子之前 必须用某种办法把实参的信息传给调用的子程序 传递实参信息方面有种种不同的方法 我们这里只讨论一种 即传实参地址的方式 若实参是一个变量或数组 则直接传递地址 若实参是表达式 如 A B或2 则把它们的值计算出来 并存放在一个临时变量T中 然后传递T的地址 传递实参地址的一个简单办法是 把实参地址逐一放在转指令的前面 例 过程调用 CallS A B Z 译为 计算A B的值置于T中 T A B ParT 第一个实参的地址 ParZ 第二个实参的地址 CallS 转指令 为了处理在实参时记住每个实参的地址 以便最后把它们排在Call指令之前 我们需要把这些地址存放起来 我们可用队列来存放 例 一个描述过程调用语句的文法如下 1 S calli 2 1 E 3 E 它的语法制导翻译见P196 例 写一个翻译过程调用语句的语义子程序 要求生成的四元式序列在转指令之前的参数四元式par按反序出现 与实在参数的顺序相反 过程调用语句的文法如下 1 S calli 2 1 E 3 E 1 E 建一个arglist Stack栈 它仅包含一项E Place 2 1 E 将E Palce压入arglist Stack栈 arglist Stack arglist1 Stack 3 S calli Whilearglist Stack nulldobegin将arglist Stack栈顶弹出生成Gen par p end Gen call Entry i 简单说明语句的翻译 程序设计语言中的说明语句旨在定义各种形式的有名实体 如常量 变量 数组 记录 结构 过程 子程序等等 说明语句的种类也多 对象说明 变量说明 类型说明 过程说明等等 编译程序把说明语句中定义的名字和性质登记在符号表中 用以检查名字的引用和说明是否一致 简单说明句的翻译