Parsing a series of lambda calculus terms

user_10218833 0
Viewed 160

I am writing a lambda calculus parser in Haskell and I can't find a solution to fix its current problem.

How I parse expressions:

expr :: Parser LamExpr
expr = do terms <- some $ token term
          return $ foldl1 LamApp terms

How I parse terms:

term :: Parser LamExpr
term = do symbol "("
          e     <- expr
          symbol ")"
          return e

   <|> do symbol "\\"
          x     <- var
          symbol "->"
          e     <- expr
          return $ LamAbs x e

   <|> do {x <- var; return $ LamVar x}

   <|> do {name <- macroName; return $ LamMacro name}

On input "x1 x2) x3" my parser returns

LamApp (LamVar 1) (LamVar 2)

Parsing should fail as it is syntactically incorrect, but it still parses the first application. I think this is because of do terms <- some $ token term which will parse as much as it can due to some.

How can I fix this so that the whole parsing fails instead of one section?

lambda-calculus parsing haskell
1 Answers

I assume you are using some parsec variant. You just have to add an eof to the end of your parser.

parseInput = do
    e <- expr
    eof
    pure e  -- (*)

Or for short using a Control.Applicative combinator:

parseInput = expr <* eof

(*) btw the community is starting to use pure instead of return these days

user_337960
Related