flex filename.l 不会产生 lex.yy.c

Question

我想检测输入中是否有重复的大写字母。该程序应该可以正常工作，但是当我尝试在 cmd windows 上运行命令 flex filename.l 时，它不会显示任何错误或警告。命令运行s 和我必须等到它输出 lex.yy.c 但那从未发生过。我还在等一个小时才能完成。为什么会这样？这是检测重复代码的部分。

// Definition Section
A_ ([B-L]*"A"[B-L]*("A"[B-L]*)+)
B_ ([ACDEFGHIJKL]*"B"[ACDEFGHIJKL]*("B"[ACDEFGHIJKL]*)+)
C_ ([ABDEFGHIJKL]*"C"[ABDEFGHIJKL]*("C"[ABDEFGHIJKL]*)+)
D_ ([ABCEFGHIJKL]*"D"[ABCEFGHIJKL]*("D"[ABCEFGHIJKL]*)+)
E_ ([ABCDFGHIJKL]*"E"[ABCDFGHIJKL]*("E"[ABCDFGHIJKL]*)+)
F_ ([ABCDEGHIJKL]*"F"[ABCDEGHIJKL]*("F"[ABCDEGHIJKL]*)+)
G_ ([ABCDEFHIJKL]*"G"[ABCDEFHIJKL]*("G"[ABCDEFHIJKL]*)+)
H_ ([ABCDEFGIJKL]*"H"[ABCDEFGIJKL]*("H"[ABCDEFGIJKL]*)+)
I_ ([ABCDEFGHJKL]*"I"[ABCDEFGHJKL]*("I"[ABCDEFGHJKL]*)+)
J_ ([ABCDEFGHIKL]*"J"[ABCDEFGHIKL]*("J"[ABCDEFGHIKL]*)+)
K_ ([ABCDEFGHIJL]*"K"[ABCDEFGHIJL]*("K"[ABCDEFGHIJL]*)+)
L_ ([ABCDEFGHIJK]*"L"[ABCDEFGHIJK]*("L"[ABCDEFGHIJK]*)+)
%%//Rule Section
{A_} {printf("Letter 'A' appeared more than once!");}
{B_} {printf("Letter 'B' appeared more than once!");}
{C_} {printf("Letter 'C' appeared more than once!");}
{D_} {printf("Letter 'D' appeared more than once!");}
{E_} {printf("Letter 'E' appeared more than once!");}
{F_} {printf("Letter 'F' appeared more than once!");}
{G_} {printf("Letter 'G' appeared more than once!");}
{H_} {printf("Letter 'H' appeared more than once!");}
{I_} {printf("Letter 'I' appeared more than once!");}
{J_} {printf("Letter 'J' appeared more than once!");}
{K_} {printf("Letter 'K' appeared more than once!");}
{L_} {printf("Letter 'L' appeared more than once!");}

Answer 1

这里确实有两个不同的问题。一个是你问的问题——为什么 flex 需要这么长时间来编译这个扫描器——另一个问题是扫描器的描述是否准确地反映了你的意图。第二个问题有点棘手，因为你没有对你的意图给出非常准确的描述，但最后我会尝试考虑一些似是而非的可能性。

首先，描述您的扫描仪描述的实际作用很有用。这也有点棘手，因为您只包含了扫描仪的一部分，所以我将冒昧地设计一个完整的扫描仪，这至少可以说明其意图。我要使用的代码如下：

注意：这些选项可防止编译器警告，消除对 yywrap 的需要，并在规则未涵盖所有可能的输入时发出警告。最后的回退模式和 main 的简短定义使扫描器运行可用。 {-} 是一个 Flex 扩展，它计算两个字符类.

之间的集合差异

  /* My standard 
   */
