Skip to content

Latest commit

 

History

History
275 lines (272 loc) · 26.2 KB

12.markdown

File metadata and controls

275 lines (272 loc) · 26.2 KB

23. Engineering a compiler. 第1章，编译概观

  • 简介
    • 编译器是一种工具，它将一种语言翻译到另一种语言，因此，它需要了解源语言的语法和语义(对应前端)，以及目标语言的语法和语义(对应后端)
    • 对比
      • 编译器：输入源语言，输出目标语言
      • 解释器：输入源语言，输出结果(尽管内部可能有编译等动作)
      • 虚拟机：输入目标语言，输出结果
    • 基本规则
      1. 必须保持语义
      2. 能以可观测的方式改进输入
    • 由于前端已经有成熟的O(n)算法了，所以编译器的开销主要在优化器和后端上
  • 转换概述
    • 前端
      • 词法分析：将字符串转化单词流
      • 语法分析：判断单词流是否是源语言的句子
      • 语义分析：类型检查等
    • 优化器
      • 数据流分析、相关性分析、转换等
    • 后端
      • 指令选择(instruction selection): 将IR转换为目标机操作。此时使用的可能是虚拟寄存器，即数量不限的寄存器符号。一般这里能用动态规划等手段
      • 寄存器分配(register allocation): 将虚拟寄存器换成物理寄存器。通常是贪心算法等
      • 指令调度(instruction scheduling): 根据数据依赖重排指令，调整emit时间，从而更高效的利用CPU流水线

