On May 20, 2007, at 4:48 AM, John Leuner wrote:
"The experiment confirmed the author’s expectations. The parser
exhibits
a moderate backtracking activity. The parsing ”time”, expressed as the
number of procedure calls, grows linearly with the input size. A
significant
improvement could be achieved by saving results of one or two most
recent
calls to each parsing procedure. (A thrifty mouse instead of a pack
rat.)
This modification could be comfortably hidden behind the scenes without
destroying the clarity of the primitive parser."
Hi John :)
That paper then differs a bit from my experience. Backtracking
slowed things down quite a bit unless you were very careful when
building your grammar and had LL(k) for k>1 to back you up.
Memoization + LL(*) or LL(k) is a hell of an optimization.
My intuition is that for typical programming languages there will
not be much backtracking.
My experience: for Java, C, etc... you will see a huge amount, even
if it it's fast, because you don't even have LL(1) optimization.
I have done a little bit of work with the PEG grammar for the
contructed language lojban, I didn't make notes but I recall a
fairly significant speedup when adding memoization.
That jives with my experience.
I typed in a Java grammar from spec, cleaning up issues. It never
terminates on some JDK 1.4 input files w/o memoization.
Ter
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
