Mixfix解析器Bug：右结合中缀运算符解析失败排查

核心原因分析 #

你遇到的问题本质是右结合运算符的解析逻辑与左/非结合混淆，具体出在两个关键环节：

1. 用Topograph生成优先级解析器时，没有为右结合运算符生成右递归的解析结构，而是套用了左结合的左递归逻辑；
2. Megaparsec组合子误用：把右结合运算符交给chainl处理，而非专用的chainr，导致解析完左 operand 后直接终止，不再处理右侧的运算符和 operand。

具体修复方案 #

1. 区分结合性选择Megaparsec组合子 #

Megaparsec的chainl是为左结合运算设计的左递归折叠逻辑，右结合必须使用chainr来实现右递归折叠：

-- 左结合运算解析器（用于_+_）
parseLeftInfix :: Parser Expr -> Parser (Expr -> Expr -> Expr) -> Parser Expr
parseLeftInfix term op = chainl term op

-- 右结合运算解析器（用于_&_）
parseRightInfix :: Parser Expr -> Parser (Expr -> Expr -> Expr) -> Parser Expr
parseRightInfix term op = chainr term op

-- 非结合运算解析器（用于_=_）
parseNonAssocInfix :: Parser Expr -> Parser (Expr -> Expr -> Expr) -> Parser Expr
parseNonAssocInfix term op = do
  x <- term
  option x $ do
    f <- op
    y <- term
    return $ f x y

2. 基于Topograph的优先级DAG绑定对应解析器 #

在利用Topograph生成优先级层级解析器时，需要根据运算符的结合性，给每个优先级层级绑定对应的组合子：

• 对右结合的_&_，使用parseRightInfix，传入下一个更高优先级的解析器作为term参数；
• 对左结合的_+_，使用parseLeftInfix；
• 对非结合的_=_，使用parseNonAssocInfix。

示例绑定逻辑：

buildParser :: TopoGraph Op -> Parser Expr
buildParser graph = foldr buildLevel parsePrimaryExpr (topoSort graph)
  where
    buildLevel :: OpLevel -> Parser Expr -> Parser Expr
    buildLevel level nextParser =
      case levelAssoc level of
        LeftAssoc -> parseLeftInfix nextParser (parseOp level)
        RightAssoc -> parseRightInfix nextParser (parseOp level)
        NonAssoc -> parseNonAssocInfix nextParser (parseOp level)
    parseOp :: OpLevel -> Parser (Expr -> Expr -> Expr)
    parseOp level = choice [symbol op >> return (mkOp op) | op <- levelOps level]

3. 确保右递归的解析边界 #

如果手动实现右结合运算符的解析逻辑，要注意调用自身而非下一级解析器，保证右侧可以递归解析相同优先级的右结合运算：

-- 手动实现_&_的右递归解析（替代chainr的写法）
parseAnd :: Parser Expr
parseAnd = do
  left <- parseAddExpr -- 调用更高优先级的解析器
  optional (do
    symbol "&"
    right <- parseAnd -- 右递归，允许右侧继续解析&运算
    return (\x -> And x right)) >>= \case
    Just f -> return $ f left
    Nothing -> return left

验证测试 #

修复后执行以下测试验证效果：

1. 输入true & false应解析为And True False；
2. 输入true & false & true应解析为And True (And False True)（符合右结合的嵌套逻辑）；
3. 混合优先级输入true & 1 + 2应解析为And True (Add (Lit 1) (Lit 2))（如果_+_优先级高于_&_）。

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