# A little Earley parser

Parser for context-free grammars.

## Example

The following module defines a grammar for arithmetic expressions
(like `1+2*3`

). It defines:

- A type of non-terminal symbols
`Ns`

.
- A type of terminal symbols
`Ts`

.
- The production rules of the grammar
`arithRules`

.
- A matching function, which interprets terminal symbols
`Ts`

as sets of
lexemes, of type `Char`

here.
- A grammar
`arithG`

packaging up all of the above.

```
import Data.Char (isDigit)
import Little.Earley
data Ns = SUM | PRODUCT | FACTOR | NUMBER deriving (Eq, Ord, Enum, Bounded, Show)
data Ts = Digit | OneOf [Char] deriving (Eq, Ord, Show)
arithRules :: Ns -> [Rule Ns Ts]
arithRules n = case n of
SUM ->
[ [ N PRODUCT ]
, [ N SUM, T (OneOf ['+', '-']), N PRODUCT ] ]
PRODUCT ->
[ [ N FACTOR ]
, [ N PRODUCT, T (OneOf ['*', '/']), N FACTOR ] ]
FACTOR ->
[ [ N NUMBER ]
, [ T (OneOf ['(']), N SUM, T (OneOf [')']) ] ]
NUMBER ->
[ [ T Digit ]
, [ T Digit, N NUMBER ] ]
matchTs :: Ts -> Char -> Bool
matchTs Digit = isDigit
matchTs (OneOf s) = (`elem` s)
arithG :: Grammar Ns Ts Char
arithG = mkGrammar arithRules matchTs
```

Load that file in GHCi:

```
ghci -package little-earley example.hs
```

Parse a string using that grammar:

```
> pparse arithG SUM "1+2*3"
```

Output:

```
+-----+--SUM #1---+
| | |
SUM #0 | +PRODUCT #1-+
| | | | |
PRODUCT #0 | PRODUCT #0 | |
| | | | |
FACTOR #0 | FACTOR #0 | FACTOR #0
| | | | |
NUMBER #0 | NUMBER #0 | NUMBER #0
| | | | |
-----------------------------------
1 + 2 * 3
```

The module `Little.Earley.Examples`

contains more examples of grammars using
this library.

## Links

- This Earley parser implementation is based on
Loup Vaillant's tutorial.
- See also the Earley library
also in Haskell, with much fancier types to encode arbitrary semantic actions
instead of clumsy trees.