在 Flex Lexer 中，为什么在加载新输入之前将最后一个字符移动到缓冲区的开头？

Question

我正在尝试理解词法分析器 (source) I'm porting to JavaScript and am stuck understanding how data from an input is read into a buffer. It's a standard Lexer so I'm hoping someone can give me some hints on what is happening on #919。

有问题的代码段：

register char *dest = yy_current_buffer->yy_ch_buf;
register char *source = yytext_ptr;
...

/* First move last chars to start of buffer. */
number_to_move = (int) (yy_c_buf_p - yytext_ptr) - 1;

for ( i = 0; i < number_to_move; ++i )
    *(dest++) = *(source++);

我不明白为什么最后一个字符必须移到缓冲区的开头。我认为如果我需要比最初分配的更多 space 缓冲区将被扩展，那么为什么需要将最后一个字符改组到前面？

此外，循环并没有真正考虑缓冲区 "current position"（我对 number_to_move 的解释）。如果我的缓冲区大小是 10000 并且我在位置 2048，那么在加载更多数据之前循环 2048x 的目的是什么？我也在考虑，如果缓冲区指针 yy_c_buf_p 和输入指针 yytext_ptr 保持同步，number_to_move 将始终为 0。但是，唉，也许有人可以告诉我什么是真正的发生在这里以及循环实际做了什么。

谢谢！

Answer 1

why is the shuffling of last characters to the front necessary?

严格来说不是，但它既节省时间又 space。当扫描器到达缓冲区的末尾时，缓冲区大致如下所示：

      already scanned tokens-----------------------Curr
      ^                                            ^    ^
      |                                            |    |
  yy_ch_buf                                   yytext    buf_p

缓冲区开始和 yytext_ptr 之间的所有内容都不再需要，复制它会浪费时间，而保留它也会浪费 space，这在编写 flex 时很重要。而不是重新分配（除非真的有必要，因为缓冲区已满），扫描器可以将部分扫描的令牌移动到缓冲区的开头，并从输入中填充缓冲区的其余部分。

... if buffer-pointer yy_c_buf_p and input-pointer yytext_ptr are kept in sync ...

这是两个不同的指针，它们只是"in sync"在一个token的开头。 yytext_ptr（这是yytext的内部名称）指向当前标记的开头； yy_c_buf_p指向当前token在扫描中的当前位置。

当检测到缓冲区结束时，yy_c_buf_p 指向终止缓冲区的 NUL 之后的一个，因此 yy_c_buf_p - yytext_ptr - 1 是当前令牌中已扫描的字符数，4上面的例子。（所以它是当前标记中的位置，而不是缓冲区中的位置。）下一步将从输入中读取 buffer_size - number_to_move 个字符，以便缓冲区现在看起来像这样：

    Current tokenNext token-----------------------------
      | |------------read from yyin--------------------|
      ^
  yy_ch_buf
    yytext
    buf_p

yytext 必须指向当前标记的开头，因为这是最终执行操作时 yytext 的预期值。 yy_c_buf_p总是指向下一个要扫描的字符，所以当真正到达token末尾时，它指向下一个token中的第一个字符。（在执行操作之前，该字符被 NUL 覆盖，并且在开始下一次扫描之前，该字符被恢复。这是代码的不同部分，对于不使用 NUL 的语言的端口可能是不必要的-终止的字符串。）

在缓冲区被重新填充后扫描指针被重新定位到令牌的开头可能看起来很奇怪，因为这意味着整个令牌将被重新扫描。这与 flex 扫描仪识别缓冲区末尾的方式有关；总之，在执行充值代码时，最后扫描的真实字符的扫描器状态已经丢失。对于编写 flex 时普遍可用的机器来说，保持旧的扫描器状态的成本被认为太高了：这意味着在内部扫描循环中有一个额外的指针副本，并且对于许多机器来说，复制必须是到内存，因为一个额外的寄存器不可用。由于重新扫描很少发生，并且由于公共令牌非常短，因此重新扫描部分令牌被认为（并被测试为）比支付保持状态可用的成本更便宜。这种权衡在您的应用程序中是否正确是您必须自己决定的事情，可能需要借助基准测试。

检测缓冲区末尾的机制也是 yy_c_buf_p 超出部分扫描令牌末尾两个字节而不是一个字节的原因。（在 flex 生成的扫描器的上下文中，这很好，因为 flex 确保缓冲区以两个 NUL 字节结束，而不仅仅是一个。）

注意：如果您使用默认的 %p 设置，Flex 将在需要大令牌时调整输入缓冲区的大小。但是原始的 lex 使用了一个 array 作为缓冲区（flex 声明 %a），无法调整大小；扫描仪会在非常长的令牌上失败。（因为这些不会在行为良好的代码中发生，所以这不是问题，尽管它会影响您扫描评论的方式，例如。）因此将当前标记向后移动是处理缓冲区结束的唯一方法。

在 Flex Lexer 中，为什么在加载新输入之前将最后一个字符移动到缓冲区的开头？

In a Flex Lexer, why are last chars moved to the beginning of a buffer before loading new input?

c

flex-lexer

lex

lexer