如何测量解析时间？

Question

我有一个 flex/bison 解析器读取文本文件，解析它，我的“.y”文件中的“开始”规则使用 printf 输出结果。我想测量解析时间（不是读取文本文件的时间，也不是输出结果的时间）。我想运行解析 100 次并计算平均解析时间。我怎么做？我尝试了下面的代码，但我发现发生的事情（我认为）是解析器读取输入文件，解析它，输出结果，然后给出 99 条“错误：语法错误”消息。哎呀！请问正确的做法是什么？

int main(int argc, char *argv[])
{
    struct timeval begin, end;
    
    yyin = fopen(argv[1], "r");
    
    // Start measuring time
    gettimeofday(&begin, 0);
    int i;
    for (i=0; i<100; i++)
        yyparse();
    
    // Stop measuring time and calculate the elapsed time
    gettimeofday(&end, 0);
    long seconds = end.tv_sec - begin.tv_sec;
    long microseconds = end.tv_usec - begin.tv_usec;
    double elapsed = seconds + microseconds*1e-6;
    printf("Total time for 100 parses: %.6f seconds.\n", elapsed);
    printf("Time per parse: %.6f seconds.\n", elapsed/100);
    
    fclose(yyin);
    
    return 0;
}

Answer 1

（注意：这个答案主要解决了如何多次读取相同输入的问题。我在最后添加了一个关于基准测试的小注释。）

在 bison 生成的解析器中，解析器在需要时向词法扫描器询问每个标记，词法扫描器读取缓冲区中的输入以满足请求。所以把解析时间和阅读时间分开是不可能的；阅读与解析交织在一起。（所有输入都由词法扫描器完成。Bison 生成的解析器根本不需要 stdio.h 进行解析，尽管通常包含它是为了能够打印错误消息和调试信息。）

正如您对该模型所期望的那样，当您通过将 FILE* 分配给 yyin 向词法扫描器提供 FILE* 时，文件将被消耗到解析终止点，或者通过读取文件末尾或遇到语法错误。为了第二次解析整个输入，您需要自己倒回文件； flex 生成的扫描仪从不尝试这样做。

并非总是可以倒回文件；仅当文件是普通磁盘文件时才有效。管道、套接字、终端和其他此类对象——所有这些在 C 标准库的术语中都是“文件”——只能读取一次。因此，依赖于重新读取其输入的代码应该为失败的可能性做好准备，也许可以通过复制到临时文件来实现。

一个可能的解决方案是自己将整个文件读入内存，然后使用 yy_scan_bytes 将其提供给 flex 生成的扫描器。请注意，flex 生成的扫描器不会保留其输入缓冲区的内容；因此，yy_scan_bytes 为您提供的数据创建一个动态分配的副本，并且您必须确保在解析完成后通过删除缓冲区状态来释放此副本。

一个更彻底的解决方案，也可以消除用于标记化输入的时间，是通过重复调用 yylex 直到它 return 成为 EOF 来创建一个标记数组指示（return 值≤0）。然后，您可以将此数组输入使用一个标记器，该标记器简单地连续 returns 数组值。（由于您不能对两个名称都使用 yylex，因此您必须安排其中一个具有不同的名称。请参阅 YY_DECL 以了解重命名由 flex 生成的扫描仪的简单方法。 )

如果这样做，请注意动态分配的标记语义值；如果您的扫描器分配了这些值并且您的解析器释放了它们（这是一种常见的架构），那么您将无法简单地重新运行令牌序列，因为所有语义值都将被释放。相反，您的令牌包装器必须在 return 将令牌发送到解析器之前制作所有动态分配值的新副本。

关于基准分析器：

在大多数情况下，这个问题中提到的详细时间测量不会很有用。如果最终目标是比较两种不同的解析策略（不同的语法，或者在解析器和扫描器之间拆分工作的不同方式），那么就没有特别需要删除 I/O 成本；除非输入文件非常大，否则 OS 内核中的输入文件缓冲将节省大部分 I/O 成本，因此只需在前几次预热迭代期间丢弃基准测试即可一个相当准确的衡量标准。无论如何，这比试图完全消除 I/O 更现实。

解析器的微基准测试很常见，主要是尝试比较不同的解析器生成器，但正如您可能想象的那样，它们并不是特别有用，因为基准测试人员往往有个人偏见（也就是说，他们想证明他们自己产品的优越性）或不具备优化不同解析框架的详细知识，或两者兼而有之。由于实际应用程序中的解析速度通常在很大程度上取决于缓存效果和所使用的动态内存分配器的速度，因此与这些外部性最小化的微基准测试的结果可能没有太大的相关性。最后，如果很难在部署解析器的上下文中看到两种不同解析策略的比较成本，这可能是初步证据表明它在实践中没有太大区别，优化工作应该在其他地方进行。

正如所建议的那样，分析解析器可能是更好的策略，具体取决于您的数据收集需求。

Answer 2

计时yyparse函数，同时计时yylex函数。用 yyparse.

花费的时间减去 yylex 花费的时间

一般情况下，这种事情都是用profiling工具来完成的。分析工具会直接告诉您在 yyparse 中花费了多少时间，并将其分解为 yyparse 本身与其子项花费了多少时间。

听起来好像您的调查正朝着需要分析的详细程度的方向发展。

如何测量解析时间？

How to measure the parse time?

bison

flex-lexer

yacc

lex

关于基准分析器：