Vorrang Klettern in Haskell: Parsec gegenseitige Rekursionsfehler

Question

Ich programmiere die Priorität Klettern Algorithmus in Haskell, aber aus einem mir unbekannten Grund, funktioniert nicht. Ich denke, dass Parsec Zustand Info irgendwann verloren, aber ich weiß nicht einmal, dass die Quelle des Fehlers ist:

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) "" 

Mein Programm aus irgendeinem Grunde nur verarbeitet die erste Operation oder der erste Operand abhängig auf den Fall, geht aber nicht weiter

GHCi Sitzung:

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

Answer 1

ich nicht sicher, genau bin, was mit Ihrem Code falsch ist, aber ich werde diese Kommentare bieten:

(1) Diese Aussagen sind nicht gleichwertig:

Generic Imperative: rhs = compute_expr(next_min_prec) 

Haskell:   rhs <- computeExpr(next_min_prec) 

Der Imperativ Aufruf compute_expr wird immer Rückkehr. Der Haskell-Aufruf kann fehlschlagen. In diesem Fall werden die dem Aufruf folgenden Schritte nicht ausgeführt.

(2) Sie arbeiten wirklich gegen Parsec's Stärken, indem Sie versuchen, Token nacheinander einzeln zu analysieren. Um die "Parsec way" von allgemein Parsing Ausdrücke mit Operatoren verschiedenen Präzedenzfälle und Assoziativitäten zu sehen, haben Sie einen Blick auf:

• buildExpression
• Parsec and Expression Printing

aktualisiert

I‘ ve gepostet eine Lösung zu http://lpaste.net/165651