I reimplemented the core Earley parser used by P3. The new version
of the core Earley parser,
earley3, now appears to meet the
desired asymptotic worst-case time complexity of
O(n^3. ln n). The following are some observations on implementing algorithms so that they achieve a given complexity bound.
New versions of P3 are now available from github here. At the moment the documentation is on the github wiki for P3. The documentation is largely out of date.
Old releases of P3 are described here here.
The following draft describes the design of the P3 combinator parsing library.
Tom Ridge. Simple, efficient, sound and complete combinator parsing for all context-free grammars, using an oracle (unpublished draft). ridge13p3_design.pdf. Slides are here (best viewable in firefox, due to latexmathml).