CODEWITHSUNDEEP
haskellparsec
sai
sai

Reputation: 55

Parsing arithmetic expression with Haskell Parsec

I'm writing a arithmetic parser to treat expressions like "1+2-3". I use this blog post as reference. To treat left associativity and precedence, I write a parser with Parsec according to this BNF (from blog post).

<exp> ::= <term> { ("+" | "-") <term> }
<term> ::= <factor> { ("*" | "/") <factor> }
<factor> ::= "(" <exp> ")" | <unary_op> <factor> | <int>

This is my parser code.

parseExp :: Parser Exp
parseExp = do
  t1 <- parseTerm
  loop t1
  where termSuffix t1 = do
          op <- lexeme $ oneOf "+-"
          t2 <- parseTerm
          case op of
            '+' -> termSuffix (Binary Plus t1 t2)
            '-' -> termSuffix (Binary Minus t1 t2)
        loop t = termSuffix t <|> return t

parseTerm :: Parser Exp
parseTerm = do
  f1 <- parseFactor
  loop f1
  where factorSuffix f1 = do
          op <- lexeme $ oneOf "*/"
          f2 <- parseFactor
          case op of
            '*' -> factorSuffix (Binary Mul f1 f2)
            '/' -> factorSuffix (Binary Div f1 f2)
        loop t = factorSuffix t <|> return t

parseFactor :: Parser Exp
parseFactor = parseConst <|> parseParen <|> parseUnary

parseParen = do
  void $ lexeme $ char '('
  e <- parseExp
  void $ lexeme $ char ')'
  return e

parseUnary :: Parser Exp
parseUnary = do
  op <- lexeme $ oneOf "!~-"
  f <- parseFactor
  case op of
    '!' -> return $ Unary LogNeg f
    '~' -> return $ Unary BitCompl f
    '-' -> return $ Unary ArithNeg f

parseConst :: Parser Exp
parseConst = do
  i <- many1 digit
  return (Const $ read i)

I also used this tutorial code as reference. tutorial

simpleExpr7 :: Parser SimpleExpr
simpleExpr7 = do
    -- first parse a term
    e <- term7
    -- then see if it is followed by an '+ expr' suffix
    maybeAddSuffix e
  where
    -- this function takes an expression, and parses a
    -- '+ expr' suffix, returning an Add expression
    -- it recursively calls itself via the maybeAddSuffix function
    addSuffix e0 = do
        void $ lexeme $ char '+'
        e1 <- term7
        maybeAddSuffix (Add e0 e1)
    -- this is the wrapper for addSuffix, which adapts it so that if
    -- addSuffix fails, it returns just the original expression
    maybeAddSuffix e = addSuffix e <|> return e

My code doesn't work. This code works like this.

*Main CodeGen Parser> parseWithEof parseExp "-2"
Right (Unary ArithNeg (Const 2))
*Main CodeGen Parser> parseWithEof parseExp "(2)"
Right (Const 2)
*Main CodeGen Parser> parseWithEof parseExp "-!(((2)))"
Right (Unary ArithNeg (Unary LogNeg (Const 2)))
*Main CodeGen Parser> parseWithEof parseExp "1+2"
Left (line 1, column 4):
unexpected end of input
expecting digit
*Main CodeGen Parser> parseWithEof parseExp "1+2+3"
Left (line 1, column 6):
unexpected end of input
expecting digit
*Main CodeGen Parser> parseWithEof parseExp "1+2*3"
Left (line 1, column 6):
unexpected end of input
expecting digit

I can't understand why this results unexpected end of input.

Upvotes: 2

Views: 2362

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 50819

Consider parsing 1+2. In parseExp this parses 1 into t1 = Const 1 and then enters the loop loop (Const 1). The loop tries the first alternative termSuffix (Const 1) which succesfully parses the operator +, the next term t2 = Const 2, and then loops back into termSuffix (Binary Plus (Const 1) (Const 2)) which expects either a + or -. The parse fails. Instead of looping back into termSuffix, you should loop back into loop to allow a single term after the first +:

parseExp :: Parser Exp
parseExp = do
  t1 <- parseTerm
  loop t1
  where termSuffix t1 = do
          op <- lexeme $ oneOf "+-"
          t2 <- parseTerm
          case op of
            -- *** use `loop` here, not `termSuffix` ***
            '+' -> loop (Binary Plus t1 t2)
            '-' -> loop (Binary Minus t1 t2)
        loop t = termSuffix t <|> return t

After making a similar change to parseTerm, your test cases all work fine.

Upvotes: 3

Related Questions