%option noinput nounput noyywrap nodefault
NOT_A  [A-L]{-}[A]
NOT_B  [A-L]{-}[B]
NOT_C  [A-L]{-}[C]
NOT_D  [A-L]{-}[D]
NOT_E  [A-L]{-}[E]
NOT_F  [A-L]{-}[F]
NOT_G  [A-L]{-}[G]
NOT_H  [A-L]{-}[H]
NOT_I  [A-L]{-}[I]
NOT_J  [A-L]{-}[J]
NOT_K  [A-L]{-}[K]
NOT_L  [A-L]{-}[L]
%%
{NOT_A}*A{NOT_A}*(A{NOT_A}*)+   { puts("Duplicate A"); }
{NOT_B}*B{NOT_B}*(B{NOT_B}*)+   { puts("Duplicate B"); }
{NOT_C}*C{NOT_C}*(C{NOT_C}*)+   { puts("Duplicate C"); }
{NOT_D}*D{NOT_D}*(D{NOT_D}*)+   { puts("Duplicate D"); }
{NOT_E}*E{NOT_E}*(E{NOT_E}*)+   { puts("Duplicate E"); }
{NOT_F}*F{NOT_F}*(F{NOT_F}*)+   { puts("Duplicate F"); }
{NOT_G}*G{NOT_G}*(G{NOT_G}*)+   { puts("Duplicate G"); }
{NOT_H}*H{NOT_H}*(H{NOT_H}*)+   { puts("Duplicate H"); }
{NOT_I}*I{NOT_I}*(I{NOT_I}*)+   { puts("Duplicate I"); }
{NOT_J}*J{NOT_J}*(J{NOT_J}*)+   { puts("Duplicate J"); }
{NOT_K}*K{NOT_K}*(K{NOT_K}*)+   { puts("Duplicate K"); }
{NOT_L}*L{NOT_L}*(L{NOT_L}*)+   { puts("Duplicate L"); }
  /* Match any string consisting of A-L */
[A-L]+                          { puts("No duplicate"); }
  /* Ignore newline or any other character */
.|\n                            ;
%%
int main(void) {
  return yylex();
}

重要的是要强调一个事实，即扫描仪的目的是将输入分成标记。扫描器不是通用的正则表达式引擎，尽管有时可以稍微突破界限。但是，如果您想执行一项任务，例如在输入中搜索可能重叠的正则表达式匹配，忽略不匹配的输入，您可能会发现 Flex 的顺序匹配架构不是很好的匹配问题。

因此，在这种情况下，我假设感兴趣的字符串是大写字母序列（具有受限制的字母表），并且可以安全地忽略其他任何内容。（这意味着输入 abcABCD993 将被分成七个标记，其中六个被忽略：开头的小写字母和结尾的数字。ABCD 被认为是一个标记，即使它没有明显地与周围的文本分隔。修复它，如果需要修复，并不困难，但与这个问题无关。）

因为我在末尾添加了模式 [A-L]+，规则集确实匹配受限字母表中的任何大写字母序列。但是只允许一个规则匹配任何这样的词。如果有重复的字母，前 12 个规则中的一个将匹配。 [A-L]+ 规则也将匹配，但由于它在末尾，因此只有在没有重复规则匹配时才会应用。同样，一个标记可以有多个重复字母（例如，CCLAAL 匹配 A、C 和 L 重复规则）。因为任何匹配的规则都将匹配整个令牌，所以应用的规则是扫描器描述中的第一条规则；字符串 CCLAAL 将触发报告 Duplicate A.

虽然看起来无害，但正是该分辨率导致扫描仪尺寸呈指数 blow-up。再次考虑示例输入 CCLAAL。开头的 CC 立即将模式 {NOT_C}*C{NOT_C}*(C{NOT_C}*)+ 置于接受状态，但匹配不会在该点终止；它可以扩展。然而，当扫描仪继续查看是否有更好的匹配时，它不能忘记 Duplicate C 是一种可能性。如果输入是 CCLAL，例如，Duplicate C 将是最佳匹配而不是 Duplicate A。需要记住的不仅仅是完整的重复匹配项。在模式 ACLLCA 中，直到到达第二个 A 才知道 Duplicate A 是正确的。因此，在读取第二个 L 时，扫描器不仅必须记住 Duplicate L 是一个可能的报告，而且还必须记住单个 A 或单个 C 可以相应地更改报告。

