> 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.
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.
What would seem more appropriate would be to cover features of
ANTLRWorks that
are designed to handle problems unique to developing with an LL(*) parser
generator. You could then give mention as to how such problems come about.
Something else that struck me, and seems very relevant to a PEG mailing
list,
was the following sentence.
> "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).
Would I be correct in saying that you made a similar assertion at the
back of
the ANTLR book?
> "Thanks to Bryan Ford, we now have a formal language treatment in the
form of
> PEGs and, most important, the packrat parsing strategy that
guarantees linear
> parse time at the cost of nonlinear memory."
Lastly, I'm not very comfortable with this statement.
> "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 could compare LL(*) to a packrat implementation but I'm not sure it
would
make for much of an analogy.
Orlando
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
