A Lexer for Haskell in Haskell

Introduction#introduction

One would have hoped that these days, the syntax is the least controversial part of a programming language specification, and that implementing a parser for the language would be a routine job, something that is not worth writing a scientific paper about. However, as witnessed by many lengthy discussions on the Haskell mailing list, this does not appear to be true for Haskell. The syntax is complex, and the specification in the Haskell report leaves room for many questions.

In spite of the complexities of the Haskell syntax, it appears that solving the problem of parsing Haskell has not been seen as prestigious enough that someone has been willing to invest the time to do it well.

Being inspired by Typing Haskell in Haskell [jones99typing], it seems like a good idea to work toward Parsing Haskell in Haskell, i.e., building an executable specification of the Haskell syntax. In this paper, we give a first contribution toward that goal by creating

• A Lexer for Haskell in Haskell that is simple, correct, efficient and reusable.

The goals are not independent: simplicity is likely to be good both for correctness and re-usability. In fact, because the specification isn't formal, we cannot expect a formal proof of correctness, but instead rely on simplicity to convince ourselves that the implementation is correct.

Method#mehod

Most of the work was done during a warm and sunny summer week in 1999. The final parts, nested comments and layout processing, were added in 2001.

The goal was to use the (original) Haskell 98 Report [haskell98] as the only source of information, preferably restricting attention to Appendix B, the syntax reference. The author tried to forget everything (he thought) he already knew about Haskell.

Appendix B consists of some segments of pseudo-formal notation, glued together and clarified by informal text. Unfortunately, the description of the lexical syntax did not appear to be self-contained. For example, it was necessary to consult Chapter 2, where one was referred to (the wrong section of) Chapter 5, to find a confirmation that qualified names are part of the lexical syntax (i.e., that spaces are not allowed in M.x).

Coincidentally, these problems appear to be fixed in the revised Haskell 98 report [haskell98revised], and some confusing formulations have been removed.

Existing solutions#existing

We have taken a very quick look at the Haskell lexers summarized in Table existinglexers. In all cases, the lexer is handwritten, essentially as a large monolithic chunk of code, without much separation of concerns.

As a result, it would presumably be difficult to verify the correctness of these lexers, and it has probably been difficult to adapt them to new versions of Haskell (1.2, 1.3, 1.4, 98, revised 98...) without introducing bugs. Only one of the goals stated in the introduction is achieved: efficiency.

Monolithic solutions are complex because of the many non-trivial subtasks involved:

• removing nested comments, preserving position information, interacting with the parser to implement the layout rule, recognizing string literals, recognizing simple identifiers, recognizing qualified identifiers, recognizing keywords and reserved operators. ...

One tempting approach to deal with the complexity of a Haskell lexer is of course to split the lexer into a number of simpler passes. At first sight, it may seem possible to implement many of the subtasks mentioned above separately, but it turns out not to be so easy. We give a few examples below.

Hopeless attempts#hopeless

Nested comments It seems easy to define a function to recognize nested comments; they are enclosed in {- -} brackets and have to be properly nested. However, doing this as a preprocessing pass, separately from the rest of the lexical analysis, seems impossible, because {- and -} do not always start and end comments:

code -- comment -} comment
code -- comment {- comment -} comment
code ----> code {- comment -} code
code "{-" code "-}" code
code " \"{-" code

Qualified names At first it may seem that recognition of qualified names could be added as a post-processing step to a lexer that only recognizes simple names by simply gluing tokens together. However, in Haskell, a qualified name M.x is treated as one lexical symbol, and extra space is not allowed before or after the dot, so it seems difficult to get the post-processing right if the simple lexer discards white space. Even if white space is preserved, there are some additional pitfalls with a post-processing solution. For example, a simple lexer would presumably treat M.. as two tokens: M followed by the reserved operator ... With qualified names, it should be treated as the operator . qualified by M. This could be handled as a special case, but then the post-processor solution does not seem like a particularly elegant solution anymore.

