Java > Open Source Codes > JFlex > DFA


1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2  * JFlex 1.4.1 *
3  * Copyright (C) 1998-2004 Gerwin Klein <lsf@jflex.de> *
4  * All rights reserved. *
5  * *
6  * This program is free software; you can redistribute it and/or modify *
7  * it under the terms of the GNU General Public License. See the file *
8  * COPYRIGHT for more information. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License along *
16  * with this program; if not, write to the Free Software Foundation, Inc., *
17  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
18  * *
19  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
20
21 package JFlex;
22
23
24 import java.io.*;
25 import java.util.*;
26
27
28 /**
29  * DFA representation in JFlex.
30  * Contains minimization algorithm.
31  *
32  * @author Gerwin Klein
33  * @version JFlex 1.4.1, $Revision: 2.7 $, $Date: 2004/11/06 23:03:31 $
34  */
35 final public class DFA {
36
37   /**
38    * The initial number of states
39    */
40   private static final int STATES = 500;
41   
42   /**
43    * The code for "no target state" in the transition table.
44    */
45   public static final int NO_TARGET = -1;
46
47   /**
48    * table[current_state][character] is the next state for <code>current_state</code>
49    * with input <code>character</code>, <code>NO_TARGET</code> if there is no transition for
50    * this input in <code>current_state</code>
51    */
52   int [][] table;
53
54
55   /**
56    * <code>isFinal[state] == true</code> <=> the state <code>state</code> is
57    * a final state.
58    */
59   boolean [] isFinal;
60
61   /**
62    * <code>isPushback[state] == true</code> <=> the state <code>state</code> is
63    * a final state of an expression that can only be matched when followed by
64    * a certain lookaead.
65    */
66   boolean [] isPushback;
67
68
69   /**
70    * <code>isLookEnd[state] == true</code> <=> the state <code>state</code> is
71    * a final state of a lookahead expression.
72    */
73   boolean [] isLookEnd;
74
75
76   /**
77    * <code>action[state]</code> is the action that is to be carried out in
78    * state <code>state</code>, <code>null</code> if there is no action.
79    */
80   Action [] action;
81
82   /**
83    * lexState[i] is the start-state of lexical state i
84    */
85   int lexState [];
86
87   /**
88    * The number of states in this DFA
89    */
90   int numStates;
91
92
93   /**
94    * The current maximum number of input characters
95    */
96   int numInput;
97     
98
99   /**
100    * all actions that are used in this DFA
101    */
102   Hashtable usedActions = new Hashtable();
103
104   public DFA(int numLexStates, int numInp) {
105     numInput = numInp;
106     
107     int statesNeeded = Math.max(numLexStates, STATES);
108     
109     table = new int [statesNeeded] [numInput];
110     action = new Action [statesNeeded];
111     isFinal = new boolean [statesNeeded];
112     isPushback = new boolean [statesNeeded];
113     isLookEnd = new boolean [statesNeeded];
114     lexState = new int [numLexStates];
115     numStates = 0;
116
117     for (int i = 0; i < statesNeeded; i++) {
118       for (char j = 0; j < numInput; j++)
119           table [i][j] = NO_TARGET;
120     }
121   }
122
123
124   public void setLexState(int lState, int trueState) {
125     lexState[lState] = trueState;
126   }
127
128   private void ensureStateCapacity(int newNumStates) {
129     int oldLength = isFinal.length;
130     
131     if ( newNumStates < oldLength ) return;
132       
133     int newLength = oldLength*2;
134     while ( newLength <= newNumStates ) newLength*= 2;
135
136     boolean [] newFinal = new boolean [newLength];
137     boolean [] newPushback = new boolean [newLength];
138     boolean [] newLookEnd = new boolean [newLength];
139     Action [] newAction = new Action [newLength];
140     int [] [] newTable = new int [newLength] [numInput];
141     
142     System.arraycopy(isFinal,0,newFinal,0,numStates);
143     System.arraycopy(isPushback,0,newPushback,0,numStates);
144     System.arraycopy(isLookEnd,0,newLookEnd,0,numStates);
145     System.arraycopy(action,0,newAction,0,numStates);
146     System.arraycopy(table,0,newTable,0,oldLength);
147   
148     int i,j;
149   
150     for (i = oldLength; i < newLength; i++) {
151       for (j = 0; j < numInput; j++) {
152         newTable[i][j] = NO_TARGET;
153       }
154     }
155
156     isFinal = newFinal;
157     isPushback = newPushback;
158     isLookEnd = newLookEnd;
159     action = newAction;
160     table = newTable;
161   }
162
163
164   public void setAction(int state, Action stateAction) {
165     action[state] = stateAction;
166     if (stateAction != null) {
167       isLookEnd[state] = stateAction.isLookAction();
168       usedActions.put(stateAction,stateAction);
169     }
170   }
171   
172   public void setFinal(int state, boolean isFinalState) {
173     isFinal[state] = isFinalState;
174   }
175
176   public void setPushback(int state, boolean isPushbackState) {
177     isPushback[state] = isPushbackState;
178   }
179
180
181   public void addTransition(int start, char input, int dest) {
182     int max = Math.max(start,dest)+1;
183     ensureStateCapacity(max);
184     if (max > numStates) numStates = max;
185
186     // Out.debug("Adding DFA transition ("+start+", "+(int)input+", "+dest+")");
187
188     table[start][input] = dest;
189   }
190
191
192
193   public String toString() {
194     StringBuffer result = new StringBuffer ();
195
196     for (int i=0; i < numStates; i++) {
197       result.append("State ");
198       if ( isFinal[i] ) result.append("[FINAL] "); // (action "+action[i].priority+")] ");
199 if ( isPushback[i] ) result.append("[PUSH] ");
200       result.append(i+":"+Out.NL);
201      
202       for (char j=0; j < numInput; j++) {
203           if ( table[i][j] >= 0 )
204             result.append(" with "+(int)j+" in "+table[i][j]+Out.NL);
205       }
206     }
207     
208     return result.toString();
209   }
210   
211   
212   public void writeDot(File file) {
213     try {
214       PrintWriter writer = new PrintWriter(new FileWriter(file));
215       writer.println(dotFormat());
216       writer.close();
217     }
218     catch (IOException e) {
219       Out.error(ErrorMessages.FILE_WRITE, file);
220       throw new GeneratorException();
221     }
222   }
223
224
225   public String dotFormat() {
226     StringBuffer result = new StringBuffer ();
227
228     result.append("digraph DFA {"+Out.NL);
229     result.append("rankdir = LR"+Out.NL);
230
231     for (int i=0; i < numStates; i++) {
232       if ( isFinal[i] || isPushback[i] ) result.append(i);
233       if ( isFinal[i] ) result.append(" [shape = doublecircle]");
234       if ( isPushback[i] ) result.append(" [shape = box]");
235       if ( isFinal[i] || isPushback[i] ) result.append(Out.NL);
236     }
237
238     for (int i=0; i < numStates; i++) {
239       for (int input = 0; input < numInput; input++) {
240           if ( table[i][input] >= 0 ) {
241           result.append(i+" -> "+table[i][input]);
242           result.append(" [label=\"["+input+"]\"]"+Out.NL);
243           // result.append(" [label=\"["+classes.toString(input)+"]\"]\n");
244 }
245       }
246     }
247
248     result.append("}"+Out.NL);
249
250     return result.toString();
251   }
252
253
254   // check if all actions can actually be matched in this DFA
255 public void checkActions(LexScan scanner, LexParse parser) {
256     EOFActions eofActions = parser.getEOFActions();
257     Enumeration l = scanner.actions.elements();
258
259     while (l.hasMoreElements()) {
260       Object next = l.nextElement();
261       if ( !next.equals(usedActions.get(next)) && !eofActions.isEOFAction(next) )
262         Out.warning(scanner.file, ErrorMessages.NEVER_MATCH, ((Action) next).priority-1, -1);
263     }
264   }
265
266
267   /**
268    * Implementation of Hopcroft's O(n log n) minimization algorithm, follows
269    * description by D. Gries.
270    *
271    * Time: O(n log n)
272    * Space: O(c n), size < 4*(5*c*n + 13*n + 3*c) byte
273    */
274   public void minimize() {
275     Out.print(numStates+" states before minimization, ");
276
277     if (numStates == 0) {
278       Out.error(ErrorMessages.ZERO_STATES);
279       throw new GeneratorException();
280     }
281
282     if (Options.no_minimize) {
283       Out.println("minimization skipped.");
284       return;
285     }
286
287     // the algorithm needs the DFA to be total, so we add an error state 0,
288 // and translate the rest of the states by +1
289 final int n = numStates+1;
290
291     // block information:
292 // [0..n-1] stores which block a state belongs to,
293 // [n..2*n-1] stores how many elements each block has
294 int [] block = new int[2*n];
295
296     // implements a doubly linked list of states (these are the actual blocks)
297 int [] b_forward = new int[2*n];
298     int [] b_backward = new int[2*n];
299
300     // the last of the blocks currently in use (in [n..2*n-1])
301 // (end of list marker, points to the last used block)
302 int lastBlock = n; // at first we start with one empty block
303 final int b0 = n; // the first block
304
305     // the circular doubly linked list L of pairs (B_i, c)
306 // (B_i, c) in L iff l_forward[(B_i-n)*numInput+c] > 0 // numeric value of block 0 = n!
307 int [] l_forward = new int[n*numInput+1];
308     int [] l_backward = new int[n*numInput+1];
309     int anchorL = n*numInput; // list anchor
310
311     // inverse of the transition table
312 // if t = inv_delta[s][c] then { inv_delta_set[t], inv_delta_set[t+1], .. inv_delta_set[k] }
313 // is the set of states, with inv_delta_set[k] = -1 and inv_delta_set[j] >= 0 for t <= j < k
314 int [] [] inv_delta = new int[n][numInput];
315     int [] inv_delta_set = new int [2*n*numInput];
316
317     // twin stores two things:
318 // twin[0]..twin[numSplit-1] is the list of blocks that have been split
319 // twin[B_i] is the twin of block B_i
320 int [] twin = new int[2*n];
321     int numSplit;
322
323     // SD[B_i] is the the number of states s in B_i with delta(s,a) in B_j
324 // if SD[B_i] == block[B_i], there is no need to split
325 int [] SD = new int[2*n]; // [only SD[n..2*n-1] is used]
326
327
328     // for fixed (B_j,a), the D[0]..D[numD-1] are the inv_delta(B_j,a)
329 int [] D = new int[n];
330     int numD;
331
332     
333     // initialize inverse of transition table
334 int lastDelta = 0;
335     int [] inv_lists = new int[n]; // holds a set of lists of states
336 int [] inv_list_last = new int[n]; // the last element
337 for (int c = 0; c < numInput; c++) {
338       // clear "head" and "last element" pointers
339 for (int s = 0; s < n; s++) {
340         inv_list_last[s] = -1;
341         inv_delta[s][c] = -1;
342       }
343       
344       // the error state has a transition for each character into itself
345 inv_delta[0][c] = 0;
346       inv_list_last[0] = 0;
347
348       // accumulate states of inverse delta into lists (inv_delta serves as head of list)
349 for (int s = 1; s < n; s++) {
350         int t = table[s-1][c]+1;
351
352         if (inv_list_last[t] == -1) { // if there are no elements in the list yet
353 inv_delta[t][c] = s; // mark t as first and last element
354 inv_list_last[t] = s;
355         }
356         else {
357           inv_lists[inv_list_last[t]] = s; // link t into chain
358 inv_list_last[t] = s; // and mark as last element
359 }
360       }
361
362       // now move them to inv_delta_set in sequential order,
363 // and update inv_delta accordingly
364 for (int s = 0; s < n; s++) {
365         int i = inv_delta[s][c]; inv_delta[s][c] = lastDelta;
366         int j = inv_list_last[s];
367         boolean go_on = (i != -1);
368         while (go_on) {
369           go_on = (i != j);
370           inv_delta_set[lastDelta++] = i;
371           i = inv_lists[i];
372         }
373         inv_delta_set[lastDelta++] = -1;
374       }
375     } // of initialize inv_delta
376
377     // printInvDelta(inv_delta, inv_delta_set);
378
379     // initialize blocks
380
381     // make b0 = {0} where 0 = the additional error state
382 b_forward[b0] = 0;
383     b_backward[b0] = 0;
384     b_forward[0] = b0;
385     b_backward[0] = b0;
386     block[0] = b0;
387     block[b0] = 1;
388
389     for (int s = 1; s < n; s++) {
390       // System.out.println("Checking state ["+(s-1)+"]");
391 // search the blocks if it fits in somewhere
392 // (fit in = same pushback behavior, same finalness, same lookahead behavior, same action)
393 int b = b0+1; // no state can be equivalent to the error state
394 boolean found = false;
395       while (!found && b <= lastBlock) {
396         // get some state out of the current block
397 int t = b_forward[b];
398         // System.out.println(" picking state ["+(t-1)+"]");
399
400         // check, if s could be equivalent with t
401 found = (isPushback[s-1] == isPushback[t-1]) && (isLookEnd[s-1] == isLookEnd[t-1]);
402         if (found) {
403           if (isFinal[s-1]) {
404             found = isFinal[t-1] && action[s-1].isEquiv(action[t-1]);
405           }
406           else {
407             found = !isFinal[t-1];
408           }
409         
410           if (found) { // found -> add state s to block b
411 // System.out.println("Found! Adding to block "+(b-b0));
412 // update block information
413 block[s] = b;
414             block[b]++;
415             
416             // chain in the new element
417 int last = b_backward[b];
418             b_forward[last] = s;
419             b_forward[s] = b;
420             b_backward[b] = s;
421             b_backward[s] = last;
422           }
423         }
424
425         b++;
426       }
427       
428       if (!found) { // fits in nowhere -> create new block
429 // System.out.println("not found, lastBlock = "+lastBlock);
430
431         // update block information
432 block[s] = b;
433         block[b]++;
434         
435         // chain in the new element
436 b_forward[b] = s;
437         b_forward[s] = b;
438         b_backward[b] = s;
439         b_backward[s] = b;
440         
441         lastBlock++;
442       }
443     } // of initialize blocks
444
445     // printBlocks(block,b_forward,b_backward,lastBlock);
446
447     // initialize worklist L
448 // first, find the largest block B_max, then, all other (B_i,c) go into the list
449 int B_max = b0;
450     int B_i;
451     for (B_i = b0+1; B_i <= lastBlock; B_i++)
452       if (block[B_max] < block[B_i]) B_max = B_i;
453     
454     // L = empty
455 l_forward[anchorL] = anchorL;
456     l_backward[anchorL] = anchorL;
457
458     // set up the first list element
459 if (B_max == b0) B_i = b0+1; else B_i = b0; // there must be at least two blocks
460
461     int index = (B_i-b0)*numInput; // (B_i, 0)
462 while (index < (B_i+1-b0)*numInput) {
463       int last = l_backward[anchorL];
464       l_forward[last] = index;
465       l_forward[index] = anchorL;
466       l_backward[index] = last;
467       l_backward[anchorL] = index;
468       index++;
469     }
470
471     // now do the rest of L
472 while (B_i <= lastBlock) {
473       if (B_i != B_max) {
474         index = (B_i-b0)*numInput;
475         while (index < (B_i+1-b0)*numInput) {
476           int last = l_backward[anchorL];
477           l_forward[last] = index;
478           l_forward[index] = anchorL;
479           l_backward[index] = last;
480           l_backward[anchorL] = index;
481           index++;
482         }
483       }
484       B_i++;
485     }
486     // end of setup L
487
488     // start of "real" algorithm
489 // int step = 0;
490 // System.out.println("max_steps = "+(n*numInput));
491 // while L not empty
492 while (l_forward[anchorL] != anchorL) {
493       // System.out.println("step : "+(step++));
494 // printL(l_forward, l_backward, anchorL);
495
496       // pick and delete (B_j, a) in L:
497
498       // pick
499 int B_j_a = l_forward[anchorL];
500       // delete
501 l_forward[anchorL] = l_forward[B_j_a];
502       l_backward[l_forward[anchorL]] = anchorL;
503       l_forward[B_j_a] = 0;
504       // take B_j_a = (B_j-b0)*numInput+c apart into (B_j, a)
505 int B_j = b0 + B_j_a / numInput;
506       int a = B_j_a % numInput;
507
508       // printL(l_forward, l_backward, anchorL);
509
510       // System.out.println("picked ("+B_j+","+a+")");
511 // printL(l_forward, l_backward, anchorL);
512
513       // determine splittings of all blocks wrt (B_j, a)
514 // i.e. D = inv_delta(B_j,a)
515 numD = 0;
516       int s = b_forward[B_j];
517       while (s != B_j) {
518         // System.out.println("splitting wrt. state "+s);
519 int t = inv_delta[s][a];
520         // System.out.println("inv_delta chunk "+t);
521 while (inv_delta_set[t] != -1) {
522           // System.out.println("D+= state "+inv_delta_set[t]);
523 D[numD++] = inv_delta_set[t++];
524         }
525         s = b_forward[s];
526       }
527
528       // clear the twin list
529 numSplit = 0;
530
531       // System.out.println("splitting blocks according to D");
532
533       // clear SD and twins (only those B_i that occur in D)
534 for (int indexD = 0; indexD < numD; indexD++) { // for each s in D
535 s = D[indexD];
536         B_i = block[s];
537         SD[B_i] = -1;
538         twin[B_i] = 0;
539       }
540       
541       // count how many states of each B_i occuring in D go with a into B_j
542 // Actually we only check, if *all* t in B_i go with a into B_j.
543 // In this case SD[B_i] == block[B_i] will hold.
544 for (int indexD = 0; indexD < numD; indexD++) { // for each s in D
545 s = D[indexD];
546         B_i = block[s];
547
548         // only count, if we haven't checked this block already
549 if (SD[B_i] < 0) {
550           SD[B_i] = 0;
551           int t = b_forward[B_i];
552           while (t != B_i && (t != 0 || block[0] == B_j) &&
553                  (t == 0 || block[table[t-1][a]+1] == B_j)) {
554             SD[B_i]++;
555             t = b_forward[t];
556           }
557         }
558       }
559   
560       // split each block according to D
561 for (int indexD = 0; indexD < numD; indexD++) { // for each s in D
562 s = D[indexD];
563         B_i = block[s];
564         
565         // System.out.println("checking if block "+(B_i-b0)+" must be split because of state "+s);
566
567         if (SD[B_i] != block[B_i]) {
568           // System.out.println("state "+(s-1)+" must be moved");
569 int B_k = twin[B_i];
570           if (B_k == 0) {
571             // no twin for B_i yet -> generate new block B_k, make it B_i's twin
572 B_k = ++lastBlock;
573             // System.out.println("creating block "+(B_k-n));
574 // printBlocks(block,b_forward,b_backward,lastBlock-1);
575 b_forward[B_k] = B_k;
576             b_backward[B_k] = B_k;
577             
578             twin[B_i] = B_k;
579
580             // mark B_i as split
581 twin[numSplit++] = B_i;
582           }
583           // move s from B_i to B_k
584
585           // remove s from B_i
586 b_forward[b_backward[s]] = b_forward[s];
587           b_backward[b_forward[s]] = b_backward[s];
588
589           // add s to B_k
590 int last = b_backward[B_k];
591           b_forward[last] = s;
592           b_forward[s] = B_k;
593           b_backward[s] = last;
594           b_backward[B_k] = s;
595
596           block[s] = B_k;
597           block[B_k]++;
598           block[B_i]--;
599
600           SD[B_i]--; // there is now one state less in B_i that goes with a into B_j
601 // printBlocks(block, b_forward, b_backward, lastBlock);
602 // System.out.println("finished move");
603 }
604       } // of block splitting
605
606       // printBlocks(block, b_forward, b_backward, lastBlock);
607
608       // System.out.println("updating L");
609
610       // update L
611 for (int indexTwin = 0; indexTwin < numSplit; indexTwin++) {
612         B_i = twin[indexTwin];
613         int B_k = twin[B_i];
614         for (int c = 0; c < numInput; c++) {
615           int B_i_c = (B_i-b0)*numInput+c;
616           int B_k_c = (B_k-b0)*numInput+c;
617           if (l_forward[B_i_c] > 0) {
618             // (B_i,c) already in L --> put (B_k,c) in L
619 int last = l_backward[anchorL];
620             l_backward[anchorL] = B_k_c;
621             l_forward[last] = B_k_c;
622             l_backward[B_k_c] = last;
623             l_forward[B_k_c] = anchorL;
624           }
625           else {
626             // put the smaller block in L
627 if (block[B_i] <= block[B_k]) {
628               int last = l_backward[anchorL];
629               l_backward[anchorL] = B_i_c;
630               l_forward[last] = B_i_c;
631               l_backward[B_i_c] = last;
632               l_forward[B_i_c] = anchorL;
633             }
634             else {
635               int last = l_backward[anchorL];
636               l_backward[anchorL] = B_k_c;
637               l_forward[last] = B_k_c;
638               l_backward[B_k_c] = last;
639               l_forward[B_k_c] = anchorL;
640             }
641           }
642         }
643       }
644     }
645
646     // System.out.println("Result");
647 // printBlocks(block,b_forward,b_backward,lastBlock);
648
649     /*
650     System.out.println("Old minimization:");
651     boolean [] [] equiv = old_minimize();
652
653     boolean error = false;
654     for (int i = 1; i < equiv.length; i++) {
655       for (int j = 0; j < equiv[i].length; j++) {
656         if (equiv[i][j] != (block[i+1] == block[j+1])) {
657           System.out.println("error: equiv["+i+"]["+j+"] = "+equiv[i][j]+
658                              ", block["+i+"] = "+block[i+1]+", block["+j+"] = "+block[j]);
659           error = true;
660         }
661       }
662     }
663
664     if (error) System.exit(1);
665     System.out.println("check");
666     */
667
668     // transform the transition table
669
670     // trans[i] is the state j that will replace state i, i.e.
671 // states i and j are equivalent
672 int trans [] = new int [numStates];
673     
674     // kill[i] is true iff state i is redundant and can be removed
675 boolean kill [] = new boolean [numStates];
676     
677     // move[i] is the amount line i has to be moved in the transition table
678 // (because states j < i have been removed)
679 int move [] = new int [numStates];
680     
681     // fill arrays trans[] and kill[] (in O(n))
682 for (int b = b0+1; b <= lastBlock; b++) { // b0 contains the error state
683 // get the state with smallest value in current block
684 int s = b_forward[b];
685       int min_s = s; // there are no empty blocks!
686 for (; s != b; s = b_forward[s])
687         if (min_s > s) min_s = s;
688       // now fill trans[] and kill[] for this block
689 // (and translate states back to partial DFA)
690 min_s--;
691       for (s = b_forward[b]-1; s != b-1; s = b_forward[s+1]-1) {
692         trans[s] = min_s;
693         kill[s] = s != min_s;
694       }
695     }
696     
697     // fill array move[] (in O(n))
698 int amount = 0;
699     for (int i = 0; i < numStates; i++) {
700       if ( kill[i] )
701         amount++;
702       else
703         move[i] = amount;
704     }
705
706     int i,j;
707     // j is the index in the new transition table
708 // the transition table is transformed in place (in O(c n))
709 for (i = 0, j = 0; i < numStates; i++) {
710       
711       // we only copy lines that have not been removed
712 if ( !kill[i] ) {
713         
714         // translate the target states
715 for (int c = 0; c < numInput; c++) {
716           if ( table[i][c] >= 0 ) {
717             table[j][c] = trans[ table[i][c] ];
718             table[j][c]-= move[ table[j][c] ];
719           }
720           else {
721             table[j][c] = table[i][c];
722           }
723         }
724
725         isFinal[j] = isFinal[i];
726         isPushback[j] = isPushback[i];
727         isLookEnd[j] = isLookEnd[i];
728         action[j] = action[i];
729         
730         j++;
731       }
732     }
733     
734     numStates = j;
735     
736     // translate lexical states
737 for (i = 0; i < lexState.length; i++) {
738       lexState[i] = trans[ lexState[i] ];
739       lexState[i]-= move[ lexState[i] ];
740     }
741   
742     Out.println(numStates+" states in minimized DFA");
743   }
744
745   public String toString(int [] a) {
746     String r = "{";
747     int i;
748     for (i = 0; i < a.length-1; i++) r += a[i]+",";
749     return r+a[i]+"}";
750   }
751
752   public void printBlocks(int [] b, int [] b_f, int [] b_b, int last) {
753     Out.dump("block : "+toString(b));
754     Out.dump("b_forward : "+toString(b_f));
755     Out.dump("b_backward: "+toString(b_b));
756     Out.dump("lastBlock : "+last);
757     final int n = numStates+1;
758     for (int i = n; i <= last; i ++) {
759       Out.dump("Block "+(i-n)+" (size "+b[i]+"):");
760       String line = "{";
761       int s = b_f[i];
762       while (s != i) {
763         line = line+(s-1);
764         int t = s;
765         s = b_f[s];
766         if (s != i) {
767           line = line+",";
768           if (b[s] != i) Out.dump("consistency error for state "+(s-1)+" (block "+b[s]+")");
769         }
770         if (b_b[s] != t) Out.dump("consistency error for b_back in state "+(s-1)+" (back = "+b_b[s]+", should be = "+t+")");
771       }
772       Out.dump(line+"}");
773     }
774   }
775
776   public void printL(int [] l_f, int [] l_b, int anchor) {
777     String l = "L = {";
778     int bc = l_f[anchor];
779     while (bc != anchor) {
780       int b = bc / numInput;
781       int c = bc % numInput;
782       l+= "("+b+","+c+")";
783       int old_bc = bc;
784       bc = l_f[bc];
785       if (bc != anchor) l+= ",";
786       if (l_b[bc] != old_bc) Out.dump("consistency error for ("+b+","+c+")");
787     }
788     Out.dump(l+"}");
789   }
790
791
792   public boolean [] [] old_minimize() {
793
794     int i,j;
795     char c;
796     
797     Out.print(numStates+" states before minimization, ");
798
799     if (numStates == 0) {
800       Out.error(ErrorMessages.ZERO_STATES);
801       throw new GeneratorException();
802     }
803
804     if (Options.no_minimize) {
805       Out.println("minimization skipped.");
806       return null;
807     }
808
809     // notequiv[i][j] == true <=> state i and state j are equivalent
810 boolean [] [] equiv = new boolean [numStates] [];
811
812     // list[i][j] contains all pairs of states that have to be marked "not equivalent"
813 // if states i and j are recognized to be not equivalent
814 StatePairList [] [] list = new StatePairList [numStates] [];
815
816     // construct a triangular matrix equiv[i][j] with j < i
817 // and mark pairs (final state, not final state) as not equivalent
818 for (i = 1; i < numStates; i++) {
819       list[i] = new StatePairList[i];
820       equiv[i] = new boolean [i];
821       for (j = 0; j < i; j++) {
822         // i and j are equivalent, iff :
823 // i and j are both final and their actions are equivalent and have same pushback behaviour or
824 // i and j are both not final
825
826         if ( isFinal[i] && isFinal[j] && (isPushback[i] == isPushback[j]) && (isLookEnd[i] == isLookEnd[j]) )
827           equiv[i][j] = action[i].isEquiv(action[j]);
828         else
829           equiv[i][j] = !isFinal[j] && !isFinal[i] && (isPushback[i] == isPushback[j]) && (isLookEnd[i] == isLookEnd[j]);
830       }
831     }
832
833
834     for (i = 1; i < numStates; i++) {
835       
836       Out.debug("Testing state "+i);
837
838       for (j = 0; j < i; j++) {
839     
840         if ( equiv[i][j] ) {
841   
842           for (c = 0; c < numInput; c++) {
843   
844             if (equiv[i][j]) {
845
846               int p = table[i][c];
847               int q = table[j][c];
848               if (p < q) {
849                 int t = p;
850                 p = q;
851                 q = t;
852               }
853               if ( p >= 0 || q >= 0 ) {
854                 // Out.debug("Testing input '"+c+"' for ("+i+","+j+")");
855 // Out.debug("Target states are ("+p+","+q+")");
856 if ( p!=q && (p == -1 || q == -1 || !equiv[p][q]) ) {
857                   equiv[i][j] = false;
858                   if (list[i][j] != null) list[i][j].markAll(list,equiv);
859                 }
860                 // printTable(equiv);
861 } // if (p >= 0) ..
862 } // if (equiv[i][j]
863 } // for (char c = 0; c < numInput ..
864
865           // if i and j are still marked equivalent..
866
867           if ( equiv[i][j] ) {
868          
869             // Out.debug("("+i+","+j+") are still marked equivalent");
870
871             for (c = 0; c < numInput; c++) {
872       
873               int p = table[i][c];
874               int q = table[j][c];
875               if (p < q) {
876                 int t = p;
877                 p = q;
878                 q = t;
879               }
880               
881               if (p != q && p >= 0 && q >= 0) {
882                 if ( list[p][q] == null ) {
883                   list[p][q] = new StatePairList();
884                 }
885                 list[p][q].addPair(i,j);
886               }
887             }
888           }
889           else {
890             // Out.debug("("+i+","+j+") are not equivalent");
891 }
892           
893           } // of first if (equiv[i][j])
894 } // of for j
895 } // of for i
896 // }
897
898     // printTable(equiv);
899
900     return equiv;
901   }
902
903
904   public void printInvDelta(int [] [] inv_delta, int [] inv_delta_set) {
905     Out.dump("Inverse of transition table: ");
906     for (int s = 0; s < numStates+1; s++) {
907       Out.dump("State ["+(s-1)+"]");
908       for (int c = 0; c < numInput; c++) {
909         String line = "With <"+c+"> in {";
910         int t = inv_delta[s][c];
911         while (inv_delta_set[t] != -1) {
912           line += inv_delta_set[t++]-1;
913           if (inv_delta_set[t] != -1) line += ",";
914         }
915         if (inv_delta_set[inv_delta[s][c]] != -1)
916           Out.dump(line+"}");
917       }
918     }
919   }
920
921   public void printTable(boolean [] [] equiv) {
922
923     Out.dump("Equivalence table is : ");
924     for (int i = 1; i < numStates; i++) {
925       String line = i+" :";
926       for (int j = 0; j < i; j++) {
927           if (equiv[i][j])
928             line+= " E";
929         else
930             line+= " x";
931       }
932       Out.dump(line);
933     }
934   }
935
936 }
937

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags