第5章语法制导翻译技术和中间代码生成

S P O P 第5章语法制导翻译技术和中间代码生成 要求明确语义分析的任务明确属性文法和语法制导翻译的含义明确自底向上和自顶向下语法制导翻译的区别和特点明确生成中间代码的目的 中间代码的几种形式 教学目标 属性文法语法制导翻译法的基本思想常见的中间代码各种不同语法结构的语法制导翻译技术 教学内容 词法分析 语法分析 解决单词和语言成分的识别及词法和语法结构的检查 语法结构可形式化地用一组产生式来描述 给定一组产生式 我们能够很容易地将其分析器构造出来 本章要介绍的是语义分析和中间代码生成技术 程序语言中间代码目标代码 翻译 翻译 根据语义规则对识别出的各种语法成分析其含义 进行初步翻译 生成相应的中间代码或直接生成目标代码 第一 审查每个语法结构的静态语义 即检查语法结构合法的程序是否真正有意义 也称静态语义检查 类型检查 控制流的检查 一致性检查 相关名字的检查 第二 如果静态语义正确 语义处理则要执行真正的翻译 要么生成中间代码 要么生成实际的目标代码 说明性语句 填符号表 可执行性语句 生成中间代码 语义分析的任务 类型检查 控制流检查 确保控制语句有合法的转向点 例如 C语言中的break语句使控制跳离包括该语句的最小的switch while或for语句 如果不存在包括它的这样的语句 则应报错 静态语义检查 静态语义检查 一致性检查 很多情况下要求对象只能被定义一次 例如 语言中规定一个标识符在同一作用域中只能被说明一次 同一case语句的标号不能相同 枚举类型的元素不能重复出现等 相关名字检查 有的语言中有时规定 同一名字必须出现两次或多次 例如 Ada语言中 循环或程序块可以有一个名字 它出现在这些结构的开头和结尾 如同语句括号一般 编译程序必须检查它们的配对情况 附加了一组属性和运算 语义 规则的文法 5 2属性文法 文法符号X的属性t常用X t来表示 语义规则是根据产生式所蕴涵的语义操作建立起来的 并与语义分析的目标有关不同的产生式对应不同的语义规则不同的分析目标也对应不同的语义规则 静态语义检查 符号表操作 代码生成及打印各种错误信息 属性文法 属性文法的形式定义 AG AG G V E G 上下文无关文法 V 属性的有穷集合 每一个属性与某一个文法符号相关联 用文法符号 属性表示E 表示属性的断言或谓词的有穷集合 语义规则 每一个断言与文法的某个产生式相关联 属性 综合属性 自下而上传递信息 继承属性 自上而下传递信息 非终结符E T及F都有一个综合属性val 符号i有一个综合属性 某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现 语义规则 EE1 T ET TT1 F TF F E Fi 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 i lexval 产生式 例5 1 语法制导翻译的过程 语法制导翻译 将语义规则与语法规则相结合 在语法分析的过程中通过执行语义动作 计算语义属性值 从而完成预定的翻译工作 自底向上语法制导翻译 自顶向下语法制导翻译 语法制导翻译的实现 语法制导翻译分为两种处理方法 1 语法制导定义 自底向上 对每个产生式编制一个语义子程序 在进行语法分析的过程中 当一个产生式获得匹配时 就调用相应的语义子程序实现语义检查与翻译 这种实现方案隐藏了其中语义规则的计算次序等实现细节 不必规定翻译顺序 2 翻译方案 自顶向下 在产生式右部的适当位置 插入相应的语义动作 按照分析的进程 执行遇到的语义动作 这是一种动作与分析交错的实现方案 输入符号串 分析树 执行语义规则 翻译结果 翻译步骤 从分析树得到描述结点属性间依赖关系的依赖图 由依赖图得到语义规则的计算次序 1 分析输入符号串 建立分析语法树 进行语义规则的计算 得到翻译结果 语法制导定义 对每个产生式编制一个语义子程序在进行语法分析的过程中 当一个产生式获得匹配时 就调用相应的语义子程序实现语义检查与翻译 自底向上传递信息 自顶向下 自左向右 传递信息 print E val 打印由E产生的算术表达式的值 可认为这条规则定义了L的一个虚属性 LE EE1 T ET TT1 F TF F E Fi 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 i lexval 例5 综合属性 语义规则 产生式 一个结点的综合属性值是其子结点的某些属性来决定的 3 4的注释分析树 通常使用自底向上的分析方法在每个结点处使用语义规则来计算综合属性值当一个产生式获得匹配时 就调用相应的语义子程序从叶结点到根结点进行计算 只含有综合属性的语法制导定义称为S属性定义 S属性定义与自底向上翻译 LR分析器可以改造为一个翻译器 在对输入串进行语法分析的同时对属性进行计算LR分析器增加属性值 语义 栈 首先 为文法的每条规则设计相应的语义子程序 增加一个语义信息栈 在语法分析的同时做语义处理 即在用某一个产生式进行规约的同时 调用相应的语义子程序完成所用规则的语义动作 并将每次动作后的值保存在语义栈中 翻译步骤 计算表达式2 3 5 G E 1E E T2E T3T T F4T F5F E 6F i i i i 表达式2 3 5的归约过程 注意 句柄归约在先 语义动作调用在后归约时 栈内句柄各符号的语义信息与句柄及同时出栈 整个句柄所表示的语义信息则赋给相应产生式左部非终结符号的语义变量 并让该非终结符号及语义信息同时入栈 生成中间代码的目的 1 便于优化 2 便于移植 3 逻辑结构清晰 常见的中间代码形式 后缀式三地址代码 四元式 三元式和间接三元式 图形 抽象语法树 有向无环图 中间代码 一种介于源语言和目标语言之间的中间语言形式 5 中间代码 中缀表示后缀表示a bab a b cabc a b cab c a b c b dabc bd 特点 1 运算对象出现的顺序和原有顺序 从左到右 相同2 运算符按实际计算顺序 从左到右 出现3 运算符紧跟在运算对象的后面出现 且没有括号 优点 简明 便于计值 后缀式 分别给出下列表达式的后缀表示 1 a b c d 2 X a b c d a b c 3 a c b d4 a b c a d a b e 逆波兰表示法 后缀式 特点 运算符直接写在其运算对象之后 不再有括号运算对象出现的次序未变求值过程简单 宜于用栈实现 后缀式的计算用一个栈实现 一般的计算过程是 自左至右扫描后缀式 每碰到运算量就把它推进栈 每碰到k目运算符就把它作用于栈顶的k个项 并用运算结果代替这k个项 三地址代码 种类 1 x yopz形式的赋值语句 其中op是二元运算符 2 x opy形式的赋值语句 其中op是一元运算符 3 x y形式的赋值语句 4 无条件转移语句gotoL 表示下一个要执行的语句是标号为L的语句 5 条件转移语句ifxropygotoL中 rop为关系运算符 如果x和y满足关系rop 就转而执行标号为L的语句 否则顺序执行下一个语句 6 过程调用语句paramx和callp n 源程序中的过程调用语句p x1 x2 xn 可以产生如下的三地址代码 paramx1paramx2 paramxncallp n其中n为实参个数 过程返回语句形如returny 其中y为过程返回的一个值 7 变址赋值 x y i 把从y开始的第i个存储单元的值赋给x x i y 把y的值赋给x开始的第i个存储单元 其中 x y和i都代表数据对象 8 地址和指针赋值 x y 把y的地址赋给x x y 把y指示的地址单元中的内容赋给x x y 把x指向的存储单元的值置为y 2 具体实现 四元式 结果 通常是由编译引进的临时变量 例 X A B C D E T1 T2 T3 T4为临时变量 由四元式优化比较方便 表达式的三元式 第三个三元式中的操作数 1 2 表示第 1 和第 2 条三元式的计算结果 三元式 不便于代码优化 删除某些三元式后可能需作一系列的修改 图形表示法 无循环有向图 DirectedAcyclicGraph 简称DAG 对表达式中的每个子表达式 DAG中都有一个结点一个内部结点代表一个操作符 它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点 例 x y y z y z 抽象语法树 图形表示 有向无环图 表达式a b c的三元式 1 b 单目运算 运算对象2为空 2 1 c 3 a 2 三元式 X a b cY d b c 三元式表 1 b c 2 a 1 3 x 2 4 d 1 5 y 4 四元式 三地址代码 X a b c d的四元式序列三地址代码 1 a b T1 1 T1 a b 2 c d T2 2 T2 c d 3 T1 T2 T3 3 T3 T1 T2 4 T3 X 4 X T3 2020年4月7日 编译原理 a b c b c 的图表示法 2020年4月7日 编译原理 抽象语法树对应的代码 T1 cT2 b T1T3 cT4 b T3T5 T2 T4a T5 2020年4月7日 编译原理 DAG对应的代码 T1 cT2 b T1T5 T2 T2a T5 抽象语法树对应的代码 T1 cT2 b T1T3 cT4 b T3T5 T2 T4a T5 属性翻译文法的应用 综合属性与自下而上定值每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的 即按一种自下而上的方式来确定的 继承属性和自上而下定值非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定 这种属性值是根据自上而下方式确定的 自底向上的语法制导翻译 自底向上的语法制导翻译方法是在自底向上的语法分析过程中逐步实现语义规则的翻译方法 在实现时注意以下几点 1 自底向上的翻译的特点 栈的操作 对产生式的要求等 2 各种程序语句的目标结构 3 从源结构到目标结构的变换方法 包括对产生式的改造等 算术表达式和赋值语句的翻译 翻译步骤 1 分析文法的特点 2 设计一系列的语义变量 定义语义过程 语义函数 3 设计每一条规则的语义子程序 4 增加一个语义信息栈 构造LR分析表 5 语法分析同时语义处理 例 有文法G A 1 A i E2 E E T T3 T T F F4 F P5 P i E 简单算术表达式的计值顺序与四元式出现的顺序相同 因此目标代码的顺序 结构 为 1 先生成E的代码 一系列顺序执行的四元式 2 把E的值赋给变量i 表达式的结果赋给赋值语句的左变量 引入语义变量 语义过程和语义函数 1 语义变量E place 表示存放E值的变量名在符号表中的入口地址或临时变量的整数码 2 语义函数newtemp 申请一个临时单元 存放中间结果 3 语义过程emit T arg1oparg2 产生一条四元式 并添入四元式表中 4 语义过程lookup i name 审查i name是否出现在符号表中 在 返回地址 不在 返回NULL 5 语义函数entry i 回送标识符i在符号表中的入口地址 表达式的语义动作设计 1 A i E emit entry i E place 2 E E1 T E place newtemp emit E place E1 place T place 3 E T E place newtemp emit E place T place 4 T T1 F T place newtemp emit T place T1 place F place 5 T F T place newtemp emit T place F place 6 F P F place newtemp emit F place P place 7 P E P place newtemp emit P place E place 8 P i P place newtemp emit P place Entry i 例如 表达式X a b c d 的翻译 K 1 T1 c dK 2 T2 b T1K 3 T3 a T2K 4 X T3 c d T1 b T1 T2 a T2 T3 T3 X 布尔表达式的翻译 布尔表达式是由布尔运算符 and or not 作用于布尔变量 或常数 或关系表达式而形成的 布尔表达式的作用 用作控制语句中的条件 if then while repeat等逻辑赋值句中的逻辑运算 布尔表达式到四元式的翻译 文法 E E E E E E E id EropE其中 and or not 为布尔 逻辑 运算符 rop为关系运算符 id为布尔 逻辑 变量或布尔 逻辑 常数 EropE为关系表达式 布尔表达式的求值方法 通过逐步计算出各部分的值来计算整个表达式 利用布尔运算符的性质计算其值 布尔表达式作为控制语句中的条件式 作用是用于选择下一个执行点whileEdoS1E的作用是选择S1执行 还是跳过S1语句 执行S1后面的语句E有两个出口 真 S1语句假 S1后面的语句 While语句的目标结构 布尔初等量 布尔变量和关系表达式 的目标结构 由两个转移四元式构成 一个表示真出口Li 另一个表示假出口Lj 设E是一布尔变量 它的目标结构为 1 ifEgotoLi jumpt E Li jnz A Li 2 ifE1ropE2gotoLi jump E1 E2 Li jrop E1 E2 Li 例 j a b p 3 gotoLj jumpLj j Lj 举例 ifa bthenA x y的四元式序列 ifa bgotoLi 真出口 gotoLj 假出口 Li S的第一个四元式 S的最后一个四元式Lj S后面的语句 1 ifa bgoto 3 2 goto 5 3 T1 x y 4 A T1 5 多因子组成的布尔表达式的翻译 例 ifa b cthenS1elseS2分析结果如下 当a b为真 执行S1 不需要计算c的值当a b为假 计算c的值 c为真 执行S1 为假 执行S2当a b与c分别为真时 程序转向一致 真出口相同 S1 当a b与c分别为假时 程序转向一致 假出口相同 S2 ifa b cthenS1elseS2的四元式序列 1 ifa bgotoS1的第一条语句 5 2 goto 3 3 ifcgotoS1的第一条语句 5 4 gotoS2的第一条语句 p 1 5 关于S1的四元式序列 p Gotoq p 1 关于S2的四元式序列 q 后继四元式 目标结构 E的代码TF S1的代码 JUMPS S2的代码 S 后继语句 2020年4月7日 编译原理 ifEthenS1elseS2的四元式序列 1 ifEgoto 3 2 goto S2的第一个四元式 p 1 3 关于S1的四元式序列 p gotor 执行完S1后转出 p 1 关于S2的四元式序列 r 后继四元式 2020年4月7日 编译原理 whileEdoS1的四元式序列 1 ifEgoto 3 2 goto S1后面的语句 p 1 3 关于S1的四元式序列 p goto 1 p 1 后继四元式 2020年4月7日 编译原理 真出口链 假出口链 回填 Backparch 在多个因子组成的布尔表达式中 可能有多个因子的真出口或假出口的转移去向相同 但又不能立刻知道具体转向位置 把转移方向相同的四元式链在一起 一旦发现具体转移目标 就回填 真出口用Etrue来表示 假出口用Efalse来表示 回填Backparch g t 将t填入由g所指向的四元式的结果部分 2020年4月7日 编译原理 ifa b cthenS1elseS2的真假出口回填描述 1 ifa bgoto0 E的真出口Etrue有待回填 2 goto 3 回填E的第一个假出口 3 ifcgoto 1 3 是E的真出口链 4 goto0 E的假出口Efalse有待回填 5 关于S1的四元式序列 此时回填真出口Etrue p goto0 有待回填q的位置 p 1 关于S2的四元式序列 此时回填假出口Efalse q 后继四元式 此时回填q 2020年4月7日 编译原理 语法制导翻译中使用的公共变量 过程和函数 guad 四元式指针 表示四元式的编号或地址 GEN X 生成一条四元式 把它放到四元式表的尾部 和前面介绍的emit功能相同 Nextguad 指向下一个即将形成的四元式的编号 其初值为1 执行一次GEN X Nextguad自动加1 merg p1 p2 函数将以p1 p2为链首的两个四元式合并为一 返回合并后的链首 条件语句的翻译 基本思路 先对定义它的文法进行改造 以便能在相应处添加上语义子程序 根据它的语义 设计出相应语义子程序的动作 2020年4月7日 编译原理 if语句的文法 S ifEthenS1S ifEthenS1elseS2 E是转移条件 对ifEthenS1elseS2 其Etrue直到扫描到then 产生S1的第一个四元式序号时 才能将该标号作为E的真链填入到Etrue 而Efalse直到扫描到else 产生S2的第一个四元式序号时 才得到Efalse的值 2020年4月7日 编译原理 if语句文法的改造 1 C ifEthen 2 T CS1else 3 S TS2 4 S CS1目标结构如右图 2020年4月7日 编译原理 1 C ifEthen backpatch Etrue Nextguad C chain Efalse 当用产生式ifEthen进行归约时 生成了条件E的代码 E的假出口不能回填 通过非终结符C向后传递 所以引入C chain链 if语句的语义动作 2020年4月7日 编译原理 2 T CS1else q Nextguad emit goto0 Backpatch C chain Nextguad T chain merg S1 chain q 当用产生式T CS1else归约时 S1的代码已经形成 回填E的假出口即C chain 此时S2的代码尚未形成 S1的转出链和JMP转向相同 合并为一 通过T向后传递 if语句的语义动作 2020年4月7日 编译原理 if语句的语义动作 3 S TS2 S chain merg T chain S2 chain 4 S CS1 S chain merg C chain S1 chain 2020年4月7日 编译原理 IfA B C DthenifA BthenF 1elseF 0elseG G 1 采用then与else的最近匹配原则 三地址指令 1 ifAgoto 3 2 goto0 13 3 ifBgoto 5 4 goto 2 13 5 ifC Dgoto 7 6 goto 4 13 7 ifA Bgoto 9 8 goto0 11 9 F 1 10 goto0 15 11 F 0 12 goto 10 15 13 T G 1 14 G T 15 2020年4月7日 编译原理 IfA B C DthenifA BthenF 1elseF 0elseG G 1 四元式形式代码 1 jnz A 3 2 j 0 13 3 jnz B 5 4 j 2 13 5 j C D 7 6 j 4 13 7 j A B 9 8 j 0 11 9 1 F 10 j 0 15 11 0 F 12 j 10 15 13 G 1 T 14 T G 15 2020年4月7日 编译原理 While语句的翻译 文法 G S S whileEdoS文法改造为 S CS1C WEdoW while 2020年4月7日 编译原理 1 W while W head Nextguad 当用W while归约时 Nextguad记下E的第一个四元式的位置 保留在Wguad中 2 C WEdo backpatch Etrue Nextguad C chain Efalse C head W head 当使用C WEdo进行归约时 E的代码已经生成有两个出口Etrue和Efalse 扫描完do后 可以回填Etrue 而Efalse要到S1语句全部生成后才能回填 因此为待填信息 由C向后传递 While语句的语义动作 2020年4月7日 编译原理 While语句的语义动作 3 S CS1 Backpatch S1chain C head S chain C chain GEN goto W head 当用上式进行归约时 S1语句全部产生 while语句结束应返回 因此产生四元式 gotow head 同时回填Efalse 2020年4月7日 编译原理 whilea 0 b 0doifx ythenb b 1elsea a 1 假设四元式序列从100开始编号100 j a 0 102 101 j 0 112 102 j b 0 104 103 j 101 112 104 j x y 106 105 j 0 109 106 b 1 T1 107 T1 b 108 j 100 109 j a 1 T2 110 T2 a 111 j 100 112 2020年4月7日 编译原理 文法G S S SaA AA AbB BB cSd e 1 证明AacAbcBaAdbed是文法的一个句型 2 请写出该句型的所有短语 素短语及句柄 3 为文法G S 的产生式构造相应的翻译子程序 使句型AacAbcBaAdbed经该翻译方案翻译后 输出为131042521430 2020年4月7日 编译原理 文法及相应的翻译方案如下 S bTc print 1 S a print 2 T R print 3 R R S print 4 R S print 5 对于输入符号串bR bTc bSc ac 该符号串的输出是什么 输出为1453142431 归约的次序为