0

我在 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
4

1 回答 1

1

我不确定您的代码到底有什么问题，但我会提供以下评论：

(1)这些陈述不等同：

Generic Imperative: rhs = compute_expr(next_min_prec)

Haskell:            rhs <- computeExpr(next_min_prec)

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

(2)通过尝试按顺序一次解析一个令牌，您确实在对抗 Parsec 的优势。要查看使用各种优先级和关联性的运算符进行通用解析表达式的“Parsec 方式”，请查看：

更新

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

于 2016-06-07T15:47:30.433 回答