时间戳

首页 > 解决方案 > 替代在扫描仪中备份？

compiler-construction - 替代在扫描仪中备份？

问题描述

我有时会发现自己在扫描仪中备份。这是一个典型的例子：

    private static final JSON_Value readArray( StringBuffer sbContent, StringBuffer sbError ){
        JSON_Value value_array = JSON_Value.createNull();
        char c;
BeginningOfArray:
        while( true ){
            pos++;
            c = sbContent.charAt( pos - 1 );
            switch( c ){
                case '\n': case '\r': case '\t': case ' ': case '\f': // blank space at beginning of array
                    continue;
                case ']':
                    return JSON_Value.createEmptyArray();
                case ',':
                    value_array.size = 1;
                    break BeginningOfArray; // process next value
                default:
                    pos--;  <-- BACKING UP
                    value_array.size = 0;
                    break BeginningOfArray; // process next value
            }
        }
        while( true ){
            pos++;
            c = sbContent.charAt( pos - 1 );
            switch( c ){
            ... etc

在上面处理 JSON 数组的扫描器中，数组中的第一个元素可能会丢失，在这种情况下，扫描器会首先遇到一个逗号，否则它将遇到一个将开始一个值的字符。由于主循环总是以前进开始，如果遇到非逗号字符，则我备份，使其成为第一个字符。

是否有替代方案可以使扫描仪始终保持前进，或者在某些情况下不可避免地进行备份？

标签： compiler-constructionlanguage-theory

解决方案

这取决于您正在分析的语言的词汇结构的确切性质，但通常可以消除备份。但是，将其保留通常更方便，从而避免一定数量的代码重复和/或笨拙的控制结构。

通过“备份”准确说明您的意思很有用，因为我通常不会将您问题中的示例视为一个实例。如果不查看标记后面的字符，则绝大多数标记都无法识别（例如，标识符一直延伸到下一个字符不是字母数字）。虽然可以通过一些工作来避免它，但是两次考虑终止字符是正常的：一次确定它不能是前一个标记的一部分，然后再次确定它可能启动哪种标记。

这是否看起来像备份将在某种程度上取决于您用于读取输入的范例。一般而言，有两种可能的范例（以及许多不完全适合任何一种模型的混合搭配实现）：

  1. peek和accept。

    peek返回下一个输入字符而不修改读取光标的位置，因此连续两次查看将看到相同的字符。accept将读取光标移动到下一个位置而不返回任何内容。因此，处理一个字符将需要一个（或多个）peek操作，并且恰好需要一个accept.

    这可能是更有效的范例，但由于需要显式的accept.

    对于一个简单的内存输入缓冲区，peek()基本上是return inputBuffer.charAt(pos);和accept()是++pos;；这两个通常都是由编译器或程序员内联的。

  2. get和unaccept。

    get返回下一个输入字符并将读取的光标前进一个位置，以便下一个get将读取下一个字符。unaccept将读取的光标向后移动一个字符，以便下一个字符get重新读取前一个字符。（这与标准 C 库的 不太一样ungetc，它允许将不同的字符插入到读取缓冲区中，并且可能允许多个字符未被获取。稍后会详细介绍。）

    对于一个简单的内存输入缓冲区，get()基本上是c = peek(); accept(); return c;和unaccept()是--pos。同样，它们通常会被内联。

由于get(); unaccept();序列与 完全相同peek();，因此这两种范式非常同构。unaccept()尽管包括减少的事实，但pos我很难将其视为“备份”。它只是重读一个字符，就像peek/accept范式一样。

高度简化和部分词法分析器（非上下文）的摘录可能如下所示：

c = peek();
while (isblank(c))   { accept(); c = peek(); }
if (c == '<') {
  accept();
  c = peek();
  if (c == '=')      { accept(); return Token_LessEquals; }
  else if (c == '<') { accept(); return Token_LeftShift; }
  else return Token_Less;
}
if (isalpha(c)) {
  tstart = pos;
  accept();
  while (isalnum(peek())) { accept(); }
  return makeIdToken(tstart, pos);
}
// etc.

以 get/unaccept 样式编写的相同片段：

c = get();
while (isblank(c))     { c = get(); }
if (c == '<') {
  c = get();
  if (c == '=')        { return Token_LessEquals; }
  else if (c == '<')   { return Token_LeftShift; }
  else                 { unaccept(); return Token_Less; }
}
if (isalpha(c)) {
  tstart = pos - 1;
  while (isalnum(get())) { }
  unaccept();
  return makeIdToken(tstart, pos);
}
// etc.

由于unaccept()接受令牌时很常见（尽管不是通用的），因此很容易将其从操作中删除并在我们开始尝试识别令牌之前简单地为其添加前缀。当然，如果我们这样做，我们需要在没有前瞻的情况下找到令牌末尾的情况下添加冗余get()（或）：accept()

unaccept();
c = get();
while (isblank(c))     { c = get(); }
if (c == '<') {
  c = get();
  if (c == '=')        { accept(); return Token_LessEquals; }
  else if (c == '<')   { accept(); return Token_LeftShift; }
  else                 { return Token_Less; }
}
if (isalpha(c)) {
  tstart = pos - 1;
  while (isalnum(get())) { }
  return makeIdToken(tstart, pos);
}
// etc.

现在，唯一unaccept()安全地隐藏在标记器的序言中。（碰巧，这实际上是 Flex 使用的样式。“冗余”accept()实际上隐藏在转换表中。没有“令牌接受”动作，所以在看到 的第二个字符后<<，扫描仪继续读取一个前瞻字符，然后发现没有使用该字符的转换。然后它接受令牌，并在下一次调用时重新读取前瞻字符yylex();。这可能看起来有点笨拙，但事实证明 main 的简化循环比偶尔阅读不需要的前瞻更有价值。

我们能摆脱最后剩下的unaccept()吗？是的，如果我们愿意通过使用推送解析器来反转控制流，我们可以。（我自己非常喜欢这个解决方案。）在这个模型中，词法扫描器驱动解析过程，每当它有一个标记时调用解析器。这在递归下降解析器中表现不佳，但它可以与维护自己的堆栈的解析器一起正常工作。对于生成的解析器来说，这显然比手写解析器更容易，并且有几个 LALR(1) 解析器生成器支持这种风格。（没有什么能阻止自上而下的解析器使用它自己的堆栈而不是调用堆栈，但我不知道是否有任何自上而下的生成器合作。）

在这个模型中，词法分析器有自己的循环来读取标记，并且在调用解析器时保留了前瞻字符：

c = get();   /* Start by reading the first character */
for (;;) {   /* Token loop assumes that every action will read a lookahead */
  while (isblank(c))   { c = get(); }
  if (c == '<') {
    c = get();
    if (c == '=')      { c = get(); parse(Token_LessEquals); }
    else if (c == '<') { c = get(); parse(Token_LeftShift); }
    else               {            parse(Token_Less); }
  }
  if (isalpha(c)) {
    tstart = pos - 1;
    while (isalnum(get())) { }
    parse(makeIdToken(tstart, pos));
  }
  // etc.
}

如果您使用推送解析器，还有一个更有趣的替代方案，但我只见过它使用带有转换表的生成扫描器实现；对于开放编码的扫描仪，这将是很多代码重复。

在推送解析器的扫描器操作中，没有什么能阻止我们调用解析器两次（甚至更多）。如果你仔细想想，JSON 中最常见的情况是，一个值后面紧跟一个逗号或右括号。如果是这种情况，我们可以通过使用与值和以下运算符字符匹配的模式集合来保存动作调度，并将它们都输入解析器。（如果该值后跟空格，则可以丢弃空格字符；无需重新扫描它。因此，除非该值后跟多字符标记 - 在 JSON 中，这是不可能的 afaik - 这个优化将是一个胜利。）

实际上实现该优化很烦人，但扫描仪生成器可以轻松完成它。不过，我不知道有哪个可以。

以上所有的文体都很好，我不确定它是否真的解决了这个问题。因为在很多情况下，如果不是大多数语言，回溯——真正的回溯，而不仅仅是重读过渡字符——更难摆脱。

假设该语言有一个标记是另一个标记的前缀，但中间前缀不是有效标记。作为一个具体的例子，C 标记包括.and...但不包括... 因此，a..b必须将序列标记为a..bwhile a..bis a...b。.在第一种情况下可以发出令牌之前，必须读取第二种. 和以下两种情况。b如果结果是b，则扫描仪必须备份一个额外的字符。这种备份很难摆脱。

一个有点类似的例子出现在 Rust 的范围运算符..中。在这里，问题在于它1..5是一个范围表达式1..5，而1.0它是一个浮点文字。再次，1直到两个前瞻字符被消耗后才能发出令牌，如果它们都是.，则需要将它们放回输入流中，或者（如果控制流反转可用）需要发出两个令牌。因此，在这种情况下，更容易摆脱备份，但仅限于特定架构。这在 C 的情况下会更棘手，因为a..3是两个标记和第三个标记的开始，a..3….

如果您编写需要备份的词汇规范（在最后几段的意义上；即，多个字符），Flex 可能会被要求警告您。那是因为：

  • 处理备份的可能性会使生成的扫描程序在整个过程中稍微变慢，尽管今天的减速远没有 Flex 首次编写时那么重要，更重要的是，

  • 这样的词法说明通常是错误的。

作为此类错误的示例，请考虑扫描仪中的以下两条规则：

["][^"\n]*["]    { yylval = strndup(yytext + 1, yyleng - 2); return STRING; }
  // ...
.                { return *yytext; /* Standard fallback rule */ }

未终止的字符串文字将导致选择回退规则，这涉及备份字符串的整个长度。该备份是不必要的，并且只会在解析器尝试错误恢复时导致混乱。

实际上需要长时间备份的语言非常罕见，但我当然不会冒险说它们不存在。我确定有一些。如果可能的备份不限于固定长度，那么标准的最大 munch 扫描算法就变成了二次的。通过一些工作，即使面对任意备份也可以进行线性时间扫描，但代价是增加了空间消耗。

推荐阅读