[antlr-interest] THEORY / WAS: antlr vs. sableCC comparison

[Oliver Zeigermann]

John D. Mitchell wrote:
>>Even in guessing mode ANTLR can only do backtracking *depth-first*
>>search. This limitation is tied to the fact that ANTLR generates
>>recursive descent code. There is no way to implement e.g.
>>*breadth-first* with ordinary stack frames. Because of this depth-first
>>approach ANTLR guessing has the same limitations as depth-first search:
>>you may not find the optimal solution or may you may not find a solution
>>at all, although one exists. Applied to parsing the second limitation can
>>be observed with inifite left recursive stuff, the first may occur when
>>you have an ambiguous grammar, i.e. more than one parse tree or more than
>>one solution to the search.
> 
> 
> This gets into a morass of what "optimal" means (which almost instantly
> devolves into a question of who is defining what "optimal" means :-).

Well, I could have said, goal nearest to the root or "shortest parse 
tree"...

> That is, one of the key points of LL in general is that the grammar is
> really (trying to) express what we expect to see and then tries to match
> the input against those expectations.
> 
> Predicated-LL deals with syntactic and contextual ambiguities by allowing
> us (the grammar developers) to specify strong "preferences" (if you will)
> as to how we want our expectations to be met in the face of (certain types
> of) ambiguities.
> 
> Indeed, given the static nature of the language grammars, we are, perforce,
> forced to specify, a priori, a basically static ordering to our
> preferences.  Addressing this facet more dynamically is how I would
> characterize what Ter's playing with for ANTLR 3.0 (at least given the
> talks he and I had low, way too many moons ago now).

Hmmm, well, hmmm, I was much more thinking of a really theoretical 
thing. You see, I like ANTLR and prefer it over any LR-stuff, I was just 
wondering where the *theoretical* limitations are.

Oliver



 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/