Keywords Keywords is another candidate for recognition in a post-processor. But keywords interact with qualified names, for example while M.them is a qualified name, M.then is three tokens, the last one being the keyword then.

A better solution#better

To achieve our goals of simplicity and correctness, it seems like a good idea to structure the implementation of the lexer according to the structure of the specification given in Appendix B of the Haskell 98 report (Chapter 9 in the revised report).

Appendix B of the Haskell report contains the following lexer related parts:

• B.2 The lexical syntax: this is a BNF-like description of what a Haskell program looks like on the lexical level.
• B.3 Layout: this section discusses several relevant issues:
  • How to compute the indentation of a lexeme,
  • How to insert the additional tokens <n> and {n} to indicate layout.
  • Layout contexts and the function L that implements the layout rule.

The lexical syntax#lexicalsyntax

From the lexical syntax in Appendix B.2, we construct a token recognizing function called haskellLex,

haskellLex :: String -> [(Token,String)]

The output is a list of tokens, represented as pairs of values from the type Token that classifies tokens (see Figure HsTokens),

module HsTokens where

-- Haskell token classifications:
data Token = Varid | Conid | Varsym | Consym
           | Reservedid | Reservedop | Specialid
           | IntLit | FloatLit | CharLit | StringLit
           | Qvarid | Qconid | Qvarsym | Qconsym
           | Special | Whitespace

           | NestedCommentStart | NestedComment
           | Commentstart  -- dashes
           | Comment -- what follows the dashes

           | ErrorToken | GotEOF | TheRest

           -- Inserted during layout processing:
           | Layout     -- tags implicit braces
           | Indent Int -- <n>
           | Open Int   -- {n}
           deriving (Show,Eq,Ord)

In previous lexers for Haskell, this part is typically implemented as a handwritten function that in addition to recognizing tokens also computes positions and discards white space. By preserving white space, we can compute positions separately. This solution also allows the function haskellLex to be reused in applications where it is desirable to preserve white space.

While this separation of concerns makes haskellLex a much easier function to implement by hand, we have gone one step further: we have simply transliterated the lexical grammar, using a set of regular expression combinators, and automatically generated the function from the grammar using a regular expression compiler.

The transliterated lexical syntax is included in Appendix HaskellLexicalSyntax,

and the regular expression combinators are explained below. The application of the regular expression compiler to the Haskell lexical grammar is shown in Figure HsLexerGen. Notice that it is the nonterminal program that specifies what a Haskell program is on the lexical level, so that is the nonterminal from which we generate our token recognizing function.

While the generated function haskellLex is too big to be included here, it is available on-line [lhih-online] and Section compiler includes an example of what the regular expression compiler produces for a simpler regular expression.

import HaskellLexicalSyntax(program)
import LexerGen(lexerGen)

main = lexerGen "HsLex" "haskellLex" program

The regular expressions combinators are summarized in Table regexp. To specify output, our combinators include the combinator o, and the lexical grammar has been augmented to indicate what output to produce. So, the combinators do not specify pure regular expressions, but rather transducers, i.e., automata that

have both input and output transitions. This is a slight deviation from standard text book methods, where output is represented by final states rather than output transitions.

