Haskell用组合子实现表达式求值时同优先级运算符解析失败如何解决

问题根源 #

你当前的语法规则只支持「单份高优先级表达式 + 运算符 + 单份高优先级表达式」的二元结构，无法处理同优先级的链式运算。如果直接把add_sub的左操作数设为add_sub会触发无限左递归：解析add_sub的第一步就会再次调用add_sub，没有任何输入消耗就进入死循环。

解决方案 #

消除左递归，改为「先解析第一个高优先级项，再反复匹配「运算符+高优先级项」的序列，最后按结合性折叠成AST」的结构，加减乘除是左结合，幂运算默认是右结合。

首先你需要先实现两个通用解析组合子：

-- 反复运行解析器直到失败，返回所有成功解析的结果列表
many :: Parser i a -> Parser i [a]
many p = (do x <- p; xs <- many p; pure (x:xs)) <|> pure []

-- 尝试运行解析器，成功返回Just结果，失败返回Nothing
optional :: Parser i a -> Parser i (Maybe a)
optional p = (Just <$> p) <|> pure Nothing

然后修改各优先级的解析规则：

expr :: Parser Char Expr
expr = add_sub
  where
    -- 加减：左结合
    add_sub = do
      first <- mul_div
      opPairs <- many $ (,) 
        <$> (parseChar '+' *> pure Add <|> parseChar '-' *> pure Sub)
        <*> mul_div
      pure $ foldl (\acc (op, rhs) -> Op op acc rhs) first opPairs

    -- 乘除：左结合
    mul_div = do
      first <- pow
      opPairs <- many $ (,)
        <$> (parseChar '*' *> pure Mul <|> parseChar '/' *> pure Div)
        <*> pow
      pure $ foldl (\acc (op, rhs) -> Op op acc rhs) first opPairs

    -- 幂运算：右结合
    pow = do
      first <- factor
      mbOpRhs <- optional $ (,) <$> parseChar '^' *> pure Pow <*> pow
      case mbOpRhs of
        Nothing -> first
        Just (op, rhs) -> Op op first rhs

    -- 原有基础规则不变
    factor  =  parens  <|>  val
    val     =  Val  <$>  parseDouble
    parens  =  parseChar '('  *>  expr  <*  parseChar ')'

原理解释 #

• 不会触发无限递归：每个优先级规则的第一步都是解析更高优先级的表达式（比如add_sub第一步先跑mul_div），一定会消耗输入，不会出现无输入消耗的递归调用。
• 链式运算支持：many会把同优先级的所有后续运算符和操作数都收集起来，左结合折叠的结果完全符合1+1-1 = (1+1)-1的常规运算语义，幂运算的右结合处理也符合2^3^2 = 2^(3^2)的数学规则。

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