I've been working on a derivative parsing algorithm for PEGs; it only uses memory proportional to the amount of backtracking and grammar nesting (i.e. about the same as recursive descent), but still gives a polynomial worst-case bound on time. An early draft of my paper on it is at [1]; this turned out to be about 6x slower than packrat when I actually built and tested it, but I've come up with a substantial simplification to the algorithm that I'm quite optimistic will have better performance results once I finish debugging my code.

[1] http://arxiv.org/abs/1405.4841