[antlr-interest] Re: Nondeterminism problem

[sarah2geller]

--- In antlr-interest at yahoogroups.com, Oliver Zeigermann 
<oliver at z...> wrote:
> For me it boils down to what is the relation of approximate LALL(k) 
> and SLL(k)? Certainly not SLL(k) superset approximate LALL(k) and 
> also not the other way round. Can someone clarify for me, please?
> 

For the case of k=1, all top-down grammars are equivalent. That is

    LL(1) == SLL(1) == LALL(1)

Only for the case of k>1 does the left context become a factor in the 
strength of the grammar. The difference is subtle, and always depends 
on the lookahead strings. Approximate lookahead has no knowledge of 
strings, only token sets at each k-level. So the distinction between 
LL, LALL, and SLL is meaningless and

    LL'(k) == SLL'(k) == LALL'(k) 

and these are all very small subsets of any of the classical LL 
grammars, including SLL(k).

Put another way, if you convert an exponential number of lookaheads 
to a linear one, would you not expect to lose considerable 
recognition power?

Go back to the original grammar of this thread. It was SLL(2) by 
inspection, yet approximate lookahead could not handle it. 




 

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/