The Haskell report uses one nonstandard operation: difference r_1<r2>. It is used to exclude keywords from the productions for identifiers, and in other similar situations. Our combinators do not include the difference operator (It is sad that the Haskell report doesn't say where one can find a description of how to implement it.), and we have simply omitted such exclusions from the grammar. This introduces ambiguities in the grammar, resulting in an automaton that, e.g., after seeing the string then could output either a Varid token or a Reservedid token. The ambiguity is resolved by assigning precedences to token classes and choosing the token with the highest precedence. In the implementation, we use a derived Ord instance for the Token data type and put the constructors in the appropriate order.

There is another source of ambiguity in the lexical grammar, which is to be resolved by the ``maximal munch'' rule. This is implemented by giving priority to input over output in the generated token recognizing function (see Section compiler).

Apropos the ``maximal munch'' rule, the correct application of it is not without pitfalls, and it seems that Haskell 98 introduced an exeption to it: it no longer applies to one-line comments. For example, although the string --+xyz matches the nonterminal comment in the lexical grammar, it should be parsed as two shorter tokens, --+ followed by xyz. We implement this by treating one-line comments as two lexical units: the leading dashes, and the rest of the comment.

Computing source positions and removing white space#positions

The output from the token recognizing function haskellLex is fed to the function addPos, that adds source positions, and then to the function rmSpace that removes white space.

type Pos = (Int,Int) -- (row,column)
type PosToken = (Token,(Pos,String))

addPos    :: [(Token,String)] -> [PosToken]
rmSpace   :: [PosToken] -> [PosToken]

We compute both the horizontal and vertical position of every token. While this is more than we need to implement layout, accurate source positions are of course useful in error messages.

While the Haskell report specifies that tab stops are 8 characters apart, it does not say where the first tab stop is located. For the implementation of function addPos, we have, in apparent agreement with other Haskell implementations, assumed that the first tab stop is located in column 1.

Adding layout indicator tokens#layoutpre

The layout indicating tokens <n> and {n} are added by the separate function layoutPre,

layoutPre :: [PosToken] -> [PosToken]

Layout contexts and the function L#layout

The function L is responsible for implementing the layout rule, i.e., inserting { and } tokens that are implied by layout. It uses a layout context stack to do its job, and also needs cooperation with the parser.

If it weren't for the need for cooperation with the parser, the function L could have been implemented as a pure function of type [PosToken] -> [PosToken], pretty much as it is presented in the Haskell report.

To implement the interaction with the parser, we use a parser monad that as part of its state has the remaining tokens, and the current layout context stack:

type LayoutContextStack = [Int]
type State = ([PosToken],LayoutContextStack)

-- The parser monad:
newtype PM a=PM (State->Either Error (a,State))
type Error = String
get :: PM State
set :: State -> PM ()

token :: PM PosToken
popContext :: PM ()

Additional pieces#additional

Nested comments can not be described by regular expressions, so to recognize them, the generated function haskellLex calls a handwritten function nestedComment, which is included in Appendix HsLexUtils, together with some other auxiliary functions that are called from haskellLex.

Putting it together#together

The part of the lexing that is independent of the parser is combined into a function called lexerPass1:

lexerPass1 :: String -> [PosToken]
lexerPass1 =
    layoutPre . rmSpace . addPos . haskellLex

parseFile :: Monad m => PM a -> String -> m a
parseFile (PM p) s = 
  case p (lexerPass1 s,[]) of
    Left err    -> fail err
    Right (x,_) -> return x

The regular expression compiler#compiler

As described in Section lexicalsyntax, we use transducer expressions rather than plain regular expressions. For the implementation, the only difference is that some transitions denote input and some denote output, so we compile them in much the same way as regular expressions are typically compiled (see, e.g. [appel98:compiler]):

• An NFA (nondeterministic finite automaton) is generated from the regular expression.
• States that are equivalent, because they are connected by ε edges, are combined.
• The NFA is converted into a DFA (deterministic finite automaton), where each state in the DFA corresponds to a set of states in the NFA.
• The DFA is pretty printed as Haskell source code, with states implemented as functions and edges implemented as tail calls in the branches of a case expression.
• Optionally, character classes are used reduce the number of branches in the case expressions. For the Haskell lexer, using character classes halves the size of the generated Haskell code.

To illustrate what the generated Haskell code looks like, Figure Example-input shows a small regular expression and Figure Example-output shows the code that is generated for it by our regular expression compiler. For simplicity, we have switched off the use of character classes.

As can be seen in the example, the function generated for each state has three arguments:

• An error handler function. It is used to backtrack to the most recent position in the input where a token can be output, when the lexer reaches a dead end. ( Yes, contrary to what the original Haskell 98 report says, a Haskell lexer needs backtracking! Consider, for example, the state of the lexer when it has seen M.then. If the next input character is a space, the lexer has to backtrack and output the tokens M, . and then, but if the next character is a letter, it can be added to the accumulator, and at some later point a Qvarid can be output. Similarly, while 1.2e-3 is one token, 1.2e-x is four tokens.)
• The characters accumulated for the current token.
• The remaining input to be analyzed.

The choice to generate functions, rather than a data structure representing the DFA, was based on the assumption that it would result in the fastest token recognizing function. For example, we assumed that case analysis on characters and small numbers would be faster than array indexing.

import LexerGen(lexerGen)
import RegExp
import HaskellChars
import HsTokens

main = lexerGen "TstHsLex" "tstLex" r

r  = many (r1!r2!r3)
r1 = some (aa 'a' ! aa 'b') & aa 'c' & o Varid
r2 = some (aa 'a') & o Reservedid
r3 = aa 'd' & o Special

aa = t . ASCII -- recognize one ASCII character

module TstHsLex (tstLex) where
import Char
import HsLexUtils

type Output = [(Token,String)]
type Input = String
type Acc = Input -- reversed
type Lexer = Input -> Output
type LexerState = (Acc->Lexer) -> Acc -> Lexer

tstLex :: Lexer
tstLex is = start1 is

start1 :: Lexer
start1 is =
    state1 (\ as is -> gotError as is) "" is
state1 :: LexerState
state1 err as [] = gotEOF as
state1 err as iis@(i:is) =
  case i of
    'b' -> state3 err (i:as) is
    'a' -> state4 err (i:as) is
    'd' -> state5 err (i:as) is
    _ -> err as iis

state2 :: LexerState
state2 err as is = output Varid as (start1 is)

state3 :: LexerState
state3 err as [] = err as []
state3 err as iis@(i:is) =
  case i of
    'c' -> state2 err (i:as) is
    'a' -> state3 err (i:as) is
    'b' -> state3 err (i:as) is
    _ -> err as iis

state4 :: LexerState
state4 err as [] = err as []
  where err _ _ = output Reservedid as (start1 [])
state4 err as iis@(i:is) =
  case i of
    'c' -> state2 err (i:as) is
    'b' -> state3 err (i:as) is
    'a' -> state4 err (i:as) is
    _ -> err as iis
  where err _ _ = output Reservedid as (start1 iis)

state5 :: LexerState
state5 err as is = output Special as (start1 is)

Evaluation#evaluation

The lexer described in this paper has been developed and used as part of a Haskell front-end in the Programatica project [programatica]. It is based on code from the hssource library [hssource], so we mostly compare with the lexer from that library.

While the lexer has been replaced completely, the parser used in the Programatica Haskell front-end remains essentially the same as the one in the hssource library.

Below, we briefly discuss to what extent the goals stated in the introduction have been achieved.

Simplicity#simplicity

Using size as a measure of simplicity:

• The old handwritten lexer for Haskell: 664 lines
• The regular expression compiler: 678 lines
• The transliterated lexical syntax for Haskell: 193 lines
• The new layout processing: 100 lines

Efficiency#efficiency

Regarding speed, the new lexer+parser seems to be 10-15 percent slower than the old one. The Haskell Prelude and Standard Libraries (2943 lines) are still parsed in less than one second (on a 600MHz Pentium III), so the speed is still more than adequate.

Regarding size, the generated DFA has 153 states, and the Haskell code for the token recognizing function is ~5600 lines long. The lexer is thus considerably larger than the handwritten one. When compiled with ghc-5.04.2 -O, the size of the object code for the module HsLex is 529KB. As a comparison, our Haskell parser, generated by Happy, is 740KB, and the total size of our Haskell front-end is 5458KB.

A drawback with large, automatically generated Haskell modules is that current Haskell compilers need a ridiculous amount of time and space to compile them. While Hugs [hugs] loads the module containing function haskellLex in 1.3 seconds, both GHC and HBC need minutes to compile it. Somewhat better was nhc98, which needed less than a minute with a 20MB heap.

Correctness#correctness

The original motivation for replacing the hssource library lexer with a completely new one was that we encountered several bugs in the hssource lexer, and because of the complexity of the code, fixing the bugs was rather tedious.

After the replacement, we have not had to pay much attention to the lexer. There has been a small number of changes to the Haskell report (regarding layout processing) and we have found it easy to adapt our lexer to those changes.

Our new lexer is more modular, the parts are simpler and the structure follows the structure of the specification in the Haskell report more closely, so it should be easier to convince oneself that the implementation is correct, and to maintain correctness when changes are made. In particular, to check that the transliteration of lexical syntax is correct, a visual inspection should be enough.

Apart from the correct transliteration of the lexical syntax, the correctness of the generated token recognizing function depends on two more factors:

• The correctness of the regular expression compiler, with respect to the text book methods it is based on [appel98:compiler]. This is an independent issue.
• The agreement of the semantics implemented by the regular expression compiler with the intended semantics of the pseudo-formal specification in the Haskell report. Due the informal style of Haskell report, we can not make any guarantees about this step.

Re-usability#reusability

The lexer has already been reused in two applications:

• An HTML renderer with syntax highlighting for Haskell [h2h]. This application generates HTML from the output of the function haskellLex, so the fact that it preserves white space was useful.
• A simple program called stripcomments [stripcomments] that removes comments and blank lines from Haskell source code. Someone asked for this on the Haskell mailing list, and by re-using the functions haskellLex, addPos and rmSpace, this simple application was very easy to implement.

What about Unicode?#unicode

The Haskell report states that Haskell uses the Unicode character sets. Our lexer supports Unicode, provided that it is compiled with a Haskell compiler that supports Unicode. It also requires that functions in the standard library module Char support Unicode, since the nonterminals uniWhite, uniSmall, uniLarge and uniDigit in the lexical syntax are implemented by calls to the functions isSpace, isLower, isUpper and isDigit, respectively. HBC [hbc] is still the only Haskell compiler that implements this, as far as we know. Also, the character class uniSymbol is implemented by the function isSymbol, available in HBC's Char module, but sadly missing in the Haskell 98 libraries.

Conclusion#conclusion

We have described a lexer for Haskell in Haskell. It is in Haskell in several ways:

1. The lexical grammar is specified in Haskell using regular expression combinators.
2. The lexical grammar is compiled into a token recognizing Haskell function.
3. The regular expression compiler is implemented in Haskell.

The fact that the lexer is in active use in the the Haskell tools developed as part of the Programatica project, which have been used to process substantial Haskell programs, shows not only that the lexer is efficient enough to be useful in practice, but also contributes to our confidence that the lexer is correct.

We can not give a formal proof of correctness, because the specification in the Haskell report is informal. We hope that, in future revisions of the Haskell report, a move to a more formal specification is made. Preferably, the syntax reference (and perhaps other parts of the report) should be self-contained and stick to a well established formal notation, reducing the role of the (unavoidable) informal text to indicating which formalism is used, giving references to its specification. Defining a home-made notation in parallel with the primary purpose of the report (definition of the language Haskell itself) makes the report too long.

We also hope that the function isSymbol is added to the Char module in a future revision of Haskell and that the efficiency of Haskell compilers will improve, so that automatically generated code for lexers and parser can be compiled in a reasonable time.

Future work#future

The current solution is far from perfect. Possible improvements include:

• See if size of the generated DFA can be reduced further, or if other optimizations can reduce the size of the generated code.
• Make some of the handwritten parts, e.g., the implementation of function L, more readable.
• Make the regular expression compiler more readable.
• Update it to the revised Haskell 98 report.
• Implement the difference operator, so that our lexical grammar can correspond even more accurately to the grammar in the report. (Or eliminate the difference operator from the report...)
• Since the lexical syntax is not specified by a regular expression, but a context-free grammar, it seems that a parser generator would be a more appropriate tool than a regular expression compiler...

• Extend the work to a complete Parser for Haskell in Haskell.

On-line version#online

The lexer described in this paper is available on-line, see [lhih-online].

Appendix#appendix

Module HaskellLexicalSyntax#HaskellLexicalSyntax

This module is a transcription of the Lexical Syntax given in appendix B.2 of the Haskell 98 Report, except for character set definitions, which are given in module HaskellChars (Appendix HaskellChars).

The grammar below contains extra annotations (not found in the report) to allow the recognized strings to be paired with token classifications (Figure HsTokens).

module HaskellLexicalSyntax(program) where
import List((\\))
import HaskellChars
import HsTokens
import RegExp

program = many (lexeme ! whitespace)

lexeme  = varid      & o Varid  
        ! conid      & o Conid
        ! varsym     & o Varsym
        ! consym     & o Consym
        ! literal -- & o Literal
        ! a special  & o Special
        ! reservedop & o Reservedop
        ! reservedid & o Reservedid
--      ! specialid  & o Specialid
         -- (recognized by the parser)

        ! qvarid     & o Qvarid
        ! qconid     & o Qconid
        ! qvarsym    & o Qvarsym
        ! qconsym    & o Qconsym

literal = integer    & o IntLit
        ! float      & o FloatLit
        ! char       & o CharLit
        ! string     & o StringLit

whitechar = newline ! a vertab ! a formfeed ! a space ! a tab
newline   = a creturn & a linefeed
          ! a creturn ! a linefeed ! a formfeed

whitespace = some whitechar & o Whitespace
           ! comment & o Comment
           ! ncomment & o NestedComment
comment = dashes & o Commentstart & many (a cany) & newline
dashes = as "--" & many (aa "-")
opencom = as "{-"
ncomment = opencom & o NestedCommentStart
  -- nested comments are handled by
  -- calling an external function

varid = a small & idtail -- <reservedid>
conid = a large & idtail
idtail =  many (a small ! a large ! a digit ! aa "'")

reservedid = ass [ "case", "class", "data", "default", "deriving",
                   "do", "else", "if", "import", "in", "infix",
                   "infixl", "infixr", "instance", "let", "module",
                   "newtype", "of", "then", "type", "where", "_"]

--specialid = as"as" ! as"qualified" ! as"hiding" 

varsym = a symbol & symtail  -- <reservedop>
consym = aa ":" & symtail    -- <reservedop>
symtail = many (a symbol ! aa ":")

reservedop = ass ["..", ":","::", "=","\\",
                  "|","<-","->","@","~","=>"]

modid = conid
optq = opt qual
qual = modid & aa "."

qvarid = qual & varid
qconid = qual & conid
qvarsym = qual & varsym
qconsym = qual & consym

decimal = some (a digit)
octal = some (a octit)
hexadecimal = some (a hexit)

integer = decimal
        ! aa "0" & aa "Oo" & octal
        ! aa "0" & aa "Xx" & hexadecimal

float = decimal & aa "." & decimal
      & opt (aa "eE" & opt (aa "-+") & decimal)
char = aa "'" & (a (graphic \\ acs "'\\")
     ! a space ! escape{-<\&>-}) & aa "'"
string =
    aa "\"" & many (a (graphic \\ acs "\"\\")
    ! a space ! escape ! gap) & aa "\""

escape =
   aa "\\" &
    (charesc ! ascii ! decimal !
     aa "o" & octal ! aa "x" & hexadecimal )

charesc = aa "abfnrtv\\\"'&"

ascii =
  aa "^" & cntrl !
  ass ["NUL","SOH","STX","ETX","EOT","ENQ",
       "ACK","BEL","BS","HT","LF","VT","FF",
       "CR","SO","SI","DLE","DC1","DC2","DC3",
       "DC4","NAK","SYN","ETB","CAN","EM","SUB",
       "ESC","FS","GS","RS","US","SP","DEL"]

cntrl = a ascLarge ! aa "@[\\]^_"

gap = aa "\\" & some whitechar & aa "\\"

aa = a . acs
as = ts . acs
ass = foldr1 (!) . map as

Module HaskellChars#HaskellChars

This module collects the definitions from the Lexical Syntax in appendix B.3 of the (revised) Haskell 98 report that define sets of characters. These sets are referred to in the rest of the lexical syntax, which is given in module HaskellLexicalSyntax (Appendix HaskellLexicalSyntax).

module HaskellChars where

data HaskellChar
  = ASCII Char
  | UniWhite   -- any whitespace character
  | UniSymbol  -- any symbol or punctuation
  | UniDigit   -- any numeric
  | UniLarge   -- any uppercase or titlecase
  | UniSmall   -- any lowercase letter
  deriving (Eq,Ord,Show)

acs = map ASCII

-- Character classifications:
special   = acs "(),;[]`{}"
creturn   = acs "\r"
linefeed  = acs "\LF"
vertab    = acs "\VT"
formfeed  = acs "\FF"
space     = acs " \xa0"
tab       = acs "\t"
uniWhite  = [UniWhite]

cany      = graphic++space++tab
graphic   = small++large++symbol++digit++special++acs ":\"'"
small     = ascSmall++uniSmall++acs "_"
ascSmall  = acs ['a'..'z']
uniSmall  = [UniSmall]
large     = ascLarge++uniLarge
ascLarge  = acs ['A'..'Z']
uniLarge  = [UniLarge]
symbol    = ascSymbol++uniSymbol
ascSymbol = acs "!#$uniSymbol = [UniSymbol]
digit     = ascDigit++uniDigit
ascDigit  = acs ['0'..'9']
uniDigit  = [UniDigit]
octit     = acs ['0'..'7']
hexit     = digit ++ acs ['A'..'F'] ++ acs ['a'..'f']

Module HsLexerPass1#HsLexerPass1

module HsLexerPass1 where
import HsLex(haskellLex)
import HsLexUtils
import HsLayoutPre(layoutPre)
import List(mapAccumL)

default(Int)

type LexerOutput = [(Token,(Pos,String))]
type Lexer = String -> LexerOutput

lexerPass1 :: Lexer
lexerPass1 = lexerPass1Only . lexerPass0

lexerPass1Only = layoutPre . rmSpace

rmSpace = filter (notWhite.fst)
  where notWhite t =
          t/=Whitespace &&
          t/=Commentstart &&
          t/=Comment &&
          t/=NestedComment

-- Tokenize and add position information:

lexerPass0 :: Lexer
lexerPass0 = addPos . haskellLex

addPos = snd . mapAccumL pos startPos
  where
    pos p (t,r) = (nextPos p s,(t,(p,s)))
      where s = reverse r

type Pos = (Int,Int)
startPos = (1,1) :: Pos
-- The first column is 1, not 0.

nextPos :: Pos -> String -> Pos
nextPos = foldl nextPos1

nextPos1 :: Pos -> Char -> Pos
nextPos1 (y,x) c =
    case c of
      -- The characters newline, return, linefeed,
      -- and formfeed, all start a new line.
      '\n'  -> (y+1, 1)
      '\CR' -> (y+1, 1)
      '\LF' -> (y+1, 1)
      '\FF' -> (y+1, 1)

      '\t'  -> (y, x+8 - (x-1) `mod` 8)
      _ -> (y, x+1)

Module HsLexutils#HsLexUtils

module HsLexUtils
 (module HsLexUtils,Token(..)) where
import HsTokens

gotEOF [] = []
gotEOF as = [(GotEOF, as)]

gotError as is =
  (ErrorToken, as):
  if null is
  then [(GotEOF,[])]
  else [(TheRest,reverse (take 80 is))]

-- Not reversing the token string here
-- seems to save about 10output token as cont = (token,as):cont

#ifndef __HBC__
isSymbol _ = False
#endif

nestedComment as is next = nest 0 as is
  where
    nest n as is =
      case is of
        '-':'}':is ->
          if n==0
          then next gotError ('}':'-':as) is
          else nest (n-1) ('}':'-':as) is
        '{':'-':is -> nest (n+1) ('-':'{':as) is
        c:is -> nest n (c:as) is
        _ -> gotError as is  -- EOF inside comment

The module HsLayoutPre#HsLayoutPre

This is an implementation of Haskell layout, as specified in section 9.3 of the revised Haskell 98 report.

This module contains the layout preprocessor that inserts the extra <n> and {n} tokens.

module HsLayoutPre(layoutPre,Pos,PosToken) where
import HsTokens

type Pos = (Int,Int) -- (row,column)
type PosToken = (Token,(Pos,String))

layoutPre :: [PosToken] -> [PosToken]
layoutPre = indent . open

open = open1

open1 (t1@(Reservedid,(_,"module")):ts) = t1:open2 ts
open1 (t1@(Special,(_,"{")):ts)         = t1:open2 ts
open1 ts@((t,(p@(r,c),s)):_)            = (Open c,(p,"")):open2 ts
open1 []                                = []

open2 (t1:ts1) | isLtoken t1 =
    case ts1 of
      t2@(_,(p@(r,c),_)):ts2 ->
        if notLBrace t2
        then t1:(Open c,(p,"")):open2 ts1
        else t1:t2:open2 ts2
      [] -> t1:(Open 0,(fst (snd t1),"")):[]
  where
    isLtoken (Reservedid,(_,s)) = s `elem` ["let","where","do","of"]
    isLtoken _ = False

    notLBrace (Special,(_,"{")) = False
    notLBrace _ = True
open2 (t:ts) = t:open2 ts
open2 [] = []

indent (t1@(Open _,((r,c),_)):ts) = t1:indent2 r ts
indent (t1@(t,(p@(r,c),s)):ts)    = (Indent c,(p,"")):t1:indent2 r ts
indent [] = []

indent2 r (t1@(_,((r',_),_)):ts) | r'==(r::Int) = t1:indent2 r ts
indent2 r ts = indent ts

Module HsLexer#HsLexer

This module implements the part of the lexer that interacts with the Happy parser, i.e., the layout processing.

module HsLexer where
import ParseMonad
import HsTokens(Token(..))

lexer cont = cont =<< token

popContext =
    do (ts,m:ms) <- get
       if m/=0 then set (ts,ms) -- redudant test
         else fail "Grammar bug? Unbalanced implicit braces?"

token = uncurry l =<< get
  where
    -- Here is the rest of the function L in the report:
    -- The equations for cases when <n> is the first token:
    l ts0@((Indent n,(p,_)):ts) ms0@(m:ms)
        | m==n      = ok (semi p)    ts  ms0
        | n<m       = ok (vrcurly p) ts0 ms
    l ((Indent _,_):ts) ms = l ts ms
    -- The equations for cases when {n} is the first token:
    l ((Open n,(p,_)):ts) (m:ms) | n>m = ok (vlcurly p) ts (n:m:ms)
    l ((Open n,(p,_)):ts) []     | n>0 = ok (vlcurly p) ts [n]
    l ((Open n,(p,_)):ts) ms           = ok (vlcurly p)
                                            (vrcurly p:(Indent n,(p,"")):ts)
                                            (0:ms)
    -- Equations for explicit braces:
    l (t1@(Special,(_,"}")):ts) (0:ms) = ok t1 ts ms
    l (t1@(Layout, (_,"}")):ts) (0:ms) = ok t1 ts ms
    l (t1@(Special,(_,"}")):ts) ms     = fail "unexpected }"
    l (t1@(Special,(p,"{")):ts) ms     = ok t1 ts (0:ms)
    -- The equation for ordinary tokens:
    l (t:ts) ms = ok t ts ms
    -- Equations for end of file:
    l [] [] = return eoftoken
    l [] (m:ms) = if m/=0
                  then ok (vrcurly eof) [] ms
                  else fail "missing } at eof"

    ok t ts ctx = setreturn t (ts,ctx)

    vlcurly p = (Layout,(p,"{"))
    vrcurly p = (Layout,(p,"}"))
    semi p = (Special,(p,";"))