Exercises

1. Extend the program with an evaluator for lambda-calculus terms. Use de Bruijn's name-free representation of lambda-terms, instead of the naive datatype used here. Chapter 9 of Paulson's book [16] is a good starting point.
2. Extend the lexer to recognise numerals. Extend the grammar and parser with syntax for numerals and binary arithmetic operators.
3. Rewrite the lexer using a Haskell array to dispatch on whether the next character is whitespace, alphabetic, symbolic or illegal.
4. Find a grammar that can be parsed with arbitrary lookahead but not by a predictive parser.
5. Modify the Parser monad to admit arbitrary lookahead. Hint: use the following definition of Parser, which explicitly represents lookahead errors rather than using the builtin error-handling mechanism.

   
     type Parser a =
       Handle -> [Token] ->
       IO ([Token], Maybe (a, [Token]))

   If such a parser is run on a handle h with lookahead toks, it returns pair (toks1,m) where toks1 is the new lookahead, and m is either Nothing if the parse has failed or Just (x,toks2) if the parse was successful. In the latter case, x is the result of the parse and toks2 is the list of tokens accepted.