[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