Flex 如何区分 A、AB 和 ABC？

Question

我为 Flex 做了这个实验，看看我是否输入 ABC，它是否会看到所有 A、AB、ABC 或仅 ABC 或仅表达式列表中的第一个匹配项。

%{
#include <stdio.h>
%}

%%
A puts("got A");
AB puts("got AB");
ABC puts("got ABC");
%%

int main(int argc, char **argv)
{
    yylex();

    return 0;
}

当我在编译和运行程序后输入 ABC 时，它以 "Got ABC" 响应，这让我很惊讶，因为我认为 lex 不会跟踪访问过的文本，只会找到第一个比赛;但实际上，它似乎找到了最长的匹配项。

当且仅当不再匹配时，Flex使用什么策略来响应A？

Answer 1

(F)lex 使用 maximal-munch principle should hardly be surprising, since it is well documented in the Flex manual 的事实：

When the generated scanner is run, it analyzes its input looking for strings which match any of its patterns. If it finds more than one match, it takes the one matching the most text…. If it finds two or more matches of the same length, the rule listed first in the flex input file is chosen. (First paragraph of the section "How the input is matched")

精确算法非常简单：每次请求令牌时，flex 都会扫描文本，在 DFA 中移动。每次它达到接受状态时，它都会记录当前的文本位置。当没有更多的转换可能时，它 returns 到最后记录的接受位置，这成为令牌的结尾。

结果是 (F)lex 可以多次扫描同一文本，尽管它只为每个标记扫描一次。

一组要求过多的词法规则back-tracking会减慢词法扫描速度。这在 Flex 手册部分 Performance Considerations 中进行了讨论，以及一些避免该问题的策略。但是，除了病态情况外，back-tracking 的开销并不明显。

Flex 如何区分 A、AB 和 ABC？

How does Flex distinguish between A, AB, and ABC?

parsing

flex-lexer