FormalGrammars: (Context-free) grammars in formal language theory

[ bioinformatics, formal-languages, gpl, library ] [ Propose Tags ]

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.


[Skip to Readme]

Flags

Manual Flags

NameDescriptionDefault
examples

build the examples

Disabled
debug

dump intermediate Core files

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.0.0.1, 0.0.0.2, 0.2.0.0, 0.2.1.0, 0.2.1.1, 0.3.0.0, 0.3.1.0, 0.3.1.1, 0.3.1.2, 0.4.0.0
Change log changelog.md
Dependencies ADPfusion (>=0.5.2 && <0.5.3), ansi-wl-pprint (>=0.6.7), base (>=4.7 && <5.0), bytestring (>=0.10), cmdargs (>=0.10), containers, data-default (>=0.5), FormalGrammars, HaTeX (>=3.16), lens (>=4.0), mtl (>=2.0), parsers (>=0.12), PrimitiveArray (>=0.8.0 && <0.8.1), semigroups (>=0.16), template-haskell, text (>=1.0), transformers (>=0.3), trifecta (>=1.6), unordered-containers (>=0.2), vector (>=0.10) [details]
License GPL-3.0-only
Copyright Christian Hoener zu Siederdissen, 2013-2017
Author Christian Hoener zu Siederdissen, 2013-2017
Maintainer choener@bioinf.uni-leipzig.de
Category Formal Languages, Bioinformatics
Home page https://github.com/choener/FormalGrammars
Bug tracker https://github.com/choener/FormalGrammars/issues
Source repo head: git clone git://github.com/choener/FormalGrammars
Uploaded by ChristianHoener at 2017-03-06T19:13:12Z
Distributions
Reverse Dependencies 9 direct, 1 indirect [details]
Executables TriNeedleFG, NeedlemanWunschFG, NussinovFG, GrammarPP
Downloads 8461 total (25 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-03-06 [all 1 reports]

Readme for FormalGrammars-0.3.1.1

[back to package description]

Build Status

FormalGrammars: A DSL for formal languages in Haskell

generalized Algebraic Dynamic Programming Homepage

The gADP homepage has a tutorial and example on how to write algorithms / grammars.

Ideas implemented here are described in a couple of papers:

  1. Christian Hoener zu Siederdissen
    Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
    2012, Proceedings of the 17th ACM SIGPLAN international conference on Functional programming
    paper preprint
  2. Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill.
    The HERMIT in the stream: fusing stream fusion’s concatMap
    2014, Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation.
    paper
  3. Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
    Product Grammars for Alignment and Folding
    2014, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99
    paper
  4. Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler
    Algebraic Dynamic Programming over General Data Structures
    2015, BMC Bioinformatics
    preprint
  5. Maik Riechert, Christian Höner zu Siederdissen, and Peter F. Stadler
    Algebraic dynamic programming for multiple context-free languages
    2015, submitted
    preprint

Contact

Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
choener@bioinf.uni-leipzig.de
http://www.bioinf.uni-leipzig.de/~choener/