减少疯狂的 flex 词法分析器扩展？

Question

我已经编写了一个 flex 词法分析器来处理 BYOND's .dmi file format. The contents inside are (key, value) pairs delimited by '=' 中的文本。有效键本质上都是关键字（例如"width"），无效键不是错误：它们只是被忽略了。

有趣的是，BYOND 的 .dmi 解析器的当前状态使用“=”之前的 everything 作为其关键字，并简单地忽略任何多余的垃圾。这意味着 "\twidth123" 被识别为 "width".

我的问题的症结在于允许这种不规则性。这样做时，我生成的词法分析器从 ~40-50KB 扩展到 ~13-14MB。作为参考，我提出了以下人为的例子：

%option c++ noyywrap

fill    [^=#\n]*

%%
{fill}version{fill}     { return 0; }
{fill}width{fill}       { return 0; }
{fill}height{fill}      { return 0; }
{fill}state{fill}       { return 0; }
{fill}dirs{fill}        { return 0; }
{fill}frames{fill}      { return 0; }
{fill}delay{fill}       { return 0; }
{fill}loop{fill}        { return 0; }
{fill}rewind{fill}      { return 0; }
{fill}movement{fill}    { return 0; }
{fill}hotspot{fill}     { return 0; }
%%

fill 是用于将关键字与 "anything before the =" 合并的规则。运行上面的 flex 在我的电脑上产生了 ~13MB lex.yy.cc。简单地删除填充规则中的 kleene 星号 (*) 会产生一个 45KB lex.yy.cc 文件；但是，很明显，这会使词法分析器不正确。

是否有任何技巧、弹性选项或词法分析器黑客可以避免这种疯狂的扩展？我唯一能想到的是：

不允许 "width123" 表示 "width"，这是不可取的，因为当时无法解析技术上正确的文件。
制定一个简单的规则 [^=\n]+ 到 return 一些 identifier 标记，然后在解析器中挑选关键字。这对我来说似乎也不是最理想的，特别是因为不同的关键字具有不同的值类型，并且能够处理“'width''='INT”和“'version''='FLOAT”似乎是最自然的解析器而不是 "ID '=' VALUE" 然后在标识符中挑选关键字，确保值是正确的类型等
我可以制定规则 {fill}(width|height|version|...){fill}，这确实使生成的文件变小了。然而，虽然正则表达式解析器倾向于生成 "captures," flex 只是给我 yytext 并重新解析关键字以生成所需的标记，但就算法复杂性而言，这似乎是非常不可取的。

Answer 1

使 fill 成为一个不执行任何操作的单独规则，并将其从所有其他规则中删除，并将其定义与空格分开以清楚起见：

whitespace [ \t\f]
fill [^#=\n]
%%
{whitespace}+ ;
{fill}+ ;

我可能还会避免将关键字构建到词法分析器中，而只使用执行 table 查找的 identifier [a-zA-Z]+ 规则。最后添加一条规则来捕获 =:

. return yytext[0];

让解析器处理所有特殊字符。

Answer 2

这其实不是flex的问题"good at"，但是如果精确定义就可以解决。特别是，如果 = 之前的随机字母字符串包含多个关键字，那么知道应该返回 中的哪个 关键字很重要。例如，假设输入是：

garbage_widtheight_moregarbage = 42

现在，设置 width 还是 height？

请记住，flex 扫描器将选择匹配最长的规则，以及匹配长度相同的规则，词法描述中的第一个规则。

因此 OP 中提供的模型：

fill    [^=#\n]*

%%
{fill}width{fill}       { return 0; }
{fill}height{fill}      { return 0; }
  /* SNIP */

总是优先选择 width 而不是 height，因为匹配的长度相同（都在 = 之前的最后一个字符处终止）， width 模式在文件中排在第一位。如果规则写的顺序相反，优先选择height。

另一方面，如果您删除第二个 {fill}:

{fill}width{fill}       { return 0; }
{fill}height{fill}      { return 0; }

那么输入中的 last 关键字（在本例中为 height）将是首选，因为它具有更长的匹配。

然而，最有可能的要求是识别 first 关键字，因此前面的两个都不起作用。为了匹配第一个关键词，需要先匹配最短可能的序列{fill}。而且由于 flex 没有实现非贪婪重复，这只能通过逐个字符的跨度来完成。

这是一个使用开始条件的示例。请注意，我们保留关键字标记，直到我们真正找到 =，以防找不到 =。

 /* INITIAL:    beginning of a line
  * FIND_EQUAL: keyword recognized, looking for the =
  * VALUE:      = recognized, lexing the right-hand side
  * NEXT_LINE:  find the next line and continue the scan
  */
%x FIND_EQUAL VALUE
%%
    int keyword;
"[#=]".*         /* Skip comments and lines with no recognizable keyword */
version           { keyword = KW_VERSION; BEGIN(FIND_EQUAL); }
width             { keyword = KW_WIDTH;   BEGIN(FIND_EQUAL); }
height            { keyword = KW_HEIGHT;  BEGIN(FIND_EQUAL); }
  /* etc. */
.|\n              /* Skip any other single character, or newline */

<FIND_EQUAL>{
  [^=#\n]*"="     { BEGIN(VALUE); return keyword; }
  "#".*           { BEGIN(INITIAL); }
  \n              { BEGIN(INITIAL); }
}

<VALUE>{
  "#".*           { BEGIN(INITIAL); }
  \n              { BEGIN(INITIAL); }
  [[:blank:]]+    ;  /* Ignore space and tab characters */
  [[:digit:]]+    { yylval.ival = atoi(yytext);
                    BEGIN(NEXT_LINE); return INTEGER;
                  }
  [[:digit:]]+"."[[:digit:]]*|"."[[:digit:]]+ {
                    yylval.fval = atod(yytext);
                    BEGIN(NEXT_LINE); return FLOAT;
                  }
  \"([^"]|\.)*\" { char* s = malloc(yyleng - 1);
                    yylval.sval = s;
                    /* Remove quotes and escape characters */
                    yytext[yyleng - 1] = '[=13=]';
                    do {
                      if (*++yytext == '\') ++yytext;
                      *s++ = *yytext;
                    } while (*yytext);
                    BEGIN(NEXT_LINE); return STRING;
                  }
    /* Other possible value token types */
  .               BEGIN(NEXT_LINE); /* bad character in value */ 
}                         
<NEXT_LINE>.*\n?  BEGIN(INITIAL);

在转义移除代码中，您可能需要翻译 \n 之类的内容。您可能还想避免使用物理换行符的字符串值。还有一堆等等。它仅用作模型。

减少疯狂的 flex 词法分析器扩展？

Reducing insane flex lexer expansion?

flex-lexer