Hello, On Tue, May 20, 2014 at 11:36 AM, Aaron Moss <a3m...@uwaterloo.ca> wrote: > Good day all, > I've developed a new PEG parsing algorithm, and have an early paper draft > on arXiv[1]. This work is still in a fairly early stage, though I do have > working code on Github[2]. If anyone could give me some feedback on the > paper and/or suggested publication venues I would really appreciate it; I'm > still working on empirical performance results, but should have some within > a month or two. > > The algorithm is a derivative parsing algorithm, based on the derivative > parsing algorithm for CFGs of Might, Darais & Spiewak. Unlike the algorithm > of Might et al., the worst case time and space bounds are polynomial. The > bounds are quartic time and cubic space, unfortunately, though I think the > practical performance will be closer to the roughly linear time and constant > space acheived by the cut-augmented packrat parsing of Mizushima et al. > > The paper has only been minimally edited, the empirical results necessary > to back up my conjectures about the performance are still forthcoming, and > the current version of the code is largely unoptimized, but I'd appreciate > any feedback anyone has, or suggestions for publication venues. >
I will look at this paper carefully... I have recently made a fork of parboiled (also a PEG package; the difference is that you write your rules entirely in Java and don't need preprocessing) and the theory behind PEGs and parsing in general still eludes me. Regards, -- Francis Galiegue, fgalie...@gmail.com, https://github.com/fge JSON Schema in Java: http://json-schema-validator.herokuapp.com Parsers in pure Java: https://github.com/parboiled1/grappa (redde Caesaris: https://github.com/sirthias) _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
