DeprecatedDfa.java
/*
* Copyright (C) 2022, Gerwin Klein, R��gis D��camps
* SPDX-License-Identifier: BSD-3-Clause
*/
package jflex.dfa;
import java.util.Arrays;
import jflex.exceptions.GeneratorException;
import jflex.logging.Out;
import jflex.option.Options;
/** Deprecated DFA class, only used for testing. */
@Deprecated
public class DeprecatedDfa extends DFA {
DeprecatedDfa(int numEntryStates, int numInputs, int numLexStates, int numStates) {
super(numEntryStates, numInputs, numLexStates, numStates);
}
/**
* Much simpler, but slower and less memory efficient minimization algorithm than {@link
* DFA#minimize()}.
*
* <p>This implementation is only useful for testing.
*
* @return the equivalence relation on states.
* @deprecated Use {@link DFA#minimize()} instead.
*/
@Deprecated
public boolean[][] old_minimize() {
int i;
int j;
int c;
if (numStates() == 0) {
throw new GeneratorException(new IllegalStateException("DFA has no states"));
}
if (Options.no_minimize) {
throw new UnsupportedOperationException(
"Options.no_minimize is set. Minimization is not allowed in this case");
}
// equiv[i][j] == true <=> state i and state j are equivalent
boolean[][] equiv = new boolean[numStates()][];
// list[i][j] contains all pairs of states that have to be marked "not equivalent"
// if states i and j are recognized to be not equivalent
StatePairList[][] list = new StatePairList[numStates()][];
// construct a triangular matrix equiv[i][j] with j < i
// and mark pairs (final state, not final state) as not equivalent
for (i = 1; i < numStates(); i++) {
list[i] = new StatePairList[i];
equiv[i] = new boolean[i];
for (j = 0; j < i; j++) {
// i and j are equivalent, iff :
// i and j are both final and their actions are equivalent and have same pushback behaviour
// or
// i and j are both not final
if (isFinal[i] && isFinal[j]) {
equiv[i][j] = action(i).isEquiv(action(j));
} else {
equiv[i][j] = !isFinal[j] && !isFinal[i];
}
}
}
for (i = 1; i < numStates(); i++) {
for (j = 0; j < i; j++) {
if (equiv[i][j]) {
for (c = 0; c < numInput(); c++) {
if (equiv[i][j]) {
int p = table[i][c];
int q = table[j][c];
if (p < q) {
int t = p;
p = q;
q = t;
}
if (p >= 0) {
if (p != q && (q == -1 || !equiv[p][q])) {
equiv[i][j] = false;
if (list[i][j] != null) list[i][j].markAll(list, equiv);
}
if (DFA.DFA_DEBUG) {
printTable(equiv);
}
} // if (p >= 0) ..
} // if (equiv[i][j]
} // for (char c = 0; c < numInput ..
// if i and j are still marked equivalent..
if (equiv[i][j]) {
for (c = 0; c < numInput(); c++) {
int p = table[i][c];
int q = table[j][c];
if (p < q) {
int t = p;
p = q;
q = t;
}
if (p != q && p >= 0 && q >= 0) {
if (list[p][q] == null) {
list[p][q] = new StatePairList();
}
list[p][q].addPair(i, j);
}
}
}
} // of first if (equiv[i][j])
} // of for j
} // of for i
// }
if (DFA.DFA_DEBUG) {
printTable(equiv);
}
return equiv;
}
/**
* Prints the equivalence table.
*
* @param equiv Equivalence table from {@link #old_minimize()}
*/
void printTable(boolean[][] equiv) {
Out.dump("Equivalence table is : ");
StringBuilder line = new StringBuilder();
for (int i = 1; i < numStates(); i++) {
line.setLength(0);
line.append(i).append(" :");
for (int j = 0; j < i; j++) {
if (equiv[i][j]) {
line.append(" E");
} else {
line.append(" x");
}
}
Out.dump(line.toString());
}
}
public static DeprecatedDfa copyOf(DFA dfa) {
DeprecatedDfa copy =
new DeprecatedDfa(
dfa.entryState.length, dfa.numInput(), dfa.numLexStates(), dfa.numStates());
copy.table = new int[dfa.table.length][dfa.numInput()];
for (int i = 0; i < dfa.table.length; i++) {
System.arraycopy(dfa.table[i], 0, copy.table[i], 0, copy.numInput());
}
copy.isFinal = Arrays.copyOf(dfa.isFinal, dfa.isFinal.length);
copy.entryState = Arrays.copyOf(dfa.entryState, dfa.entryState.length);
// Sets action and usedActions
for (int i = 0; i < dfa.numStates(); i++) {
copy.setAction(i, dfa.action(i));
}
return copy;
}
}