编译原理(8).ppt

第八章语法制导翻译和中间代码生成 华北电力大学 计算机系 8 0 编译程序的任务是把源程序翻译成目标程序 这个目标程序必须和源程序的语义等同 尽管它们的结构完全不同 但它们表达的结果应完全相同 编译的阶段分为 源程序 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 目标程序语法分析以后 将进入语义分析阶段 语义分析主要有两个功能 第一 审查每个语法结构的静态语义 即验证语法结构合法的程序是否真正有意义 第二 如果静态语义正确 语义处理要执行真正的翻译 即要么生成程序的一种中间代码 要么生成实际的目标代码 中间代码 是复杂性介于源程序语言和机器语言的一种表现形式 直接生成目标代码 可以减少中间环节 加快处理速度 节省额外开销 通过中间代码生成目标代码 使得编译程序结构在逻辑上更为简单明确 同时细化处理过程 有利于代码优化 语义分析与中间代码生成 词法分析与语法分析以后进入语义分析和中间代码生成阶段希望语义分析和中间代码生成自动实现但语义分析过程中语义形式化的方法很困难 没有类似词法或语法那样形式化的方法实现语义的分析 至少没有公认的实用方法目前 普遍采用属性文法和语法制导的翻译方法对语义处理工作进行比较规范和抽象的描述 8 1属性文法 属性文法是语法制导翻译的重要工具 通过它来说明程序设计语言的语义 也就是说 属性文法来实现制导作用 一个属性文法包含一个上下文无关文法和一系列语义规则 这些语义规则附在文法的每个产生式上 在语法分析过程中 既要分析语法正确性 又要描述语义规则的动作 从而实现语义处理 可见 与以前文法增加了语义规则的描述 实际上 在语法分析过程中 除了考虑移进和规约 又要解释语义描述 属性概念解释 属性常用以描述事物或人物的特征 性质 品质等等 定义 一个属性文法是一个三元组 A G V F 其中 G是上下文无关文法 V是属性集 F是断言或谓词集 属性与文法的非终结符或终结符相联 属性像变量一样 可以计算和传递 属性计算的过程就是语义处理的过程 断言或谓词与文法的产生式相联 断言或谓词就是一组属性的计算规则 即语义规则 属性文法记号 N t 表示与非终结符N相联的属性t 例如 E T1 T2 T1orT2T num true false属性文法可以描述为 E 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 与非终结符相关的属性t 与产生式相关的断言为 两个T的属性相同 在属性文法中 描述属性 断言和语义规则的形式多种多样 例如 简单算术表达式求值的语义描述 产生式语义规则 0 L Eprint E val 1 E E1 TE val E1 val T val 2 E TE val T val 3 T T1 FT val T1 val F val 4 T FT val F val 5 F E F val E val 6 F digitF val digit lexval在上述属性文法中的每个非终结符都有一个属性 val 属性 属性分为两种 继承属性 用于 自上而下 传递和计算综合属性 用于 自下而上 传递和计算 属性信息的传递 对每个产生式 左部的非终结符属性来自右部非终结符的计算 也就是说这种属性的获得受到右部属性的影响 是综合属性 对于终结符 只有综合属性 产生式左部属性可能来自右部某个非终结符属性的传递 即存在着继承属性 8 2语法制导翻译概论 在语法分析过程中 每一步的进展 都根据每个产生式所对应的语义规则描述的语义动作进行翻译的方法称做语法制导翻译 采用自上而下的分析 在用某一个产生式进行推导的同时就进行相应的语义动作 即执行对应的一组语义规则 采用自下而上的分析 在用某一个产生式进行规约的同时就执行相应的语义动作 即执行对应的一组语义规则 这些语义规则就是程序设计语言中的语义子程序 语义子程序可以完成任何语义动作 在语法分析的同时调用这些语义子程序完成相应的语义分析工作 这样在分析语句符合语法的同时也就求出表达式的 值 如果仍然采用自下向上分析方法 在分析过程中 也要有分析栈 分析表和输入串 因为 增加了语义分析 所以增加了一个语义栈 即栈包括三个部分 状态栈 符号栈和语义栈 举例 产生式语义规则 0 L Eprint E val 1 E E1 TE val E1 val T val 2 E TE val T val 3 T T1 FT val T1 val F val 4 T FT val F val 5 F E F val E val 6 F digitF val digit lexval 对输入符号串 2 3 5进行分析 扩充的分析栈 状态栈 语义栈和文法符号栈 使得每个文法符号都与语义有关 形式如下表 分析与计算过程 本例是直接生成计算值 如果把语义子程序该为生成中间代码 那么就可以在语法制导下逐步产生中间代码 8 3中间代码的形式 中间代码是编译程序使用的一种独立于目标机的 易于翻译成目标程序的中间表示形式中间代码的复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间常用的中间代码 逆波兰式 树形表示 三元式 四元式等 其中以四元式最为普遍 例如 赋值语句 A B C D 四元式为 B T1 C D T2 T1 T2 T3 T3 A 8 3中间代码的形式 逆波兰记号将运算对象写在前面 运算符号写在后面 如 a b ab a b ab 也称为后缀式 逆波兰表示最大的优点是易于计算机处理表达式 表现为利用栈的操作 自左向右扫描算术表达式 如果遇到算术运算对象 则将其压入栈顶 如果遇到运算符 若为两目运算 则对栈顶两元素计算 将结果替换栈顶两元素 若为一目运算 则结果替换栈顶一个元素 这种方式特别适合解释执行的程序设计语言的中间表示 逆波兰表示不仅适用于算术表达式 也可以用于结构的控制语句 转移语句等 但是 处理起来要复杂的多 逆波兰表示 遇到运算对象后 就把它压入堆栈 分别将a b c压入栈底 a在最底 遇到运算符号 若为两目运算 计算栈顶的两个运算对象 b c 再做 运算 8 3中间代码的形式 三元式和树形表示把表达式或语句用一组三个元素的式子表示 三个元素为 算符 OP 第一运算对象 第二运算对象 例如 a b c b d可以表示为 1 b c 2 b d 3 1 2 4 3 a 三元式中含有对中间结果的引用 即具有继承性 这种继承性可以表述多目计算 三元式的树形表示 简单变量或常数的树就是该变量或常数自身 二目运算对应二叉树 多目运算对应多叉树 为了便于安排存贮空间 多叉树往往要转换为二叉树 8 3中间代码的形式 四元式四元式是一种比较常见的中间代码形式 四元式的四个元素为 运算符 第一运算对象 第二运算对象 运算结果 四元式简单表示 t1 b c b c为运算对象 为运算符 t1为运算结果 例如 a b c b d的四元式表示为 1 b c t1 2 b d t2 3 t1 t2 t3 4 t3 a 与三元式的区别在于对中间结果的引用必须通过给定的名字 而三元式通过中间结果的编号 所谓三地址 就是计算机指令除了操作码外 包含三个地址 两个为运算对象 一个结果 8 3中间代码的形式 例题 分别给出表达式 a b c d的逆波兰式和四元式表示 逆波兰式 a b c d a bc d abc d abc d abc d 注意 为求负的运算符 四元式 b c T1 a T1 T2 T2 T3 T3 d T4 8 3中间代码的形式 无论是逆波兰表示 还是三元式或四元式都是编译过程中的中间代码表现形式 将程序设计语言中的各种语句按照语义规则进行翻译的过程中形成的中间代码可以是四元式 三元式或逆波兰式等 8 4简单赋值语句的翻译 符号表 在编译过程中 为了完成源程序到目标代码的翻译 需要不断收集 记录和使用源程序中一些语法符号 特征和属性等相关信息 将这些信息建立一个表格 称为符号表 赋值语句由文法A id E描述 其中 A为非终结符代表赋值语句 id为赋值语句的左部 可以为简单变量或逻辑变量 E为右部的算术表达式 逻辑表达式或者其他类型的表达式 首先对id表示的单词定义一个属性id name 用做语义变量 用Lookup id name 表示审查id name是否出现在符号表中 如果在 则指向该项的登录指针 否则 返回nil 语义过程emit表示输出四元式到输出文件上 语义过程newtemp表示生成一个临时变量 每调用一次 生成一新的临时变量 语义变量E place表示存放E值的变量在符号表的登录项 如果E是一个临时变量 则E place表示一个整数码 赋值语句直观的语义是将赋值号右边表达式的值赋予左部量 具体语义处理时要注意赋值号两边类型一致的要求 若类型一致可直接赋值 若不一致或拒绝赋值或以左部量类型为准对右部表达式E的值产生类型转换指令 赋值语句的四元式翻译 S id E p lookup id name ifpnilthenemit p E place elseerror E E1 E2 E place newtemp emit E place E1 place E2 place 上述假设变量类型是一致的 但是 实际上 一个表达式中有各种类型的变量 所以语义规则上要有相应的处理 见P180 181 这时需要注意的是 除了值的属性以外 还要有类型的属性 根据数据结构类型的不同 语义处理的复杂程度也不同 8 5布尔表达式的翻译 布尔表达式的作用 一是计算逻辑值 二是控制流程 布尔表达式的组成由布尔运算符 与 或 非 和布尔变量或关系表达式 关系表达式结果为布尔量 关系表达式的形式为 E1ropE2 其中 E1和E2都是算术表达式 rop为关系运算符 布尔表达式的翻译方法 计算布尔表达式的第一种方法 计算每部分的真假值 步步计算 最后计算整个表达式的值 计算布尔表达式的第二种方法 采用某种优化算法 即只计算部分表达式 就能得出整个表达式结果 根据不同计算方法 翻译的过程不同 布尔表达式aorbandnotc翻译成四元式序列t1 notct2 bandt1t3 aort2关系表达式a b 可以看成等价的条件语句ifa bthen1else0 翻译成四元式序列为 ifa bgoto 4 t 0goto 5 t 1 其中用临时变量t存放关系表达式a b的值 控制语句中布尔表达式的翻译方法 控制语句通常有三种 if then if then else和while do 语法形式为 S ifEthenS1 ifEthenS1elseS2 whileEdoS1实际上作为条件控制的语句E 它的的四元式翻译思路是 E为aropb生成代码为 ifaropbgotoE true和E false 表达式有两个出口 真出口和假出口 af表达式翻译成四元式序列ifafgotoE truegotoE false上述四元式序列引出两个问题 1是优化代码 2是 真出口 和 假出口 在四元式生成时并不能具体确定 必须要生成完后 返回来重新确认 即 回填 为了记录将来需要 回填 的地址 采用一种叫 拉链 的办法 回填E true地址叫 真 拉链 回填E false地址叫 假 拉链 程序设计语言中的语句标号是标识一个语句的 它在程序中出现有两种意义 一是定义性出现 如 L S 另一是使用性出现 如 gotoL 编译程序处理过程中 对标号的处理是 程序中某个标号的第一次出现 无论是定义性还是使用性 都要填写标号表 标号名即标号本身或相应的内码表示 定义与否标志为 定义性出现D 1 使用性出现D 0 地址 当D 1时 add为标号L所标识的语句翻译成四元式序列的第一个四元式地址 当D 0时 标号L还未定义 需要将来回填 但这时要把所有以L为转移目标的四元式地址记录下来 以便一旦L确定可以回填 关于拉链回填方法的另外一角度的分析 关于拉链回填方法的另外一角度的分析 例如 10gotoL1 20gotoL1 30gotoL1 40L1 注意上述10 20 30 40不是语句标号 而是语句的地址 前3次出现L1标号 为使用性 第四次出现为定义性出现 每出现L1标号对应的四元式10 j 0 20 j 10 30 j 20 40 j 30 按照逆序反填回去 8 6控制结构的翻译 在程序设计语言中 控制结构语句通常有 if thenif then elsewhile do在控制语句中的布尔表达式翻译过程中 对 真出口 和 假出口 通常采用 拉链 回填 方法进行翻译确认 事实上 在对于整个控制结构语句也存在着一个出口不确定的问题 那就是当执行完整个控制语句后 将执行一个无条件转移语句指令 将控制离开这个语句 但是 在完成整个语句前这个无条件转移指令的地址无法确认 8 6控制结构的翻译 以条件控制语句ifEthenS1elseS2为例 在扫描到then时才能知道E的 真出口 在处理完S1 到达else时才能确定 假出口 只有翻译完S2以后才能确定无条件转移的地址OUT 对于嵌套的控制结构语句也是如此 如 ifE1thenifE2thenS1elseS2elseS3 当翻译完S2后仍然无法确定无条件转移控制目标地址 可见 转移目标的确定与语句所处环境有关 与布尔表达式翻译类似采用链的方式将所有四元式链接起来 一旦确定了转移目标地址 立刻回填 真正的回填工作将在处理该控制语句的外层环境后的时候进行 E的代码 S1的代码 Jumpout S2代码 Out 8 6控制结构的翻译 开关语句 假定的语句形式为 SwitchEofCaseV1 S1CaseV2 S2 CaseVn 1 Sn 1Default Sn endCase语句翻译成一系列的转移语句 t E L1 ift V1gotoL2 S1 gotonext L2 ift V2gotoL3 S2 gotonext LN 1 ift Vn 1gotoLn Sn 1 gotonext Ln Sn next 开关语句也可采用二维表方式翻译处理 建立一个n项元维数组 第一元为Vi的值 第二元为Si的值 语句标号 编译程序构造这个二维表 将计算出的E的值送入这个表的最后一项的Vn中 最后一项的Sn就是default对应的语句标号 构造查表程序 将计算出的E的值与表中的每个Vi值进行对比 如果相等 则执行对应的Si语句如果找不到相等的Vi则执行最后一项的Sn 如果case项比较多 则构造二维表可采用杂凑方法 如果E的值范围比较小 则可建立连续二维表 在空白单元放缺省语句标号 这样查询效率会高 8 6控制结构的翻译 开关语句的翻译也可以将测试都放在最后 计算E的值 并把结果放在临时变量t的中间代码gototest L1 S1的中间代码 gotonext L2 S2的中间代码 gotonext Ln 1 Sn 1的中间代码 gotonext Ln Sn的中间代码 gotonext test ift V1gotoL1ift V2gotoL2 ift Vn 1gotoLn 1gotoLnnext 对于开关语句结构 当扫描到switch时 产生语句标号next tset和临时变量t 计算表达式E的值 并赋予临时变量t 扫描到of后则产生四元式gototest 每扫描到一个case 就产生一个语句标号L 并送入符号表 同时存入对应的V值 生成对应S语句的中间代码 生成gotonext 扫描到end后 则形成多个分支代码 8 6控制结构的翻译 gotoL语句的翻译 如果gotoL语句时向上的 那么 当编译碰到这个语句时 L必然时已经定义过的 通过对L查找符号表获得它的地址p 编译程序可产生gotoL语句的四元式 j p 如果gotoL语句时向下的语句 则语句标号L就尚未定义 如果L是第一次碰到 则L填