编译原理 之 语法制导翻译和中间代码生成.ppt

第八章语法制导翻译和中间代码生成 属性文法语法制导翻译中间代码的形式一些语句的翻译 概述 语义处理 程序设计语言的语义静态语义是对程序约束的描述 这些约束无法通过抽象语法规则来妥善地描述 它可以分为类型规则和作用域 可见性规则 类型相容性 变量先声明后引用 名称相关要求 概述 语义处理 动态语义是真正的翻译成中间代码 或直接生成目标代码 编译程序的语义处理工作 静态语义审查 解释执行动态语义 计算 生成代码 8 1属性文法 语义形式化 语义建模命令式或操作式模型 操作语义学应用式模型 指称语义学公理式模型 公理语义学 形式语义学 如指称语义学 公理语义学 操作语义学等 的研究已取得了许多重大的进展目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法 8 1属性文法 属性文法 attributegrammar 是一个三元组 A G V F 其中G 是一个上下文无关文法V 有穷的属性集 每个属性与文法的一个终结符或非终结符相连 这些属性代表与文法符号相关信息 如它的类型 值 代码序列 符号表内容等等 属性与变量一样 可以进行计算和传递 属性加工的过程即是语义处理的过程 F 关于属性的断言或一组属性的计算规则 称为语义规则 断言或语义规则与一个产生式相联 只引用该产生式左端或右端的终结符或非终结符相联的属性 例 类型检查的属性文法 表达式文法E T T TorTT num true falseE T1 T2 T1 t intandT2 t int E T1orT2 T1 t boolandT2 t bool T num T t int T true T t bool T false T t bool 属性有两种 继承属性和综合属性 综合属性用于 自下而上 传递信息 继承属性用于 自上而下 传递信息 在一个属性文法中 对应于每个产生式A 都有一套与之相关联的语义规则 每条规则的形式为b f c1 c2 ck 这里f是一个函数 1 如果b是A的一个属性并且c1 c2 ck是产生式右边文法符号的属性或A的其它属性 则称b是A的综合属性 2 b是产生式右边某个文法符号X的一个属性并且c1 c2 ck是A或产生式右边任何文法符号的属性 则称b是文法符号X的继承属性 在上述两种情况下 我们都说属性b依赖于属性c1 c2 ck 1 非终结符既可有综合属性也可有继承属性 但文法开始符号没有继承属性 除非另有说明 2 终结符只有综合属性 例8 1简单算术表达式求值的语义描述 语义规则 LE EE1 T ET TT1 F TF F E Fdigit Print E val E val E1 val T val E val T val T val T1 val F val T val F val F val E val F val digit lexval 产生式 非终结符E T及F都有一个综合属性val 符号digit有一个综合属性 它的值由词法分析器提供 与产生式L E对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程 我们可认为这条规则定义了L的一个虚属性 某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现 设表达式为3 5 4 则语义动作打印数值19 L E val 19 E val 15 T val 4 T val 15 F val 4 T val 3 F val 3 F val 5 digit lexval 4 digit lexval 5 digit lexval 3 3 5 4的带注释的分析树 例8 2说明语句语义规则 生产式 语义规则 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in 非终结符T有一个综合属性type 其值有关键字决定 int或real L in T type L in是继承属性 它将沿着语法树传递到下边的结点 与L相联的语义规则中有一个过程调用 addtype把标识符的类型信息登录在符号表中 一个结点的继承属性值是由此结点的父结点和 或兄弟结点的某些属性来决定的 D L in real L in real T type real real id1 id2 Realid1 id2 8 2语法制导翻译方法 基于属性文法的处理 语法制导翻译在语法分析过程中 随着分析的步步进展 根据每个产生式所对应的语义子程序 或语义规则描述的语义动作 进行翻译的办法称作语法制导翻译 假如我们现在要分析的语法成分是简单算术表达式 所完成的语义处理不是将它翻译成中间代码或是目标代码 而是计算表达式的值 产生式语义规则 print E val 1 E val E1 val val E val T val 1 T val T1 val F val FT val F val F val E val digitF val digit lexvalLR分析器可以改造为一个翻译器 在对输入串进行语法分析的同时对属性进行计算 LR分析器增加语义栈 的分析和计值过程 步骤动作状态栈语义栈 值栈 符号栈余留输入串 3 2 3 r603 r402 r2 016 0165 r60163 r40169 01697 016975 r601697 10 r30169 r101 接受 8 3中间代码的几种形式 逆波兰 栈三元式 树四元式 三地址指令 逆波兰 后缀式 表达式 A B C D E C D N 后缀式 ABCD ECD N 表达式 A B C D E C D N DCBA 后缀式 ABCD ECD N T1BA T1 C D T1BA T2A T2 B T1 T2A T3 T3 A T2 DCET3 T4ET3 T4 C D NT4ET3 T5ET3 NT4ET3 T5 T4 N T5ET3 T6T3 T6 E T5 T6T3 T7 T7 T3 T6 T7 A B C D E C D N 三元式 树形表示 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 A B B C D E C D N 四元式 三地址指令 A B C D E C D N 1 CDT1 2 BT1T2 3 AT2T3 4 CDT4 5 T4NT5 6 ET5T6 7 T3T6T7 8 4简单赋值语句的翻译 id name 语义变量lookup id name 语义函数emit t arg1oparg2 语义过程newtemp 语义过程E place 语义变量 存放E值的变量名在符号表的登录项或一整数码 若此变量是临时变量 8 4简单赋值语句的翻译 四元式形式 result arg1 op arg2 产生式和语义描述 1 S id E P lookup id name ifP nilthenemit P E place elseerror op arg1 arg2 result 或 2 E E1 E2 E place newtemp emit E place E1 place E2 place 3 E E1 E place newtemp emit E place uminus E1 place 4 E E1 E place E1 place 5 E id E place newtemp P lookup id name ifP nilthenE place Pelseerror 简单赋值语句的四元式翻译 8 5布尔表达式的翻译 布尔表达式 用布尔运算符号 and or not 作用到布尔变量或关系表达式上而组成布尔表达式的作用 1 用作计算逻辑值2 用作控制流语句如if then if then else和while do等之中的条件表达式 翻译布尔表达式的方法 法一 用数值表示真和假 从而对布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算 方法二 通过程序的控制流 即用程序中控制转移到达的位置来表示布尔表达式的值 方法二用于翻译控制流语句中的布尔表达式尤其方便 8 5 1数值表示的布尔表达式翻译方案 用1表示真 0表示假来实现布尔表达式的翻译布尔表达式 aorbandnotc翻译成三地址代码序列 100 t1 notc101 t2 bandt1102 t3 aort1 关系表达式 a b等价于ifa bthen1else0翻译成三地址代码序列 100 ifa bgotol03101 t 0102 gotol04 103 t 1104 nextstat的语义说明 nextstat 给出在输出序列中下一四元式序号 emit过程每调用一次 nextstat增加1 关于布尔表达式的数值表示法的翻译模式 E E1orE2 E place newtemp emit E place E1 place orE2 place E E1andE2 E place newtemp emit E place E1 place andE2 place E notE1 E place newtemp emit E place not E1 place E id1ropid2 E place newtemp emit if id1 place rop id2 place goto nextstat 3 emit E place 0 emit goto nextstat 2 emit E place 1 E ture E place newtemp emit E place 1 E false E place newtemp emit E place 0 数值表示法的布尔式的翻译方案 8 5 2控制结构中布尔表达式的翻译 文法 S ifEthenS1 ifEthenS1elseS2 whileEdoS1 S ifEthenS1 E code S1 code E true E false toE true toE false E false S ifEthenS1elseS2 E 的代码 E true E true S 1 的代码 gotoout E false S 2 的代码 out E false S whileEdoS1 E 的代码 E true E S 1 的代码 控制流语句布尔表达式翻译的基本思想 假定E形如aropd 则将生成如下的E的代码 ifaropbgotoE truegotoE falseE true E false分别表示E的 真 假 出口 产生式 语义规则 E E1orE2 E1 true E true E1 false newlabel E2 true E true E2 false E false E E1andE2 E1 true newlabel E1 false E false E2 true E true E2 false E false E notE1 E1 true E false E1 false E true 产生式 语义规则 E id1ropid2 emit if id1 place rop id2 place goto E true emit goto E false E true emit goto E true E false emit goto E false E E1 E1 true E true E1 false E false 考虑布尔运算符or和and的逻辑关系 决定布尔表达式的真假出口 例8 5布尔表达式af翻译为如下的四元式序列 ifafgotoE truegotoE false 显然生成的四元式不是最优的 如 2 是不需要的 留作代码优化处理 E true和E false是整个表达式的真假出口 不能在产生四元式的同时就知道 语句 ifa borc dande fthenS 1 else S 2 的四元式 1 转移至 E true 2 goto 3 3 ifc dgoto 5 转移至 E false 7 S 1 的四元式 p 1 p goto p 1 S 2 的四元式 q 1 q 转移至 E true 转移至 E false E false 入口 E true 入口 4 goto p 1 5 ife fgoto 7 6 goto p 1 q ifa bgoto 7 回填 两遍扫描 从给定的输入构造出一棵语法树 对语法树按深度优先遍历 来进行定义中给出的翻译 一遍扫描 先产生暂时没有填写目标标号的转移指令 对于每一条这样的指令作适当的记录 一旦目标标号被确定下来 再将它 回填 到相应的指令中 记录需回填地址的四元式 把需回填E true的四元式拉成一链 把需回填E false的四元式拉成一链 分别称做 真 链和 假 链 10 gotoE true 20 gotoE true 30 gotoE true则链成 10 goto 0 20 goto 10 30 goto 20 把地址 30 称作 真 链链首 0为链尾标志 即地址为 真 链链尾 两个函数 backpatch p i 把i作为目标标号回填到p所指向的表中的每一个转移指令中去 merge p1 p2 连接由指针p1和p2指向的两个表并且返回一个指向连接后的表的指针 语义描述使用的变量和过程 E true 真 链 E false 假 链 E codebegin E 的第一个四元式 Nextstat 下一四元式地址 过程 emit 输出一条四元式 而 nextstat 1 merge p1 p2 把 p1 的链首填在 p2 的链尾 例 merge p1 p2 p10 goto 0 p1 链 p 10 0 goto p10 p1 goto p100 p20 goto 0 p1 p2 链 p200 goto p20 p2 goto p200 backpatch p t 把 链首p 所链接的每个四元式 的第四区段都填为 t 4 E E1 E true E1 true E codebegin E1 codebegin E false E1 false 5 E id1ropid2 E true nextstat E codebegin nextstat E false nextstat 1 emit if id1 place rop id2 place goto emit goto 6 E id E true nextstat E codebegin nextstat E false nextstat 1 emit if id place goto emit goto 以表达式a borc dande f为例 在归约a b到E时 产生2个四元式100 ifa bgoto 101 goto 由c d归约E时产生四元式102 ifc dgoto 103 goto 把e f归约成E时产生四元式104 ife fgoto 105 goto E id1ropid2 E true nextstat E codebegin nextstat E false nextstat 1 emit if id1 place rop id2 place goto emit goto 真 假 真 假 真 假 100 ifa bgoto 101 goto102 ifc dgoto103 goto 104 ife fgoto 105 goto E1 E2 and E E1andE2 bachpatch E1 true E2 codebegin E codebegin E1 codebeginE true E2 true E false merge E1 false E2 false 104 E E1orE2 bachpatch E1 false E2 codebegin E codebegin E1 codebeginE true merge E1 true E2 true E false E2 false 假链 103 105 E1 E2 or E 102 真链 100 104 100 ifa bgoto 101 goto102102 ifc dgoto104103 goto 104 ife fgoto 105 goto 当且仅当到达100或104的goto时 整个表达式为真 当且仅当到达103或105的goto时 整个表达式为假 这些指令的目标标号将在后面的编译中填写 那时根据表达式的真假状态分别应做哪些事时就可以进行回填 8 6控制语句的翻译 文法 1 S ifEthenS 2 ifEthenSelseS 3 whileEdoS 4 beginLend 5 A 6 L L S 7 SS表示语句L表示语句表A为赋值语句E为一个布尔表达式 控制流语句的翻译方案 ifE1thenifEthenS1elseS2elseS3只有翻译完S3之后 其它转移目标才能确定 增加S和L的语义值S chain和L chain 把四元式串在一起 在翻译完S L 之后回填转移目标 为了及时回填四元式转移目标 可对文法进行改写 S CS1 TpS2 beginLend A WdS3 L LsS1 S2 C ifEthen Tp CSelse Wd WEdo W while Ls L S CS1 S chain merge C chain S1 chain S TpS2 S chain merge Tp chain S2 chain S WdS3 backpatch S3 chain Wd codebegin emit goto Wd codebegin S chain Wd chain S beginLend S chain L chain S A S chain 0 L LsS1 L chain S1 chain L S L chain S chain C ifEthen backpatch E true nextstat C chain E false Tp CSelse q nextstat emit goto backpatch C chain nextstat Tp chain merge S chain q W while W codebegin nextstat Wd WEdo backpatch E true nextstat Wd chain E false Wd codebegin W codebegin Ls L backpatch L chain nextstat 例 将下列语句翻译成四元式 while A B doif C D thenX Y ZS WdS3Wd WEdoS3 CS1C ifE1thenS1 AA X Y ZE A BE1 C D backpatch S3 chain Wd codebegin emit goto Wd codebegin S chain Wd chain backpatch E true nextstat Wd chain E false Wd codebegin W codebegin W do A B E if S C C D A E while S1 then x y z W codebegin nextstat 100ifA Bgoto 101goto 102 W codeb 100 Wd chain 101 Wd codeb 100 backpatch E true nextstat C chain E false C chain 103 104 104T Y Z105X T S chain 0 S1 chain 0 S chain merge C chain S1 chain S3 chain 103 100 102ifC Dgoto 103goto 106goto100107 S chain 101 107 全部四元式代码如下 100 ifA Bgoto102101 goto107102 ifC Dgotol04103 goto100104 T Y Z105 X T106 goto100107 8 7数组说明和数组元素的引用 静态数组动态数组 将产生两组计算数组元素地址的四元式一组计算 将它放在某个临时单元 中 一组计算 放在另一个临时单元T1中 同时用表示数组元素的地址 对应 数组元素引用 引用其值 和 对数组元素赋值 有两个相应的四元式 变址取数 和 变址存数 变址取数 的四元式是 T1 T 相当于X T1 T 变址存数 的四元式是 T1 T 相当于T1 T 例 令A是一个10 20的数组 即d1 10 d2 20 那么赋值语句X A I J 的四元式序列为 I 20 T1 其中20指d2 J T1 T1 T1为VARPART A 21 T2 T2 a C T2 T1 T3 T3 T2 T1 T3 X X T3 赋值语句A I 2 J 1 M N的四元式序列为 I 2 T1 J 1 T2 T1 20 T3 T2 T3 T3 T3为VARPART A 21 T4 T4 a C CONSPART M N T5 T5 T4 T3 T4 T3 T5 作业 P2021 1 3 将下列语句翻译成四元式序列 If y1 theny y xelsey y x 假定四元式起始标号为100 开关语句 switchEofcaseV1 S1caseV2 S2 caseVn 1 Sn 1default Sn 开关语句的翻译方法 建立一个n项的二元组表 第一元为Vi的值 第二元为Vi对应的语句Si的标号 构造一个对E值查该表的程序 即该程序把E的值和二元组表项中的各个Vi值相比 若与某个Vi匹配 就去执行相应的Si 如果找不到这样的Vi 则末项自动匹配 便去执行Sn 开关语句的翻译结果 计算E的值 并把结果放到临时变量t的中间代码gototestL1 S1的中间代码gotonextL2 S2的中间代码gotonext Ln 1 Sn 1的中间代码gotonextLn Sn的中间代码gotonexttest ift V1gotoL1ift V2gotoL2 ift VngotoLn 1gotoLnnext for循环语句 fori E1stepE2untilE3doS1其意义等价于 i E1gotoOVERAGAIN i i E2OVER ifi