为何Megaparsec中some与many组合会引发无限递归？

问题场景 #

你在GHCI中执行了以下代码：

ghci> :m +Text.Megaparsec
ghci> :m +Data.Void 
ghci> :m +System.Timeout
ghci> :m +Text.Megaparsec.Char
ghci> timeout (15*10^(6::Int)) $ parseTest (some (many digitChar :: Parsec Void String String)) ""
Nothing

该操作导致系统崩溃，只能通过C-c终止，你想知道如何在编写解析器时检测这类问题。

问题本质 #

你的案例并非传统意义上的左递归，但属于无进展的无限循环：many digitChar在空输入时会返回空列表，而some要求至少匹配一个结果，因此解析器会不断重复尝试many digitChar，每次都不消耗输入，陷入死循环，最终耗尽系统资源。

检测与避免方法 #

一、静态分析工具 #

• 使用hlint：这款工具能识别解析器的常见反模式，比如some (many p)这种无意义的组合，会直接给出优化建议。
• 自定义静态检查：针对左递归场景，直接左递归（如p = p >> q）或间接左递归（如p = q >> r; q = p >> s），可以通过遍历解析器的依赖结构，检查是否存在循环依赖。

二、动态调试技巧 #

• 添加解析日志：使用Megaparsec的Text.Megaparsec.Debug模块中的debug组合子，打印每次解析的尝试内容和输入消耗状态，能快速发现解析器是否在重复相同的无进展操作。示例：

  parseTest (some (debug "many-digit" (many digitChar))) ""
  

• 限制解析步数：自定义一个步数限制组合子，每执行一步解析就减少计数，达到阈值时终止解析，避免无限循环：

  import Control.Monad.State
  
  stepLimit :: Int -> Parsec e s a -> Parsec e s a
  stepLimit n p = do
    remaining <- getState
    if remaining <= 0
      then fail "Exceeded step limit"
      else putState (remaining - 1) >> p
  

  使用时将解析器包裹进去：parseTest (stepLimit 1000 (some (many digitChar))) ""

三、遵循解析器设计规范 #

• 避免无意义的组合：some和many的语义要理清，some p要求p至少成功一次，而many p允许0次成功，因此some (many p)在空输入或p无法匹配时必然陷入循环。如果要匹配1个以上的数字，直接用some digitChar（或many1 digitChar）即可。
• 左递归处理：Megaparsec不支持左递归解析器，遇到左递归结构时，需要改写为右递归或使用chainl等专门的组合子处理表达式解析。

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