[antlr-interest] Re: antlr vs. sableCC comparison

[Terence Parr]

On Sunday, May 25, 2003, at 03:18  AM, Oliver Zeigermann wrote:

> --- 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.
>
> It seems you forgot about left recursion in grammars which can not
> be handled with ANTLR or any other top down approach.

Ooops..you're right.  Minus 5 points. ;)  Of course, you can actually 
do some left recursive grammars by adding semantic predicates.  I 
parsed the usual yacc expression grammar once with predicates on the 
left edge to know how many times to recurse to get the right 
precedence.  Recall that left recursion is only bad if it is 
*infinite*. ;)

>  Also, what
> about ambigous grammars? ANTLR hardly generates more than a single
> parse tree ;)

Too true.  Ambiguous grammars will always result in a nondeterministic 
LL or LR parser unless you add some form of tracking multiple paths 
like tomita.

> Of course, as I also admitted, ANTLR can handle all context free
> *languages* (not *grammars*).
>
> I think the question is not the class of languages you can parse -
> as with ANTLR I am pretty sure (even though I can not proove it) it
> is phrase structure languages - but the way you can express it.
> Using no tool at all, but a turing machine, you can just as well
> parse phrase-structure languages. So what is the use of a tool like
> ANTLR? It is the elegant way to describe the language using a
> grammar. So, the question is what kind of grammar can you use to
> describe the language. If this question was not important why using
> LL(k>1) grammars? You can always left factor, so LL(k) can never
> describe a language you can not describe by LL(k-1).

Actually I believe there are *languages* that are LL(k) but not 
LL(k-1).  The same is not true for LR.  LR(k) is same as LR(k-1) 
languages and grammars.  Just saw that lemma in a book I think ;)

> The answer is
> convenience. A LL(k) grammar might be much more readble than a LL(k-
> 1) one.

That is certainly true ;)  Again, though for grammars it is certain 
that LL(k) is stronger and I believe even for languages LL(k) is 
stronger than LL(k-1).

Ter
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Co-founder, http://www.peerscope.com link sharing, pure-n-simple
Lecturer in Comp. Sci., University of San Francisco


 

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