[antlr-dev] Re: [antlr-interest] generating cyclic state machines in Java

Jeff Barnes jbarnesweb at yahoo.com
Wed Feb 15 23:16:15 PST 2006


Hi everyone,

Please take a look at my take on this problem from a
conceptual standpoint. 

http://www.geocities.com/jbarnesweb/fsmsurvey.pdf

If you like it, I could propose a template to replace
Java.stg.

More below:


--- Terence Parr <parrt at cs.usfca.edu> wrote:

> First, my goals:
> 
> 1. don't create a lot of classes
> 2. don't create a lot of instances

I'm pretty sure one of the models I'm proposing fits
both of those requirements.

> 3. avoid method calls per character just to
> transition

How about InputSymbol? (could be a TokenType wrapper)

> 4. be as small as possible

The smallest possible would probably be a table
lookup. For just a little more size, you get
readability too. ;)

> 
> I thought about just making a huge switch on state
> number that jumped  
> to a CASE:
> 
> switch ( s ) {
>    case 0 : ...
>    case 1 : ...
>    ...
> }

Say it ain't so, Ter...

sigh.

> 
> But, with say 500 states I'm not sure java would do
> this efficiently  
> and it would limit the size of our DFAs due to java
> method size  
> limits.  For states that have semantic predicates
> are truly  
> complicated transitions, we could do this.
> 

Yeah, I just don't buy the switch stuff. Better to
know what you want upfront for me.


> As an optimization, I would like something tight
> like this:
> 
> while ( s != accept state ) {
>    s = states[s][input.LA(1)];
>    if ( s==-1 ) error;
> }
> return predictedAlt[s];

That is a classic Cargill take on state machines, I
believe. Please take a look at the doc and let me know
which way you are leaning.

Regards,
Jeff


=========
Jeff Barnes
(206)245-6100


Few things are impossible to diligence and skill.
--- Samuel Johnson (Rasselas Chap. xii.)


More information about the antlr-interest mailing list