解析器组合子和LR(1)分析方法的性能比较

在使用解析器组合子编写编译器前端时，其与LR分析方法之间的性能差距是开发人员关心的重点问题之一。

背景

解析器组合子是一种使用函数式编程思想编写编译器前端中的词法分析器和语法分析器的编程范式。这种方式通过利用函数式编程语言将词法和语法直接嵌入在解析器代码中，大大提高了编写分析器的效率，降低了编写的难度。

但是这种以函数的嵌套和递归为核心的编程范式却带来了分析器运行效率下降的问题，在运行效率和编写效率之前的取舍成为了编译器研究人员十分关心的话题。因此，为了实际对比两种编写方式的运行效率，并为解析器组合子库的后续优化提升指明方向，本文中通过使用两种方式编写针对Pascal-S语言的解析器，设计了多组Benchmark对比两个解析器的运行效率。

Pascal-S语言

本次测试使用的语言为Pascal-S语言，这是Pascal语言的一个简化版本，语言的具体语法如下所示。

ProgramStart -> ProgramStruct
ProgramStruct -> ProgramHead ; ProgramBody .
ProgramHead -> program id (IdList) | program id
ProgramBody -> ConstDeclarations
               VarDeclarations
               SubprogramDeclarations
               CompoundStatement
IdList -> , id IdList | : Type
ConstDeclarations -> $\epsilon$ | const ConstDeclaration ;
ConstDeclaration -> id = ConstValue | ConstDeclaration ; id = ConstValue
ConstValue -> +num | -num | num | 'letter' | true | false
VarDeclarations ->  | var VarDeclaration ;
VarDeclaration -> id IdList | VarDeclaration ; id IdList
Type -> BasicType | array [ Period ] of BasicType
BasicType -> integer | real | boolean | char
Period -> digits .. digits | Period , digits .. digits
SubprogramDeclarations -> $\epsilon$ | SubprogramDeclarations Subprogram ;
Subprogram -> SubprogramHead ; SubprogramBody
SubprogramHead -> procedure id FormalParameter 
                | function id FormalParameter : BasicType
FormalParameter -> $\epsilon$ | () | ( ParameterList )
ParameterList -> Parameter | ParameterList ; Parameter
Parameter -> VarParameter | ValueParameter
VarParameter -> var ValueParameter
ValueParameter -> id IdList
SubprogramBody -> ConstDeclarations
                  VarDeclarations
                  CompoundStatement
CompoundStatement -> begin StatementList end
StatementList -> Statement | StatementList ; Statement
Statement -> $\epsilon$
             | Variable assignOp Expression
             | ProcedureCall
             | CompoundStatement
             | if Expression then Statement ElsePart
             | for id assignOp Expression to Expression do Statement
             | while Expression do Statement
Variable -> id IdVarPart
IdVarPart -> $\epsilon$ | [ ExpressionList ]
ProcedureCall -> id | id () | id ( ExpressionList )
ElsePart -> $\epsilon$ | else Statement
ExpressionList -> Expression | ExpressionList , Expression
Expression -> SimpleExpression | SimpleExpression RelationOperator SimpleExpression
SimpleExpression -> Term | SimpleExpression AddOperator Term
Term -> Factor | Term MultiplyOperator Factor
Factor -> num 
          | true
          | false
          | Variable
          | ( Expression )
          | id () 
          | id ( ExpressionList )
          | not Factor
          | - Factor
          | + Factor
AddOperator -> + | - | or
MultiplyOperator -> * | / | div | mod | and
RelationOperator -> = | <> | < | <= | > | >=

分析器的实现

本次测试中涉及到两个分析器的实现。两个分析器都是使用C#语言编写，运行在.NET 8.0.7平台上，使用X64 RyuJIT AVX2配置进行运行。

第一个分析器称为Canon。词法分析器使用朴素的自动机实现，没有使用任何的高端技术。将所有的词法规则写在一个巨大的自动机中，代码长度600行，是一个在可读性上堪称地狱，但是在效率上做到极致的方式。语法分析器虽然使用LR(1)分析方式，但是没有使用任何成熟的语法分析工具，而是自行实现的LR(1)语法分析器，在构建LR(1)分析表之后将分析表生成为C#代码编译到最终的程序集中，以求获得和传统语法分析器工具近似的运行效率。本分析器具体的实现可以在jackfiled/Canon获得。