23. Engineering a compiler. 附录B, 数据结构

  • 集合
    • 适用通用ADT的Set：bst、hashtable、ordered array、ordered list
      • 对全集U的大小无限制，可以动态适应
    • 当元素能被表示成整数，且全集U大小固定时(即离线算法，比如编译器领域，前端parse源码过后，IR的规模已知，因此全集U大小固定)
      • ordered list(linked list): 适合集合容量S绝对数值较小时
      • bitset: 空间效率最高: 缺点是，因为foreach、intersect、union等操作都是O(U)的，所以，如果S总是远远小于U(稀疏)，则不划算
      • bitset+ordered list: member是O(1)，insert、delete是O(S)，foreach、intersect、union都是O(S)，效果介于纯ordered list/bitset之间
      • sparse set: 一个O(U)大的sparse数组存放dense数组的索引，加上一个O(S)大的dense数组存放sparse索引，以及一个标量next
        • 优点1：无需初始化，或者说，初始化及clear都是O(1)的：next = 0
        • 优点2：insert、delete是O(1)的，而bitset+ordered list是O(S)的，类似S=10^3、U=10^6的时候，很合适
        • member的实现：0 <= sparse[i] < next && dense[sparse[i]] == i
        • insert的实现：sparse[i] = next; dense[next++] = i;
        • delete的实现：j = dense[next - 1]; dense[sparse[i]] = j; dense[sparse[j]] = i; swap(sparse[i], sparse[j]); --next
        • foreach的实现：for (i<-dense[0:next]) {...}
  • IR的表示
    • 图
      • 树
        • 所有使用指针的地方，都可以等价的换成数组索引，前提是IR规模已知(恰好编译器大部分算法是离线算法，满足这个条件)
          • 分配快速（除非指针方案的内存池做得够好）
          • 内存局部性更好
          • 可以直接进行块IO，而无需额外的一趟指针序列化
          • 便于调试
          • 数组索引相对指针更有利于编译器优化
        • 任何树都可以表示为二叉树，从而高效的分配、释放节点；当子节点数可变时，尤为有效
          • 如 struct Node{ T value; LinkedList<Node*> children; }, 其sizeof大致等于sizeof(T) + sizeof(void*)，即使子节点数可变，依然可高效分配
      • 有向图
        • 同样可以表达为二叉树
          • 如 struct Node { T value; LinkedList<Node*> outEdges; }
        • 可以配置额外的vector<Node*>来加速某些访问
      • 无向图
        • 密集图，考虑使用下三角的bit矩阵
        • 稀疏图，可以使用hashtable<tuple<Node*, Node*>>等
    • 线性
      • 数组
        • 优点是空间局部性好，直接块IO等
        • 缺点是插入、删除效率低。但IR数组不同于普通数据数组，它能借助detour运算符(类似于jump指令？)，通过类似memory patch的方式引入out-of-line代码，从而高效的增删IR数组
          • 最后需要在每个pass末尾，或者detour超过一定次数后，重新数组数组，对所有的detour操作进行线性化(inline?)
      • 链表
        • 高效的insert/delete
        • 空间局部性差(用内存池弥补，尤其是IR规模U已知的条件下...)
        • 指针相比数组，对编译器优化分析更困难
  • 哈希表
    • hash表的关键在于散列函数和碰撞处理
      • Knuth提出了一个简单的乘法散列函数：h(key) = tableSize * ((C * key) mod 1)，一个建议的C值是0.618((sqrt(5) - 1) / 2)
    • 开放散列法(open hashing)
      • 缺点及对策:
        1. 内存分配瓶颈 => free list的内存池
        2. 链表过长 => 通过rehash使得U/S足够大
      • 在每次访问后，还可以选择将项往前移1，或者直接提到开头
    • 开放地址法(open addressing)
      • 缺点
        1. 当U/S接近1的时候，性能急剧下降，需要rehash
      • 两种选择的内存占用
        1. bucket上面保存指针: 相比open hashing，少了linkedList的next指针，总内存占用可能更少
        2. bucket上面保存key/value的entry: 虽然少了一层指针的间接层，但由于有大量闲置entry，如果key/value的size明显大于指针，那么，有可能总内存更多；因此，这种嵌入的存储，主要适合小对象
  • 符号表
    • 符号表被用于编译期(注意，不是运行时，运行时直接lexical addressing)，虽然可选的方案可以是ordered key/value list、balance bst、hashtable，但因为没有顺序遍历的要求，一般采用hashtable实现
    • 符号表虽然用hashtable实现，但它的行为更特殊，与其说是insert、member、delete，不如说是push(key, value)、lookup(key)、pop()这组接口，即，它的增删复合栈顺序，因此可以比普通hashtable更优化
      • 存储方面，由于增删的栈顺序，相比用free list，它可以进一步用栈分配器，而且真正的支持单个项的free
      • 通过一个栈来保存已分配元素，它能支持O(S)而非O(U)(这里的U指bucket项数)的遍历，而且有更好的局部性(栈顶访问更频繁)，甚至能块IO
      • rehash的时候，不需要同时保存新旧两个数组，直接旧数组resize后，反向遍历栈然后插入
      • 这里的栈为了提供稳定的项指针，可能实现为分段栈
    • scoped symbol table(词法作用域的符号表)
      • 简单的做法是准备一个stack，这样，insert、delete都很快，但是lookup、update需要沿着栈逐个查找，更慢；实际的符号表是查找、修改更多，而增删很少，所以需要将开销分摊在pushScope、popScope、insert/delete上，进而提供O(1)的lookup/update
      • open hashing + stack allocator可以提供一个高效的scoped symbol table实现：
        • pushScope => ++currScope
        • push => buckets[h(key)] = new List(key, value, currScope, buckets[h(key)])
        • lookup => list = buckets[h(key)]; while (list != null && list.key != key); list.value
        • pop => node = stack.pop(); buckets[h(node.key)] = node.next
        • popScope => while (stack.top.scope == currScope) pop(); --currScope

