# [antlr-interest] Analysis of fixed repetition loop construct

Terence Parr parrt at jguru.com
Fri Dec 7 13:03:31 PST 2001

```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/

```