编译原理第八章详解.ppt

第八章 语法制导翻译和中间代码生成 ;源程序的结构分析 词法分析 ch4 语法分析 ch5、ch6、ch7 语义分析 由语法分析程序直接调用相应的语义子程序 首先生成语法树（或该结构的某种表示），再进行语义处理 生成中间代码 ;编译中的逻辑阶段;语义处理的任务： 静态语义检查 静态语义：语法结构 静态语义检查：审查静态语义 动态语义处理 动态语义：程序单元执行的操作 动态语义处理：生成(中间/目标)代码;语义处理的实现： 属性文法：描述语义规则。--工具 语法制导翻译：在语法分析的同时，执行语义规则描述的动作： 检查静态语义 生成中间代码/目标代码;语义处理的环境：符号表 为语义分析提供类型、作用域等信息。 为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。; 本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式，最后讨论一些语法成分的翻译工作。 ; 第8章 语法制导翻译和中间代码生成 ;8．1 属性文法 ;;例如 G：E→ T1 + T2 | T1 or T2 　　　　 T→ num | true | false;E→ T1 + T2 { T1．t = int AND T2．t = int } E→ T1 or T2 { T1．t = bool AND T2．t = bool } T→ num { T．t = int } T→ true { T．t = bool } T→ false { T．t = bool } ;对输入串3+4的语法树： ;例8.2 描述说明语句中各种变量的类型信息的语义规则;8．2 语法制导翻译概论 ; 语法制导翻译的具体实现途径不难。如有一个LR分析器，扩充它的分析栈，使得每个文法符号都跟有语义值。同时扩充LR分析器功能，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应语义子程序。 ;例 算术表达式求值的语义描述 ;LR分析表如下;LR分析输入串2+3*5;步骤 状态栈 语义栈（值栈） 符号栈 剩余输入串 归约动作 8 0163 -2-3 #E+F *5# r6 9 0169 -2-3 #E+T *5# r4 10 01697 -2-3- #E+T* 5# 11 016975 -2-3-- #E+T*5 # 12 01697（10）-2-3-5 #E+T*F # r6 13 0169 -2-（15） #E+T # r3 14 01 -（17） #E # r1 15 接受 ; 按照上述实现办法，若把语义子程序改为产生中间代码的动作，则可在语法制导下生成中间代码。 （选作实验） ;8．3 中间代码的形式 ;一、 逆波兰记号 ; 逆波兰表示很容易扩充到表达式以外的范围，只要遵守运算对象后直接跟它们的运算符这条规则即可。 ;二、 三元式和树形表示 ;如： a：=b*c+c/d表示为： ; 树形表示是三元式的翻版。表达式的树形表示很容易实现：简单变量或常数的树是自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2、e1*e2，-e1的树为： ;; 有时为了直观，也把四元式的形式写成简单赋值形式，例如把上述四元式写成： ; 四元式和三元式的主要不同在于：四元式对中间结果的引用必须通过给定的名字，三元式是通过产生中间结果的三元式编号。 ;8．4 简单赋值语句的翻译 ;语义变量id．name：id表示的单词的一属性 语义变量E．place：表示存放E值的变量名在符 号表的登录项或一整数码 语义过程emit：表示输出四元式到输出文件上 语义过程newtemp：表示生成一临时变量。 函数Lookup（id．name）：查id．name是否在符号表中，如在，则返回指向该登录项指针，否则返回nil。 ; 下面列出了翻译赋值语句到四元式的语义描述，这里的语义工作包括对变量进行“先定义后使用”的检查。 ;（2） E→E1 + E2 { E.place := newtemp； emit（E.place ‘:= ’ E1.place‘+’E2.place）