为何Idris 2 Text.Parser实现的表达式解析器随规则数增加性能劣化严重？

核心根因 #

你实现的表达式解析器在同一优先级运算符的选择逻辑上存在设计缺陷，直接导致了超线性的性能开销：

• 同一优先级下的每个运算符解析分支，都会先独立完整解析一次factor：你当前的level函数用choiceMap toP ops遍历所有运算符，每个toP生成的Infix解析分支第一步都是执行x <- factor。如果该分支后续匹配运算符失败，会触发回溯，下一个运算符分支又会重新解析一次factor。
• 递归解析放大了重复开销：你的term定义中包含parens expr，会递归调用整个表达式解析器，导致每次重复解析factor的代价本身就很高，最终整体耗时随运算符数量呈近似立方级增长，和你测试的耗时趋势完全匹配。

其他加剧开销的因素 #

• 缺少运算符前置预判：你没有先匹配运算符再关联前后操作数，而是先解析操作数再匹配运算符，大幅增加了无效回溯的开销。
• Idris 2的Text.Parser默认全回溯特性：备选分支失败时会完整回滚所有已消耗的输入状态，进一步放大了重复解析的性能损失。

修复建议 #

调整优先级层的解析逻辑，保证同一优先级下factor仅解析一次，再集中尝试匹配所有可能的运算符：

level : Grammar state k True a -> List (Op state k a) -> Grammar state k True a
level factor ops = do
  -- 仅解析一次左侧操作数
  first <- factor
  -- 尝试匹配任意当前优先级运算符和后续操作数
  applyOps first
  where
    applyOps : a -> Grammar state k True a
    applyOps lhs = choice (map opToCont ops) <|> pure lhs
      where
        opToCont : Op state k a -> Grammar state k True a
        opToCont (Infix op AssocLeft) = do
          f <- op
          rhs <- factor
          applyOps (f lhs rhs)
        opToCont (Infix op AssocRight) = do
          f <- op
          rhs <- level factor ops
          pure (f lhs rhs)
        opToCont (Infix op AssocNone) = do
          f <- op
          rhs <- factor
          pure (f lhs rhs)
        opToCont (Prefix op) = op <*> factor

内容的提问来源于stack exchange，提问作者Cactus