C#词法分析器（二）输入缓冲和代码定位

C#词法分析器（二）输入缓冲和代码定位2014-04-14一、输入缓冲

在介绍如何进行词法分析之前，先来说说一个不怎么被提及的问题——怎么从源文件中读取字符流。为什么这个问题这么重要呢？是因为在词法分析中，对字符流是有要求的，它必须能够支持回退操作（就是将多个字符放回到流中，以后会再次被读取）。

先来解释下为什么需要支持回退操作，举个简单的例子来说，现在要对两个模式进行匹配：

图 1 流的回退过程

上面是一个简单的匹配过程，仅为了展示回退过程，在后面实现 DFA 模拟器时会详细解释是如何匹配词素的。

现在来看看 C# 中与输入相关的类，有 Stream，它支持流的查找，但是只能以字节方式访问；BinaryReader 和 TextReader 虽然支持读取字符，但是又不能支持回退。所以，就必须自己完成这个输入缓冲类了，大致思路就是以 TextReader 作为底层的字符输入，然后由自己的类完成对回退能力的支持。

《编译原理》上给出了一种缓冲区对的方法，简单的说就是开辟两个缓冲区，设缓冲区大小都是 N 个字符。每一次都将 N 个字符读入到缓冲区中，并在这个缓冲区上实现字符操作。如果当前缓冲区的数据已经处理完毕，就将 N 个新字符读入到另一个缓冲区中，接下来就换做操作新的缓冲区。

这样的数据结构效率很高，而且只要维护合适的指针，就可以很容易的实现回退功能。不过它的缓冲区大小是固定的，新读入的字符会覆盖旧的字符。如果需要回退的字符数量过多（比如在分析很长的字符串时），就容易出现错误。我通过使用多个缓冲区解决了旧字符被覆盖的问题——如果缓冲区不足了，就开辟新缓冲区，而不是覆盖旧数据。

如果仅仅是不断的添加缓冲区，那么占用的内存只会不断增加，这样是没有什么意义的，因此我定义了三个释放缓冲区的操作：Drop，Accept 和 AcceptToken。Drop 的作用是将当前位置之前的所有数据标记为无效（被抛弃），被标记无效的数据占用的缓冲区就被释放掉，可以拿来被重复利用了；Accept 则会将标记为无效的数据以字符串形式返回，而不仅仅是简单的抛弃；类似的，AcceptToken 是以 Token 形式返回被无效化的数据，是为了方便进行词法分析。

这样的数据结构比较类似于 STL 中的 deque，不过这里不需要随机访问和插入、删除数据，仅会在数据的头、尾进行操作，因此我直接将多个缓冲区使用双向链表连成一个环，使用三个指针 current，first 和 last 指向链表中有数据的缓冲区，如下图所示：

图 2 多个缓冲区组成的链表，红色的部分表示有数据，白色的部分没有数据