语义分析与中间代码生成.ppt

S P O P 第8章语义分析与中间代码生成 要求明确语义分析的任务明确属性文法和语法制导翻译的含义明确自底向上和自顶向下语法制导翻译的区别和特点明确生成中间代码的目的 中间代码的几种形式 教学目标 8 1语义分析的任务8 2语法制导翻译8 3中间代码8 4简单赋值语句的翻译8 5布尔表达式的翻译 教学内容 词法分析 语法分析 解决单词和语言成分的识别及词法和语法结构的检查 语法结构可形式化地用一组产生式来描述 给定一组产生式 我们能够很容易地将其分析器构造出来 本章要介绍的是语义分析和中间代码生成技术 程序语言中间代码目标代码 翻译 翻译 根据语义规则对识别出的各种语法成份分析其含义 进行初步翻译 生成相应的中间代码或直接生成目标代码 1 确定数据类型 2 语义检查动态语义检查 在运行时刻进行静态语义检查 在编译时完成 3 识别含义 进行真正的翻译 8 1语义分析的任务 类型检查 控制流检查 确保控制语句有合法的转向点 例如 C语言中的break语句使控制跳离包括该语句的最小的switch while或for语句 如果不存在包括它的这样的语句 则应报错 静态语义检查 静态语义检查 一致性检查 很多情况下要求对象只能被定义一次 例如 语言中规定一个标识符在同一作用域中只能被说明一次 同一case语句的标号不能相同 枚举类型的元素不能重复出现等 相关名字检查 有的语言中有时规定 同一名字必须出现两次或多次 例如 Ada语言中 循环或程序块可以有一个名字 它出现在这些结构的开头和结尾 如同语句括号一般 编译程序必须检查它们的配对情况 实际应用中比较流行的语义分析方法 基于属性文法的语法制导翻译方法 8 2语法制导翻译 属性文法是Knuth在1968年提出的属性文法的特点是一种接近形式化的语义描述方法长于描述静态语义 短于描述动态语义每个语法符号有相应的属性符号每个产生式有相应计算属性的规则属性变量 属性表达式 8 2 1属性文法 附加了一组属性和运算 语义 规则的文法 文法符号X的属性t常用X t来表示 语义规则是根据产生式所蕴涵的语义操作建立起来的 并与语义分析的目标有关不同的产生式对应不同的语义规则不同的分析目标也对应不同的语义规则 静态语义检查 符号表操作 代码生成及打印各种错误信息 非终结符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 产生式 例8 1 根据文法符号的语义 为文法符号设置属性 用来表示文法符号的语义终结符使用单词的属性 id val 保留字 if begin function 常数 40 12 232 80 TCP IP 标识符 sum tcc id语法变量根据实际需要设定属性表达式E E type E val 属性的设定 8 2 2语法制导翻译的过程 语法制导翻译 将语义规则与语法规则相结合 在语法分析的过程中通过执行语义动作 计算语义属性值 从而完成预定的翻译工作 自底向上语法制导翻译 自顶向下语法制导翻译 语法制导翻译的实现 语法制导翻译分为两种处理方法 1 语法制导定义 自底向上 对每个产生式编制一个语义子程序 在进行语法分析的过程中 当一个产生式获得匹配时 就调用相应的语义子程序实现语义检查与翻译 这种实现方案隐藏了其中语义规则的计算次序等实现细节 不必规定翻译顺序 2 翻译方案 自顶向下 在产生式右部的适当位置 插入相应的语义动作 按照分析的进程 执行遇到的语义动作 这是一种动作与分析交错的实现方案 输入符号串 分析树 执行语义规则 翻译结果 翻译步骤 从分析树得到描述结点属性间依赖关系的依赖图 由依赖图得到语义规则的计算次序 1 分析输入符号串 建立分析语法树 进行语义规则的计算 得到翻译结果 8 2 3语法制导定义 对每个产生式编制一个语义子程序在进行语法分析的过程中 当一个产生式获得匹配时 就调用相应的语义子程序实现语义检查与翻译 自底向上传递信息 自顶向下 自左向右 传递信息 1 文法非终结符既有综合属性 也可有继承属性 2 开始符号没有继承属性 3 终结符只有综合属性 由词法分析器提供 几点说明 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 例8 综合属性 语义规则 产生式 一个结点的综合属性值是其子结点的某些属性来决定的 3 4的注释分析树 通常使用自底向上的分析方法在每个结点处使用语义规则来计算综合属性值当一个产生式获得匹配时 就调用相应的语义子程序从叶结点到根结点进行计算 只含有综合属性的语法制导定义称为S属性定义 8 2 4S属性定义与自底向上翻译 LR分析器可以改造为一个翻译器 在对输入串进行语法分析的同时对属性进行计算LR分析器增加属性值 语义 栈 例8 3继承属性L in intid1 id2 id3 一个结点的继承属性值是由其父结点或兄弟结点的某些属性决定的 8 2 5L 属性定义 L 属性文法 包含综合属性和继承属性的属性文法 语法制导定义 如 算术表达式求值的属性文法 说明语句的属性文法 翻译思想 将语义动作插入到产生式的某个位置特征规定在语法分析中使用语义规则进行计算的次序保证当动作使用某属性时 该属性必须是有效的 最左派生表示形式 例8 4 建立说明语句的翻译方案 将语义动作中继承属性的计算前移 使它出现在其相应文法符号之前D T L in T type LT int T type integer T real T type real L L1 in L in L1 id addtype id entry L in L id addtype id entry L in realid1 id2的处理过程D T L in T type L real T type real L in T type L real L in real L real L in real L1 in L in L1 id2 addtype id2 entry L in real L1 in real L1 id2 addtype id2 entry L in real L1 in real id1 addtype id1 entry L1 in id2 addtype id2 entry L in realid1 id1 entry real id2 id2 entry real D T L in T type LT int T type integer T real T type real L L1 in L in L1 id addtype id entry L in L id addtype id entry L in 生成中间代码的目的 1 便于优化 2 便于移植 常见的中间代码形式 后缀式三地址代码 四元式 三元式和间接三元式 图形 抽象语法树 有向无环图 中间代码 一种介于源语言和目标语言之间的中间语言形式 8 中间代码 Java语言 NET框架 GCC 中缀表示后缀表示a bab a b cabc a b cab c a b c b dabc bd 特点 1 运算对象出现的顺序和原有顺序 从左到右 相同2 运算符按实际计算顺序 从左到右 出现3 运算符紧跟在运算对象的后面出现 且没有括号 优点 简明 便于计值 8 3 1后缀式 分别给出下列表达式的后缀表示 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 8 3 2三地址代码 种类 1 x yopz形式的赋值语句 其中op是二元运算符 2 x opy形式的赋值语句 其中op是一元运算符 3 x y形式的赋值语句 4 无条件转移语句gotoL 表示下一个要执行的语句是标号为L的语句 5 条件转移语句ifxropygotoL中 rop为关系运算符 如果x和y满足关系rop 就转而执行标号为L的语句 否则顺序执行下一个语句 2 具体实现 四元式 结果 通常是由编译引进的临时变量 例 X A B C D E T1 T2 T3 T4为临时变量 由四元式优化比较方便 表达式的三元式 第三个三元式中的操作数 1 2 表示第 1 和第 2 条三元式的计算结果 三元式 不便于代码优化 删除某些三元式后可能需作一系列的修改 例 x y y z y z 抽象语法树 8 3 3图形表示 有向无环图 8 4表达式及赋值语句的翻译 简单表达式的文法如下 A i EE E E E E E E i非终结符A代表 赋值语句 语义子程序所涉及到语义变量 语义过程及函数说明如下 1 对非终结符的E定义语义变量E place 即E place表示存放 值的变量名在符号表中的入口地址或临时变量名的整数码 定义语义函数newtemp 即每次调用newtemp 时都要回送一个代表新临时变量的整数码 临时变量按产生的次序为 定义语义过程emit op arg1 arg2 result 其中的emit是产生一个四元式并填入四元式的表中 arg1 arg2是操作数 result是运算结果 4 定义语义函数lookup i name 其功能是审查i name是否出现在符号表中 是则返回i name在符号表中的入口指针 否则返回空 使用上述的语义变量 过程和函数 可以写出文法每个产生式的语义子程序 1 A i E p lookup i name if p NULL error elseemit E place P 2 E E 1 E 2 E place newtemp Emit E 1 place E 2 place E place 3 E E 1 E 2 E place newtemp emit E 1 place E 2 place E place 4 E E 1 E place newtemp emit uminus E 1 place E place 5 E E 1 E place E 1 place 6 E i p lookup i name if p NULL E place p elseerror 在上面的语义分析过程中 没有考虑到静态语义检查 在实际应用中 要全面考虑语句的翻译 例如 E E 1 E 2 该语句的语义子程序的翻译可以写成 E E 1 E 2 E place newtemp ifE 1 type intANDE 2 type intthenbeginemit E place E 1 place i E 2 place E type intendelseifE 1 type realANDE 2 type realthenbeginemit E place E 1 place r E 2 place E type realend elseifE 1 type int andE 2 type real thenbegint newtemp emit t itr E 1 place emit E place t r E 2 place E type realendelse E 1 type realANDE 2 type int begint newtemp emit t itr E 2 place emit E place E 1 place r t E type realend 例题8 7试分析赋值语句X B C D 的语法制导翻译解答 赋值语句X B C D 的语法制导翻译过程如表8 2所示 8 4 2布尔表达式的翻译 布尔表达式的文法为 E E E E E E E i iropi其中的rop为 运算符 1 布尔表达式值的计算计算布尔表达式的值通常有两种方法 第一种方法和算术表达式的计算方法一样 根据顺序和优先级一步步计算出来 例如 1 0 0 0 1 1 0 0 1 0 0 1 0 1 另一种方法就是根据布尔表达式的特点实施某种优化 即不必一步一步地计算布尔表达式中所有运算对象的值 而是省略不影响结果的运算 例如 在计算A B时 若计算出A的值为1 则B的值就无须再计算 在计算A B时 若A的值为0 则B的值无须要再计算 因为A B的值一定为0 2 布尔表达式的翻译方法 给出布尔表达式ifa bthen1else0 根据布尔表达式的第一种计算方法 写出该表达式的四元式为 1 ifa bgoto 4 2 t 0 3 goto 5 4 t 1 5 翻译方法如下 E 1 E 2 E 1 为TRUE 则整个表达式为TRUE 转向条件为 真 的出口 E 1 为FALSE 则转向E 2 的判断 若E 2 为TRUE 则整个表达式为TRUE 转向条件为 真 的出口 用E true指针代表真的出口 若E 1 为FALSE 则转向E 2 的判断 若E 2 为FALSE 则整个表达式为FALSE 则转向条件为 假 的出口 用E false代表假的出口 E 1 E 2 E 1 为FALSE 则整个表达式为FALSE 转向条件为 假 的出口 E 1 为TRUE 则转向E 2 的判断 若E 2 为TRUE 则整个表达式为TRUE 转向条件为 真 的出口 若E 1 为TRUE 则转向E 2 的判断 若E 2 为FALSE 则整个表达式为FALSE 转向条件为 假 的出口 根据上述的思想将布尔表达式翻译成四元式的描述 其中nextstat给出输出序列中下一个四元式序号 emit过程每被调用一次 nextstat增加1 E E 1 E 2 E place newtemp emit E place E 1 place E 2 place E E 1 E 2 E place newtemp emit E place E 1 Place E 2 place E E 1 E place newtemp emit E place E 1 place E E 1 E place E 1 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 true E place newtemp emit E place 1 E true E place newtemp emit E place 0 8 4 3在控制语句中布尔表达式的翻译 2020 3 25 56 S ifEthenS1的翻译 代码结构 E true E false 2020 3 25 57 例 ifa bthena a a ifa bgotoC true S1 begin gotoC false S next S1 begin t1 a aa t1S next 1 E E 1 VE 2 backpatch E 1 false E 2 codebegin E codebegin E 1 codebeginE true merge E 1 true E 2 true E false E 2 false 2 E E 1 E 2 backpatch E 1 true E 2 codebegin E codebegin E 1 codebeginE true E 2 trueE false merge E 1 false E 2 false 3 E E 1 E true E 1 False E codebegin E 1 CodebeginE false E 1 true 4 E E 1 E true E 1 true E false E 1 falseE codebegin E 1 codebegin 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 true E true nextstat E codebegin nextstat emit goto 7 E false E false nextstat E codebegin nextstat emit goto 代码结构 S ifEthenS1elseS2的翻译 例题8 8给出布尔表达式ifafthenS1elseS2 它翻译成四元式序列为 1 ifaf 例题8 8给出布尔表达式ifafthenS1elseS2 它翻译成四元式序列为 1 ifa bgotoE true 2 goto 3 3 ifc dgoto 5 4 gotoE false 5 ife fgotoE true 6 gotoE false 7 S1的四元式 p goto q p 1 关于S2的的四元式 q 7 p 1 7 p 1 通过上面的例子可以看出 7 是该条件语句的真出口 p 1 是该条件语句的假出口 而E true和E false必须是在翻译到S1或S2时才能确定它的语句编号是什么 所以需要回填 并且需要回填的语句很多 如四元式 1 和 5 需要回填E true的值 4 和 6 需要回填E false的值 这些要回填的四元式标号需要记住 因此就采用 拉链 的技术 如果不能记住 则无法回填了 把需要回填E true的值作为真链 把需要回填E false的值作为 假 链 2020 3 25 65 拉链回填 一遍扫描先产生暂时没有填写目标标号的转移指令 对于每一条这样的指令作适当的记录 一旦转移的目标 标号 被确定下来 再将它 回填 到相应的指令中布尔表达式E设属性E turelist和E falselistE truelist 对应真出口EtrueE falselist 对应假出口Efalse两遍扫描 2020 3 25 66 拉链回填 翻译模式用到如下两个函数 1 merge p1 p2 将由p2指向的表接在p1所指向的链表后 返回p12 backpatch p i 把i作为目标标号回填到p所指向的链表中的每一个转移指令中去 此处的 链表 都是为 回填 作准备的 2020 3 25 67 拉链回填举例 拉链 P1 n4 j 0 n5 j a b n4 n6 j c d n5 n5 n6 n4 2020 3 25 68 拉链回填举例 并链 n1 j 0 n2 j a b n1 n3 j c d n2 P2 n3 n4 j n5 j a b n4 n6 j c d n5 P1 n6 0 n3 2020 3 25 69 n4 n2 n3 n5 n6 拉链回填 回填 n1 j n2 j a b n3 j c d n4 j n5 j a b n6 j c d P1 backpatch p i n5 n4 n3 n2 n1 i 0 i i i i i n1 0 拉链的技术如下 100 gotoE true 200 gotoE true 300 gotoE true 则链成 100 goto 0 200 goto 100 300 goto 200 把地址300作为链首 地址 100 为链尾 0为链尾标志 根据上面的翻译思想 我们给出将布尔表达式翻译成四元式的描述 其中 1 nextstat为给出序列中的下一个四元式的序号 emit过程每调用一次 nextstat的值就增加1 2 merge p1 p2 把以p1和p2为链首的两条链合并为一条以p2为链首的链 3 backpatch p t 把链首