[antlr-interest] packrat vs. LL(*)
Jim Idle
jimi at temporal-wave.com
Mon Jun 8 12:54:15 PDT 2009
Steven Obua wrote:
>>> It is really just a parsing question, the whole lexing issue is
>>> besides the point. Note that you can have ANTLR grammars without a
>>> lexer, just as in a packrat grammar.
>>>
>> No, it isn't. Even if you put your rules into 'literals'', ANTLR
>> still produces a lexer; it isn't syntax directed lexing. However, if
>> you have 'literals' only, then you should not end up with a an
>> ambiguous lexer. The problems come from people turning on
>> backtracking without a thought and just randomly typing; a good
>> parser just doesn't happen that way :-)
>>
>
> Yes it is :-) I am not talking about an ambiguous lexer, but about an
> ambiguous grammar.
You need to distinguish between ambiguous grammar and ambiguous language.
> And ambigous grammars can be made non-ambiguous by forcing an order on
> rules. This is what backtracking does, and this is what packrat
> parsing does.
I think you probably need to read and experience a bit more before
making such bold statements. I don't think you appreciate the differences.
>
> My parser is pretty good right know, I am very happy with it :-)
> Your comments imply that you think packrat grammars are not good
> grammars.
They might, if I was addressing questions about packrat grammars, but I
am not, we are talking about grammars written with backtrack=true, and
basically yes, they are not good grammars. The main reason is to do with
error identification.
> People which accepted the packrat parsing paper at POPL, one of the
> most respected conferences in computer science, seem to think different.
Your statement would be valid if they had accepted a paper about ANTLR
backtrack=true and further if you were not taking the paper as
justification for using the approach on your particular task, without
telling us what that task is and why, in this case, the approach is
sensible (which it may indeed be). The paper does not say "Oh, just go
ahead and do it this way all the time", it is about the approach itself.
With a bit of up front effort it is usually much more time efficient
(when using ANTLR) to write a good left factored grammar. Please
remember this statement later when you are trying to track down where
things are going wrong in your ambiguous grammar :-)
Jim
More information about the antlr-interest
mailing list