如果我们要编写一个程序来实现这些语义，最简单的方法是保留一个整数向量，表示每个字母 A 到 L 的出现次数。这样的代码可能看起来像这样:

int check_for_duplicate(void) {
  int ch;
  int seen['L' - 'A' + 1] = {0};
  while ((ch = getchar()) != EOF && (ch < 'A' || ch > 'L'))
    continue;
  if (ch == EOF) return EOF;
  seen[ch - 'A'] = 1;
  while ( (ch = getchar()) != EOF &&  >= 'A' && ch <= 'L') {
    ++seen[ch - 'A'];
  }
  /* Put the following character back into the stream */
  if (ch != EOF) ungetc(ch, stdin);
  /* See if a duplicate was found */
  for (int i = 0; i < sizeof(seen) / sizeof(*seen); ++i) {
    if (seen[i] >= 2) {
      printf("Duplicate %c\n", 'A' + i);
      return 1;
    }
  }
  puts("No duplicates");
  return 0;
}

在该程序中，数组seen 维护扫描的状态。每个可能的计数值中只有三个实际上是重要的，因此作为第一个近似值，总共有 3¹² = 531,441 个可能的有意义的扫描器状态。这在这里无关紧要，但对 Flex 来说却很重要； Flex 构建的扫描器是一个状态机，除了扫描器状态外没有其他数据。

这似乎是可以管理的，当我们注意到前 2 之后的任何内容都无关紧要时更是如此，将计数减少到 3*(2¹²-1)，即 12,287 .不幸的是，Flex 实际上是在处理正则表达式，而减少重复计数是它无法实现的抽象。我们可以看到每个字母只有三个相关计数，但 Flex 仅限于记录它在正则表达式中对每个可能的重复匹配进行了多远。而且正则表达式中的位置不止三个。

如果你运行Flex 与 -v 选项，它将打印出统计摘要，其中之一是它从规则集中生成的“DFA 状态”的数量。 Flex生成的scanner包含一个状态t运行sitiontable，它的大小和状态的数量有关，所以这个统计量很重要。我运行 Flex具有不同数量的重复匹配规则，从2到9，并提取每个状态机中的状态数；正如上面所预料的那样，状态计数在规则数量上是指数级的：

Rules   States
  2       28
  3       89
  4      306
  5     1063
  6     3656
  7    12405
  8    41566
  9   137795

根据这一进展，可以合理预测 12 个字母的扫描器将具有超过 5000 万个状态，并且包含状态 t运行sitions 的源文件将以千兆字节为单位进行测量。因此，Flex 需要一段时间才能生成它也就不足为奇了。

要做什么？

就个人而言，我宁愿自己做，也不愿尝试编写 Flex 模式。您可以使用 Flex 来识别要扫描重复项的令牌，然后使用简单的 C 函数对其进行扫描。您可以通过在令牌中的第一个重复字符处停止而不是尝试查找按字母顺序排在第一位的重复字符来加快扫描速度。

如果你真的想在 Flex 中做这个分析，这个行为，你可以通过多次扫描来完成。每次扫描都有自己的开始条件；您可以通过调用 yyless(0) 到 return 到令牌的开头来尝试下一个替代方案，然后调用 BEGIN(next_sc) 尝试下一个替代方案。但是进行 12 次（或 26 次）扫描是很不错的 time-consuming（在令牌不包含任何重复项的情况下）。

flex filename.l 不会产生 lex.yy.c

flex filename.l won't produce lex.yy.c

c++

flex-lexer

lex

lexical-analysis

要做什么？