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

Oliver Zeigermann oliver at zeigermann.de
Sun Oct 26 05:36:53 PST 2003


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

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

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

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

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. 

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?

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

Oliver :)

--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at j...>
wrote:
> ANTLR's predicated LL(k) parsers can handle a class of languages
that 
> might be hard to nail down.  Because it has backtracking, it could
in 
> theory (backtracking every single decision) handle all context-free 
> grammars.  Because it has semantic predicates it can handle some 
> context-SENSITIVE languages.


 

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




More information about the antlr-interest mailing list