Return to Contents

Lexing and Parsing

Combinators are provided to build both lexers and parsers. Lexing is less flexible as it does not need to incorporate choices, left recursion, or ambiguity.

Left Recursion

Any form of left recursive grammar will be parsed correctly, without infinite loops.


All possible valid parses of the input by a constructed grammar will be followed and incorporated into the resulting parse graph.

Polynomial Complexity

As per the paper that this library draws most of its ideas from, the worst case complexity involved for both time and space should be polynomial. This has been experimentally confirmed but as of yet no analysis has been done to determine specifics.

Error Messages

If there is a lexer or parser error then a message will be sent with the exception that records what symbols were expected and where they were expected.

Piecewise Parsing

Both lexers and parsers can have their input fed to them piece by piece instead of all at once.