编译器设计和实现-——Lcc原理剖析.ppt

编译器设计与实现 Lcc原理剖析 华中科技大学计算机学院张德 2020 4 15 一 概述 1 编译器各阶段 2020 4 15 2 编译器各阶段的分组 前端 依赖于语言并很大程度上独立于目标机器 一般包括语法分析 词法分析 符号表的建立 语义分析 中间代码生成以及相关错误处理 后端 依赖于目标机器的阶段或某些阶段的某些部分 一般来说 后端完成的任务不依赖于源语言而只依赖于中间语言 主要包括代码优化 代码生成以及相关的错误处理和符号表操作 2020 4 15 二 符号表 符号表是编译器保存信息的中心库 编译器的各部分通过符号表进行交互 并访问符号表中的数据 符号 符号表把各种名字映射到符号集合 常量 标识符和标号都是名字 不同名字有不同的属性 符号管理不仅要处理符号本身 还管理符号的作用域 2020 4 15 1 符号的表示 structsymbol char name 名称intscope 作用域Coordinatesrc 在源程序中位置Symbolup 连接符号表中上一个符号Listuses 可保存一个Coordinate列表 表示使用情况intsclass 扩展存储类型 符号标记Typetype 如变量 函数 常量 结构或联合等信息floatref 被引用的粗略次数union 联合u为标号 结构 联合 枚举 常量 全局 和静态变量提供附加信息 u Xsymbolx 由后端处理 如为变量分配寄存器 为调试器产生数据信息 2020 4 15 1 符号的表示 scope域 enum CONSTANTS 1 LABELS GLOBAL PARAM LOCAL 第k层中声明的局部变量其scope域等于LOCAL k src域 typedefstructcoord char file unsignedx y Coordinate file指名包含该符号定义文件名 y和x表示出现的行号及行中位置 sclass域 符号扩展类型可以是AUTO REGISTER STATIC或EXTERN等首字母大写的类型表示全小写类型的指针 如Symbol 2020 4 15 2 符号表的表示 externTableconstants externTableexternals externTableglobals externTableidentifiers externTablelabels externTabletypes structtable intlevel 同symbol中scope域Tableprevious 符号表链表 指向level 1的表structentry structsymbolsym structentry link buckets 256 这是一个哈希链数组 方便插入 查找Symbolall 指向当前及其外层所有符号列表的表头 2020 4 15 3 符号表举例 intx y f intx inta intb y x a b if y 5 inta y x a b 2020 4 15 2020 4 15 4 符号表的相关操作 查找和建立标识符Symbolinstall constchar name Table tpp intlevel intarena Symbollookup constchar name Tabletp 标号 与标识符相似 但不涉及作用域常量 这些符号保存在constants表中产生变量 用于产生静态变量保存字符串等 2020 4 15 三 代码生成接口 这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口 Lcc接口包括一些共享数据结构 18个函数和包括36个操作符的语言 该语言用于将可执行代码从源程序生成dag 有向无环图 共享数据结构可供前后端共享 但某些域为一端私有 symbol就是一个共享数据结构 2020 4 15 1 类型度量 typedefstructmetrics unsignedcharsize align outofline Metrics size 类型的大小 align 对齐字节数 outofline 控制相关类型的常量的放置 为1时 不出现在dag中 存于静态变量中 Metricscharmetric Metricsshortmetric Metricsintmetric Metricsfloatmetric Metricsdoublemetric Metricsstructmetric 2020 4 15 2 接口记录 typedefstructinterface Xinterfacex Interface lcc为每一种目标机器形成一个独有的接口实例 x域是对interface的扩展 后段使用它存放与目标及其相关的接口数据和函数 对后端私有 2020 4 15 3 dag操作 可执行代码用dag来描述 函数体是用dag组成的序列或森林 每个dag都可以同过gen函数传给后端 dag节点structnode shortop shortcount Symbolsyms 3 Nodekids 2 Nodelink Xnodex 2020 4 15 3 dag操作 op域存放dag操作符 dag操作符后缀表示操作数类型 enum F FLOAT I INT U UNSIGNED P POINTER V VOID B STRUCT 如CNST 有变体CNSTI CNSTU CNSTP等 CNST 1 4 CNSTC CNST F CNSTI CNST I 2020 4 15 2020 4 15 2020 4 15 3 dag操作 举例 inti p f i p 2020 4 15 4 接口标志 unsignedlittle endian 1 目标机器存储是低位优先还是高位优先unsignedmulops calls 1 有硬件实现乘 除和求余 mulopes calls应等于0unsignedwants callb 1 通知前端产生CALLB节点以调用返回结构的函数unsignedwants argb 1 通知前端节点产生ARGB节点以产生结构参数unsignedleft to right 1 告诉前端按照从左到右的顺序计算和提交参数给后端unsignedwants dag 1 告诉前端传递dag给后端 2020 4 15 5 函数 前端将函数编译为私有数据结构 将函数的任意部分传递给后端之前 前端必须先对每个函数进行完整的分析 函数的处理 function函数包括前端过程gencode遍历前端的私有数据结构 将dag的每个森林传给后端过程gen gen选择代码 在dag上添加注释并将返回一个dag指针 gencode还可以调用local宣告新的局不变量 前端过程emitcode再次遍历 将gen返回的指针传递给emit函数发送代码 2020 4 15 6 上行调用 前段调用后端以执行代码生成和发送 后端调用前端完成输出 分配存储空间 查询类型等功能 上行调用即后端调用前端 allocate分配空间 保证对齐方式符合机器多数类型newnode分配新的dag节点newconst符号表中创建新的常量newtemp符号表中创建新的变量 2020 4 15 四 词法分析 词法分析器读入源程序 产生语言的基本词法单元 例 prt 56 2020 4 15 1 输入 2020 4 15 n cp limit 当limit cp小于某一个固定值时 调用fillbuf函数填充buffer 2 单词识别 部分文法 token keywordidentifierconstantoperatorpunctuatorpunctuator oneof 2020 4 15 定义 ID标识符FCON浮点常量ICON整型常量SCON INCRDECRDEREF emun definexx a b c d e f g a b defineyy a b c d e f g include token h LAST token h文件 yy 0 0 0 0 0 0 0 xx FLOAT 1 0 0 0 CHAR float xx DOUBLE 2 0 0 0 CHAR double xx CHAR 3 0 0 0 CHAR char xx SHORT 4 0 0 0 CHAR short xx INT 5 0 0 0 CHAR int xx UNSIGNED 6 0 0 0 CHAR unsigned xx POINTER 7 0 0 0 0 pointer xx VOID 8 0 0 0 CHAR void xx STRUCT 9 0 0 0 CHAR struct 2020 4 15 3 关键字的识别 可以通过查表完成 也可以通过硬编码方式识别 例如 当起始小写字母为i时由gettok函数中switch语句的case i 处理 2020 4 15 case i if rcp 0 f 4 标识符识别 case h case j case k case m case n case o case p case q case x case y case z case A case B case C case D case E case F case G case H case I case J case K case M case N case O case P case Q case R case S case T case U case V case W case X case Y case Z id if limit rcp MAXLINE cp rcp 1 fillbuf rcp cp 2020 4 15 assert cp rcp token char rcp 1 while map rcp 检查是否需要填充buffer 5 其他 另外还有 数字识别字符常量和字符串识别都是有gettok函数实现 实现方法相似 词法分析器可以有象LEX这样的工具实现 Lcc手工实现了词法分析器 体积更小 2020 4 15 五 语法分析 根据语言的文法分析 以确认输入是否符合语言规则 并建立输入源程序的内部表示 Lcc采用递归下降的语法分析 语法分析以形式语言理论为基础 采取语法制导翻译方法 处理程序中的错误 2020 4 15 1 表达式 表达式的表示 a b b a b 2020 4 15 表达式的分析 c语言的小部分表达式语法 expr term term term factor factor factor ID expr T expr T term term T term T term term T term term while t T term term while t T T term term while t t gettok T term term while t t gettok term 同理得分析函数term是 factor while t t gettok factor 2020 4 15 voidfactor if t ID t gettok elseif t t gettok expr expect c语言表达式分析赋值表达式 assignment expression conditional expressionunary expressionassign operatorassignment expressionTreeexpr1 inttok staticcharstop IF ID 0 Treep expr2 if t prec t 6elsereturnp 2020 4 15 条件表达式 conditonal expression binary expression expression conditional expression staticTreeexpr2 void Treep expr3 4 if t Treel r Coordinatepts 2 if Aflag 1 2020 4 15 另有二元表达式 一元表达式 后缀表达式和基本表达式 表达式分析多是用递归和大量switch语句实现 在编译领域用一个分析函数代替n个函数处理n级优先是非常流行的 关于表达式的分析还包括表达式语义的分析 如类型检查转换 函数调用分析等各种操作 2020 4 15 2 语句分析 代码的表示 表达式首先被编译为分析树然后转化为dag 每个函数的dag在代码表中被串起来 代码表表示了函数的代码 code结构 structcode enum Blockbeg Blockend Local Address Defpoint Label Start Gen Jump Switch kind Codeprev next union u 2020 4 15 语句的识别 voidstatement intloop Swtchswp intlev floatref refinc if Aflag 2 2020 4 15 if语句的识别 ifexpression 0gotoLstatement1gotoL 1L statement2L 1 staticvoidifstmt intlab intloop Swtchswp intlev t gettok expect 判断if后的 definept NULL walk conditional 0 lab 包含listnode函数生成dag并加入refinc 2 0 森林 把入口加入代码表 同时根statement loop swp lev 据接过设置flab tlabif t ELSE branch lab 1 t gettok definelab lab statement loop swp lev if findlabel lab 1 ref definelab lab 1 elsedefinelab lab 2020 4 15 在循环 switch goto语句中都用到了标号和跳转 标号使通过definelab函数定义的 而跳转通过branch函数生成 除语句识别外 还有声明的识别 声明的识别非常复杂 c语言中声明的形式很多 处理时大量的相互递归调用 经过前端的分析后 将源程序转化为dag 并添加进代码表 2020 4 15 3 小结 六 中间代码生成 编译器的后端通过function接口函数调用gencode和emitcode来遍历代码表 walk和listnodes函数操作处理dag森林 newnode函数为节点分配内存并用它的参数只来初始化节点的域 listnode还负责删除公共子表达式 2020 4 15 1 构建节点 Nodelistnodes Treetp inttlab intflab Nodep NULL l r intop if tp NULL returnNULL if tp node node标识listnode访问过的树returntp node if isarray tp type op tp op sizeop voidptype size elseop tp op sizeop tp type size switch generic tp op tp node p returnp 2020 4 15 2 控制流 最简单的一元和二元操作加入结点表 但是并不会出现在根中 赋值等操作可以用这种情况解决 要改变控制流需要跳转 caseJUMP l listnodes tp kids 0 0 0 list newnode JUMP V l NULL NULL reset break 2020 4 15 staticvoidlist Nodep if p 2020 4 15 forest是一个循环链表 不为空则指向链表最后一个节点 为空则将其初始化 link域可以表示根结点 caseLT LT代表大于转移 是接口dag标识符l listnodes tp kids 0 0 0 r listnodes tp kids 1 0 0 if tlab list newnode generic tp op opkind l op l r findlabel tlab elseif flab switch generic tp op caseEQ op NE break caseNE op EQ break caseGT op LE break caseLT op GE break caseGE op LT break caseLE op GT break default assert 0 list newnode op opkind l op l r findlabel flab if forest 2020 4 15 2020 4 15 a i a i b i 0 a i b i 10的森林 七 代码生成器 代码生成器 为编译前端提供接口函数 接口函数用与目标机器相关的指令来实现无关的中间代码 接口函数也为临时变量指派寄存器 固定的函数单元或栈空间 Lcc将大部分与机器无关的函数重组到一个大的与机器无关的程序中 2020 4 15 2020 4 15 1 选择和发送指令 Lcc的指令选择器时由程序lburg根据紧缩规范自动生成的 lburg是代码生成器的生成器 lburg接收紧缩规范并产生一个用c语言编写的树分析程序 该程序为目标机器选择指令 树分析程序接受中间代码的主题树 并将它分割成与目标机器相对应的程序块 成为数覆盖 2020 4 15 模式 ADDI reg con 表示如果ADDI的第一个子节点能递归的匹配reg 第二个子节点匹配con 那么该模式就在ADDI除匹配一棵树 规则 addr ADDI reg con 规定了非终结符addr与上述模式相匹配规则 stmt ASGNI addr reg 规定了ASGNI节点的每子节点递归的与addr和reg匹配非终结符stmt就与该ASGNI匹配 例 ASGNI ADDP INDIRP ADDRLP p CNSTI 4 CNSTI 5 的覆盖 2020 4 15 2020 4 15 2020 4 15 2 发送器 Lcc发送器 emitter 的作用是为目标机器输出代码 发送器并不依赖于目标机器 由两个描述与机器相关的数据的数组驱动 Lburg为每个BURM生成一些c语言代码 用来声明并初始化这两个数组 两个数组都是通过规则号索引 规则生成模板数组 staticchar template 标记与指令对应的模板 以区别子指令 如寻址指令 staticchar isinstruction 2020 4 15 lburg从1开始为规则编号 并通过返回规则号来报告匹配情况 这样当需要的时候就可以找到响应的模板 如果模板以一个换行符为结尾表示它是一条指令 否则就必然是某条指令的一部分 比如是一个操作数 rc reg 0 rc con 0 reg ADDI4 reg mrc1 mov c 0 nadd c 1 n 1reg ADDP4 reg mrc1 mov c 0 nadd c 1 n 1 2020 4 15 emitasm对规则结构及汇编程序代码模板进行了解释 emitasm递归调用自身 以处理地址计算之类的子指令 emitasm的遍历从一个指令开始 当递归到达为该指令提供值的指令时结束 emitasm由emit调用 emit确保emitasm以正确的顺序来处理这些指令 这样便可以处理指令间的顺序 2020 4 15 例如 发送器解释字符串 lwr c 1 n 先生成 lwr 然后是目标寄存器的名字 通常是一个数字 接着是一个逗号 如果nts 1 中保存了表示非终结符addr的整数 那么递归生成p kids 1 作为一个addr 最后emitasm生成一个换行符 2020 4 15 3 寄存器的分配 从上节我们可以看出 代码发送器可以生成汇编代码 但是汇编代码中的寄存器是如何分配的 寄存器分配包括两个内容 分配 决定哪些值占用寄存器指派 为每个值指派特定的寄存器 2020 4 15 2020 4 15 在后端选择指令并将子指令从树中分离出来 linearize采用前序遍历分离的树 并按照最后执行的顺序链接指令 gen再将每条指令传递给ralloc函数 ralloc一般首先调用putreg来释放不再被其子节点使用的寄存器 然后调用getreg函数为自身分配一个寄存器 对于临时变量 ralloc在首次赋值的时候为它分配一个寄存器 在最后一次使用的时候释放该机存器 2020 4 15 寄存器状态的跟踪unsignedfreemask 2 unsignedusedmask 2 用掩码表示寄存器的状态对于寄存器r intn r set