第二个分析器称为CanonSharp，词法分析器和语法分析都是使用自行实现的解析器组合子实现，解析器组合子的实现可以参考我的上一篇文章。词法分析器的解析器以字符作为输入，解析之后输出词法令牌。语法分析器的解析器以词法令牌作为输入，解析之后输出抽象语法树。这个分析器的代码可以在jackfiled/CanonSharp获得。需要说明的是，两个分析器最终的输出有一定的不同，Canon分析器的输出是完整的语法树，在语法定义中的每一个非终结节点都在语法树上存在，CanonSharp分析器的输出是抽象语法树，语法定义中的一些冗余的节点在抽象语法树中均不存在。这种实现上的差异可能会导致两个分析器在占用内存上存在一定的差异，但是并不会在运行效率上造成明显的影响。

基准测试程序的编写

测试程序使用BenchmarkDotnet作为驱动程序。这是一个.NET平台上简单易用的基准测试框架，可以按照编写单元测试的方式编写基准测试程序。本文中使用的测试代码如下所示：

public class GrammarParserBenchmark
{
    private readonly List<string> _inputFiles = [];

    // CanonSharp
    private readonly LexicalScanner _scanner = new();
    private readonly GrammarParser _parser = new();

    // Canon
    private readonly IGrammarParser _grammarParser = GeneratedGrammarParser.Instance;

    public GrammarParserBenchmark()
    {
        // 读取文件系统中的程序文件
        _inputFiles.AddRange(ReadOpenSet());
    }

    [Benchmark]
    [ArgumentsSource(nameof(InputFiles))]
    public Pascal.SyntaxTree.Program CanonSharpParse(int index)
    {
        IEnumerable<LexicalToken> tokens = _scanner.Tokenize(new StringReadState(_inputFiles[index]));
        return _parser.Parse(tokens);
    }

    [Benchmark]
    [ArgumentsSource(nameof(InputFiles))]
    public ProgramStruct CanonParse(int index)
    {
        Lexer lexer = new();
        IEnumerable<SemanticToken> tokens = lexer.Tokenize(new StringSourceReader(_inputFiles[index]));

        return _grammarParser.Analyse(tokens);
    }

    public IEnumerable<object> InputFiles()
    {
        for (int i = 0; i < _inputFiles.Count; i++)
        {
            yield return i;
        }
    }
}

在编写测试程序中需要说明的是：在创建类的过程中，CanonSharp解析器的创建并没有计算在测试程序的运行时间中，但是Canon解析器的创建被计算在了测试程序的运行时间中。这是因为Canon解析器的词法分析器并不是一个无状态的解析器，不能重复的使用，只能在每次使用之前重新创建。

测试结果

在对原始数据进行数据处理之后我们绘制了如下的图。图中的横轴是输入测试文件的编号，图中的纵轴是CanonSharp解析器和Canon解析器运行时间的比值。从图中可以看出CanonSharp解析器的运行时间大约是Canon解析器运行时间的65到75倍，在某些极端的情况下可能会达到90倍。

结论

从相对的效率上说，使用解析器组合子编写的分析器在运行效率上大约要比使用表驱动的分析器慢上两个数量级；从绝对的运行时间上看，解析器组合子在面向一般长度的输入代码时运行的时间大约在毫秒量级。因此从Amdahl定律的角度和实际用户体验的角度出发，使用解析器组合子编写分析器不会导致最终的编译器在运行效率上的实际下降。同时，使用编译器组合子可以在保证代码高度可读性的条件下敏捷开发针对不同语言的编译器，在编写以教学和实验为目的的编译器中有着非常巨大的应用空间。

虽然在运行效率上，使用解析器组合子不会导致过多的担忧，但是从解析器组合子库的设计者角度出发，如何尽可能的提高解析器组合子库运行的效率并避免在运行时发生栈溢出错误都是重要的研究课题。

原始数据

原始数据中缺失的数据为对应测试运行失败。