# Python tokenizer in Haskell + Parsec

I wrote a tokenizer/lexer (difference?) for Python in Haskell: this is my code on GitHub.

I already tested it out with some of CPython's standard library scripts, and it doesn't fail. However, it probably outputs non-conforming output. But I don't care about this right now.

What I'm looking for is a general (functional) style review. This is my first time using Parsec and Haskell for something relatively big, so I expect my functional style to be suboptimal.

Significant code snippets:

parseTokens :: LexemeParser [PositionedToken]
parseTokens = do
P.skipMany ignorable
tokens <- concat <$> P.many parseLogicalLine P.eof endIndents <- length . filter (>0) <$> getIndentLevels
dedents <- mapM position $replicate endIndents Dedent endMarker <- position EndMarker return (tokens ++ dedents ++ [endMarker]) parseIndentation :: LexemeParser [PositionedToken] parseIndentation = mapM position =<< go where go = do curr <- length <$> P.many (P.char ' ')
prev <- getIndentLevel
case curr compare prev of
EQ -> return []
GT -> return [Indent] <* pushIndentLevel curr
LT -> do
levels <- getIndentLevels
when (not $elem curr levels) (fail$ "indentation must be: " ++ show levels)
let (pop, levels') = span (> curr) levels
putIndentLevels levels'
return $replicate (length pop) Dedent parseLogicalLine :: LexemeParser [PositionedToken] parseLogicalLine = do P.skipMany ignorable indentation <- parseIndentation (indentation ++) <$> begin
where
begin = do
tokens <- P.many1 parsePositionedToken
let continue = (tokens ++) <$> begin implicitJoin <- (> 0) <$> getOpenBraces
if implicitJoin then do
whitespace
parseComment <|> (P.optional backslash *> eol)
P.skipMany ignorable
whitespace
continue
else do
whitespace
explicitJoin <- P.optionMaybe (backslash *> eol)
case explicitJoin of
Nothing   -> ((\t -> tokens ++ [t]) <\$> position NewLine) <* P.optional eol
otherwise -> whitespace *> continue


(I was largely inspired by PureScript's lexer, though I probably ended up with something a lot worse.)

# for comparison

Here are some other ways I've found to parse indentation sensitive language:

1. Use Text.Parsec.Indent Here is a blog post containing an example: (link)

2. Have a look at the language-python package. It's lexer is built using alex: (link)

3. Purescript handles indentation via the mark, checkIndentation, indented and same functions: (link) Grep the rest of the source code for these functions to see how they are used. Its lexer defines a Indent token (link) but from what I can tell it is never returned, i.e. see (link). The indentation level is kept track of by the parser (link) via the mark function.

# returning a list of tokens?

I'm not sure there is a lot of value in parsers which return [PositionedToken] except, perhaps, for testing purposes.

Most of the time you want to run a token parser incrementally, but parseTokens has to consume the entire file before it can return anything.

There should be a function which just returns the next token. This will come in handy in conjunction with the next comment I have...

# handling dedents at eof

I would find another way to handle implicit dedents at the end of the file. I'm sure this can be handled at the grammar level. The code to add them is extremely messy - don't you agree?

Have a look at how the language-python package does it:

https://github.com/bjpop/language-python/blob/master/src/Language/Python/Version2/Parser/Lexer.x#L229-L242

The function lexToken returns just a single token. The lexer has state, so when it reaches EOF it checks the current indentation level. If the indentation level is > 1, it decrements it and returns a dedentToken. Otherwise it returns an EOF token.