24. Engineering a compiler. 第2章，词法分析器

  1. 识别单词
    • 要识别特定单词，可以通过嵌套K层if/else来手工识别
    • 嵌套if/else的代码可以表示为状态迁移图，也就是所谓的FA(finite automation)
    • FA的形式化表示：
      1. 状态集合S(包括错误状态se)
      2. 输入字符集Z
      3. 转移函数f= (State,Char)=>State
      4. 开始状态s0
      5. 接受状态集合SA
    • 对于一个输入字符c，它至少会跳转至状态se，进入se后，FA将继续消耗整个输入
    • 通过将FA对应的识别代码，从嵌套if/else改为while循环，将转移函数f表达为查表，识别器可以支持无限集合
      • 有限的单词集合，可以用无环FA表达，无限集合，必须用有环FA(对应RE的闭包)
  2. 正则表达式
    • FA在记法上太复杂，因此引入RE，而RE和FA等价，可以互相转换
    • RE的形式化定义
      1. RE描述定义在符号集Z以及空串上的语言
      2. 三个基本操作
        1. 连接
        2. 选择
        3. 克林闭包(Kleene closure)，记做*
          • 有限闭包(Finite closure)，记做Ri，如R5
          • 正闭包(Positive closure)，记做+。R+等价于RR*
    • (grep的全称global regular expresion pattern match and print)
    • 在定义程序语言的词法单元时，类似特定范围整数这样的模式，可以选择用简单的正则+后期处理，也可以直接用正则枚举。后者虽然会导致FA更复杂，生产过多状态、占用更多内存，但识别器本身仍然是O(n)的
    • RE的闭包性质，使得RE的各种处理算法仍然可以递归组合
    • RE的选择操作符，使得它可以描述任何一种有限集合的语言，只需枚举所有串并连接即可
    • RE的补集操作: 可以简单的将完整的FA的所有接受/非接受状态交换
    • 程序语言和自然语言在词法方面的一些区别：
      • 自然语言单词的拼写，和语义无关，而程序语言则尽量通过拼写来反应语法范畴(syntatic category)
      • 自然语言中，一个单词的词类，是上下文相关的，不同场合中会有不同的解释。程序语言中虽然曾经有这么做的(比如允许class作为identifier，即没有保留关键字的概念)，但新的语言已不再沿用该方案
  3. 从正则表达式到词法分析器
    • 构造法循环：RE -(Thompson construction)-> NFA -(Subset construction)-> DFA -(Hopcroft算法, minimization)-> 最小化DFA -(Kleene construction)-> RE
      • 这同时也说明了RE、NFA、DFA等价
      • 给定一个语言(比如一个单词集合：0~31这32个数字)，可以反推出它的RE
    • 通过将输入字符集Char映射成CharCategory，可以显著控制输入规模
    • 之前的RE和FA没有使用空符号，而一旦引入它，用于连接多个FA，将导致出现非确定性转移，从而引入NFA
    • NFA(Nondeterministic finite automation)相比DFA(Deterministic finite automation)，有空转移符，以及非确定性转移
      • subset construction中，由一组状态move(c)得到的一组新状态，称为一个NFA配置(configuration of an NFA)，它对应一个DFA状态
        • 可以考虑用bitset实现
    • NFA、DFA等价性: 首先，NFA至少是DFA超集；又，任意NFA可以通过subset construction构造成DFA，所以二者等价
      • DFA状态数可能是NFA状态数的指数倍(2^N(Snfa))，因此，理论上它可能存在空间问题；但用它进行识别，仍然是O(N)的，没有时间问题
    • Thompson construction有几个性质可以用于简化实现
      • 每个状态最多只有两个输出边，最多两个输入边
        • 考虑表示成struct NFAState{ int id; Tuple<Char, NFAState*> e1, e2;}
    • Subset construction
      • 对每个状态n，可以离线计算e-closure{n}
        • 考虑表示成bitset
    • DFA minimization-Hopcroft算法
      • 是一种不动点应用，停止条件为，不可再split
      • 最小化之后，可以考虑再次进行CharCategory的压缩：当两个category在DFA table中的列完全相同时
    • 实现Scanner的时候，需要处理不同token的优先级，比如，new到底算关键字还是identifier
  4. 实现词法分析器
    • 一些细节优化
      • 词素(lexeme)可以被hash，从而节省内存
        • 考虑用Symbol实现；同时也能加速后续symbol table访问的hashcode/equals性能
      • token本身可以被hash，从而各种单词素token可以共享内存
      • 特殊词素无需存储为字符串，可节省内存，比如float/int
        • 参照lex的做法，在token识别成功输出时，直接保存成int/float
      • 输入流为支持高效的readChar和rollback，可以考虑double buffer的block IO
    • 表驱动法分析器(table-driven scanners)
      • 固定的Scanner框架代码 + 语言特定的DFA table
        • 核心代码：while (state != Se) { c = nextChar(); lexeme += c; state = table[state][category[c]]; }
      • CharCategory的使用有利于减少DFA table的列数，从而有可能使得算法核心内存放入CPU cache
      • 最长匹配的贪婪策略可能引起的平方开销: 比如，以a|a*b匹配aaaaa...
        • 应对策略是，添加Fail[State,InputPos]的失败表，回滚的时候写表，而贪婪尝试的时候判断表项为空
    • 直接编码分析器(direct-coded scanners)
      • 每个状态用一个label表示，状态间转移，用goto来进行
      • 在状态中做category-based分派时，如果category对应单字符，那么可以直接用if；如果是连续的多字符，可以用if + range测试；简单的非连续字符，可以用switch；如果是复杂非连续的字符，仍然使用category table
        • 注意，当category对应的字符分布无规律时，switch可能慢于category table的lookup
      • 可以在生成各个状态代码时，根据状态特点来特化代码(相当于手工Scanner的部分好处)
    • 手工编码分析器(hand-coded scanners)
      • 可以做很多手工的细节优化
        • int的token，边识别，便进行输出值的累积value = value * 10 + (c - '0')
        • 单词素的token，识别过程中不必累积lexeme
        • 注释、空格/换行等，都不必累积lexeme
    • 关键字处理
      • 提供关键字RE
        • DFA状态数较多，适合table-driven scanner和direct-coded scanner
      • 使用identifier的RE，输出时查表判断是否是关键字，是的话输出对应token
        • DFA状态数较少，适合hand-coded scanner
        • 缺点是，每个identifier都要追加一次查表的额外开销
  5. 高级主题
    • 从DFA到RE - Kleene construction
      • 很像最短路径中的Floyd算法
    • 从DFA到RE 2 - States reducing
      • 性能比Kleene construction高，避免了很多冗余计算
    • DFA最小化算法之2 - Brzozowski算法
      • 利用Subset construction会合并公共前缀的性质
      • 定义操作
        • reverse(NFA/DFA)->NFA: 反向所有转移边；开始状态变成结束状态；添加一个新的开始状态，通过e指向原来的所有结束状态
        • reachable(DFA)->DFA: 去掉不能从开始状态达到的状态
      • 算法核心：reachable(subset(reverse(reachable(subset(reverse(n))))))，即，先去掉公共后缀，再全掉所有公共前缀
    • 无闭包正则(closure-free regular expression)
      • 无闭包语言考察的对象，实际上是类似一组单词|起来的语言
      • 可以通过类似构造Trie的方式构造一个DFA，然后最小化，最后甚至反推出RE
        • 和Trie相比，优势在于会合并公共后缀(最小化后)，状态数更少，空间效率可能更高(如果CharCategory种类不多，即DFA table列不多的话)
        • 当状态少时，要识别一个有限语言，可能比hash表的member更高效
        • 作为对比，根据语言集合大小，可考虑的测试手段：bloom filter -> trie tree -> hash table -> DFA
  6. 小结
    • 只要必须识别的单词是一个有限集合，都有必要考虑DFA(其他选择包括hashtable、trie、bloom filter等)
    • 最初词法分析器由于提供O(n)的渐进复杂度，以及很小的常因子，所以从语法分析中独立出来；后来由于高性能语法分析算法的出现，这种性能考虑弱化了，只是作为正交模块的习惯被继承下来
      • 换句话说，出于性能考虑，相比LALR语法分析器，Parser combinator对基于DFA的词法分析器依赖更大
    • 判断两个RE/NFA是否等价，可以比较它们的最小化DFA

