我应该避免"|" 在柔性模式？

Question

我听说过"|" 运算符会减慢正则表达式匹配,例如,它在Perl中似乎也是如此.

当我使用Flex词法分析器等工具构建扫描仪时,我是否需要担心？

Answer 1

绝对不.Flex(就像它所基于的lex词法分析器,以及大多数其他类似的编译器构造工具)将扫描器中的所有正则表达式编译成单个确定性有限状态自动机(DFA).在扫描词法标记时,DFA永远不会备份,并且组件正则表达式的复杂性和它们使用的精确运算符都没有区别.

这与Perl的正则表达式匹配方法完全不同.Perl(至少在某些情况下)将一次一个地在一个交替表达式中探索可能的子模式,结果是可以注意到显着的性能损失.在这个答案中,@ sln构建的Perl基准证明了这种效果.

为了证明Flex生成的解析器不是这样,我在Flex中构建了一个非常相似的基准.两个Flex输入文件:

(有|):

%{
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <time.h>

  static int echo_match = 0;
  static const char* regex="'''([^']|['][^']|[']['][^'])*'''";
%}

%option noyywrap noinput nounput nodefault

%%

[^'\n]+   { }
\n        { }
'[^'\n]*' {
            if (echo_match) printf("%s\n", yytext);
          }
'''([^']|['][^']|[']['][^'])*''' {
            if (echo_match) printf("%s\n", yytext);
          }
'         { fputs("Unmatched quote\n", stderr); }

没有|相同的,除了正则表达式模式(在两个地方):

'''[^']*(?:[']{1,2}[^']+)*'''

然后我用它main来测试每个扫描仪:

static const char* dataset[] = {
  "'''Set 1 - this\nis another\nmultiline\nstring'''",
  "'''Set 2 - this\nis' another\nmul'tiline\nst''ring'''"
};

#define COUNTOF(ARY) (sizeof(ARY)/sizeof(ARY[0]))

int main(int argc, char** argv) {
  int reps = 500000;
  printf("-----------------------\nUsing regex: %s\n", regex);
  for (unsigned d = 0; d < COUNTOF(dataset); ++d) {
    echo_match = 1;
    yy_scan_string(dataset[d]);
    yylex();
    yy_delete_buffer(YY_CURRENT_BUFFER);
    echo_match = 0;
    struct timespec before, after;
    if (clock_gettime(CLOCK_REALTIME, &before)) perror("gettime");
    for (int r = 0; r < reps; ++r) {
      yy_scan_string(dataset[d]);
      yylex();
      yy_delete_buffer(YY_CURRENT_BUFFER);
    }
    if (clock_gettime(CLOCK_REALTIME, &after)) perror("gettime");
    unsigned long elapsed =
        (after.tv_sec - before.tv_sec) * 1000000
        + (after.tv_nsec - before.tv_nsec) / 1000;
    printf("Wall-clock: %ld microseconds\n", elapsed);
  }
  return 0;
}

两组基准的随机结果(来自每组10个运行):

$ tail -n+$((1+12*(RAND/10))) threeq.log | head -n12
-----------------------
Using regex: '''([^']|['][^']|[']['][^'])*'''
'''Set 1 - this
is another
multiline
string'''
Wall-clock: 243410 microseconds
'''Set 2 - this
is' another
mul'tiline
st''ring'''
Wall-clock: 233519 microseconds

$ tail -n+$((1+12*(RAND/10))) threeq2.log | head -n12
-----------------------
Using regex: '''[^']*(?:[']{1,2}[^']+)*'''
'''Set 1 - this
is another
multiline
string'''
Wall-clock: 246842 microseconds
'''Set 2 - this
is' another
mul'tiline
st''ring'''
Wall-clock: 242191 microseconds

在某些情况下,Flex在识别出令牌后需要重新扫描输入,但这些与交替操作符无关|.由于Flex总是尝试找到最长匹配,因此即使在识别了令牌之后,它也可能需要继续扫描,以防该令牌是另一个可能令牌的前缀.如果较长的令牌证明不匹配,则Flex扫描程序将备份到匹配的最长令牌的末尾,其余字符将在下一个令牌中重新扫描.

例如,在C中,.并且...都是有效的令牌,但..不是.如果..出现在输入中,那么Flex构建的扫描仪必须在第一个之后继续扫描,.以查看它是否匹配....但是,当第三个字符证明不是a时.,它必须返回.令牌,然后第二个字符.将被重新扫描.(这几乎总是语法错误,所以问题不是很严重.)

Flex构建的扫描仪需要重新扫描的另一种情况/是使用(尾随上下文)运算符.由于尾随上下文实际上不是返回令牌的一部分,因此必须将其重新扫描为下一个令牌的一部分.

这些情况都不常见,重新扫描的序列通常非常短(通常是一个字符),因此性能影响微不足道.但是,如果您真的担心这一点,您可以--backup向Flex 提供选项,要求它准备备份状态报告.如果您设法消除所有备份状态,您将获得较小的性能提升,但大多数情况下这属于过早优化.