1
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
3
* Copyright (C) 1998-2001 Gerwin Klein <lsf@jflex.de> *
4
* All rights reserved. *
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. *
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. *
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 *
19
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
29
* DFA representation in JFlex.
30
* Contains minimization algorithm.
32
* @author Gerwin Klein
33
* @version JFlex 1.3.5, $Revision: 1.27 $, $Date: 2001/10/08 10:07:58 $
35
final public class DFA implements ErrorMessages {
38
* The initial number of states
40
private static final int STATES = 500;
43
* The code for "no target state" in the transition table.
45
public static final int NO_TARGET = -1;
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>
56
* <code>isFinal[state] == true</code> <=> the state <code>state</code> is
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
66
boolean [] isPushback;
70
* <code>isLookEnd[state] == true</code> <=> the state <code>state</code> is
71
* a final state of a lookahead expression.
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.
83
* lexState[i] is the start-state of lexical state i
88
* The number of states in this DFA
94
* The current maximum number of input characters
100
* all actions that are used in this DFA
102
Hashtable usedActions = new Hashtable();
104
public DFA(int numLexStates, int numInp) {
107
int statesNeeded = Math.max(numLexStates, STATES);
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];
117
for (int i = 0; i < statesNeeded; i++) {
118
for (char j = 0; j < numInput; j++)
119
table [i][j] = NO_TARGET;
124
public void setLexState(int lState, int trueState) {
125
lexState[lState] = trueState;
128
private void ensureStateCapacity(int newNumStates) {
130
int oldLength = isFinal.length;
132
if ( newNumStates < oldLength ) return;
134
int newLength = oldLength*2;
135
while ( newLength <= newNumStates ) newLength*= 2;
137
boolean [] newFinal = new boolean [newLength];
138
boolean [] newPushback = new boolean [newLength];
139
boolean [] newLookEnd = new boolean [newLength];
140
Action [] newAction = new Action [newLength];
141
int [] [] newTable = new int [newLength] [numInput];
143
System.arraycopy(isFinal,0,newFinal,0,numStates);
144
System.arraycopy(isPushback,0,newPushback,0,numStates);
145
System.arraycopy(isLookEnd,0,newLookEnd,0,numStates);
146
System.arraycopy(action,0,newAction,0,numStates);
147
System.arraycopy(table,0,newTable,0,oldLength);
151
for (i = oldLength; i < newLength; i++) {
152
for (j = 0; j < numInput; j++) {
153
newTable[i][j] = NO_TARGET;
158
isPushback = newPushback;
159
isLookEnd = newLookEnd;
165
public void setAction(int state, Action stateAction) {
166
action[state] = stateAction;
167
if (stateAction != null) {
168
isLookEnd[state] = stateAction.isLookAction;
169
usedActions.put(stateAction,stateAction);
173
public void setFinal(int state, boolean isFinalState) {
174
isFinal[state] = isFinalState;
177
public void setPushback(int state, boolean isPushbackState) {
178
isPushback[state] = isPushbackState;
182
public void addTransition(int start, char input, int dest) {
183
int max = Math.max(start,dest)+1;
184
ensureStateCapacity(max);
185
if (max > numStates) numStates = max;
187
// Out.debug("Adding DFA transition ("+start+", "+(int)input+", "+dest+")");
189
table[start][input] = dest;
194
public String toString() {
195
StringBuffer result = new StringBuffer();
197
for (int i=0; i < numStates; i++) {
198
result.append("State ");
199
if ( isFinal[i] ) result.append("[FINAL] ");
200
if ( isPushback[i] ) result.append("[PUSH] ");
201
result.append(i+":"+Out.NL);
203
for (char j=0; j < numInput; j++) {
204
if ( table[i][j] >= 0 )
205
result.append(" with "+(int)j+" in "+table[i][j]+Out.NL);
209
return result.toString();
213
public void writeDot(File file) {
215
PrintWriter writer = new PrintWriter(new FileWriter(file));
216
writer.println(dotFormat());
219
catch (IOException e) {
220
Out.error(ErrorMessages.FILE_WRITE, file);
221
throw new GeneratorException();
226
public String dotFormat() {
227
StringBuffer result = new StringBuffer();
229
result.append("digraph DFA {"+Out.NL);
230
result.append("rankdir = LR"+Out.NL);
232
for (int i=0; i < numStates; i++) {
233
if ( isFinal[i] || isPushback[i] ) result.append(i);
234
if ( isFinal[i] ) result.append(" [shape = doublecircle]");
235
if ( isPushback[i] ) result.append(" [shape = box]");
236
if ( isFinal[i] || isPushback[i] ) result.append(Out.NL);
239
for (int i=0; i < numStates; i++) {
240
for (int input = 0; input < numInput; input++) {
241
if ( table[i][input] >= 0 ) {
242
result.append(i+" -> "+table[i][input]);
243
result.append(" [label=\"["+input+"]\"]"+Out.NL);
244
// result.append(" [label=\"["+classes.toString(input)+"]\"]\n");
249
result.append("}"+Out.NL);
251
return result.toString();
255
// check if all actions can actually be matched in this DFA
256
public void checkActions(LexScan scanner, LexParse parser) {
257
EOFActions eofActions = parser.getEOFActions();
258
Enumeration l = scanner.actions.elements();
260
while (l.hasMoreElements()) {
261
Object next = l.nextElement();
262
if ( usedActions.get(next) != next && !eofActions.isEOFAction(next) )
263
Out.warning(scanner.file, NEVER_MATCH, ((Action) next).priority-1, -1);
268
public void minimize() {
273
Out.print(numStates+" states before minimization, ");
275
if (numStates == 0) {
276
Out.error(ZERO_STATES);
277
throw new GeneratorException();
280
if (Main.no_minimize) {
281
Out.println("minimization skipped.");
285
// notequiv[i][j] == true <=> state i and state j are equivalent
286
boolean [] [] equiv = new boolean [numStates] [];
288
// list[i][j] contains all pairs of states that have to be marked "not equivalent"
289
// if states i and j are recognized to be not equivalent
290
StatePairList [] [] list = new StatePairList [numStates] [];
292
// construct a triangular matrix equiv[i][j] with j < i
293
// and mark pairs (final state, not final state) as not equivalent
294
for (i = 1; i < numStates; i++) {
295
list[i] = new StatePairList[i];
296
equiv[i] = new boolean [i];
297
for (j = 0; j < i; j++) {
298
// i and j are equivalent, iff :
299
// i and j are both final and their actions are equivalent and have same pushback behaviour or
300
// i and j are both not final
302
if ( isFinal[i] && isFinal[j] && (isPushback[i] == isPushback[j]) && (isLookEnd[i] == isLookEnd[j]) )
303
equiv[i][j] = action[i].isEquiv(action[j]);
305
equiv[i][j] = !isFinal[j] && !isFinal[i] && (isPushback[i] == isPushback[j]) && (isLookEnd[i] == isLookEnd[j]);
310
for (i = 1; i < numStates; i++) {
312
// Out.debug("Testing state "+i);
314
for (j = 0; j < i; j++) {
318
for (c = 0; c < numInput; c++) {
329
if ( p >= 0 || q >= 0 ) {
330
// Out.debug("Testing input '"+c+"' for ("+i+","+j+")");
331
// Out.debug("Target states are ("+p+","+q+")");
332
if ( p!=q && (p == -1 || q == -1 || !equiv[p][q]) ) {
334
if (list[i][j] != null) list[i][j].markAll(list,equiv);
336
// printTable(equiv);
339
} // for (char c = 0; c < numInput ..
341
// if i and j are still marked equivalent..
345
// Out.debug("("+i+","+j+") are still marked equivalent");
347
for (c = 0; c < numInput; c++) {
357
if (p != q && p >= 0 && q >= 0) {
358
if ( list[p][q] == null ) {
359
list[p][q] = new StatePairList();
361
list[p][q].addPair(i,j);
366
// Out.debug("("+i+","+j+") are not equivalent");
369
} // of first if (equiv[i][j])
374
// printTable(equiv);
376
// transform the transition table
378
// trans[i] is the state j that will replace state i, i.e. when
379
// states i and j are equivalent
380
int trans [] = new int [numStates];
382
// kill[i] is true, iff state i is redundant and can be removed
383
boolean kill [] = new boolean [numStates];
385
// move[i] is the amount line i has to be moved in the transitiontable
386
// (because states j < i have been removed)
387
int move [] = new int [numStates];
389
// fill arrays trans[] and kill[]
390
for (i = 0; i < numStates; i++) {
392
for (j = 0; j < i; j++)
402
for (i = 0; i < numStates; i++) {
409
// j is now the index in the new transition table
411
// the transition table is transformed in place
412
// (without using a new array)
413
for (i = 0, j = 0; i < numStates; i++) {
415
// we only copy lines that have not been removed
418
// translate the target states
419
for (c = 0; c < numInput; c++) {
420
if ( table[i][c] >= 0 ) {
421
table[j][c] = trans[ table[i][c] ];
422
table[j][c]-= move[ table[j][c] ];
425
table[j][c] = table[i][c];
429
isFinal[j] = isFinal[i];
430
isPushback[j] = isPushback[i];
431
isLookEnd[j] = isLookEnd[i];
432
action[j] = action[i];
440
// translate lexical states
441
for (i = 0; i < lexState.length; i++) {
442
lexState[i] = trans[ lexState[i] ];
443
lexState[i]-= move[ lexState[i] ];
446
Out.println(numStates+" states in minimized DFA");
449
public void printTable(boolean [] [] equiv) {
451
Out.dump("Equivalence table is : ");
452
for (int i = 1; i < numStates; i++) {
453
String line = i+" :";
454
for (int j = 0; j < i; j++) {
added
removed
src/JFlex/DFA.java
