[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

--- In antlr-interest at yahoogroups.com, "sarah2geller"
<sarah2geller at y...> wrote:
> --- 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).

Could you explain why this is the case? Maybe it is obvious, but I do
not see why LALL'(k) subset 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?

Of course, but this only is an argument for LL'(k) subset LL(k), isn't it?

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

I got that, but this does not prove LALL'(k) subset SLL(k). It only
proves SLL(k) not subset LALL'(k), but not the other way round.

Anyway, thanks for taking it this far! I really appreciate that :)

Oliver


 

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/