[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


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


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


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. :)

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/ 

More information about the antlr-interest mailing list