On 07-Jul-12 20:56, Chad J wrote:
On 07/07/2012 12:37 PM, Roman D. Boiko wrote:
On Saturday, 7 July 2012 at 16:27:00 UTC, Philippe Sigaud wrote:
Note that PEG does not impose to use packrat parsing, even though it
was developed to use it. I think it's a historical 'accident' that put
the two together: Bryan Ford thesis used the two together.
Note that many PEG parsers do not rely on packrat (Pegged does not).
There are a bunch of articles on Bryan Ford's website by a guy
writting a PEG parser for Java, and who found that storing the last
rules was enought to get a slight speed improvement, buth that doing
anymore sotrage was detrimental to the parser's overall efficiency.
That's great! Anyway I want to understand the advantages and limitations
of both Pegged and ANTLR, and probably study some more techniques. Such
research consumes a lot of time but can be done incrementally along with
development.
Yeah, it's good to hear this notion reinforced. I had this suspicion
that the packrat parser is not necessarily the best/fastest solution,
mostly because of the large allocation that has to happen before you get
O(n) performance. Thus I figured that pegged might eventually use
different parsing strategies underneath it all, possibly with a lot of
special-casing and clever hand-tuned and profiled optimizations. At
least that's what makes sense to me.
Another idea that I've never realized is to add operator precedence
grammar to pegged. Of course it should fit naturally with traditional
PEG, for instance taking responsibility for parsing expressions.
--
Dmitry Olshansky
