generalized Algebraic Dynamic Programming
Context-free grammars in formal language theory are sets of production rules,
non-terminal and terminal symbols. This library provides basic data types and
functions to manipulate such grammars.
Grammars can be defined in a small domain-specific language that is very close to
typical CFG notation. The DSL parser can easily be extended. Grammar products, for
example, are implemented as a single additional sub-parser.
This library also provides the machinery that transforms an Inside grammar into the
corresponding Outside grammar.
Starting with version 0.2.1 it is possible to write multiple context-free grammars
within this framework.
In addition, TemplateHaskell and QuasiQuoting functionality allow embedding thusly
defined grammars in Haskell programs. ADPfusion then turns such a grammar into an
efficient dynamic program. It is also possible to generate Haskell modules that
contain the resulting grammar, signature and algebra product.
Alternatives are ansi- or LaTeX-based pretty-printing for users that want to
implement their CFG in another language than Haskell.
Formal background can be found in a number of papers which are given in the README.