FormalGrammars: (Context-free) grammars in formal language theory
This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.
Warnings:
- 'ghc-options: -O2' is rarely needed. Check that it is giving a real benefit and not just imposing longer compile times on your users.
- Exposed modules use unallocated top-level names: FormalLanguage
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]
Properties
| Versions | 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.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-08-31T14:11:23Z |
Modules
[Index]
Flags
Manual Flags
| Name | Description | Default |
|---|---|---|
| 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
- FormalGrammars-0.3.1.2.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
Package maintainers
For package maintainers and hackage trustees
Readme for FormalGrammars-0.3.1.2
[back to package description]
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:
- 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 - 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 - 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 - Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler
Algebraic Dynamic Programming over General Data Structures
2015, BMC Bioinformatics
preprint - 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/