[antlr-interest] Re: Nondeterminism problem

[Terence Parr]

On Friday, December 19, 2003, at 09:21 AM, mzukowski at yci.com wrote:

> I can't think of any reason an LL grammar couldn't be one method per 
> rule.
> Do you have a counter example?
>
> My understanding of LALL is that it "simply" collapses the search 
> space for
> lookahead tests at the expense of some accuracy.  I don't see any 
> reason why
> doing that would be related to the one method per rule question.

Hi Monty,

It turns out that, bizarre as it seems, indeed full LL parsers are 
nonlinear in just the grammar not just the lookahead.  Let's turn to a 
tweaked version of my LALL test grammar from previous posts:

s : (a|C) B ;

a : A|; // nondeterministic upon A

t : a A ;

This is non-LALL(1) because the lookahead of alt 2 for 'a' is generic 
global FOLLOW(a)=={A,B}.  The A collides with the first alt.  An LL(1) 
parser generator would handle this no problem.  You can convert this to 
an LALL(1) and SLL(1) grammar by duplicating 'a' as follows:

s : (a|C) B ;

a : A|;

a2 : A|;

t : a2 C ;

That extra contextual information is why full LL grammars are more 
expressive than LALL and SLL and gives you a hint why LL(k) languages 
are the strongest.

Ter
--
Professor Comp. Sci., University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Co-founder, http://www.jguru.com
Co-founder, http://www.knowspam.net enjoy email again!
Co-founder, http://www.peerscope.com pure link sharing




 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

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