FormalGrammars

(Context-free) grammars in formal language theory

https://github.com/choener/FormalGrammars

Latest on Hackage:0.4.0.0

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

GPL-3.0-only licensed by Christian Hoener zu Siederdissen, 2013-2019
Maintained by [email protected]

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.