FormalGrammars

(Context-free) grammars in formal language theory https://github.com/choener/FormalGrammars

Latest on Hackage:0.3.1.1

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 licensed by Christian Hoener zu Siederdissen, 2013-2017

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/

Changes

0.3.1.1

  • removed most upper bounds, and version bumped stuff

0.3.1.0

  • This version only works together with ADPfusion-0.5.2, this update improves performance for all grammars.

0.3.0.0

  • Major change in terminal symbol handling: In 0.2.x.y versions, when you named a terminal (say 'c') then each occurance of 'c' had the same type. This was independent of the tape the symbol occured on. Starting with 0.3.0.0 if you have a terminal with the same name on different tapes, then you will have to give each type explicitly. This requires a bit more typing for homogenous grammars, but makes heterogenous multi-tape grammars much more flexible.

0.2.1.0

  • indexed rules and grammars (revamped system)
  • multi-context free grammars available!
  • new travis.yml

0.2.0.0

  • completely rewritten parsing system
  • makes use of newer ADPfusion 0.4.0
  • travis-ci integration

0.1.0.0

  • fixed dependencies
  • major version bump
  • new TH code generator using ADPfusion 0.3

0.0.0.2

  • cleaned up the TH generator. Should be easier now to build more complex auto-generators

0.0.0.1

  • basic operations on context-free formal grammars.
comments powered byDisqus