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.
Thanks,
Aaron Moss
[1] http://arxiv.org/abs/1405.4841
[2] https://github.com/bruceiv/egg/tree/deriv
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
