TextParsecExpr.lhs

[[parsing-expressions-with-fixity]]
= Parsing expressions with fixity

Text.Parsec.Expr allows building expression parsers with a range of
operators with different precedences and associativities
easily. Fixity is the (not completely standard) term for precendence
and associativity together.

`Text.Parsec.Expr` can be great to quickly get a parser for simple
expressions or a simple programming language with simple expressions
up and running.

> import Text.Parsec.String (Parser)
> import Text.Parsec.String.Combinator (many1, between)
> import Text.Parsec.String.Char (letter, char, digit, string, oneOf)
>
> import Control.Applicative ((<$>), (<*>), (<*), (<|>), many, (<$))
> import Control.Monad (void)
>
> import qualified Text.Parsec.String.Expr as E
> import FunctionsAndTypesForParsing

Let's extend the SimpleExpression type and parsers to cover a range of
operators with different precedences and associativity.

== expressions with plus and times

Let's start with a simple case: + and * with the usual fixity. Here is
the abstract syntax:

> data PlusTimesExpr = PteVar String
>                    | PteNum Integer
>                    | PteParens PlusTimesExpr
>                    | Plus PlusTimesExpr PlusTimesExpr
>                    | Times PlusTimesExpr PlusTimesExpr
>                          deriving (Eq,Show)

> plusTimesExpr :: Parser PlusTimesExpr
> plusTimesExpr = E.buildExpressionParser pteTable pteTerm

> pteTable :: [[E.Operator PlusTimesExpr]]
> pteTable = [[E.Infix (Times <$ symbol "*") E.AssocLeft]
>            ,[E.Infix (Plus <$ symbol "+") E.AssocLeft]
>            ]

Here you can see the operator parsers are the same as the previous
`SimpleExpr` parser which used `chainl1`: `Times <$ symbol "*"` and
`Plus <$ symbol "+"`. We just wrapped these up in the `E.Infix`
constructor with the associativity, and put them in a list of lists
which represents the precendence classes.

Here is the term parser and components. All this is just the same as
the `SimpleExpr` parser a previous tutorial.

> pteTerm :: Parser PlusTimesExpr
> pteTerm = pteVar <|> pteNum <|> pteParens

> pteNum :: Parser PlusTimesExpr
> pteNum = PteNum <$> integer

> pteVar :: Parser PlusTimesExpr
> pteVar = PteVar <$> identifier

> pteParens :: Parser PlusTimesExpr
> pteParens = PteParens <$> between (symbol "(") (symbol ")") plusTimesExpr

support functions:

> whitespace :: Parser ()
> whitespace = void $ many $ oneOf " \n\t"

> lexeme :: Parser a -> Parser a
> lexeme p = p <* whitespace

> integer :: Parser Integer
> integer = read <$> lexeme (many1 digit)

> identifier :: Parser String
> identifier = lexeme ((:) <$> firstChar <*> many nonFirstChar)
>   where
>     firstChar = letter <|> char '_'
>     nonFirstChar = digit <|> firstChar

> symbol :: String -> Parser String
> symbol s = lexeme $ string s

Here you can see the precendence in action:

```
*Main> regularParse plusTimesExpr "a + b * c"
Right (Plus (PteVar "a") (Times (PteVar "b") (PteVar "c")))

*Main> regularParse plusTimesExpr "a * b + c"
Right (Plus (Times (PteVar "a") (PteVar "b")) (PteVar "c"))
```

== a full featured expression type

Now let's try a much bigger example with lots more operators. Now we
are thinking ahead to the first version of the SQL query parser, and
preparing for this.

Here are our new operators in precedence order:

=== unary + -

```
+a
-3
```

=== exponentiation

```
a ^ 3
```

associativity: left

=== multiplication, division, modulo

```
a * 3
3 / b
a % 5
```

associativity: left

=== addition, subtraction

```
a + b
a - b
```

associativity: left

=== less than, greater than

```
a < b
a > b
```

associativity: none

=== equals

```
a = 3
```

associativity: right

=== not

```
not a
```

=== and

```
a and b
```

associativity: left

=== or

```
a or b
```

associativity: left

Here is the abstract syntax type:

> data SimpleExpr = Num Integer
>                 | Var String
>                 | Parens SimpleExpr
>                 | PrefixOp String SimpleExpr
>                 | BinaryOp SimpleExpr String SimpleExpr
>                    deriving (Eq,Show)

Here is the new expression parser:

> simpleExpr :: Parser SimpleExpr
> simpleExpr = E.buildExpressionParser table term

> table :: [[E.Operator SimpleExpr]]
> table = [[prefix "-", prefix "+"]
>         ,[binary "^" E.AssocLeft]
>         ,[binary "*" E.AssocLeft
>          ,binary "/" E.AssocLeft
>          ,binary "%" E.AssocLeft]
>         ,[binary "+" E.AssocLeft
>          ,binary "-" E.AssocLeft]
>         ,[binary "<" E.AssocNone
>          ,binary ">" E.AssocNone]
>         ,[binary "=" E.AssocRight]
>         ,[prefix "not"]
>         ,[binary "and" E.AssocLeft]
>         ,[binary "or" E.AssocLeft]
>         ]
>   where
>     binary name assoc =
>         E.Infix (mkBinOp name <$ symbol name) assoc
>     mkBinOp nm a b = BinaryOp a nm b
>     prefix name = E.Prefix (PrefixOp name <$ symbol name)

TODO: expand and explain the bits.

Here is the term parser.

> term :: Parser SimpleExpr
> term = var <|> num <|> parens

> num :: Parser SimpleExpr
> num = Num <$> integer

> var :: Parser SimpleExpr
> var = Var <$> identifier

> parens :: Parser SimpleExpr
> parens = between (symbol "(") (symbol ")") simpleExpr

TODO: write lots of parsing examples, including parse failures with
ambiguity.

issue: double prefix op, link to bug on parsec bug tracker.

The source in Text.Parsec.Expr is not too big. You can have a look and
try to understand it. There are several standard approaches in parsing
theory to parse expressions with data driven precendences and
associativity. I don't know which one Text.Parsec.Expr uses, but if
you find these and read about them, then the source of
Text.Parsec.Expr might be a bit more understandable.