Ambiparse

Ambiparse is an embedded Clojure DSL that provides parsing for very rich grammars including ambiguity and adaptability.

Overview

Ambiparse is capable of parsing any context free language, including both left-and-right recursive grammars, as well as ambiguous grammars. The parser is capable of returning a parse tree for ambiguous parses. Furthermore, grammar productions can be modified during parsing, allowing langauges to express arbitrary syntax extensions. This means that the parser is actually capable of parsing many context-sensitive grammars as well.

Ambiguity can be reduced or eliminated from grammars with "disambiguation filters", which allow for declarative operator associativity and precedence, as well as filtering by arbitrary predicates.

Being an embedded DSL enables inline semantic actions. Semantic actions can rewrite concrete syntax trees at parse time in to arbitrary abstract syntax trees, or even perform simple interpretation.

To the best of my knowledge, this confluence of features is novel.

Usage

Ambiparse is still very early days, so no release has been published, and a metric ton of documentation is yet to be written. This project was built to serve a higher-priority project, so it may be a while, if ever, that this changes.

See the calculator and edn parser test code for examples.

The public API is provided by ambiparse.clj exclusively.

Note that performance is expectedly awful. This too may never change.

References

GLL Parsing by Scott and Johnstone.
Disambiguation Filters for Scannerless Generalized LR Parsers
by M.G.J. van den Brand et al.
Faster, Practical GLL Parsing by Afroozeh and Izmaylova.
Recursive Adaptable Grammars by John Shutt.

Acknowledgements

Thanks to Mark Engelberg for Instaparse, an excellent library that you probably should use over Ambiparse, his talk which is an excellent explanation of the GLL algorithm, as well as several excellent discussions on the finer points of the algorithm's implementation.