Parsec hanging when using buildExpressionParser

I’m trying to create a basic parser for math equations using Parsec, and I’m having some trouble using the buildExpressionParser function.

I’ve created a parsecParse function, but it just hangs forever when I call it in ghci: parse parsecParse "" "200*6". I can’t figure out why. Any ideas?

module Equation where

import Control.Applicative hiding (many, (<|>))

import Text.Parsec.Char (char, digit)
import Text.Parsec.Combinator (many1, option)
import Text.Parsec.Expr (Assoc (..), Operator (..), buildExpressionParser)
import Text.Parsec.Prim ((<|>), try)
import Text.Parsec.String (Parser)

data Equation = Leaf Double | Tree Op Equation Equation deriving (Show)
data Op = Plus | Minus | Multiply | Divide deriving (Show)

parsecParse :: Parser Equation
parsecParse = try parseOperator <|> parseDouble

parseDouble :: Parser Equation
parseDouble = fmap (Leaf . read) $ (++) <$> integer <*> fraction
    where integer  = many1 digit
          fraction = option "" $ (:) <$> char '.' <*> many1 digit

parseOperator :: Parser Equation
parseOperator = buildExpressionParser table parsecParse
    where table     = [[ getOp '*' Multiply, getOp '/' Divide ],
                       [ getOp '+' Plus,     getOp '-' Minus ]]
          getOp c o = Infix (char c >> return (Tree o)) AssocLeft

Solution

You are getting problems because parseOperator is recursing back on itself in leftmost position, something which Parsec cannot handle directly, and which gives an infinite recursion.

The last argument to buildExpressionParser should be a parser that parses more "basic" elements.

It is fine to recurse indirectly on parseOperator, e.g. to handle parenthesized elements, but not such that it ends up in the leftmost position of itself.