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

John D. Mitchell johnm-antlr at non.net
Mon Oct 27 09:24:59 PST 2003


>>>>> "Oliver" == Oliver Zeigermann <oliver at zeigermann.de> writes:
[...]

> I know, this thread is long time dead, but mister know-it-all (=me) feels
> some appetite for some weekendly theoretical quarrel.

We love the pain! :-? 

> After understanding the idea to see parsing as an application of search
> from this book

> http://www.cs.vu.nl/~dick/PTAPG.html

FYI, I haven't read it (yet) but that's certainly one way to look at this
subject.

> I am not so sure any more, if all LR languages can be parsed by a
> backtracking LL parser, even though I thought this before (Terence might
> think so as well?!).

Predicated-LL(k) seems to cover an interesting in-between ground.  To me,
it's the combination of both the syntactic (aka backtracking) predicates
and the semantic predicates that makes predicated-LL(k) so useful.

> 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 :-).

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).


> Now, as LR does some sort of restricted *breadh-first* search it does not
> have these limitations, so I though there may be languages only
> expressible by LR. Of course infinite left recursion can be expressed
> differently, but what about languages that rely on shortest parse
> trees. Are there any imaginable?

Let me throw in my periodic rant that most people usually try to do way too
much in each phase of translation.  For example, look at all of the lexer
hacks that keep getting tried. IMNSHOAM, folks persist in trying to do way
too much in the parsers.  I humbly beseech thee to ponder the utility of
utilizing more phases in your translators.


> Thanks for listening and forbear my figurative way of seeing things, I am
> no theoretician, but a practitioner,

Thanks for bringing this issue back to life.

Take care,
	John


 

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




More information about the antlr-interest mailing list