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