[antlr-interest] generating cyclic state machines in Java

[Matt Benson]

Not much to add here, and am interested to see what
else Jeff says, but I seriously doubt Java would wipe
the contents of arrays for which initial values are
provided... working on the assumption that over the
ten years of Java's evolution somebody smarter than I
has touched each of the major JREs...

-Matt

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

> Hi Jeff,
> 
> Well, I'm not sure I fully understand what you have,
> but while  
> sitting in the beautiful California sun today I
> thought about how I  
> would redo them.  Perhaps this is similar to what
> you would suggest.
> 
> First, my goals:
> 
> 1. don't create a lot of classes
> 2. don't create a lot of instances
> 3. avoid method calls per character just to
> transition
> 4. be as small as possible
> 
> I thought about just making a huge switch on state
> number that jumped  
> to a CASE:
> 
> switch ( s ) {
>    case 0 : ...
>    case 1 : ...
>    ...
> }
> 
> 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.
> 
> 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];
> 
> which works well enough for 8 bits. Actually when
> the range from low  
> to high of the edge labels is > threshold then you'd
> decide the array  
> would be too big and you resort to another case in
> your switch.  So  
> for single char labels very high into the unicode
> range, you could  
> still use this approach.  You need min/max arrays
> too:
> 
> while ( s != accept state ) {
>    c = input.LA(1);
>    if ( c>max[s] ) error;
>    s = states[s][c-min[s]];
>    if ( s==-1 ) error;
> }
> return predictedAlt[s];
> 
> For most states then, you could do this fast scheme
> and then resort  
> to a big switch for the others or even use methods
> for s0(), s32(),  
> etc.. and jump to them to reduce the size of the
> method containing  
> the switch.
> 
> Do you see any problems with this?
> 
> One could be defining the stuff; java does
> what...ok, web says I can  
> do this:
> 
> int dfa1_min[] = {...};
> int dfa1_max[] = {...};
> ...
> int dfa1_states[][] = {
> 	{ 0,0,0,3,0,2,0,... }, // state 1 transitions where
> on char x?
> 	{ ... },			// state 2
> 	...
> };
> 
> Java creates an array of arrays, which is a lot of
> objects and  
> hopefully it doesn't wipe to 0 first and then add
> these default  
> values. :(
> 
> Anybody have experience with this in Java?
> 
> Ter
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com