自己动手用java写编译器 课时4 输入系统及分词系统概述

缘起

《自己动手用java写编译器》 课时4

分析

从本节课开始往后注重的是输入系统的设计和词法解析用到的各种算法和理论基础. 本节给出对”词法解析系统和输入系统一个大概的介绍”.

词法解析是一种相当实用的技术——除了在编译器中，在很多应用场合也是十分实用的——如果把词法解析看做是一种模式识别引擎的话，那么它可以应用到文本编辑器、数据模式识别等方面，稍加扩展，还可以应用到网络协议解析等方面.

在编译器中，词法解析的作用是将输入流解析为一种能够被语法解析器使用和管理的格式——词法解析器将输入的文本分割、打标签（即token，其实也就是用数字代替一系列相应的字符串，例如while可以和一个标签关联起来.）一般情况下一个标签可以和很多字符串关联起来——例如上一节看到的NUM_OR_ID这个标签（token）指代的是代码中的数字或者标识符，显然后者是无穷无尽的. 词法解析器还可以将代码中的注释剔除，忽略换行符、空格、Tab，从而语法解析器就不需要处理这些了——简化了语法解析器的设计和工作（可以这么理解——语法解析器拿到的是经过词法解析器处理过的代码, 这种代码比源代码更加精简, 即词法解析器其实是咀嚼过源代码之后，喂咀嚼过后的源代码给语法解析器）.

第一节课就说了，词法解析是编译过程中一个独立的阶段，它通过advance和match接口和语法解析器交互. 下图表明了编译器的骨架

词法解析器从输入系统捞词出来. 语法解析器通过 match和advance接口和词法解析器交互（通过【1】中自己实现的代码，advance解析文本之后，可以通过访问lexer的current成员得到解析的字符的token，通过访问lexer的symbol成员得到解析的有意义的字符串）. 语法解析器负责代码的生成和判断输入代码的合法性. 最后编译器输出汇编代码（输出到磁盘上，成为编译后的文件）. 所以上图中 “请求下一个标签” 就是 【1】中Lexer的的advance接口.

唯一【1】没有说过的就是这个符号表. 符号表是什么鬼??? 例如C语言中的

1
typedef int Integer；

即提示编译器把源码中的Integer看做是int类型，而不要看成是一个标识符. 这是怎么做到的呢? 其实就是词法解析器读到了这行代码之后，将信息告诉语法解析器, 语法解析器就会将Integer插入符号表, 则后面词法解析器读取到了Integer之后会去符号表搜索一波，搜到了就不会再把Integer打上NUM_OR_ID标签而是TYPE标签. 而且符号表是调试器进行单步调试的基石（这个后面再说）. 所以符号表其实是词法解析器和语法解析器共享的部分. 即词法解析器其实需要语法解析器插入符号表来辅助完成正确的打标签.

上面的图中的架构的好处是显然的——因为职责的解耦使得局部的优化可以优化整体编译器的性能. 例如我们可以优化词法解析器从输入系统中读取字符的速度来降低IO的成本，从而达到编译器性能的优化. 而且我们可以仅仅将C语言的词法解析器替换成C#的词法解析器，来轻松实现一个C编译器到C#编译器的转换. 这都是面向对象（分层）的思想运用的体现.

词法解析的过程中发生错误是很正常的，例如C语言中 @num 是非法的标识符，但是词法解析器遇到这种错误的时候有若干种处理方法，最简单的就是忽略@ , 给出错误提示，当然，也有复杂的，例如读取到的是swotch, 则可以基于某种字符纠正算法（例如BK树就是不错的选择）来实现自动识别为switch. 当然，完全可以有更加粗暴的方式——直接报错，不给你做任何修正，也不继续进行编译了.

输入系统

注意到上图中有一个模块叫输入系统——它的作用是将源代码从磁盘或内存中读入编译器内存. 而且根据面向对象的设计思想——输入系统必定和词法解析器之间以固定的接口进行交互，这样维护起来才更加方便.

