Parsing in Haskell for a simple interpreter

Question

I'm relatively new to Haskell with main programming background coming from OO languages. I am trying to write an interpreter with a parser for a simple programming language. So far I have the interpreter at a state which I am reasonably happy with, but am struggling slightly with the parser.

Here is the piece of code which I am having problems with

data IntExp
 = IVar Var
 | ICon Int
 | Add IntExp IntExp
 deriving (Read, Show)

whitespace = many1 (char ' ')

parseICon :: Parser IntExp
parseICon =
  do x <- many (digit)
     return (ICon (read x :: Int))

parseIVar :: Parser IntExp
parseIVar = 
  do x <- many (letter)
     prime <- string "'" <|> string ""
     return (IVar (x ++ prime))

parseIntExp :: Parser IntExp
parseIntExp =
  do x <- try(parseICon)<|>try(parseIVar)<|>parseAdd
     return x

parseAdd :: Parser IntExp
parseAdd =
  do x <- parseIntExp   
     whitespace
     string "+"
     whitespace
     y <- parseIntExp
     return (Add x y)

runP :: Show a => Parser a -> String -> IO ()
runP p input
  = case parse p "" input of
      Left err ->
        do putStr "parse error at "
           print err
      Right x -> print x

The language is slightly more complex, but this is enough to show my problem.

So in the type IntExp ICon is a constant and IVar is a variable, but now onto the problem. This for example runs successfully

runP parseAdd "5 + 5"

which gives (Add (ICon 5) (ICon 5)), which is the expected result. The problem arises when using IVars rather than ICons eg

runP parseAdd "n + m"

This causes the program to error out saying there was an unexpected "n" where a digit was expected. This leads me to believe that parseIntExp isn't working as I intended. My intention was that it will try to parse an ICon, if that fails then try to parse an IVar and so on.

So I either think the problem exists in parseIntExp, or that I am missing something in parseIVar and parseICon.

I hope I've given enough info about my problem and I was clear enough.

Thanks for any help you can give me!

Answer 1

Your problem is actually in parseICon:

parseICon =
  do x <- many (digit)
     return (ICon (read x :: Int))

The many combinator matches zero or more occurrences, so it's succeeding on "m" by matching zero digits, then probably dying when read fails.

---

And while I'm at it, since you're new to Haskell, here's some unsolicited advice:

• Don't use spurious parentheses. many (digit) should just be many digit. Parentheses here just group things, they're not necessary for function application.

• You don't need to do ICon (read x :: Int). The data constructor ICon can only take an Int, so the compiler can figure out what you meant on its own.

• You don't need try around the first two options in parseIntExp as it stands--there's no input that would result in either one consuming some input before failing. They'll either fail immediately (which doesn't need try) or they'll succeed after matching a single character.

• It's usually a better idea to tokenize first before parsing. Dealing with whitespace at the same time as syntax is a headache.

• It's common in Haskell to use the ($) operator to avoid parentheses. It's just function application, but with very low precedence, so that something like many1 (char ' ') can be written many1 $ char ' '.

Also, doing this sort of thing is redundant and unnecessary:

parseICon :: Parser IntExp
parseICon =
  do x <- many digit
     return (ICon (read x))

When all you're doing is applying a regular function to the result of a parser, you can just use fmap:

parseICon :: Parser IntExp
parseICon = fmap (ICon . read) (many digit)

They're the exact same thing. You can make things look even nicer if you import the Control.Applicative module, which gives you an operator version of fmap, called (<$>), as well as another operator (<*>) that lets you do the same thing with functions of multiple arguments. There's also operators (<*) and (*>) that discard the right or left values, respectively, which in this case lets you parse something while discarding the result, e.g., whitespace and such.

Here's a lightly modified version of your code with some of the above suggestions applied and some other minor stylistic tweaks:

whitespace = many1 $ char ' '

parseICon :: Parser IntExp
parseICon = ICon . read <$> many1 digit

parseIVar :: Parser IntExp
parseIVar = IVar <$> parseVarName

parseVarName :: Parser String
parseVarName = (++) <$> many1 letter <*> parsePrime

parsePrime :: Parser String
parsePrime = option "" $ string "'"

parseIntExp :: Parser IntExp
parseIntExp = parseICon <|> parseIVar <|> parseAdd

parsePlusWithSpaces :: Parser ()
parsePlusWithSpaces = whitespace *> string "+" *> whitespace *> pure ()

parseAdd :: Parser IntExp
parseAdd = Add <$> parseIntExp <* parsePlusWithSpaces <*> parseIntExp

Answer 2

I'm also new to Haskell, just wondering:

will parseIntExp ever make it to parseAdd?

It seems like ICon or IVar will always get parsed before reaching 'parseAdd'.

e.g. runP parseIntExp "3 + m"

would try parseICon, and succeed, giving

(ICon 3) instead of (Add (ICon 3) (IVar m))

Sorry if I'm being stupid here, I'm just unsure.