如何用解析器组合子解析一元表达式？Haskell实现求助

Dhall的makeOperator函数用于处理同一优先级、左结合的二元操作符，核心逻辑分为三步：

1. 解析初始左值：先调用parseValue解析表达式的最左单元（通常是更高优先级的表达式，比如字面量、括号表达式或一元表达式），得到初始左值l0。
2. 收集操作符与右值组合：用many匹配零个或多个「空白+操作符+空白+右值」的片段，每一段都会生成一个函数——接受一个左表达式，返回将该左值、当前操作符、右值组合后的BinaryOperation。
3. 左结合折叠：用foldl将这些函数依次作用在l0上，实现左结合逻辑。比如a + b + c会被解析为((a + b) + c)，符合多数二元操作的求值顺序。

这个设计的关键前提是：parseValue必须是更高优先级的解析器，确保先处理括号、一元操作等，再处理当前优先级的二元操作。

你的makeOperatorUnary存在两个核心问题：

• 强制要求输入中存在一元操作符，无法兼容没有一元操作的普通表达式。
• 未融入优先级解析体系，单独使用时会抢占输入，导致后续二元解析器无法处理剩余内容。

正确的一元解析实现 #

一元操作符是前缀可选的（支持多个连续前缀，比如--x或++x），应作为更高优先级的解析器包裹基础表达式，再传给二元解析器使用：

makeOperatorUnary :: Parser Operator -> Parser Expression -> Parser Expression
makeOperatorUnary parseOperator parseValue = do
  -- 匹配零个或多个前缀一元操作符
  operators <- many parseOperator
  -- 解析基础表达式单元
  coreExpr <- parseValue
  -- 从右往左折叠：多个一元操作符是右结合的（如--x等价于-(-x)）
  pure $ foldr (\op expr -> UnaryOperation op expr) coreExpr operators

整合优先级解析链 #

要解决+2 + 2的解析问题，需要构建分层的解析器链：

1. 基础解析器：解析字面量、括号表达式等最基础的单元（示例如下）。
2. 一元解析器：用makeOperatorUnary包裹基础解析器，处理前缀一元操作。
3. 二元解析器：用makeOperator包裹一元解析器，处理二元操作。

示例代码结构：

-- 假设Expression新增Literal构造器用于数字字面量
data Expression
  = BinaryOperation Expression Operator Expression
  | UnaryOperation Operator Expression
  | Literal Integer
  deriving (Show, Eq)

-- 基础表达式解析器：解析整数字面量
parsePrimary :: Parser Expression
parsePrimary = do
  num <- integer  -- 假设integer是解析整数的Parser
  pure $ Literal num

-- 一元操作符解析器：解析+/-
parseUnaryOp :: Parser Operator
parseUnaryOp = (char '+' >> pure Plus) <|> (char '-' >> pure Minus)

-- 一元表达式解析器
parseUnary :: Parser Expression
parseUnary = makeOperatorUnary parseUnaryOp parsePrimary

-- 二元操作符解析器：解析+/-
parseBinaryOp :: Parser Operator
parseBinaryOp = (char '+' >> pure Plus) <|> (char '-' >> pure Minus)

-- 顶层表达式解析器
parseExpression :: Parser Expression
parseExpression = makeOperator parseBinaryOp parseUnary

这样解析+2 + 2时：

1. parseUnary先解析+2，得到UnaryOperation Plus (Literal 2)。
2. makeOperator继续解析后续的+ 2，将其组合为BinaryOperation (UnaryOperation Plus (Literal 2)) Plus (Literal 2)，完整处理整个输入。

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