Consider the following grammar of the Pablum expression language.

<expr> ::= <term> | <expr> "OR" <term>
<term> ::= <factor> | <factor> "AND" <term> 
<factor> ::= "0" | "1" | <ident> | "(" <expr> ")"

where identifiers have syntax given by the following regular expression.

<ident> ::= [A-Za-z]+

Assume that the Pablum follows the normal free-format rules for programming languages:

• White space may (blanks and newlines) may freely occur between tokens.
• Tokens follow the longest-match rule, so that white space is necessary between identifiers and keywords.

Note: you may use the Haskell predicate function isAlpha to test for an alphabetic character ([A-Za-z]).

1. (1 mark) Write a Haskell algebraic data type definition for tokens of the language.

data Token = OR_t | AND_t | T_0 | T_1 | LP | RP | Id String | Bad   deriving Show
-- Short names are useful on exams

2. (1 mark) Write a Haskell algebraic data type definition suitable for representing Pablum ASTs (abstract syntax trees).

data AST = Or (AST, AST) | And (AST, AST) | Zero | One | Var String deriving Show

3. (1 mark) Write the Haskell type signature of a Pablum lexer function lex that converts a list of characters into a list of tokens.

lexer :: [Char] -> [Token]

4. (2 marks) Implement the Pablum lexer function lex in Haskell.

lexer [] = []
lexer (' ':more) = lexer more  -- skip blanks
lexer ('\n':more) = lexer more -- skip newlines (optional)
lexer ('(':more) = LP: (lexer more)
lexer (')':more) = RP: (lexer more)
lexer ('0':more) = T_0: (lexer more)
lexer ('1':more) = T_1: (lexer more)
lexer (c : more)
  | isAlpha c  = case (span isAlpha (c : more)) of
                     ("OR", after) -> OR_t : (lexer after)
                     ("AND", after) -> AND_t : (lexer after)
                     (id, after) -> (Id id): (lexer after)
  | otherwise = Bad : (lexer more)

5. (1 mark) Write the Haskell type signature of the three recursive descent parsing functions required by the grammar.

parseExpr :: [Token] -> Maybe (AST, [Token])
parseTerm :: [Token] -> Maybe (AST, [Token])
parseFactor :: [Token] -> Maybe (AST, [Token])

6. (1 mark) Implement the parseFactor function in Haskell.

parseFactor (T_0: more) = Just (Zero, more)
parseFactor (T_1: more) = Just (One, more)
parseFactor (Id id: more) = Just (Var id, more)
parseFactor (LP: after) =
   case parseExpr after of
      Just (e, RP:remaining) -> Just (e, remaining)
      _ -> Nothing
parseFactor _ = Nothing

7. (1 mark) Implement the parseTerm function in Haskell.

--Note: this is not left-recursive!
parseTerm s =
   case parseFactor(s) of
       Just(f, AND_t:more) ->
            case parseTerm(more) of
                Just(t, afterTerm2) -> Just(And(f, t), afterTerm2)
                _ -> Nothing
       Just(f, more) -> Just(f, more)
       _ -> Nothing

8. (2 marks) Implement the parseExpr function in Haskell.

parseExpr s =
    case parseTerm(s) of
        Just (t, after) -> extendExpr(t, after)
        _ -> Nothing

extendExpr(e, []) = Just(e, [])
extendExpr(e, OR_t:more) =
    case parseTerm(more) of
        Just(t, remain) -> extendExpr(Or(e, t), remain)
        _ -> Nothing
extendExpr(e, ts) = Just(e, ts)