haskell中的优先级爬升: parsec互递归错误

Question

我正在编写Haskell中的优先爬升算法，但是由于我不知道的原因，它不起作用。我认为Parsec状态信息在某个时候丢失了，但我甚至不知道这是错误的根源：

module PrecedenceClimbing where

import Text.Parsec
import Text.Parsec.Char

{-
Algorithm

compute_expr(min_prec):
  result = compute_atom()

  while cur token is a binary operator with precedence >= min_prec:
    prec, assoc = precedence and associativity of current token
    if assoc is left:
      next_min_prec = prec + 1
    else:
      next_min_prec = prec
    rhs = compute_expr(next_min_prec)
    result = compute operator(result, rhs)

  return result
-}

type Precedence = Int
data Associativity = LeftAssoc
                   | RightAssoc
                   deriving (Eq, Show)
data OperatorInfo = OPInfo Precedence Associativity (Int -> Int -> Int)

mkOperator :: Char -> OperatorInfo
mkOperator = \c -> case c of
                     '+' -> OPInfo 1 LeftAssoc  (+)
                     '-' -> OPInfo 1 LeftAssoc  (-)
                     '*' -> OPInfo 2 LeftAssoc  (*)
                     '/' -> OPInfo 2 LeftAssoc  div
                     '^' -> OPInfo 3 RightAssoc (^)

getPrecedence :: OperatorInfo -> Precedence
getPrecedence (OPInfo prec _ _) = prec

getAssoc :: OperatorInfo -> Associativity
getAssoc (OPInfo _ assoc _) = assoc

getFun :: OperatorInfo -> (Int -> Int -> Int)
getFun (OPInfo _ _ fun) = fun

number :: Parsec String () Int
number = do
  spaces
  fmap read $ many1 digit

operator :: Parsec String () OperatorInfo
operator = do
  spaces
  fmap mkOperator $ oneOf "+-*/^"

computeAtom = do
  spaces
  number

loop minPrec res = (do
  oper <- operator
  let prec = getPrecedence oper
  if prec >= minPrec
  then do
    let assoc = getAssoc oper
        next_min_prec = if assoc == LeftAssoc
                        then prec + 1
                        else prec
    rhs <- computeExpr(next_min_prec)
    loop minPrec $ getFun oper res rhs
  else return res) <|> (return res)

computeExpr :: Int -> Parsec String () Int
computeExpr minPrec = (do
  result <- computeAtom
  loop minPrec result) <|> (computeAtom)

getResult minPrec = parse (computeExpr minPrec) ""

由于某种原因，我的程序只是根据情况处理第一个操作或第一个操作数，但没有进一步处理。

GHCi会话：

*PrecedenceClimbing> getResult 1 "46+10"
Right 56
*PrecedenceClimbing> getResult 1 "46+10+1"
Right 56

Answer 1

我不清楚您的代码到底出了什么问题，但我将提供以下评论：

(1)这些陈述不等于：

Generic Imperative: rhs = compute_expr(next_min_prec)

Haskell:            rhs <- computeExpr(next_min_prec)

对compute_expr的命令式调用将始终返回。Haskell呼叫可能失败，在这种情况下，调用后的内容永远不会发生。

(2)您实际上是在利用Parsec的优势，一次一次地解析令牌。要了解具有各种先例和关联的运算符的一般解析表达式的"Parsec方式“，请查看：

• buildExpression
• Parsec和表达式打印

更新

我已经向http://lpaste.net/165651发布了一个解决方案