Safe Haskell | None |
---|---|

Language | Haskell98 |

Parser combinators with support for left recursion, following Johnson's "Memoization in Top-Down Parsing".

This implementation is based on an implementation due to Atkey (attached to an edlambda-members mailing list message from 2011-02-15 titled 'Slides for "Introduction to Parser Combinators"').

Note that non-memoised left recursion is not guaranteed to work.

The code contains an important deviation from Johnson's paper: the
check for subsumed results is not included. This means that one can
get the same result multiple times when parsing using ambiguous
grammars. As an example, parsing the empty string using ```
S ∷= ε |
ε
```

succeeds twice. This change also means that parsing fails to
terminate for some cyclic grammars that would otherwise be handled
successfully, such as `S ∷= S | ε`

. However, the library is not
intended to handle infinitely ambiguous grammars. (It is unclear to
the author of this module whether the change leads to more
non-termination for grammars that are not cyclic.)

- data Parser k r tok a
- parse :: Parser k r tok a -> [tok] -> [a]
- token :: Parser k r tok tok
- tok :: Eq tok => tok -> Parser k r tok tok
- sat :: (tok -> Bool) -> Parser k r tok tok
- chainl1 :: Parser k r tok a -> Parser k r tok (a -> a -> a) -> Parser k r tok a
- chainr1 :: Parser k r tok a -> Parser k r tok (a -> a -> a) -> Parser k r tok a
- memoise :: (Eq k, Hashable k) => k -> Parser k r tok r -> Parser k r tok r

# Documentation

data Parser k r tok a Source #

The parser type.

The parameters of the type `Parser k r tok a`

have the following
meanings:

`k`

- Type used for memoisation keys.
`r`

- The type of memoised values. (Yes, all memoised values have to have the same type.)
`tok`

- The token type.
`a`

- The result type.

:: Parser k r tok a | Parser for a thing. |

-> Parser k r tok (a -> a -> a) | Parser for a separator. |

-> Parser k r tok a |

Parses one or more things, separated by separators.

Combines the results in a left-associative way.