理解词法分析器中的双缓冲
Understanding Double Buffering in Lexical Analyzer
作为大学编译器构建课程的一部分，我正在阅读有关编译器的“紫龙书”。作为词法分析的一部分扫描输入时，我无法理解有关双缓冲的一些事情。
这是书中的文字：
Two pointers to the input are maintained:
- Pointer lexemeBegin, marks the beginning of the current lexeme, whose extent we are attempting to determine.
- Pointer forward scans ahead until a pattern match is found; the exact strategy whereby this determination is made will be covered in
the balance of this chapter.
所以，如果我错了，请纠正我：一个缓冲区被读取，当该缓冲区的输入耗尽时，另一个缓冲区被源文件中的新数据填充，现在缓冲区被交换。 Forward 和 beginnig 指针现在指向新填充的缓冲区。
我的问题是，如果词位的某些部分位于当前缓冲区的末尾怎么办？然后当缓冲区切换时，一半的词素将在一个缓冲区的末尾，另一半在新缓冲区的末尾。指针将移动到新的缓冲区，我们不知道另一半留在其他缓冲区？
抱歉，如果问题含糊不清，但我已经为如何处理这种情况而苦恼了很长一段时间。我认为使用单个缓冲区也会出现同样的问题。
当前的词位很可能在两个缓冲区之间被分割。没有尝试避免这种可能性。
对于某些词法模式集合，当前词素也可能完全包含在较旧的缓冲区中，即使较新缓冲区中的数据也是有效的。龙之书的作者似乎在英勇地避免这种可能性，尽管我认为它不那么重要（而且在文字写成三十年后甚至不那么重要）。
归根结底，token在哪并不重要，因为龙书上描述的输入缓冲区只是作为输入缓冲区使用的。扫描器会有一个单独的令牌缓冲区，传统上是静态分配的 char 数组，这是传递给操作过程的令牌的来源。
保留令牌的单独副本似乎有点低效，但还算不错，特别是假设您愿意限制令牌的最大大小。令牌缓冲区解决了许多问题，特别是对于用 C 编写的词法扫描器。首先，它解决了令牌在输入缓冲区之间拆分的问题。此外，它还解决了 NUL 终止扫描令牌的问题，如果令牌将被任何 C 标准库字符串函数使用，则这是必需的。以 NUL 终止输入缓冲区中的令牌并不容易，因为令牌后面的字符很可能是下一个令牌的重要组成部分。 （在某些情况下，它会是可忽略的空格，但即使那样也不是所有的空格都是可忽略的；必须计算换行符，例如，为了维护错误消息和调试信息的行号。
（有一些方法可以生成以 NUL 结尾的字符串，我稍后可能会讲到，但这肯定会使扫描器的逻辑复杂化。例如，Flex NUL 以适当的方式终止令牌，但这意味着它必须覆盖然后恢复输入缓冲区中的一个字节，结果是您无法按词法扫描字符串文字。）
通过在令牌缓冲区中保留指向下一个字节的指针并在处理每个字符时无条件地将每个字符复制到令牌缓冲区中，可以将扫描的令牌低成本地复制到令牌缓冲区中。一旦识别出令牌的结尾，如有必要，将备份令牌指针，并在那里存储一个 NUL 终止符，覆盖任何可能不必要地放入令牌缓冲区的不需要的字符。
孪生缓冲区的要点是可以在令牌末尾回退一个以上的字节。这不是经常发生的事情，但在许多语言中它都可能发生。例如，C 和 C++ 允许 . 标记和 ... 标记，但不允许 .. 标记。扫描仪需要能够处理这种情况。例如，如果输入是 a..4，则扫描器需要 return 三个标记（a、. 和 .4）。但是 a... 将是一个标识符 a 后跟 ...。 （在 C++ 中这在语法上是可能的。在 C 中它很可能是一个语法错误。）
所以你需要考虑这样的可能性，即 . 落在输入缓冲区的末尾，而下一个输入缓冲区以 .4 开头。扫描器必须向前读取 4 以决定将哪个标记 return，但是一旦它这样做，它将 return 标记 .，它完全包含在第一个缓冲区。当扫描恢复时，重要的是扫描器不要尝试重新填充第二个缓冲区，因为那样会丢失缓冲区的数据。
尽管有这种极端情况，但仍然可以使用 Dragon 书中描述的哨兵技术来消除几乎所有的缓冲区结束检查，从而显着加快扫描仪的速度。可以消除的检查之一是检查令牌缓冲区溢出。只需要使令牌缓冲区与一对输入缓冲区的总和一样大；然后，只有在检测到哨兵时才需要测试令牌长度限制，这种情况很少发生。 （大概四八千字一次。）
当时编写的大多数词法扫描器都严格限制标记长度，有些现在仍然如此。 （Flex 不再自动施加令牌长度限制，但仍有配置选项具有限制令牌长度的效果。）
当然，这不是编写扫描器的唯一方法。 Flex 扫描仪生成器生成的扫描仪没有人为的令牌长度限制，也不将字符集限制为 255 个有效字符。确实，它在处理长令牌和包含 NUL 的令牌时效率不高，但这些情况非常罕见，因此效率低下的情况几乎可以忽略不计。
Flex 仅使用单个缓冲区，并且还将指针作为 yytext 的值传递到此缓冲区。它通过将自 lexemeBegin 以来扫描的文本重新定位到缓冲区的开头，然后从 forward 的重新定位值填充缓冲区到缓冲区。如果到达缓冲区末尾并且不需要重定位，因为令牌文本已经从缓冲区的开头开始，那么它调用 realloc 或等价物来扩展输入缓冲区，然后将几千字节读入新输入缓冲区，从前一个缓冲区的重定位端点开始。为了能够使用哨兵，即使输入中可能出现 NUL 字节，它也会使用输入缓冲区末尾的地址检查 NUL 的地址；如果它们不相同，则 NUL 是输入的一部分，并且 Flex 在状态转换 table 中查找 NUL 的操作。 （它比那更复杂一点，但这是高层次的概述。）由于缓冲端只是偶尔到达，因此检查 NUL 等的额外成本并不经常支付。
flex 架构的优点是它读取速度更快，因为它不是一次处理一个字符，而且它可以处理大令牌，尽管效率低下。 Lex 无法处理大令牌，因为令牌缓冲区 (yytext) 是一个静态数组，不是动态分配的，因此无法增长。
作为大学编译器构建课程的一部分，我正在阅读有关编译器的“紫龙书”。作为词法分析的一部分扫描输入时，我无法理解有关双缓冲的一些事情。
这是书中的文字：
Two pointers to the input are maintained:
- Pointer lexemeBegin, marks the beginning of the current lexeme, whose extent we are attempting to determine.
- Pointer forward scans ahead until a pattern match is found; the exact strategy whereby this determination is made will be covered in the balance of this chapter.
所以，如果我错了，请纠正我：一个缓冲区被读取，当该缓冲区的输入耗尽时，另一个缓冲区被源文件中的新数据填充，现在缓冲区被交换。 Forward 和 beginnig 指针现在指向新填充的缓冲区。
我的问题是，如果词位的某些部分位于当前缓冲区的末尾怎么办？然后当缓冲区切换时，一半的词素将在一个缓冲区的末尾，另一半在新缓冲区的末尾。指针将移动到新的缓冲区，我们不知道另一半留在其他缓冲区？
抱歉，如果问题含糊不清，但我已经为如何处理这种情况而苦恼了很长一段时间。我认为使用单个缓冲区也会出现同样的问题。
当前的词位很可能在两个缓冲区之间被分割。没有尝试避免这种可能性。
对于某些词法模式集合，当前词素也可能完全包含在较旧的缓冲区中，即使较新缓冲区中的数据也是有效的。龙之书的作者似乎在英勇地避免这种可能性，尽管我认为它不那么重要（而且在文字写成三十年后甚至不那么重要）。
归根结底，token在哪并不重要，因为龙书上描述的输入缓冲区只是作为输入缓冲区使用的。扫描器会有一个单独的令牌缓冲区，传统上是静态分配的 char 数组，这是传递给操作过程的令牌的来源。
保留令牌的单独副本似乎有点低效，但还算不错，特别是假设您愿意限制令牌的最大大小。令牌缓冲区解决了许多问题，特别是对于用 C 编写的词法扫描器。首先，它解决了令牌在输入缓冲区之间拆分的问题。此外，它还解决了 NUL 终止扫描令牌的问题，如果令牌将被任何 C 标准库字符串函数使用，则这是必需的。以 NUL 终止输入缓冲区中的令牌并不容易，因为令牌后面的字符很可能是下一个令牌的重要组成部分。 （在某些情况下，它会是可忽略的空格，但即使那样也不是所有的空格都是可忽略的；必须计算换行符，例如，为了维护错误消息和调试信息的行号。
（有一些方法可以生成以 NUL 结尾的字符串，我稍后可能会讲到，但这肯定会使扫描器的逻辑复杂化。例如，Flex NUL 以适当的方式终止令牌，但这意味着它必须覆盖然后恢复输入缓冲区中的一个字节，结果是您无法按词法扫描字符串文字。）
通过在令牌缓冲区中保留指向下一个字节的指针并在处理每个字符时无条件地将每个字符复制到令牌缓冲区中，可以将扫描的令牌低成本地复制到令牌缓冲区中。一旦识别出令牌的结尾，如有必要，将备份令牌指针，并在那里存储一个 NUL 终止符，覆盖任何可能不必要地放入令牌缓冲区的不需要的字符。
孪生缓冲区的要点是可以在令牌末尾回退一个以上的字节。这不是经常发生的事情，但在许多语言中它都可能发生。例如，C 和 C++ 允许 . 标记和 ... 标记，但不允许 .. 标记。扫描仪需要能够处理这种情况。例如，如果输入是 a..4，则扫描器需要 return 三个标记（a、. 和 .4）。但是 a... 将是一个标识符 a 后跟 ...。 （在 C++ 中这在语法上是可能的。在 C 中它很可能是一个语法错误。）
所以你需要考虑这样的可能性，即 . 落在输入缓冲区的末尾，而下一个输入缓冲区以 .4 开头。扫描器必须向前读取 4 以决定将哪个标记 return，但是一旦它这样做，它将 return 标记 .，它完全包含在第一个缓冲区。当扫描恢复时，重要的是扫描器不要尝试重新填充第二个缓冲区，因为那样会丢失缓冲区的数据。
尽管有这种极端情况，但仍然可以使用 Dragon 书中描述的哨兵技术来消除几乎所有的缓冲区结束检查，从而显着加快扫描仪的速度。可以消除的检查之一是检查令牌缓冲区溢出。只需要使令牌缓冲区与一对输入缓冲区的总和一样大；然后，只有在检测到哨兵时才需要测试令牌长度限制，这种情况很少发生。 （大概四八千字一次。）
当时编写的大多数词法扫描器都严格限制标记长度，有些现在仍然如此。 （Flex 不再自动施加令牌长度限制，但仍有配置选项具有限制令牌长度的效果。）
当然，这不是编写扫描器的唯一方法。 Flex 扫描仪生成器生成的扫描仪没有人为的令牌长度限制，也不将字符集限制为 255 个有效字符。确实，它在处理长令牌和包含 NUL 的令牌时效率不高，但这些情况非常罕见，因此效率低下的情况几乎可以忽略不计。
Flex 仅使用单个缓冲区，并且还将指针作为 yytext 的值传递到此缓冲区。它通过将自 lexemeBegin 以来扫描的文本重新定位到缓冲区的开头，然后从 forward 的重新定位值填充缓冲区到缓冲区。如果到达缓冲区末尾并且不需要重定位，因为令牌文本已经从缓冲区的开头开始，那么它调用 realloc 或等价物来扩展输入缓冲区，然后将几千字节读入新输入缓冲区，从前一个缓冲区的重定位端点开始。为了能够使用哨兵，即使输入中可能出现 NUL 字节，它也会使用输入缓冲区末尾的地址检查 NUL 的地址；如果它们不相同，则 NUL 是输入的一部分，并且 Flex 在状态转换 table 中查找 NUL 的操作。 （它比那更复杂一点，但这是高层次的概述。）由于缓冲端只是偶尔到达，因此检查 NUL 等的额外成本并不经常支付。
flex 架构的优点是它读取速度更快，因为它不是一次处理一个字符，而且它可以处理大令牌，尽管效率低下。 Lex 无法处理大令牌，因为令牌缓冲区 (yytext) 是一个静态数组，不是动态分配的，因此无法增长。