[antlr-interest] Analysis of fixed repetition loop construct

[Terence Parr]

On Friday, December 7, 2001, at 02:18  AM, Ric Klaren wrote:

> Hi,
>
> On Thu, Dec 06, 2001 at 12:23:08PM -0800, Terence Parr wrote:
>> Hmm...not sure if it's an issue or not.  I just realized though that 
>> the
>> code gen is easy but the analysis might not be so easy to enhance.
>
> Do you have to enhance the analysis. The analysis fase expects a 
> closure.
> So something that repeats a lot of times. The only thing is that by 
> other
> means (a counter and a if break or something) an extra requirement is
> forced upon the closure. I think it should be safe (as long as the type 
> of
> closure matches the bounds)
>
> Or am I missing something here?

Possibly.  The analysis of

a : (ID)+ COLON ;

is very different than

a_ : (ID)+<4> COLON ;

which is really

a_ : ID ID ID ID COLON ;

In the nonspecific case, the k=5 lookahead for 'a' is

{(ID,COLON,EOF,EOF,EOF),
  (ID,ID,COLON,EOF,EOF),
  (ID,ID,ID,COLON,EOF),
  (ID,ID,ID,ID,COLON),
  (ID,ID,ID,ID,ID)}

whereas k=5 lookahead for a_ is exactly *1* k-tuple:

{(ID,ID,ID,ID,COLON)}

So, you can see that there is a big difference between infinite and a 
fixed number.  The "infinitely long sequence" problem is how I came up 
with the user-specified syntactic predicate.  Specifically, I wanted to 
solve this:

a : (A|B)+ C
    | (B)+ D
    ;

I asked "what would solve this from the left edge?"  The obvious answer 
is infinite lookahead so you can see the C or D. (without infinite 
lookahead I couldn't predicate which alternative to choose).  So I 
devised a construct that borrowed from the notion of a predicate, but 
was predicated on syntax not semantics.  Slick.

Interestingly enough, using an "interpreted on-demand analysis 
(runtime)", this is truly easy because you have an exact k sequence to 
tokens to look at.  You don't have to examine all possibilities. :)

Ter
--
Chief Scientist & Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org


 

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