[antlr-interest] Re: Nondeterminism problem

[Oliver Zeigermann]

Terence Parr wrote:

> On Monday, December 15, 2003, at 01:31  AM, Oliver Zeigermann wrote:
> 
>>I guess this is a misunderstanding, Sarah does not claim LALL(k) is a
>>subset of SLL(k), but SLK's algorithm is the only that does practical
>>SLL(k) near computation. ANTLR does approximate LALL(k), so SLK subset
>>ANTLR is not true.
> 
> 
> Hi Oliver,
> 
> Actually "Sarah" does indeed claim SLK is more powerful than any other 
> LL(k) subset:
> 
> "All other practical LL(k) analysis algorithms work on  language 
> classes that are proper subsets of the strong LL(k) languages. "
> 
> I think you'll find that LALL(k) done by PCCTS is a proper *superset*.  
> I don't understand "only one that does practical SLL(k) near 
> computation".  Can you rephrase?  

I browsed around the SLK site a bit and guess SLK *nearly* is able to 
solve the SLL(k) computation in polynomial time instead of exponential. 
As far as I understand it uses the fact SLL(k) computation for any 
*fixed* k is polynomial only. So SLK begins to create a table assuming 
the grammar is SLL(1). If it detects an ambiguity it augments it with 
SLL(2), etc. How does ANTLR do it?

> Again, PCCTS does full LALL(k); my 
> dissertation was how approximate lookahead can be used to attenuate the 
> complexity of computation and storage of lookahead.  This includes 
> weaker parser as well as helping to build full LALL(k) parsers.

Yes, but isn't the creation time for such a parser exponential in 
respect to k?

> Let's see if I can come up with an example that PCCTS will accept, but 
> is not SLL(k).  Ok, this grammar is LALL(1) and even approximate 
> LALL(1), meaning even ANTLR 2 will handle it no sweat.  A Strong LL(k) 
> analysis should find a nondeterminism upon A in rule s's subrule for 
> ANY value of k.  The problem is in the accuracy of lookahead not the 
> depth.
> 
> s : Z (a | ) B ;
> 
> a : A;
> 
> t : X a A ;
> 
> The (a | ) subrule in s needs to see the "local FOLLOW" as B not {A,B} 
> which is the "global FOLLOW" seen by a Strong LL(k) analysis.  Here is 
> the correct prediction for the subrule generated by ANTLR 2.7.2:
> 
>                          switch ( LA(1)) {
>                          case A:
>                          {
>                                  a();
>                                  break;
>                          }
>                          case B:
>                          {
>                                  break;
>                          }
> 
> Duplicating rule a will make this LALL(1) grammar SLL(1) and 
> demonstrates part of the reason LL(k) is exponentially complex in terms 
> of just the parser size (not including lookahead).

Ah, this is interesting. *Obviously this shows LALL' grammars are not a 
subset of SLL grammars*!

What about languages then? As far as I understand from the above there 
is always a way to rephrase your LL grammar to SLL to parse any LL 
language, is this correct? Is it always possible to make a LL grammar 
LALL', parsing the same language? If not the LALL' languages indeed seem 
to be a subset of the SLL languages, right?

Cheers :)

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/