[antlr-interest] Re: Local lookahead depth

lgcraymer lgc at mail1.jpl.nasa.gov
Sat Nov 8 22:44:29 PST 2003


--- In antlr-interest at yahoogroups.com, Oliver Zeigermann 
<oliver at z...> wrote:
> Hi Loring!
> 
> lgcraymer wrote:
> > ANTLR is actually quite a bit smarter about lookahead--k is 
maximum lookahead, and ANTLR generates minimum lookahead.  If you 
> > set k=20 but don't need more than k=2, then 2 is the maximum 
lookahead in the generated code.  I think that Sriram put local 
> > lookahead into JavaCC as a workaround--it does add a step to 
grammar debugging that is not necessary for ANTLR.
> 
> Hmmm. Is this true? Definitly not when using greedy blocks... Have 
a 
> look at this simple grammar
> 
> top : TOKEN0 (sub | top )* TOKEN3 ;
> 
> sub : TOKEN1
>          ( options {greedy=false;} : . )*
>          TOKEN2
>      ;
> 
> k=1 is needed and works ok. Try using k=10 and: Ooops!

Oliver--

I have to say that the greedy option is a hack, originally intended 
for use in the lexer.  Also, loop analysis is flawed in the current 
ANTLR--exit predicates don't work on * loops. I'm not surprised that 
this example fails.

> > Also, as to actions in lookahead code:  this is something that 
Ter supported in PCCTS under the name "guarded predicates" or some 
> > such.  I don't know that it saw much use, and I suspect that 
usage indicates a too early incorporation of semantic information 
into the 
> > translator--tree transformation helps avoid that.
> 
> 1.) You might really increase the set of parseable languages using 
this 
> technique

Possible, but I don't really see how.  You would have to have 
extreme interdependency between semantics and syntax at the very 
least.

> 2.) Sometimes using tree transformation is too expensive

Sometimes it is overkill (unnecessary development), but too 
expensive?  I doubt it, especially for languages where lexing and 
parsing are complex.  [BTW, my experience is that unsubstantiated 
performance arguments are usually bogus and made in an attempt to 
subjectively win an argument that cannot be won on the basis of 
objective evidence.]

> > LLK is interesting, but it is a synthesis of implementation 
approaches from a number of sources (ANTLR, JavaCC, flex) and not an 
> > extension to the state of the art.  I think that's why Leung 
describes it as an ANTLR 2.7.2 derivative despite what seems to be 
the 
> > complete absence of any ANTLR 2.7.2 source code in the 
distribution.  It is also a work in progress.
> 
> Who knows ;) In any case it brings a bit life into discussion :)

It would be nice if Leung showed up on this list.  I disagee with 
his choice of syntax, but it would be interesting why he felt 
strongly enough about it to do the implementation.

--Loring

> Oliver


 

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




More information about the antlr-interest mailing list