31. 词法分析总结

  1. 编译器是语言到语言的翻译，其中前端的工作是理解源语言的语法和语义。这里本没有词法的概念，词法分析是早期为了性能而引入的，因为自动机理论能提供O(n)的时间复杂度，这一优势对早期的语法分析器尤为重要
    • Parser combinator这样的高层Parser也能从独立的lexical analysis受益，即以Token流而非Char流作为输入
  2. 词法分析的目的，只是通过类似"if str[0] == 'i' && str[1] == 'f'"的方法，从源码字符串中抽取语法分析所需要的终结符。因为Terminate symbols不要求递归，所以用正则语言就能描述，从而可以从语法分析中剥离出来
    • 正则语言，只支持顺序、选择、循环三种操作(因此，状态是有限的，可以用FA描述；其中循环通过带环图描述)，而上下文无关语言，是RL的超集，还能进行递归，因此，直接用CFG来描述词法规则也是可行的，比如在Parser combinator中，将终结符也作为Parser
    • CFG的表达能力，关键在于抽象和应用抽象，加上基本单元(终结符)，实际上已具备lambda演算的计算能力，因此自然能够做递归，也能够覆盖RE的顺序、选择、循环操作
  3. 相比直接用源码描述词法分析规则，采用自动机(DFA)来描述一个语言的词法规则更直观；进一步的，可以使用正则表达式来形式化表示。现代词法分析的任务就是，根据描述词法单元的正则表达式，生成高性能的词法分析器，这中间可能涉及RE->NFA->DFA->CodeGen的操作
  4. 词法分析中涉及的算法和细节
    • 将正则字符串Parse成正则的AST。这里可以手工进行Recursive decent parsing，或者用Parser combinator
    • 根据正则AST引用Literal string的情况，将字符分类，减小输入空间；输出的Character classify table是一个Char=>Int的表。比如\d+|[a-z]，只需要3个分类，0-9、a-z、其他，于是，输入可以被转换成0~2的整数
      • 分类算法：对于一个输入的分组chars，进行chars.groupBy(c=>table(c))，然后每个group中的字符都分配一个更大的id。最后进行一趟处理(0 until n).groupBy(c=>table(c))然后从0开始分配id
    • 根据包含CharCategory的正则AST，生成NFA。这里得到的NFA可以直接用于匹配，可以进一步转换成DFA
      • Thompson construction
        • 这里是非常简单的一趟递归pattern matching，每次输出一个(开始状态,接收状态)对
        • 分支无非是，Chars、KleeneStar(用KleenePlus会有问题)、Concatenation、Alternation
      • 由于这里实际上是离线算法，NFA状态数已知，因此每个状态可以分配一个整数，进而，状态的集合，比如NFA的configuration，可以表示成Bitset
    • 将NFA转换成DFA
      • Subset construction
        • 这里实际上是在模拟NFA的执行
        • 可以用整数表示NFA状态，以Bitset表示NFA状态集合，从而进行高效的并运算和相交测试
        • 离线计算e-closure{Si}，即通过空字符与状态Si直接/间接相连的状态集合
        • move({s1, s2...}, c) => 将e-closure{s1.transitions.filter(.symbol==c).map(.target)}并起来
        • 多个NFA接收状态可能对应同一个DFA状态，DFA接收状态的属性应该考虑NFA状态的优先级。比如，对于输入for，它应该作为token("for")，而非token("IDENT")
    • DFA最小化
      • Hopcroft算法，常用
        • 最初按(非接收状态组，接收组1，接收组2...)分组，之后对每个分组，尝试在所有字符集下进行split，直到所有分组都不可再细分
      • Brzozowski算法
        • 利用Subset construction会合并公共前缀的事实，进行一系列操作得到最小化：reverse => subset => reachable => reverse => subset => reachable
        • 由于reverse会导致多接受状态变成一个接受状态，因此将该算法应用到Scanner上稍微有些麻烦
    • NFA/DFA上的相关操作
      • union: 添加新开始状态指向已有的开始状态，将所有接收状态的并作为新的接收状态集合
      • complement: 反转所有状态的开始/接收角色。由于原先的Serror变成了接收状态，所以这里可能需要用DFA来表达
      • intersect: (a.complement | b.complement).complement
      • diff: a & b.complement
    • DFA到RE
      • Kleene construction算法，较慢，N^3
        • 类似Floyd最短路径算法，以动态规划的方式，构造任意两个状态间的路径的并，最后再将开始状态到所有接收状态的路径并起来
      • State recuding算法，更高效
        • 每次移除一个状态，移除的时候，为它的每个前驱，增加到每个后继的新路径，该路径是通过被消除状态抵达的
        • 对于每个接收状态，分别消除开始状态和它之外的状态，然后再枚举所有路径(这里分两种情况，开始状态和该接收状态是否是同一状态)。最后并上到所有接收状态的路径
      • 为了实现上面的基于正则的构造算法，最好以正则AST来操作，在正则AST构造的过程中，根据正则性质，进行各种结合、简化
        • 有了这里的正则AST变换，也就能对正则AST进行独立的simplify操作
    • DFA状态迁移表的合并
      • 相同列可以合并，减小表规模
    • 基于上面的算法，能够进行的衍生操作
      • RE简化：RE => NFA => DFA => minimal DFA => RE
        • 直接在RE的AST上进行变换，也能收到有限的简化效果
      • 根据一组单词，生成正则：将单词并起来，作为一个Closure Free RE ，之后再进行RE简化
      • 判断两个RE的等价性： RE1 => minimal DFA1，RE2 => minimal DFA2，DFA1 == DFA2 ?
      • 构造特殊的DFA，再输出对应的正则
        • 比如，%n==0的结果，构成一个0~n-1的有限集，因此，可以构建DFA，然后再最小化进而输出正则
    • 支持高效readChar和rollback的双缓冲CharStream
    • 考虑总是利用Graphviz进行FA的图像化输出，有利于调试
  5. 再来回顾一下，所谓前端，就是"理解源语言的语法(长什么样)和语义(效果是什么)"
    • 什么是词法分析？
      • 语法当中，有一组最底层的元素，它们不是递归定义的，因此，可以用更弱的语言，即正则语言来描述，从而得到比通过上下文无关语言来描述更高的效率
      • 因此，词法分析，实际上是语法分析的一部分，仅仅是对无递归符号的鉴别的一种优化
    • 没有词法分析会怎么样？
      • 不怎样，既然只是优化，完全不做词法分析，直接上语法分析，慢一点而已
      • 怎么做？将原本的词法单元，作为语法单元，单词的识别，改为语法符号的CFG描述。对于类似\d+的规则，如果用BNF，需要递归，而EBNF则不必。
    • 什么是语法分析？
      • 语法，是语义的一种对人友好的文本化描述，它重新组织了语义的顺序、层次以及隐式规则(比如类型推导)。总之，语法是在保持语义的条件下的重新组织、去除冗余和噪音，只是为了对人友好。
      • 语法分析，就是要从对人友好表示中，还原语义的结构化表示，进而程序化处理
    • 没有语法分析会怎么样？
      • 不怎样，只要你能以文本之外的其他方式呈现语义
      • 如果提供的本来就是结构化表示，甚至可能直接处理(即解释)，跳过词法分析和语法分析环节！
        • 函数式语言的Algebraic data type可以极其便利的构造树状结构，因此，在函数式语言中，可以利用ADT直接构造程序语义的结构化描述(AST，抽象语法树)，进而开始解释语义
        • ADT(construction)加上Pattern matching(deconstruction)，允许对程序的结构化表示进行直观的变换，因此，具备这两个feature的语言，都是进行解释、编译的强力工具
          • 与结构化表示中ADT和Pattern matching对应的设施，在字符串表示中，是RE和String interpolation。不过，由于RE无法递归(计数)的缺点，后者表达力不能代替前者
        • 直接用ADT构造程序并解释，绕过了语法分析，自然也要付出相应代价，即，失去语法的一部分噪音隔离效果，对终端用户不友好。
          • 语法越简洁(形式上)，就需要语法/语义分析做更多事(比如类型推导)；而语法越薄，语法分析容易，但形式上就更复杂。
            • Lisp是这方面的典型代表，S表达式极易Parse，但语法噪音太大。相应的，得到的好处之一是，语法树通过宏被直接递交到终端用户手中，用户手中的语法树和源码结构上一致，因此用户可以以解释器的身份，进行语法变换。
      • Lisp适合写解释器的原因就是，被quote后的S表达式，其实就是结构化的语法树(缺点是没有静态类型安全)，从而不必再进行词法分析和语法分析(实际上S表达式的parse，还是由Lisp编译器来做的)，直接进入语义处理的环节(解释，或者编译)
        • S表达式中的List作为ADT可以高效的构造树，而Pattern matching又可以高效的解构树，所以可以便捷的进行各种语法变换。所以，即使是语义处理环节，Lisp仍然表现强力。当然，具备ADT和PM的任何函数式语言，都是解释器/编译器的好工具。
    • 总结下，不做词法分析怎么样？不怎样，延迟到语法分析中即可。不做语法分析怎样？不怎样，直接构造AST即可。既然通过ADT直接构造程序语义这么方便，为什么Lisp没有占领市场？噪音太大，体验差，更适合做解释器研究(大量使用宏也算一种，即语法抽象)。