[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