备份在 flex 中成本高昂？

Question

这是在 flex 中生成的 c 文件的摘录（为了便于阅读，进行了一些修改/重新格式化）。

yy_find_action:
        yy_act = yy_current_state[-1].yy_nxt;

        /* YY_DO_BEFORE_ACTION */
        yyg->yytext_ptr = yy_bp;
        yyg->yytext_ptr -= yyg->yy_more_len;
        yyleng = (int) (yy_cp - yyg->yytext_ptr);
        yyg->yy_hold_char = *yy_cp;
        *yy_cp = '[=10=]';
        yyg->yy_c_buf_p = yy_cp;

        // this condition will always be false when yy_act = 0
        if ( yy_act != YY_END_OF_BUFFER && yy_rule_can_match_eol[yy_act] )
            {
            ...
            }

do_action:
        switch ( yy_act )
            {
            case 0: /* must back up */

            /* undo the effects of YY_DO_BEFORE_ACTION */
            *yy_cp = yyg->yy_hold_char;
            yy_cp = yyg->yy_last_accepting_cpos + 1;
            yy_current_state = yyg->yy_last_accepting_state;
            goto yy_find_action;

            ...
            }

在上面的代码中，首先，flex 正在获取动作 (yy_act)。然后它正在设置执行操作 (YY_DO_BEFORE_ACTION)。然后它检查操作是否为 'backup'（案例 0）。然后它再次撤消并重做所有设置。

如果您看到 Flex documentation on performance，备份对生成的扫描程序的性能影响排名第三。如果在设置之前检查备份是否会提高性能？为什么生成的代码这样做我看不到任何好处？

Answer 1

Flex 是围绕“针对常见情况进行优化”的原则编写的。这有时会导致在权衡中故意悲观不常见的情况，因为不常见情况的小收益远远超过很少发生的情况的成本。

大多数词法分析器都有一个或两个需要备份的状态，但实际上这种情况很少见。例如，如果输入包含 .. 而后没有另一个 .，则 C 需要备份，但在实际程序中实际上从未发生过。需要备份的最常见（或最不常见）情况是需要在令牌中间重新填充缓冲区时，每 16K 输入会发生一次。那可能是 1000 个代币左右。

那么，哪个成本更高：1000 次失败的测试还是不到一打的终止令牌然后撤消它的指令？现代分支预测可能会大大降低失败测试的成本（比编写该代码时的典型成本要多得多），但即便如此，它似乎也不会成功。在所有其他操作中包含令牌最终确定的替代方案可能会更快，但它会显着增加代码的大小，这也会产生执行成本。

另外，说“备份对生成的扫描器的性能影响排名第三”有点误导。列表中的前两项对性能有很大影响；如果剩余项目可以忽略不计，则影响。

对可能备份的扫描器的最大影响是它强制词法分析器为每个可能是标记结尾的字符保存当前状态和光标；无论当前令牌最终是否需要备份，都需要支付该费用。所以它与您粘贴的代码没有什么关系，它只为每个令牌运行一次。换句话说，成本不是备份本身，而是使备份成为可能所需的簿记。

同样，您应该尽量避免编写可能产生大量备份的规则（包括具有无限尾随上下文的规则），因为这会导致过度扫描。在病态情况下，它会导致二次扫描时间，尽管这不太可能出现在实际语法中。（一个例子是规则对 -*: 和 - 这将花费二次方时间来分析由大量 - 后跟冒号以外的内容组成的输入。

无界备份更常见的情况是 ["]([^"\\n]|\(.|\n))*["] 之类的规则（匹配带引号的字符串文字）。在未终止的字符串文字的情况下，这将导致备份到初始 "，除了可能效率低下之外，这确实不是您想要的。最好添加另一个规则，如 ["]([^"\\n]|\(.|\n))*\?，它将匹配未终止的文字而无需备份。

备份在 flex 中成本高昂？

Backing up is costly in flex?

c

code-generation

flex-lexer