静态语义分析和中间代码生成.ppt

第八章静态语义分析和中间代码生成 学习目标 掌握 语法制导的语义分析常见的中间代码形式 常见语法成分的属性文法或翻译方案理解 静态语义分析和中间代码生成 语法制导翻译方法使用属性文法 翻译模式为描述工具定义程序设计语言的语义及代码生成方法 语义分析在处理程序的声明部分时构造标识符的符号表在处理程序的语句部分时完成静态语义检查 静态语义分析和中间代码生成 8 1符号表8 2静态语义分析8 3中间代码生成8 4多遍的方法 符号表 符号表及其作用符号表 SymbolTable 符号表是存放标识符信息的一种表 其中的信息是标识符的属性 语义 如 种类 类型 偏移地址 占用空间等 符号表 符号表的作用符号表是连接声明与引用的桥梁 一个名字在声明时 相关信息被填写进符号表 而在引用时 根据符号表中的信息进行语义检查 进而生成中间代码 它的作用主要有 辅助语义的正确性检查辅助代码生成 符号表的设计如何有效记录各类符号的属性 以便在编译的各个阶段对符号表进行快速 有效的查找 插入 修改 删除等操作 是符号表设计的基本目标 符号表的组成表项分两部分 其中前者是标识符的名字 而后者是属性部分 不同种类的标识符属性不同 符号表的组织方式和查找方法符号表的组织方式可以是数组也可以是链表等等查找算法可以是顺序查表法 平分查表法 散列查表法等合理的组织和查找 将使得符号表的操作更高效 过程的说明部分 CONSTA 35 B 49 VARC D E PROCEDUREP VARG 符号表中的信息 变量相对本过程基地址的偏移量 符号表 符号表的生存期在编译过程中 每当遇到标识符时 就要查填符号表 若是新的标识符时 就向符号表中填入一个新的表项 否则 根据情况向符号表中的已有表项增填信息 如填入存储地址 或者查获信息 如进行语义检查等 符号表的信息将在词法分析 语法分析的过程中陆续填入 将用于语义检查 中间代码生成以及目标代码生成等不同的阶段 与语义分析相关的工作 8 2静态语义分析 静态语义检查编译期间所进行的语义检查动态语义检查所生成的代码在运行期间进行的语义检查收集语义信息为语义检查收集程序的语义信息为代码生成等后续阶段收集程序的语义信息 代码生成前程序合法性检查的最后阶段控制流检查控制流语句必须使控制转移到合法的地方 如跳转语句要有合法的跳转目标 break语句必须有合法的语句包围它 唯一性检查很多场合要求对象只能被定义一次 如枚举类型的元素不能重复出现 1静态语义分析的主要任务 代码生成前程序合法性检查的最后阶段名字的上下文相关性检查例如 变量在使用前必须声明 在外部不能访问私有变量 名字的定义和使用之间要满足一定的上下文相关性类型检查检查每个操作是否遵守语言类型系统的定义 1静态语义分析的主要任务 类型检查程序 typechecker 负责类型检查验证程序的结构是否匹配上下文所期望的类型为代码生成阶段搜集及建立必要的类型信息实现某个类型系统 typesystem 2类型检查 一个简单语言的上下文无关文法G P 2类型检查 类型表达式 typeexpressions 为程序单元的类型进行解释由基本类型 类型名字 类型变量 及类型构造子 typeconstructor 通过归纳定义得到的表达式类型系统 typesystems 将类型表达式赋给程序各个部分的规则集合 类型表达式和类型系统 2类型检查 类型表达式分四类定义基本数据类型表达式 积类型表达式 过程类型表达式 专用类型表达式基本数据类型表达式纯量类型表达式 bool int real有界数组类型表达式 array I T T bool int real I代表一个整数区间 如1 10指针数据类型表达式 pointer T T bool int real 指向类型为T的对象的指针类型 类型表达式 举例 积类型表达式T1 T2 Tn为上述数据类型表达式 若n 0 则表示为过程类型表达式fun T T是上述积类型表达式专用类型表达式type error专用于有类型错误的程序单元ok专用于没有类型错误的程序单元 类型表达式 举例 续 语法制导的方法可实现语言的一个类型系统将类型表达式作为属性值赋给程序各个部分设计实现类型检查的属性文法 翻译模式 类型检查程序的设计 2类型检查 处理声明的翻译模式作用 计算变量声明相关语法单位的类型信息 并保存标识符的类型信息到符号表 语法制导的类型检查程序 举例 1 V V1 T L in T type L V type make product 3 V1 type T type L num V V type T boolean T type bool T integer T type int T real T type real make product 3 type2 n 生成积类型表达式 含n个type2 处理声明的翻译模式 语法制导的类型检查程序 举例 2 T array num ofT1 T type array 1 num lexval T1 type T T1 T type pointer T1 type L L1 in L in L1 id addtype id entry L in L num L1 num 1 L id addtype id entry L in L num 1 L in为继承属性T type V type L num为综合属性 处理声明的翻译模式例 intx y z 语法制导的类型检查程序 处理表达式的翻译模式作用 计算表达式相关语法单位的类型信息 同时检查表达式运算数类型与给定运算是否兼容 语法制导的类型检查程序 举例 3 E true E type bool E false E type bool E int E type int E real E type real E id E type iflookup type id name nilthentype errorelselookup type id name E E1opE2 E type ifE1 type realandE2 type realthenrealelseifE1 type intandE2 type intthenintelsetype error E E1ropE2 E type ifE1 type realandE2 type realthenboolelseifE1 type intandE2 type intthenboolelsetype error E E1 E2 E type ifE2 type intandE1 type array s t thentelsetype error E E1 E type ifE1 type pointer t thentelsetype error 语法制导的类型检查程序 举例 4 处理语句的翻译模式 语法制导的类型检查程序 举例 5 S id E S type iflookup type id entry E typethenokelsetype error S ifEthenS1 S type ifE type boolthenS1 typeelsetype error S ifEthenS1elseS2 S type ifE type boolandS1 type okandS2 type okthenokelsetype error 处理语句的翻译模式 语法制导的类型检查程序 举例 6 S whileEthenS1 S type ifE type boolthenS1 typeelsetype error S S1 S2 S type ifS1 type okandS2 type okthenokelsetype error S break S type ok 8 3中间代码生成 定义 中间代码是复杂性介于源程序语言和机器语言之间的一种表示形式 作用源语言和目标语言之间的桥梁 避开二者之间较大的语义跨度 使编译程序的逻辑结构更加简单明确利于编译程序的重定向利于进行与目标机无关的优化 1常见的中间代码表示形式 有不同层次不同目的之分中间代码举例AST Abstractsyntaxtree 抽象语法树 TAC Three addresscode 三地址码 四元式 P code 特别用于Pasal语言实现 Bytecode Java编译器的输出 Java虚拟机的输入 例 算术表达式A B C D E C D NAST 抽象语法树 表示 A E B D C D C N 1常见的中间代码表示形式 例 算术表达式A B C D E C D NTAC 三地址码 表示 1 CDT1 T1 C D 2 BT1T2 T2 B T1 3 AT2T3 T3 A T2 4 CDT4 或T4 C D 5 T4NT5 T5 T4 N 6 ET5T6 T6 E T5 7 T3T6T7 T7 T3 T6 1常见的中间代码表示形式 Ti是编译程序引入的临时变量 1常见的中间代码表示形式 顺序执行的语句序列 其语句的一般形式x yopz op为操作符 y和z为操作数 x为结果 也可写成四元式的形式 opyzx 三地址码TAC 1常见的中间代码表示形式 在现行的编译程序中 AST是较常用的高级中间表示形式 接近源代码 TAC是较常用的低级中间表示形式 接近目标代码 许多编译程序都是将源程序首先翻译成等价的AST 然后再从AST转换成TAC 抽象语法树AST的特点 不含我们不关心的终结符 如逗号 括号 而只含标识符 常量等终结符不具体体现语法分析的细节步骤 例如seq stmt seq 可以表示为链表能完整体现源程序的语法结构 同时也没有损失源程序的任何语义信息 2生成抽象语法树 抽象语法树AST的特点 2生成抽象语法树 1语句系列 2if语句 例 生成抽象语法树的语法制导方法 2生成抽象语法树 S id ES ifEthenS1S whileEdoS1S S1 S2 S ptr mknode assign mkleaf id entry E ptr S ptr mknode if then E ptr S1 ptr S ptr mknode while do E ptr S1 ptr S ptr mknode seq S1 ptr S2 ptr mknode 构造AST内部结点mkleaf 构造AST叶结点S Ptr E ptr 指向AST某个结点的指针 例 生成抽象语法树的语法制导方法 2生成抽象语法树 TreeNode if stmt void TreeNode t newStmtNode IfK match IF if t NULL t child 0 exp match THEN if t NULL t child 1 stmt sequence if token ELSE match ELSE if t NULL t child 2 stmt sequence match END returnt E idE E1 E2E E1 E2E E1 E ptr mkleaf id entry E ptr mknode E1 ptr E2 ptr E ptr mknode E1 ptr E2 ptr E ptr E1 ptr TreeNode simple exp void TreeNode t term while token PLUS token MINUS TreeNode p newExpNode OpK if p NULL p child 0 t p attr op token t p match token t child 1 term returnt 3生成三地址码 顺序执行的语句序列其语句的一般形式x yopz op为操作符 y和z为操作数 x为结果 也可写成四元式的形式 opyzx 三地址码TAC是一种接近汇编语言的中间表示 3生成三地址码 TAC语句赋值语句x yopz op代表二元算术 逻辑运算 赋值语句x opy op代表一元运算 复写语句x y y的值赋值给x 无条件跳转语句gotoL 无条件跳转至标号L 条件跳转语句ifxropygotoL rop代表关系运算 标号语句L 定义标号L 3生成三地址码 语义属性id place id对应的存储位置E place 用来存放E的值的存储位置E code 对应于E的TAC语句序列S code 对应于S的TAC语句序列 赋值语句及算数表达式的语法制导翻译 3生成三地址码 语义函数 过程gen 生成一条TAC语句newtemp 在符号表中新建一个从未使用过的名字 并返回该名字的存储位置 TAC语句序列之间的链接运算 赋值语句及算数表达式的语法制导翻译 赋值语句及算数表达式的翻译模式 S id E S code E code gen id place E place E id E place id place E int E place newtemp E code gen E place int val E real E place newtemp E code gen E place real val 3生成三地址码 E E1 E2 E place newtemp E code E1 code E2 code gen E place E1 place E2 place E E1 E2 E place newtemp E code E1 code E2 code gen E place E1 place E2 place E E1 E place newtemp E code E1 code gen E place uminus E1 place E E1 E place E1 place E code E1 code 3生成三地址码 赋值语句及算数表达式的翻译模式 例翻译赋值语句A B C E1 place B E2 place C E place t1 t1 B C t1 B CA t1 为了直观 用B和C分别表示B和C在符号表的入口地址 翻译结果生成TAC序列t1 B CA t1 3生成三地址码 两种方法 直接对布尔表达式求值通过控制流体现布尔表达式的语义 布尔表达式的语法制导翻译 3生成三地址码 布尔表达式 直接对布尔表达式求值 1 表示true 0 表示false 采用与算术表达式类似的翻译方法 例 aorbandnotc被翻译成 1 t1 notc 2 t2 bandt1 3 t3 aort2 3生成三地址码 布尔表达式 通过控制流体现布尔表达式的语义方法 通过转移到程序中的某个位置来表示布尔表达式的结果优点 方便实现控制流语句中布尔表达式的翻译利用短路 short circuit 代码 避免不必要的求值 3生成三地址码 短路 short circuit E1orE2ifE1then1elseE2E1andE2ifE1thenE2else0已知E1为真时 不必再对E1orE2中的E2进行求值 已知E1为假时 不必再对E1andE2中的E2进行求值 布尔表达式的语法制导翻译 例a borc dande f采用短路代码 E true和E false分别代表E为真和假时要转移到的程序位置 即标号ifa bgotoE truegotolabel1label1 ifc dgotolabel2gotoE falselabel2 ife fgotoE truegotoE false 3生成三地址码 布尔表达式 翻译布尔表达式至短路代码 L 翻译模式 E E1 true E true E1 false newlabel E1or E2 true E true E2 false E false E2 E code E1 code gen E1 false E2 code E E1 false E false E1 true newlabel E1and E2 false E false E2 true E true E2 E code E1 code gen E1 true E2 code E E1 true E false E1 false E true E1 E code E1 code newlabel返回一个新的语句标号 3生成三地址码 布尔表达式 翻译布尔表达式至短路代码 L 翻译模式 E E1 true E true E1 false E false E1 E code E1 code E id1ropid2 E code gen if id1 placerop opid2 place goto E true gen goto E false E true E code gen goto E true E false E code gen goto E false 3生成三地址码 布尔表达式 例a borc dande f的翻译过程假定整个表达的E true Ltrue E false Lfalse E true LtrueE false Lfalse E1 true LtrueE1 false L1 E2 true LtrueE2 false Lfalse E1 true L2E1 false Lfalse E true LtrueE false Lfalse ifa bgotoLtruegotoL1 ifc dgotoL2gotoLfalse ife fgotoLtruegotoLfalse LabelL1 labelL2 if then语句 L翻译模式 S if E true newlabel E false S next Ethen S1 next S next S1 S code E code gen E true S1 code 控制语句的语法制导翻译 E code S1 code E true E false toE true toE false newlabel返回一个新的语句标号S next属性表示S之后要执行的首条TAC语句的标号 3生成三地址码 控制语句的共同特点是 根据布尔表达式取值 分别执行不同的语句序列 问题 不同的语句序列结束后 如何使控制转向语句的结束 例如 ifE1thenifE2thenS1elseS2elseS3 if then else语句 L翻译模式 E code S1 code E true E false gotoS next toE true toE fase S2 code S next S if E true newlabel E false newlabel Ethen S1 next S next S1else S2 next S next S2 S code E code gen E true S1 code gen goto S next gen E false S2 code 3生成三地址码 控制语句 while语句 L翻译模式 E code S1 code S1 next E false gotoS1 next toE true toE false E true S while E true newlabel E false S next Edo S1 next newlabel S1 S code gen S1 next E code gen E true S1 code gen goto S1 next 3生成三地址码 控制语句 顺序复合语句 L翻译模式 S S1 next newlabel S1 S2 next S next S2 S code S1 code gen S1 next S2 code P D S next newlabel S gen S next S1 code S2 code S next S1 next 3生成三地址码 复合语句 例 翻译语句whilea bdoifc dthenx y zelsex y z 3生成三地址码 S next Lnext E true L1E false Lnext S next L2 E true L3E false L4 S next L2 S next L2 8 4多遍的方法 在实际的编译器中 静态语义分析和中间代码生成的实现通常采用多遍的方法多次遍历抽象语法树 AST 第一次遍历 创建符号表第二次遍历 进行静态语义分析第三次遍历 生成TAC翻译模式定义的语义计算过程 被转变成遍历过程的处理算法 作业 将语句ifC DthenwhileA BdoX Y Z翻译为TAC序列