Search code examples
parsinghaskellschemeparsec

Parsing scheme dottedlist/list with Haskell


I am following this guide on writing a scheme interpreter. In trying to left-factor the grammar for DottedList/List, I came up with this:

E -> (H T)
H -> E H'
H' -> <space> H
H' -> <term>
T ->  <term>
T -> <space> . <space> E

--

spaces :: Parser ()
spaces = skipMany1 (space <?> "spaces")

parseExpr :: Parser LispVal
parseExpr = (... omitted ...) <|>
             do char '('
                h <- sepBy parseExpr spaces
                t <- optionMaybe ((spaces' >> char '.' >> spaces' >> parseExpr)  <?> "parseDotExpr failed")
                z <- if isJust t then return $ DottedSuffix $ fromJust t else return Tail
                z' <- case z of Tail           -> return $ List x
                                DottedSuffix s -> return $ DottedList x s
                char ')'
                return z'

Unfortunately this doesn't handle the basic dottedlists:

test/Spec.hs:23: 
1) test eval 1 evals DottedList
     expected: "(1 2 . 1)"
      but got: "Parse error at \"lisp\" (line 1, column 7):\nunexpected \".\"\nexpecting spaces' or parseExpr!"

test/Spec.hs:26: 
2) test eval 1 evals DottedList (quoted)
     expected: "((1 2) . 1)"
      but got: "Parse error at \"lisp\" (line 1, column 15):\nunexpected \".\"\nexpecting spaces' or parseExpr!"

test/Spec.hs:29: 
3) test eval 1 evals DottedList (sugared)
     expected: "((1 2) . 1)"
      but got: "Parse error at \"lisp\" (line 1, column 9):\nunexpected \".\"\nexpecting spaces' or parseExpr!"

Update: From @pat's response, I got my tests to pass using:

parseExpr :: Parser LispVal
parseExpr = {- omitted -}
         <|> do char '('
                x <- many1 (do e <- parseExpr; spaces'; return e)
               {- omitted -}

Solution

  • The sepBy parser is seeing the space before the dot, and committing to parse another expression, which fails.

    You should have lexemes consume and discard trailing spaces (see parsec's lexeme) and change the sepBy to just many1. The optionMaybe can then commit after seeing a dot, which would otherwise have required a try.