derp: Derivative Parsing

[ bsd3, library, parsing ] [ Propose Tags ]

A parser based on derivatives of parser combinators (Might and Darais). Our paper on Arxiv details the theory of parsing with derivatives: This implementation uses my latest work on the theory that brings the O(n*|G|^2) complexity bound to O(n) for parsing most not-painfully-ambiguous grammars. (|G| would be the size of the initial grammar, n would be size of the input. These bounds are based off of observation and intuition; they are not proven yet.) This implementation will not terminate if the resulting parse frest is infinite. We know how to extend the implementation to work for infinite parse trees with little effort. If this is something you would like to see, shoot me an email.




Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.1.1, 0.1.2, 0.1.3, 0.1.4, 0.1.5, 0.1.6
Dependencies base (<5), containers [details]
License BSD-3-Clause
Author David Darais
Category Parsing
Uploaded by DavidDarais at 2011-03-02T18:00:22Z
Distributions NixOS:0.1.6
Reverse Dependencies 2 direct, 0 indirect [details]
Downloads 4889 total (10 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]