The FormalGrammars package

[Tags: gpl, library, program]

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.

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 these papers:

Christian Hoener zu Siederdissen
Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
2012. Proceedings of the 17th ACM SIGPLAN international conference on Functional programming
http://doi.acm.org/10.1145/2364527.2364559 preprint: http://www.tbi.univie.ac.at/newpapers/pdfs/TBI-p-2012-2.pdf
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.
http://dl.acm.org/citation.cfm?doid=2543728.2543736
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.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6819790
Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler.
Algebraic Dynamic Programming over General Data Structures.
2015. submitted.

Properties

Versions0.0.0.1, 0.0.0.2, 0.2.0.0
Change logchangelog.md
DependenciesADPfusion (==0.4.0.*), ansi-wl-pprint (==0.6.7.*), base (>=4.7 && <4.9), bytestring (==0.10.*), cmdargs (==0.10.*), containers, data-default (==0.5.*), FormalGrammars, HaTeX (==3.16.*), lens (==4.*), mtl (==2.*), parsers (==0.12.*), PrimitiveArray (==0.6.0.*), semigroups (==0.16.*), template-haskell, text (==1.*), transformers (>=0.3 && <0.5), trifecta (==1.5.*), unordered-containers (==0.2.*), vector (==0.10.*)
LicenseGPL-3
CopyrightChristian Hoener zu Siederdissen, 2013-2015
AuthorChristian Hoener zu Siederdissen, 2013-2015
Maintainerchoener@bioinf.uni-leipzig.de
Stabilityexperimental
CategoryFormal Languages, Bioinformatics
Home pagehttp://www.bioinf.uni-leipzig.de/Software/gADP/
Source repositoryhead: git clone git://github.com/choener/FormalGrammars
ExecutablesNeedlemanWunschFG, NussinovFG, GrammarPP
UploadedThu May 7 15:04:58 UTC 2015 by ChristianHoener
DistributionsNixOS:0.2.0.0
Downloads502 total (40 in last 30 days)
StatusDocs available [build log]
Last success reported on 2015-05-07 [all 1 reports]

Modules

[Index]

Flags

NameDescriptionDefault
examplesbuild the examplesDisabled
llvmbuild using LLVMDisabled
debugdump intermediate Core filesDisabled

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

Downloads

Maintainers' corner

For package maintainers and hackage trustees