On Jul 10, 2007, at 8:45 AM, Orlando wrote:
> First 40% is about LL(*) lookahead DFA and parsers. Best description
> so far. Includes discussion of how LL(*) is an optimization to PEG
> etc... Thanks to Bryan Ford and Sylvain Schmitz for their excellent
> help on the paper.
Hi, Terence.
I guess, I have a few misgivings about the paper in its current form.
To me, the content isn't quite as focused as it could be. I think
trying to
discuss a parsing algorithm, in depth, is slightly out of place in
a paper
about a graphical tool for grammar writing.
Hi Orlando :)
Unfortunately, I was responding to the reviewers that said "we
assumed intimate knowledge of antlr". W/o a discussion of LL(*),
AW's visualization of it is meaningless. It's like a ball of yarn
though. Each time I pull a string to explain it, it pulls out more
string to explain. I figured: what the hell--I'll just summarize it.
I understand that you want to have something published on LL(*) but
the paper
would seem better served with most of the discussion in section 2
omitted.
that was the original paper ;)
> "Ford also introduced packrat parsing that reduces the worst-case
exponential
> time complexity of backtracking to linear complexity by memoizing
partial
> parsing results at the cost of a potentially exponential heap."
What are you talking about when you say exponential heap? With the
most naive
implementation possible, the largest your memoization heap could be
is (n * m).
That's linear!
Not O(n log n), not O(n^2), not O(n^3), not O(n^m) and certainly
not O(m^n).
Ah! You are so right! What the hell was I thinking. It slipped
past Bryan too! Crap. I'll fix. thanks.
Would I be correct in saying that you made a similar assertion at
the back of
the ANTLR book?
Shoot. Probably. Got focused on the exponential runtime I guess.
Ugh. This is why I should stick to coding ;)
> "The effciency of ANTLR’s mechanism over pure PEG is analogous to
GLR’s
> effciency over Earley’s algorithm."
The key problem here is that your comparing apples with oranges. As
with LL(*),
GLR and Earley are both parsing algorithms, it's very appropriate
to compare
them. 'pure PEG', on the other hand, doesn't even make sense. PEGs
are a form of
grammar notation. They're not a particular algorithm.
You're right. Should be packrat parsing not PEG.
You could compare LL(*) to a packrat implementation but I'm not
sure it would
make for much of an analogy.
Really? Both are parsing algorithms. You could test on same input
like Grimm did in his work. Are you afraid packrat is slower and
requires more heap than my predictive+packrat? ;) Packrat backtracks
always...I only do that if predictive cyclic DFAs fail. Grimm's
Rats! is AMAZING in how fast it goes but I think I'm still
winning. ;) At the very least I can deal with stateful actions
better when not backtracking.
Ter
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