输入系统的效率决定着整个编译器的效率. 我们在C语言中，经常会使用到它提供的库I/O函数（C语言的输入系统设计的不是太合理），如scanf等，C语言的库函数将数据读入程序的内存中这个过程涉及到了三次拷贝

  1. 从磁盘上将数据靠拷贝到os内存（系统空间）中
  2. 从os内存拷贝到一个FILE结构体(C语言中FILE结构体用于表示一个文件)中
  3. 从FILE结构体中拷贝到程序内存（用户空间）中.

这些拷贝都需要空间和时间，另外，词法解析器在解析的时候都需要预先读入一些字符（编译原理中的lookAhead技巧），例如之前的typedef语句，一旦读到typedef就需要将后续的字符也读入才好解析，而且使用完毕之后可能需要重新放回输入缓冲区，这一取一放，如果不加以良好的设计，很可能产生I/O性能上的影响.

鉴于上面的特点，现有的输入系统可能无法满足编译系统输入的各种要求，因此我们需要自己开发一个专有的输入系统，我们的输入系统需要满足以下特点

  1. 输入过程需要尽可能的快——减少不必要的拷贝
  2. 支持多个字符的预读取和放回缓冲区的操作（参见上面的lookAhead技巧）
  3. 当解析当前分割出来的字符串的时候，上一个解析过的字符串要容易获取（参考typedef int Integer, 我读到了Integer之后，很容易获取到前面的typedef）
  4. 磁盘读写要足够便捷.

所以我们的输入系统应该设计成下面的样子

上面[startBuf, END] 是输入缓冲区的物理大小, 而[startBuf, endBuf]是输入缓冲区的逻辑大小，也就是我们虽然向操作系统申请了[startBuf, END]大小的内存，但是其实我们只使用[satrtBuf, endBuf]的空间大小. 多出来的部分称之为隔离带. MAXLEX是分割后字符串的最大长度——也就是标识符或者数字或者其他有意义的字符的最大长度，通常设定为128（你恐怕写程序从没有写过超过128个字符的标识符吧?）。 我们一次从磁盘读入输入缓冲区的大小是MAXLEX的整数倍. 也就是 endBuf-startBuf是MAXLEX的整数倍. next指针一定指向下一个要读取的字符——词法解析器是一个一个字符从输入缓冲区中读取数据的.

为了更进一步解释一些名词术语，我们来看看词法解析器解析若干个有意义字符串打上token之后输入缓冲区中的样子

pMark 指向上一个被解析的字符串的起始位置.sMark 指向当前被解析的字符串的起始位置, eMark指向当前解析的字符串的结束位置+1. sMark-pMark是上一个字符串的长度. eMark-sMark 是当前解析字符串的长度.

下面来解释一下danger的含义（其实读过一些自动扩容数组的源码的话，都能才到意思就是快怎么怎么样了…）.

词法解析器在解析当前字符串的时候需要读取当前字符串后的若干字符，所以next指针在eMark后面一段距离，这也就是编译原理中提到的lookAhead技巧.

我们前面提到的我们设计的输入缓存区需要满足预读取之后再放回输入缓冲区 . 这种操作只需要把next指针简单设置为eMark即可. lookAhead操作也是有字符限制的——通常用 MAXLOOK表示，也就是next-eMark<=MAXLOOK

当next指针接近danger时，表明输入系统的缓冲区中的数据快被读完了，当next指针越过danger时，就会触发一次flush操作. flush操作的结果是: 将 [pMark,..,endBuf]的数据平移到startBuf处，平移的距离是pMark-startBuf. 然后输入系统继续从磁盘中读取数据，填塞后面的空间. 即

参考

【1】https://yfsyfs.github.io/2019/07/20/%E8%87%AA%E5%B7%B1%E5%86%99%E4%BB%85%E5%8C%85%E5%90%AB%E5%8A%A0%E5%8F%B7%E3%80%81%E4%B9%98%E5%8F%B7%E3%80%81%E5%B0%8F%E6%8B%AC%E5%8F%B7%E3%80%81%E6%AD%A3%E6%95%B4%E6%95%B0%E6%95%B0%E5%AD%97%E7%9A%84%E8%A1%A8%E8%BE%BE%E5%BC%8F%E7%9A%84%E7%BC%96%E8%AF%91%E5%99%A8/