2020 2 10 编译器设计与实现 Lcc原理剖析 2020 2 10 一 概述 1 编译器各阶段 2020 2 10 2 编译器各阶段的分组 前端 依赖于语言并很大程度上独立于目标机器 一般包括语法分析 词法分析 符号表的建立 语义分析 中间代码生成以及相关错误处理 后端 依赖于目标机器的阶段或某些阶段的某些部分 一般来说 后端完成的任务不依赖于源语言而只依赖于中间语言 主要包括代码优化 代码生成以及相关的错误处理和符号表操作 2020 2 10 二 符号表 符号表是编译器保存信息的中心库 编译器的各部分通过符号表进行交互 并访问符号表中的数据 符号 符号表把各种名字映射到符号集合 常量 标识符和标号都是名字 不同名字有不同的属性 符号管理不仅要处理符号本身 还管理符号的作用域 2020 2 10 1 符号的表示 structsymbol char name 名称intscope 作用域Coordinatesrc 在源程序中位置Symbolup 连接符号表中上一个符号Listuses 可保存一个Coordinate列表 表示使用情况intsclass 扩展存储类型 符号标记Typetype 如变量 函数 常量 结构或联合等信息floatref 被引用的粗略次数union 联合u为标号 结构 联合 枚举 常量 全局 和静态变量提供附加信息 u Xsymbolx 由后端处理 如为变量分配寄存器 为调试器产生数据信息 2020 2 10 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 2 10 2 符号表的表示 externTableconstants externTableexternals externTableglobals externTableidentifiers externTablelabels externTabletypes structtable intlevel 同symbol中scope域Tableprevious 符号表链表 指向level 1的表structentry structsymbolsym structentry link buckets 256 这是一个哈希链数组 方便插入 查找Symbolall 指向当前及其外层所有符号列表的表头 2020 2 10 3 符号表举例 intx y f intx inta intb y x a b if y 5 inta y x a b 2020 2 10 2020 2 10 4 符号表的相关操作 查找和建立标识符Symbolinstall constchar name Table tpp intlevel intarena Symbollookup constchar name Tabletp 标号 与标识符相似 但不涉及作用域常量 这些符号保存在constants表中产生变量 用于产生静态变量保存字符串等 2020 2 10 三 代码生成接口 这一章内容定义了与目标机器无关的前端和与目标机器相关的后端之间的接口 Lcc接口包括一些共享数据结构 18个函数和包括36个操作符的语言 该语言用于将可执行代码从源程序生成dag 有向无环图 共享数据结构可供前后端共享 但某些域为一端私有 symbol就是一个共享数据结构 2020 2 10 1 类型度量 typedefstructmetrics unsignedcharsize align outofline Metrics size 类型的大小 align 对齐字节数 outofline 控制相关类型的常量的放置 为1时 不出现在dag中 存于静态变量中 Metricscharmetric Metricsshortmetric Metricsintmetric Metricsfloatmetric Metricsdoublemetric Metricsstructmetric 2020 2 10 2 接口记录 typedefstructinterface Xinterfacex Interface lcc为每一种目标机器形成一个独有的接口实例 x域是对interface的扩展 后段使用它存放与目标及其相关的接口数据和函数 对后端私有 2020 2 10 3 dag操作 可执行代码用dag来描述 函数体是用dag组成的序列或森林 每个dag都可以同过gen函数传给后端 dag节点structnode shortop shortcount Symbolsyms 3 Nodekids 2 Nodelink Xnodex 2020 2 10 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 2 10 2020 2 10 2020 2 10 3 dag操作 举例 inti p f i p 2020 2 10 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 2 10 5 函数 前端将函数编译为私有数据结构 将函数的任意部分传递给后端之前 前端必须先对每个函数进行完整的分析 函数的处理 function函数包括前端过程gencode遍历前端的私有数据结构 将dag的每个森林传给后端过程gen gen选择代码 在dag上添加注释并将返回一个dag指针 gencode还可以调用local宣告新的局不变量 前端过程emitcode再次遍历 将gen返回的指针传递给emit函数发送代码 2020 2 10 6 上行调用 前段调用后端以执行代码生成和发送 后端调用前端完成输出 分配存储空间 查询类型等功能 上行调用即后端调用前端 allocate分配空间 保证对齐方式符合机器多数类型newnode分配新的dag节点newconst符号表中创建新的常量newtemp符号表中创建新的变量 2020 2 10 四 词法分析 词法分析器读入源程序 产生语言的基本词法单元 例 prt 56 2020 2 10 1 输入 n cp limit 当limit cp小于某一个固定值时 调用fillbuf函数填充buffer 2020 2 10 2 单词识别 部分文法 token keywordidentifierconstantoperatorpunctuatorpunctuator oneof 定义 ID标识符FCON浮点常量ICON整型常量SCON INCRDECRDEREF 2020 2 10 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 2 10 3 关键字的识别 可以通过查表完成 也可以通过硬编码方式识别 例如 当起始小写字母为i时由gettok函数中switch语句的case i 处理 case i if rcp 0 f 2020 2 10 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 assert cp rcp token char rcp 1 while map rcp 检查是否需要填充buffer 2020 2 10 5 其他 另外还有 数字识别字符常量和字符串识别都是有gettok函数实现 实现方法相似 词法分析器可以有象LEX这样的工具实现 Lcc手工实现了词法分析器 体积更小 2020 2 10 五 语法分析 根据语言的文法分析 以确认输入是否符合语言规则 并建立输入源程序的内部表示 Lcc采用递归下降的语法分析 语法分析以形式语言理论为基础 采取语法制导翻译方法 处理程序中的错误 2020 2 10 1 表达式 表达式的表示 a b b a b 2020 2 10 表达式的分析 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 voidfactor if t ID t gettok elseif t t gettok expr expect 2020 2 10 c语言表达式分析赋值表达式 assignment expression conditional expressionunary expressionassign operatorassignment expressionTreeexpr1 inttok staticcharstop IF ID 0 Treep expr2 if t prec t 6elsereturnp 2020 2 10 条件表达式 conditonal expression binary expression expression conditional expression staticTreeexpr2 void Treep expr3 4 if t Treel r Coordinatepts 2 if A