haskell 中的优先级攀升：秒差距相互递归错误

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 的命令式调用将始终 return。 Haskell 调用可能会失败，在这种情况下，调用之后的内容永远不会发生。

(2) 通过尝试按顺序一次一个地解析标记，您实际上是在对抗 Parsec 的优势。要查看具有各种优先级和关联性的运算符的一般解析表达式的 "Parsec way"，请查看：

更新

我已经发布了 http://lpaste.net/165651

的解决方案

haskell 中的优先级攀升：秒差距相互递归错误

precedence climbing in haskell: parsec mutual recursion error

parsing

haskell

parsec

mutual-recursion