content: 
  [[very-simple-expression-parsing]]
  = Very simple expression parsing
  
  In this tutorial we will develop a parser for a very simple expression
  language, and start learning about the set of combinators which comes
  with Parsec.
  
  > import Text.Parsec (ParseError)
  > import Text.Parsec.String (Parser)
  > import Text.Parsec.String.Parsec (try)
  > import Text.Parsec.String.Char (oneOf, char, digit, satisfy)
  > import Text.Parsec.String.Combinator (many1, choice, chainl1)
  > import Control.Applicative ((<|>), many)
  > import Control.Monad (void)
  > import Data.Char (isLetter, isDigit)
  > import FunctionsAndTypesForParsing
  
  == num
  
  The first element we will have in this expression language is positive
  integral numbers:
  
  > numberExamples :: [(String,Integer)]
  > numberExamples = [("1", 1)
  >                  ,("23", 23)]
  
  TODO: make examples with parsing failures for all of the example
  scripts below?
  
  To parse a number, we need to parse one or more digits, and then read
  the resulting string. We can use the combinator `many1` to help with
  this. We will also use do notation.
  
  > num :: Parser Integer
  > num = do
  >     n <- many1 digit
  >     return (read n)
  
  Let's try it out.
  
  ```
  *Main> regularParse num "1"
  Right 1
  
  *Main> regularParse num "123456"
  Right 123456
  
  *Main> regularParse num "aa"
  Left (line 1, column 1):
  unexpected "a"
  expecting digit
  
  ```
  
  How does it work? First, we parse one or more (`many1`) digits (`digit`),
  and give the result the name 'n'. Then we convert the string to an
  integer using `read`.
  
  The `many1` function's type looks like this:
  
  ```
  many1 :: Parser a -> Parser [a]
  ```
  
  It applies the parser given one or more times, returning the result.
  
  Let's see what happens when we use the `many` combinator which parses
  zero or more items instead of one or more.
  
  > num1 :: Parser Integer
  > num1 = do
  >     n <- many digit
  >     return (read n)
  
  ```
  *Main> regularParse num1 "1"
  Right 1
  
  *Main> regularParse num1 "123456"
  Right 123456
  
  *Main> regularParse num1 "aa"
  Right *** Exception: Prelude.read: no parse
  ```
  
  == var
  
  For var, we have to decide on a syntax for the identifiers. Let's go
  for a common choice: identifiers must start with a letter or
  underscore, and then they can be followed by zero or more letters,
  underscores or digits in any combination.
  
  > varExamples :: [(String,String)]
  > varExamples = [("test", "test")
  >               ,("_stuff", "_stuff")
  >               ,("_1234", "_1234")]
  
  > var :: Parser String
  > var = do
  >     fc <- firstChar
  >     rest <- many nonFirstChar
  >     return (fc:rest)
  >   where
  >     firstChar = satisfy (\a -> isLetter a || a == '_')
  >     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')
  
  This time, we create two helper parsers: `firstChar`, which parses a
  letter or underscore, and `nonFirstChar` which parses a digit, letter
  or underscore. This time, we use the `many` function instead of
  `many1`.
  
  Try it out in ghci. I like to try things which you expect to work, and
  also to try things which you expect to not work and make sure you get
  an error.
  
  == parens
  
  The parens parser will eventually parse any expression inside
  parentheses. First it will just parse integers inside parentheses.
  
  > data Parentheses = Parentheses Integer
  >                    deriving (Eq,Show)
  >
  > parensExamples :: [(String, Parentheses)]
  > parensExamples = [("(1)", Parentheses 1)
  >                  ,("(17)", Parentheses 17)]
  
  > parens :: Parser Parentheses
  > parens = do
  >     void $ char '('
  >     e <- many1 digit
  >     void $ char ')'
  >     return (Parentheses (read e))
  
  There is a new function: `void`. This might be familiar to you
  already. This is used to ignore the result of the `char` parser, since
  we are not interested in this value. You can also write the function
  without `void`, but ghc will give you a warning if you have warnings
  turned on.
  
  One way of turning warnings on in ghci is to enter `:set -Wall` at the
  ghci prompt.
  
  > parens' :: Parser Parentheses
  > parens' = do
  >     char '('
  >     e <- many1 digit
  >     char ')'
  >     return (Parentheses (read e))
  
  ```
  *Main> :set -Wall
  *Main> :l "VerySimpleExpressions.lhs"
  
  ...
  
  FirstRealParsing.lhs:140:7: Warning:
      A do-notation statement discarded a result of type Char.
      Suppress this warning by saying "_ <- char '('",
      or by using the flag -fno-warn-unused-do-bind
  
  FirstRealParsing.lhs:142:7: Warning:
      A do-notation statement discarded a result of type Char.
      Suppress this warning by saying "_ <- char ')'",
      or by using the flag -fno-warn-unused-do-bind
  
  ...
  
  ```
  
  As you can see, another way to suppress the warning is to use
  `_ <- char '('`.
  
  One issue with this parser is that it doesn't handle whitespace:
  
  ```
  *Main> regularParse parens "(1)"
  Right (Parentheses 1)
  
  *Main> regularParse parens "( 1)"
  Left (line 1, column 2):
  unexpected " "
  expecting digit
  
  *Main> regularParse parens "(1 )"
  Left (line 1, column 3):
  unexpected " "
  expecting digit or ")"
  ```
  
  We will look at this issue below.
  
  == add
  
  Now we will write a little parser to parse strings like 'a+b' where a
  and b are numbers.
  
  > data SingleAdd = SingleAdd Integer Integer
  >                  deriving (Eq,Show)
  >
  > singleAddExamples :: [(String, SingleAdd)]
  > singleAddExamples = [("1+2", SingleAdd 1 2)
  >                     ,("101+202", SingleAdd 101 202)]
  
  > add :: Parser SingleAdd
  > add = do
  >     e0 <- many1 digit
  >     void $ char '+'
  >     e1 <- many1 digit
  >     return (SingleAdd (read e0) (read e1))
  
  It has the same whitespace issues as the parens parser.
  
  ```
  *Main> regularParse add "1+2"
  Right (SingleAdd 1 2)
  
  *Main> regularParse add "1 +2"
  Left (line 1, column 2):
  unexpected " "
  expecting digit or "+"
  
  ```
  
  == whitespace
  
  Here is a parser which will skip zero or more whitespace characters.
  
  > whitespace :: Parser ()
  > whitespace = void $ many $ oneOf " \n\t"
  
  We can use this to make our parsers handle whitespace better.
  
  ```
  *Main> regularParse whitespace " "
  Right ()
  *Main> regularParse whitespace "  "
  Right ()
  *Main> regularParse whitespace "\t"
  Right ()
  *Main> regularParse whitespace " \n "
  Right ()
  *Main> regularParse whitespace ""
  Right ()
  ```
  
  Notice that it always succeeds.
  
  Here is the parens parser rewritten with a common approach to
  whitespace handling:
  
  > parensW :: Parser Parentheses
  > parensW = do
  >     whitespace
  >     void $ char '('
  >     whitespace
  >     e <- many1 digit
  >     whitespace
  >     void $ char ')'
  >     whitespace
  >     return (Parentheses (read e))
  
  ```
  *Main> regularParse parensW "(1)"
  Right (Parentheses 1)
  
  *Main> regularParse parensW " (1)"
  Right (Parentheses 1)
  
  *Main> regularParse parensW " (1 )"
  Right (Parentheses 1)
  
  *Main> regularParse parensW " ( 1 ) "
  Right (Parentheses 1)
  ```
  
  Looks good.
  
  In the original parsec documentation, one of the concepts mentioned is
  the idea of 'lexeme' parsing. This is a style in which every token
  parser should also consume and ignore any trailing whitespace.
  
  This is a simple convention which with a bit of care allows skipping
  whitespace exactly once wherever it needs to be skipped. To complete
  the lexeme style, we should also always skip leading whitespace at the
  top level only. This feels more elegant than spamming all the parsing
  code with many calls to `whitespace`.
  
  > lexeme :: Parser a -> Parser a
  > lexeme p = do
  >            x <- p
  >            whitespace
  >            return x
  
  > parseWithWhitespace :: Parser a -> String -> Either ParseError a
  > parseWithWhitespace p = parseWithEof wrapper
  >   where
  >     wrapper = do
  >         whitespace
  >         p
  
  
  Here is the parens parser rewritten to use lexeme:
  
  > parensL :: Parser Parentheses
  > parensL = do
  >     void $ lexeme $ char '('
  >     e <- lexeme $ many1 digit
  >     void $ lexeme $ char ')'
  >     return (Parentheses (read e))
  
  ```
  *Main> parseWithWhitespace parensL "(1)"
  Right (Parentheses 1)
  
  *Main> parseWithWhitespace parensL " (1)"
  Right (Parentheses 1)
  
  *Main> parseWithWhitespace parensL " ( 1)"
  Right (Parentheses 1)
  
  *Main> parseWithWhitespace parensL " ( 1 ) "
  Right (Parentheses 1)
  ```
  
  The `parseWithWhitespace` function can also use `(>>)` to make it a
  bit shorter, `wrapper = whiteSpace >> p`.
  
  Here is the shorter version of this function using `(>>)`:
  
  > parseWithWhitespace' :: Parser a -> String -> Either ParseError a
  > parseWithWhitespace' p = parseWithEof (whitespace >> p)
  
  Try rewriting the SingleAdd parser to use `lexeme`, and test it out to
  convince yourself that it skips whitespace correctly.
  
  == simple expr
  
  Now we are ready to write a parser which parses simple expressions
  made from these components. Here is the data type for these
  expressions.
  
  > data SimpleExpr = Num Integer
  >                 | Var String
  >                 | Add SimpleExpr SimpleExpr
  >                 | Parens SimpleExpr
  >                   deriving (Eq,Show)
  
  It's so simple that it is almost useless at the moment.
  
  > simpleExprExamples :: [(String,SimpleExpr)]
  > simpleExprExamples =
  >     [("a", Var "a")
  >     ,("1", Num 1)
  >     ,("2 + 3", Add (Num 2) (Num 3))
  >     ,("(42)", Parens (Num 42))]
  
  TODO: some more complex examples
  
  Here are all our component parsers with `lexeme`, and with the
  `SimpleExpr` constructors:
  
  > numE :: Parser SimpleExpr
  > numE = do
  >     n <- lexeme $ many1 digit
  >     return $ Num $ read n
  
  There doesn't seem to be a unique obviously correct place to put the
  lexeme call in the var parser:
  
  > varE :: Parser SimpleExpr
  > varE = lexeme $ do
  >     fc <- firstChar
  >     rest <- many nonFirstChar
  >     return $ Var (fc:rest)
  >   where
  >     firstChar = satisfy (\a -> isLetter a || a == '_')
  >     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')
  
  Here is an alternative, with the call to lexeme in a different place,
  but gives effectively the same function.
  
  > varE' :: Parser SimpleExpr
  > varE' = do
  >     fc <- firstChar
  >     rest <- lexeme $ many nonFirstChar
  >     return $ Var (fc:rest)
  >   where
  >     firstChar = satisfy (\a -> isLetter a || a == '_')
  >     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')
  
  > parensE :: Parser SimpleExpr
  > parensE = do
  >     void $ lexeme $ char '('
  >     e <- lexeme $ many1 digit
  >     void $ lexeme $ char ')'
  >     return $ Parens $ Num $ read e
  
  In the parens parser, we can reuse the `numE` parser like this:
  
  > parensE' :: Parser SimpleExpr
  > parensE' = do
  >     void $ lexeme $ char '('
  >     e <- numE
  >     void $ lexeme $ char ')'
  >     return $ Parens e
  
  Here is the add parser using `numE` also.
  
  > addE :: Parser SimpleExpr
  > addE = do
  >     e0 <- numE
  >     void $ lexeme $ char '+'
  >     e1 <- numE
  >     return $ Add e0 e1
  
  === choice
  
  To combine these, we can use an operator called `(<|>)`:
  
  > numOrVar :: Parser SimpleExpr
  > numOrVar = numE <|> varE
  
  It tries the first parser, and it if fails (without consuming any
  input), it tries the second parser. More about the 'consuming input'
  concept later.
  
  Here is another way to write the numOrVar parser:
  
  > numOrVar' :: Parser SimpleExpr
  > numOrVar' = choice [numE,varE]
  
  `choice` is just wrapper around `(<|>)`. You can choose which one to
  use based on which is more readable in each particular case.
  
  ```
  *Main> parseWithWhitespace numOrVar "a"
  Right (Var "a")
  
  *Main> parseWithWhitespace numOrVar "1"
  Right (Num 1)
  
  *Main> parseWithWhitespace numOrVar "!"
  Left (line 1, column 1):
  unexpected "!"
  expecting digit
  ```
  
  Here is the first version of the simpleExpr parser:
  
  > simpleExpr :: Parser SimpleExpr
  > simpleExpr = numE <|> varE <|> addE <|> parensE
  
  ```
  *Main> parseWithWhitespace simpleExpr "12"
  Right (Num 12)
  
  *Main> parseWithWhitespace simpleExpr "aa"
  Right (Var "aa")
  
  *Main> parseWithWhitespace simpleExpr "1+2"
  Left (line 1, column 2):
  unexpected '+'
  expecting digit or end of input
  
  *Main> parseWithWhitespace simpleExpr "(1)"
  Right (Parens (Num 1))
  
  *Main> parseWithWhitespace simpleExpr "(aa)"
  Left (line 1, column 2):
  unexpected "a"
  expecting digit
  
  ```
  
  It works well for some of the parsers. One problem is that the `addE`
  and `parensE` parsers don't parse general expressions as the
  components, but just `numE`. Another problem is that the `addE`
  doesn't work at all: the `numE` parser parses the first number, and
  the `addE` parser is never tried. This is an example of `(<|>)` not
  trying the second parser if the first parser succeeds, even if a later
  alternative would consume more input or successfully parse the whole
  input.
  
  Let's try and rearrange the order:
  
  > simpleExpr1 :: Parser SimpleExpr
  > simpleExpr1 = addE <|> numE <|> varE <|> parensE
  
  ```
  *Main> parseWithWhitespace simpleExpr1 "12"
  Left (line 1, column 3):
  unexpected end of input
  expecting digit or "+"
  
  *Main> parseWithWhitespace simpleExpr1 "aa"
  Right (Var "aa")
  
  *Main> parseWithWhitespace simpleExpr1 "1+2"
  Right (Add (Num 1) (Num 2))
  
  *Main> parseWithWhitespace simpleExpr1 "(1)"
  Right (Parens (Num 1))
  
  ```
  
  We swapped one problem for another. Let's fix this using the `try`
  function.
  
  
  > simpleExpr2 :: Parser SimpleExpr
  > simpleExpr2 = try addE <|> numE <|> varE <|> parensE
  
  ```
  *Main> parseWithWhitespace simpleExpr2 "12"
  Right (Num 12)
  
  *Main> parseWithWhitespace simpleExpr2 "aa"
  Right (Var "aa")
  
  *Main> parseWithWhitespace simpleExpr2 "1+2"
  Right (Add (Num 1) (Num 2))
  
  *Main> parseWithWhitespace simpleExpr2 "(1)"
  Right (Parens (Num 1))
  ```
  
  Now everything seems to work fine. The `try` function is very powerful
  and easy to use, and can be used where in a more traditional parsing
  approach you would have to use left factoring or something else.
  
  The `try` function implements backtracking. When this is used with
  `(<|>)`, it means that if the first parser fails, it will undo the
  consumed input and carry on with the next option, instead of failing
  completely. This works even if the `try` is nested deeply within the
  first parser given to `(<|>)`.
  
  `try` has its downsides (some of which we will see later), and I
  usually try to minimise its use or eliminate it completely. I found I
  often got into a complete mess when I used `try` too much when writing
  parsers for something a little tricky like SQL, and that although
  doing some left-factoring appeared at first to be tedious and appeared
  to make the code less readable, I eventually decided that for me it
  made the code more readable since what was happening was more
  transparent.
  
  Now we are going to fix this parser to parse arbitrarily nested
  expressions. In a way, the method used will roughly mean we are left
  factoring the `numE` and `addE` common prefix.
  
  Here is the naive implementation:
  
  > parensE3 :: Parser SimpleExpr
  > parensE3 = do
  >     void $ lexeme $ char '('
  >     e <- simpleExpr3
  >     void $ lexeme $ char ')'
  >     return $ Parens e
  
  
  > addE3 :: Parser SimpleExpr
  > addE3 = do
  >     e0 <- simpleExpr3
  >     void $ lexeme $ char '+'
  >     e1 <- simpleExpr3
  >     return $ Add e0 e1
  
  
  > simpleExpr3 :: Parser SimpleExpr
  > simpleExpr3 = try addE3 <|> numE <|> varE <|> parensE3
  
  If you run this parser, it will enter an infinite loop, since
  `simpleExpr3` and `addE3` will keep calling each other recursively
  without making any progress.
  
  ```
  *Main> parseWithWhitespace simpleExpr3 "a+b"
    C-c Interrupted.
  ```
  Let's try without `add`.
  
  > parensE4 :: Parser SimpleExpr
  > parensE4 = do
  >     void $ lexeme $ char '('
  >     e <- simpleExpr4
  >     void $ lexeme $ char ')'
  >     return $ Parens e
  
  > simpleExpr4 :: Parser SimpleExpr
  > simpleExpr4 = numE <|> varE <|> parensE4
  
  ```
  *Main> parseWithWhitespace simpleExpr4 "a"
  Right (Var "a")
  
  *Main> parseWithWhitespace simpleExpr4 "1"
  Right (Num 1)
  
  *Main> parseWithWhitespace simpleExpr4 "(1)"
  Right (Parens (Num 1))
  
  *Main> parseWithWhitespace simpleExpr4 "((a))"
  Right (Parens (Parens (Var "a")))
  
  ```
  
  At least this part seems to work OK.
  
  Let's try to stop the add parser from calling itself indirectly:
  
  Here is a parameterized parens parser where we supply the nested
  expression parser as an argument. This is used here to try to make the
  code easier to follow and avoid rewriting this parser out again and
  again in full.
  
  > parensEN :: Parser SimpleExpr -> Parser SimpleExpr
  > parensEN simpleExprImpl = do
  >     void $ lexeme $ char '('
  >     e <- simpleExprImpl
  >     void $ lexeme $ char ')'
  >     return $ Parens e
  
  Here is a new parser, which parses expressions except add.
  
  > term :: Parser SimpleExpr -> Parser SimpleExpr
  > term simpleExprImpl = numE <|> varE <|> parensEN simpleExprImpl
  
  > term5 :: Parser SimpleExpr
  > term5 = term simpleExpr5
  
  > addE5 :: Parser SimpleExpr
  > addE5 = do
  >     e0 <- term5
  >     void $ lexeme $ char '+'
  >     e1 <- term5
  >     return $ Add e0 e1
  
  > simpleExpr5 :: Parser SimpleExpr
  > simpleExpr5 = try addE5 <|> term5
  
  ```
  *Main> parseWithWhitespace simpleExpr5 "1"
  Right (Num 1)
  
  *Main> parseWithWhitespace simpleExpr5 "a"
  Right (Var "a")
  
  *Main> parseWithWhitespace simpleExpr5 "(a)"
  Right (Parens (Var "a"))
  
  *Main> parseWithWhitespace simpleExpr5 "1+2"
  Right (Add (Num 1) (Num 2))
  
  *Main> parseWithWhitespace simpleExpr5 "1+a"
  Right (Add (Num 1) (Var "a"))
  
  *Main> parseWithWhitespace simpleExpr5 "(1+a)"
  Right (Parens (Add (Num 1) (Var "a")))
  
  *Main> parseWithWhitespace simpleExpr5 "1+a+b"
  Left (line 1, column 4):
  unexpected '+'
  expecting end of input
  ```
  
  Almost. Let's see what happens when the second `term` in `add` is
  changed to the general expression parser.
  
  > term6 :: Parser SimpleExpr
  > term6 = term simpleExpr6
  
  > addE6 :: Parser SimpleExpr
  > addE6 = do
  >     e0 <- term6
  >     void $ lexeme $ char '+'
  >     e1 <- simpleExpr6
  >     return $ Add e0 e1
  
  > simpleExpr6 :: Parser SimpleExpr
  > simpleExpr6 = try addE6 <|> term6
  
  ```
  *Main> parseWithWhitespace simpleExpr6 "a + b + c"
  Right (Add (Var "a") (Add (Var "b") (Var "c")))
  ```
  
  Maybe it looks like we've made it. But there is a problem. We've
  parsed the + operator as if it has right associativity:
  
  ```
  a + b + c -> a + (b + c)
  ```
  
  But it should be left associative:
  
  ```
  a + b + c -> (a + b) + c
  ```
  
  Let's left factor the parsing and fix this:
  
  > term7 :: Parser SimpleExpr
  > term7 = term simpleExpr7
  
  > simpleExpr7 :: Parser SimpleExpr
  > simpleExpr7 = do
  >     -- first parse a term
  >     e <- term7
  >     -- then see if it is followed by an '+ expr' suffix
  >     maybeAddSuffix e
  >   where
  >     -- this function takes an expression, and parses a
  >     -- '+ expr' suffix, returning an Add expression
  >     -- it recursively calls itself via the maybeAddSuffix function
  >     addSuffix e0 = do
  >         void $ lexeme $ char '+'
  >         e1 <- term7
  >         maybeAddSuffix (Add e0 e1)
  >     -- this is the wrapper for addSuffix, which adapts it so that if
  >     -- addSuffix fails, it returns just the original expression
  >     maybeAddSuffix e = addSuffix e <|> return e
  
  ```
  *Main> parseWithWhitespace simpleExpr7 "a + b + c"
  Right (Add (Add (Var "a") (Var "b")) (Var "c"))
  ```
  
  Now the parser seems to work for everything it should.
  
  There is a combinator function in Parsec we can use which abstracts
  this sort of pattern, `chainl1`.
  
  > simpleExpr8 :: Parser SimpleExpr
  > simpleExpr8 = chainl1 term8 op
  >   where
  >     op = do
  >         void $ lexeme $ char '+'
  >         return Add
  >     term8 = term simpleExpr8
  
  How does this work? Here is the type of `chainl1`:
  
  ```haskell
  chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
  chainl1 term op = ...
  ```
  
  The type of the Add constructor in pseudocode is:
  
  ```haskell
  Add :: SimpleExpr -> SimpleExpr -> SimpleExpr
  ```
  
  The `op` parser here now just parses the operator itself, i.e. '+'
  (and not the second expression like our simpleExpr7 parser). The
  return from the `op` function is a function which accepts two elements
  and combines them using the appropriate operator representation. In
  this case, the represenation is the `Add` constructor.
  
  You can look at the source
  <http://hackage.haskell.org/package/parsec-3.1.3/docs/src/Text-Parsec-Combinator.html#chainl1>
  and see if you can understand how it works. If you can't work it out,
  you could come back to it later when you have more experience writing
  parsing code.
  
  == Testing with the examples
  
  TODO: write a little manual tester that accepts a parser and a list of
  examples, and checks they all parse correctly.
  
  == Testing with quickcheck
  
  Let's see if we can check with quickcheck. It's a bit tricky testing
  parsers in this way, but one way to do something useful is to generate
  random asts, convert them to concrete syntax, parse them, and check
  the result. We can write a simple 'pretty printer' to convert an ast
  to concrete syntax.
  
  === a pretty printer
  
  TODO: a really simple pretty printer just pasting strings together, no
  layout.
  
  === the quick check code
  
  TODO: write a quickcheck property and arbitary instance and show
  running it at the ghci prompt
  
  