| /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * |
| * JFlex 1.4.3 * |
| * Copyright (C) 1998-2009 Gerwin Klein <lsf@jflex.de> * |
| * All rights reserved. * |
| * * |
| * This program is free software; you can redistribute it and/or modify * |
| * it under the terms of the GNU General Public License. See the file * |
| * COPYRIGHT for more information. * |
| * * |
| * This program is distributed in the hope that it will be useful, * |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * |
| * GNU General Public License for more details. * |
| * * |
| * You should have received a copy of the GNU General Public License along * |
| * with this program; if not, write to the Free Software Foundation, Inc., * |
| * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * |
| * * |
| * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
| package JFlex; |
| |
| import java.util.*; |
| import java.io.*; |
| |
| |
| /** |
| * NFA representation in JFlex. |
| * |
| * Contains algorithms RegExp -> NFA and NFA -> DFA. |
| * |
| * @author Gerwin Klein |
| * @version $Revision: 1.4.3 $, $Date: 2009/12/21 15:58:48 $ |
| */ |
| final public class NFA { |
| |
| /** table[current_state][next_char] is the set of states that can be reached |
| /* from current_state with an input next_char */ |
| StateSet [][] table; |
| |
| /** epsilon[current_state] is the set of states that can be reached |
| /* from current_state via epsilon edges */ |
| StateSet [] epsilon; |
| |
| /** isFinal[state] == true <=> state is a final state of the NFA */ |
| boolean [] isFinal; |
| |
| /** action[current_state]: the action associated with the state |
| /* current_state (null, if there is no action for the state) */ |
| Action [] action; |
| |
| /** the number of states in this NFA */ |
| int numStates; |
| |
| /** the current maximum number of input characters */ |
| int numInput; |
| |
| /** the number of lexical States. Lexical states have the indices |
| /* 0..numLexStates-1 in the transition table */ |
| int numLexStates; |
| |
| /** estimated size of the NFA (before actual construction) */ |
| int estSize = 256; |
| |
| Macros macros; |
| CharClasses classes; |
| |
| LexScan scanner; |
| RegExps regExps; |
| |
| // will be reused by several methods (avoids excessive object creation) |
| private static StateSetEnumerator states = new StateSetEnumerator(); |
| private static StateSet tempStateSet = new StateSet(); |
| |
| public NFA(int numInput, int estSize) { |
| this.numInput = numInput; |
| this.estSize = estSize; |
| numStates = 0; |
| epsilon = new StateSet [estSize]; |
| action = new Action [estSize]; |
| isFinal = new boolean [estSize]; |
| table = new StateSet [estSize][numInput]; |
| } |
| |
| /** |
| * Construct new NFA. |
| * |
| * Assumes that lookahead cases and numbers are already resolved in RegExps. |
| * @see RegExps#checkLookAheads() |
| */ |
| public NFA(int numInput, LexScan scanner, RegExps regExps, |
| Macros macros, CharClasses classes) { |
| this(numInput, regExps.NFASize(macros)+2*scanner.states.number()); |
| |
| this.scanner = scanner; |
| this.regExps = regExps; |
| this.macros = macros; |
| this.classes = classes; |
| |
| numLexStates = scanner.states.number(); |
| |
| // ensureCapacity assumes correctly set up numStates. |
| int new_num = numEntryStates(); |
| ensureCapacity(new_num); |
| numStates = new_num; |
| } |
| |
| public int numEntryStates() { |
| return 2*(numLexStates+regExps.gen_look_count); |
| } |
| |
| /** |
| * Add a standalone rule that has minimum priority, fires a transition |
| * on all single input characters and has a "print yytext" action. |
| */ |
| public void addStandaloneRule() { |
| int start = numStates; |
| int end = numStates+1; |
| |
| for (int c = 0; c < classes.getNumClasses(); c++) |
| addTransition(start, c, end); |
| |
| for (int i = 0; i < numLexStates*2; i++) |
| addEpsilonTransition(i, start); |
| |
| action[end] = new Action("System.out.print(yytext());", Integer.MAX_VALUE); |
| isFinal[end] = true; |
| } |
| |
| /** |
| * Add a regexp to this NFA. |
| * |
| * @param regExpNum the number of the regexp to add. |
| */ |
| public void addRegExp(int regExpNum) { |
| |
| if (Options.DEBUG) |
| Out.debug("Adding nfa for regexp "+regExpNum+" :"+Out.NL+regExps.getRegExp(regExpNum)); |
| |
| IntPair nfa = insertNFA( regExps.getRegExp(regExpNum) ); |
| |
| Enumeration lexStates = regExps.getStates(regExpNum).elements(); |
| |
| if ( !lexStates.hasMoreElements() ) |
| lexStates = scanner.states.getInclusiveStates(); |
| |
| while ( lexStates.hasMoreElements() ) { |
| int stateNum = ((Integer)lexStates.nextElement()).intValue(); |
| |
| if ( !regExps.isBOL(regExpNum) ) |
| addEpsilonTransition(2*stateNum, nfa.start); |
| |
| addEpsilonTransition(2*stateNum+1, nfa.start); |
| } |
| |
| |
| if ( regExps.getLookAhead(regExpNum) != null ) { |
| Action a = regExps.getAction(regExpNum); |
| |
| if (a.lookAhead() == Action.FINITE_CHOICE) { |
| insertLookAheadChoices(nfa.end, a, regExps.getLookAhead(regExpNum)); |
| // remove the original action from the collection: it will never |
| // be matched directly, only its copies will. |
| scanner.actions.remove(a); |
| } |
| else { |
| RegExp r1 = regExps.getRegExp(regExpNum); |
| RegExp r2 = regExps.getLookAhead(regExpNum); |
| |
| IntPair look = insertNFA(r2); |
| |
| addEpsilonTransition(nfa.end, look.start); |
| |
| action[look.end] = a; |
| isFinal[look.end] = true; |
| |
| if (a.lookAhead() == Action.GENERAL_LOOK) { |
| // base forward pass |
| IntPair forward = insertNFA(r1); |
| // lookahead backward pass |
| IntPair backward = insertNFA(r2.rev(macros)); |
| |
| isFinal[forward.end] = true; |
| action[forward.end] = new Action(Action.FORWARD_ACTION); |
| |
| isFinal[backward.end] = true; |
| action[backward.end] = new Action(Action.BACKWARD_ACTION); |
| |
| int entry = 2*(regExps.getLookEntry(regExpNum) + numLexStates); |
| addEpsilonTransition(entry, forward.start); |
| addEpsilonTransition(entry+1, backward.start); |
| |
| a.setEntryState(entry); |
| } |
| } |
| } |
| else { |
| action[nfa.end] = regExps.getAction(regExpNum); |
| isFinal[nfa.end] = true; |
| } |
| } |
| |
| /** |
| * Insert NFAs for the (finitely many) fixed length lookahead choices. |
| * |
| * @param lookAhead a lookahead of which isFiniteChoice is true |
| * @param baseEnd the end state of the base expression NFA |
| * @param a the action of the expression |
| * |
| * @see SemCheck#isFiniteChoice(RegExp) |
| */ |
| private void insertLookAheadChoices(int baseEnd, Action a, RegExp lookAhead) { |
| if (lookAhead.type == sym.BAR) { |
| RegExp2 r = (RegExp2) lookAhead; |
| insertLookAheadChoices(baseEnd, a, r.r1); |
| insertLookAheadChoices(baseEnd, a, r.r2); |
| } |
| else if (lookAhead.type == sym.MACROUSE) { |
| RegExp1 r = (RegExp1) lookAhead; |
| insertLookAheadChoices(baseEnd, a, macros.getDefinition((String) r.content)); |
| } |
| else { |
| int len = SemCheck.length(lookAhead); |
| |
| if (len >= 0) { |
| // termination case |
| IntPair look = insertNFA(lookAhead); |
| |
| addEpsilonTransition(baseEnd, look.start); |
| |
| Action x = a.copyChoice(len); |
| action[look.end] = x; |
| isFinal[look.end] = true; |
| |
| // add new copy to the collection of known actions such that |
| // it can be checked for the NEVER_MATCH warning. |
| scanner.actions.add(x); |
| } |
| else { |
| // should never happen |
| throw new Error("When inserting lookahead expression: unkown expression type "+lookAhead.type+" in "+lookAhead); //$NON-NLS-1$ //$NON-NLS-2$ |
| } |
| } |
| } |
| |
| /** |
| * Make sure the NFA can contain at least newNumStates states. |
| * |
| * @param newNumStates the minimu number of states. |
| */ |
| private void ensureCapacity(int newNumStates) { |
| int oldLength = epsilon.length; |
| |
| if ( newNumStates < oldLength ) return; |
| |
| int newStatesLength = Math.max(oldLength*2, newNumStates); |
| |
| boolean [] newFinal = new boolean [newStatesLength]; |
| boolean [] newIsPush = new boolean [newStatesLength]; |
| Action [] newAction = new Action [newStatesLength]; |
| StateSet [] [] newTable = new StateSet [newStatesLength] [numInput]; |
| StateSet [] newEpsilon = new StateSet [newStatesLength]; |
| |
| System.arraycopy(isFinal,0,newFinal,0,numStates); |
| System.arraycopy(action,0,newAction,0,numStates); |
| System.arraycopy(epsilon,0,newEpsilon,0,numStates); |
| System.arraycopy(table,0,newTable,0,numStates); |
| |
| isFinal = newFinal; |
| action = newAction; |
| epsilon = newEpsilon; |
| table = newTable; |
| } |
| |
| public void addTransition(int start, int input, int dest) { |
| Out.debug("Adding transition ("+start+", "+input+", "+dest+")"); |
| |
| int maxS = Math.max(start,dest)+1; |
| |
| ensureCapacity( maxS ); |
| |
| if (maxS > numStates) numStates = maxS; |
| |
| if ( table[start][input] != null ) |
| table[start][input].addState(dest); |
| else |
| table[start][input] = new StateSet(estSize,dest); |
| } |
| |
| public void addEpsilonTransition(int start, int dest) { |
| int max = Math.max(start,dest)+1; |
| ensureCapacity( max ); |
| if (max > numStates) numStates = max; |
| |
| if (epsilon[start] != null) |
| epsilon[start].addState(dest); |
| else |
| epsilon[start] = new StateSet(estSize,dest); |
| } |
| |
| |
| /** |
| * Returns <code>true</code>, iff the specified set of states |
| * contains a final state. |
| * |
| * @param set the set of states that is tested for final states. |
| */ |
| private boolean containsFinal(StateSet set) { |
| states.reset(set); |
| |
| while ( states.hasMoreElements() ) |
| if ( isFinal[states.nextElement()] ) return true; |
| |
| return false; |
| } |
| |
| |
| /** |
| * Returns <code>true</code>, iff the specified set of states |
| * contains a pushback-state. |
| * |
| * @param set the set of states that is tested for pushback-states. |
| private boolean containsPushback(StateSet set) { |
| states.reset(set); |
| |
| while ( states.hasMoreElements() ) |
| if ( isPushback[states.nextElement()] ) return true; |
| |
| return false; |
| } |
| */ |
| |
| /** |
| * Returns the action with highest priority in the specified |
| * set of states. |
| * |
| * @param set the set of states for which to determine the action |
| */ |
| private Action getAction(StateSet set) { |
| |
| states.reset(set); |
| |
| Action maxAction = null; |
| |
| Out.debug("Determining action of : "+set); |
| |
| while ( states.hasMoreElements() ) { |
| |
| Action currentAction = action[ states.nextElement() ]; |
| |
| if ( currentAction != null ) { |
| if (maxAction == null) |
| maxAction = currentAction; |
| else |
| maxAction = maxAction.getHigherPriority(currentAction); |
| } |
| |
| } |
| |
| return maxAction; |
| } |
| |
| |
| /** |
| * Calculates the epsilon closure for a specified set of states. |
| * |
| * The epsilon closure for set a is the set of states that can be reached |
| * by epsilon edges from a. |
| * |
| * @param set the set of states to calculate the epsilon closure for |
| * |
| * @return the epsilon closure of the specified set of states |
| * in this NFA |
| */ |
| private StateSet closure(int startState) { |
| |
| // Out.debug("Calculating closure of "+set); |
| |
| StateSet notvisited = tempStateSet; |
| StateSet closure = new StateSet(numStates,startState); |
| |
| notvisited.clear(); |
| notvisited.addState(startState); |
| |
| while ( notvisited.containsElements() ) { |
| // Out.debug("closure is now "+closure); |
| // Out.debug("notvisited is "+notvisited); |
| int state = notvisited.getAndRemoveElement(); |
| // Out.debug("removed element "+state+" of "+notvisited); |
| // Out.debug("epsilon[states] = "+epsilon[state]); |
| notvisited.add(closure.complement(epsilon[state])); |
| closure.add(epsilon[state]); |
| } |
| |
| // Out.debug("Closure is : "+closure); |
| |
| return closure; |
| } |
| |
| /** |
| * Returns the epsilon closure of a set of states |
| */ |
| private StateSet closure(StateSet startStates) { |
| StateSet result = new StateSet(numStates); |
| |
| if (startStates != null) { |
| states.reset(startStates); |
| while (states.hasMoreElements()) |
| result.add( closure(states.nextElement()) ); |
| } |
| |
| return result; |
| } |
| |
| |
| private void epsilonFill() { |
| for (int i = 0; i < numStates; i++) { |
| epsilon[i] = closure(i); |
| } |
| } |
| |
| /** |
| * Calculates the set of states that can be reached from another |
| * set of states <code>start</code> with an specified input |
| * character <code>input</code> |
| * |
| * @param start the set of states to start from |
| * @param input the input character for which to search the next states |
| * |
| * @return the set of states that are reached from <code>start</code> |
| * via <code>input</code> |
| */ |
| private StateSet DFAEdge(StateSet start, char input) { |
| // Out.debug("Calculating DFAEdge for state set "+start+" and input '"+input+"'"); |
| |
| tempStateSet.clear(); |
| |
| states.reset(start); |
| while ( states.hasMoreElements() ) |
| tempStateSet.add( table[states.nextElement()][input] ); |
| |
| StateSet result = new StateSet(tempStateSet); |
| |
| states.reset(tempStateSet); |
| while ( states.hasMoreElements() ) |
| result.add( epsilon[states.nextElement()] ); |
| |
| // Out.debug("DFAEdge is : "+result); |
| |
| return result; |
| } |
| |
| |
| /** |
| * Returns an DFA that accepts the same language as this NFA. |
| * This DFA is usually not minimal. |
| */ |
| public DFA getDFA() { |
| |
| Hashtable dfaStates = new Hashtable(numStates); |
| Vector dfaVector = new Vector(numStates); |
| |
| DFA dfa = new DFA(numEntryStates(), numInput, numLexStates); |
| |
| int numDFAStates = 0; |
| int currentDFAState = 0; |
| |
| Out.println("Converting NFA to DFA : "); |
| |
| epsilonFill(); |
| |
| StateSet currentState, newState; |
| |
| // create the initial states of the DFA |
| for ( int i = 0; i < numEntryStates(); i++ ) { |
| newState = epsilon[i]; |
| |
| dfaStates.put(newState, new Integer(numDFAStates)); |
| dfaVector.addElement(newState); |
| |
| dfa.setEntryState( i, numDFAStates ); |
| |
| dfa.setFinal( numDFAStates, containsFinal(newState) ); |
| dfa.setAction( numDFAStates, getAction(newState) ); |
| |
| numDFAStates++; |
| } |
| |
| numDFAStates--; |
| |
| if (Options.DEBUG) |
| Out.debug("DFA start states are :"+Out.NL+dfaStates+Out.NL+Out.NL+"ordered :"+Out.NL+dfaVector); |
| |
| currentDFAState = 0; |
| |
| StateSet tempStateSet = NFA.tempStateSet; |
| StateSetEnumerator states = NFA.states; |
| |
| // will be reused |
| newState = new StateSet(numStates); |
| |
| while ( currentDFAState <= numDFAStates ) { |
| |
| currentState = (StateSet) dfaVector.elementAt(currentDFAState); |
| |
| for (char input = 0; input < numInput; input++) { |
| |
| // newState = DFAEdge(currentState, input); |
| |
| // inlining DFAEdge for performance: |
| |
| // Out.debug("Calculating DFAEdge for state set "+currentState+" and input '"+input+"'"); |
| |
| tempStateSet.clear(); |
| states.reset(currentState); |
| while ( states.hasMoreElements() ) |
| tempStateSet.add( table[states.nextElement()][input] ); |
| |
| newState.copy(tempStateSet); |
| |
| states.reset(tempStateSet); |
| while ( states.hasMoreElements() ) |
| newState.add( epsilon[states.nextElement()] ); |
| |
| // Out.debug("DFAEdge is : "+newState); |
| |
| |
| if ( newState.containsElements() ) { |
| |
| // Out.debug("DFAEdge for input "+(int)input+" and state set "+currentState+" is "+newState); |
| |
| // Out.debug("Looking for state set "+newState); |
| Integer nextDFAState = (Integer) dfaStates.get(newState); |
| |
| if ( nextDFAState != null ) { |
| // Out.debug("FOUND!"); |
| dfa.addTransition(currentDFAState, input, nextDFAState.intValue()); |
| } |
| else { |
| if (Options.progress) Out.print("."); |
| // Out.debug("NOT FOUND!"); |
| // Out.debug("Table was "+dfaStates); |
| numDFAStates++; |
| |
| // make a new copy of newState to store in dfaStates |
| StateSet storeState = new StateSet(newState); |
| |
| dfaStates.put(storeState, new Integer(numDFAStates)); |
| dfaVector.addElement(storeState); |
| |
| dfa.addTransition(currentDFAState, input, numDFAStates); |
| dfa.setFinal( numDFAStates, containsFinal(storeState) ); |
| dfa.setAction( numDFAStates, getAction(storeState) ); |
| } |
| } |
| } |
| |
| currentDFAState++; |
| } |
| |
| if (Options.verbose) Out.println(""); |
| |
| return dfa; |
| } |
| |
| |
| public void dumpTable() { |
| Out.dump(toString()); |
| } |
| |
| public String toString() { |
| StringBuffer result = new StringBuffer(); |
| |
| for (int i=0; i < numStates; i++) { |
| result.append("State"); |
| if ( isFinal[i] ) { |
| result.append("[FINAL"); |
| String l = action[i].lookString(); |
| if (!l.equals("")) { |
| result.append(", "); |
| result.append(l); |
| } |
| result.append("]"); |
| } |
| result.append(" "+i+Out.NL); |
| |
| for (char input = 0; input < numInput; input++) { |
| if ( table[i][input] != null && table[i][input].containsElements() ) |
| result.append(" with "+((int) input)+" in "+table[i][input]+Out.NL); |
| } |
| |
| if ( epsilon[i] != null && epsilon[i].containsElements() ) |
| result.append(" with epsilon in "+epsilon[i]+Out.NL); |
| } |
| |
| return result.toString(); |
| } |
| |
| public void writeDot(File file) { |
| try { |
| PrintWriter writer = new PrintWriter(new FileWriter(file)); |
| writer.println(dotFormat()); |
| writer.close(); |
| } |
| catch (IOException e) { |
| Out.error(ErrorMessages.FILE_WRITE, file); |
| throw new GeneratorException(); |
| } |
| } |
| |
| public String dotFormat() { |
| StringBuffer result = new StringBuffer(); |
| |
| result.append("digraph NFA {"+Out.NL); |
| result.append("rankdir = LR"+Out.NL); |
| |
| for (int i=0; i < numStates; i++) { |
| if ( isFinal[i] ) { |
| result.append(i); |
| result.append(" [shape = doublecircle]"); |
| result.append(Out.NL); |
| } |
| } |
| |
| for (int i=0; i < numStates; i++) { |
| for (int input = 0; input < numInput; input++) { |
| if ( table[i][input] != null ) { |
| StateSetEnumerator states = table[i][input].states(); |
| |
| while (states.hasMoreElements()) { |
| int s = states.nextElement(); |
| result.append(i+" -> "+s); |
| result.append(" [label=\""+classes.toString(input)+"\"]"+Out.NL); |
| } |
| } |
| } |
| if ( epsilon[i] != null ) { |
| StateSetEnumerator states = epsilon[i].states(); |
| while (states.hasMoreElements()) { |
| int s = states.nextElement(); |
| result.append(i+" -> "+s+" [style=dotted]"+Out.NL); |
| } |
| } |
| } |
| |
| result.append("}"+Out.NL); |
| |
| return result.toString(); |
| } |
| |
| |
| //----------------------------------------------------------------------- |
| // Functions for constructing NFAs out of regular expressions. |
| |
| private void insertLetterNFA(boolean caseless, char letter, int start, int end) { |
| if (caseless) { |
| int lower = classes.getClassCode(Character.toLowerCase(letter)); |
| int upper = classes.getClassCode(Character.toUpperCase(letter)); |
| addTransition(start, lower, end); |
| if (upper != lower) addTransition(start, upper, end); |
| } |
| else { |
| addTransition(start, classes.getClassCode(letter), end); |
| } |
| } |
| |
| private IntPair insertStringNFA(boolean caseless, String letters) { |
| int start = numStates; |
| int i; |
| |
| for (i = 0; i < letters.length(); i++) { |
| if (caseless) { |
| char c = letters.charAt(i); |
| int lower = classes.getClassCode(Character.toLowerCase(c)); |
| int upper = classes.getClassCode(Character.toUpperCase(c)); |
| addTransition(i+start, lower, i+start+1); |
| if (upper != lower) addTransition(i+start, upper, i+start+1); |
| } |
| else { |
| addTransition(i+start, classes.getClassCode(letters.charAt(i)), i+start+1); |
| } |
| } |
| |
| return new IntPair(start, i+start); |
| } |
| |
| |
| private void insertClassNFA(Vector intervalls, int start, int end) { |
| // empty char class is ok: |
| if (intervalls == null) return; |
| |
| int [] cl = classes.getClassCodes(intervalls); |
| for (int i = 0; i < cl.length; i++) |
| addTransition(start, cl[i], end); |
| } |
| |
| private void insertNotClassNFA(Vector intervalls, int start, int end) { |
| int [] cl = classes.getNotClassCodes(intervalls); |
| |
| for (int i = 0; i < cl.length; i++) |
| addTransition(start, cl[i], end); |
| } |
| |
| |
| /** |
| * Constructs an NFA accepting the complement of the language |
| * of a given NFA. |
| * |
| * Converts the NFA into a DFA, then negates that DFA. |
| * Exponential state blowup possible and common. |
| * |
| * @param the NFA to construct the complement for. |
| * |
| * @return a pair of integers denoting the index of start |
| * and end state of the complement NFA. |
| */ |
| private IntPair complement(IntPair nfa) { |
| |
| if (Options.DEBUG) { |
| Out.debug("complement for "+nfa); |
| Out.debug("NFA is :"+Out.NL+this); |
| } |
| |
| int dfaStart = nfa.end+1; |
| |
| // FIXME: only need epsilon closure of states reachable from nfa.start |
| epsilonFill(); |
| |
| Hashtable dfaStates = new Hashtable(numStates); |
| Vector dfaVector = new Vector(numStates); |
| |
| int numDFAStates = 0; |
| int currentDFAState = 0; |
| |
| StateSet currentState, newState; |
| |
| newState = epsilon[nfa.start]; |
| dfaStates.put(newState, new Integer(numDFAStates)); |
| dfaVector.addElement(newState); |
| |
| if (Options.DEBUG) |
| Out.debug("pos DFA start state is :"+Out.NL+dfaStates+Out.NL+Out.NL+"ordered :"+Out.NL+dfaVector); |
| |
| currentDFAState = 0; |
| |
| while ( currentDFAState <= numDFAStates ) { |
| |
| currentState = (StateSet) dfaVector.elementAt(currentDFAState); |
| |
| for (char input = 0; input < numInput; input++) { |
| newState = DFAEdge(currentState, input); |
| |
| if ( newState.containsElements() ) { |
| |
| // Out.debug("DFAEdge for input "+(int)input+" and state set "+currentState+" is "+newState); |
| |
| // Out.debug("Looking for state set "+newState); |
| Integer nextDFAState = (Integer) dfaStates.get(newState); |
| |
| if ( nextDFAState != null ) { |
| // Out.debug("FOUND!"); |
| addTransition(dfaStart+currentDFAState, input, dfaStart+nextDFAState.intValue()); |
| } |
| else { |
| if (Options.dump) Out.print("+"); |
| // Out.debug("NOT FOUND!"); |
| // Out.debug("Table was "+dfaStates); |
| numDFAStates++; |
| |
| dfaStates.put(newState, new Integer(numDFAStates)); |
| dfaVector.addElement(newState); |
| |
| addTransition(dfaStart+currentDFAState, input, dfaStart+numDFAStates); |
| } |
| } |
| } |
| |
| currentDFAState++; |
| } |
| |
| // We have a dfa accepting the positive regexp. |
| |
| // Now the complement: |
| if (Options.DEBUG) |
| Out.debug("dfa finished, nfa is now :"+Out.NL+this); |
| |
| int start = dfaStart+numDFAStates+1; |
| int error = dfaStart+numDFAStates+2; |
| int end = dfaStart+numDFAStates+3; |
| |
| addEpsilonTransition(start, dfaStart); |
| |
| for (int i = 0; i < numInput; i++) |
| addTransition(error, i, error); |
| |
| addEpsilonTransition(error, end); |
| |
| for (int s = 0; s <= numDFAStates; s++) { |
| currentState = (StateSet) dfaVector.elementAt(s); |
| |
| currentDFAState = dfaStart+s; |
| |
| // if it was not a final state, it is now in the complement |
| if (!currentState.isElement(nfa.end)) |
| addEpsilonTransition(currentDFAState, end); |
| |
| // all inputs not present (formerly leading to an implicit error) |
| // now lead to an explicit (final) state accepting everything. |
| for (int i = 0; i < numInput; i++) |
| if (table[currentDFAState][i] == null) |
| addTransition(currentDFAState, i, error); |
| } |
| |
| // eliminate transitions leading to dead states |
| if (live == null || live.length < numStates) { |
| live = new boolean [2*numStates]; |
| visited = new boolean [2*numStates]; |
| } |
| |
| removeDead(dfaStart, end); |
| |
| if (Options.DEBUG) |
| Out.debug("complement finished, nfa ("+start+","+end+") is now :"+this); |
| |
| return new IntPair(start, end); |
| } |
| |
| // "global" data for use in method removeDead only: |
| // live[s] == false <=> no final state can be reached from s |
| private boolean [] live; // = new boolean [estSize]; |
| private boolean [] visited; // = new boolean [estSize]; |
| |
| private void removeDead(int start, int end) { |
| // Out.debug("removeDead ("+start+")"); |
| |
| if ( visited[start] || live[start] ) return; |
| visited[start] = true; |
| |
| // Out.debug("not yet visited"); |
| |
| if (closure(start).isElement(end)) |
| live[start] = true; |
| |
| // Out.debug("is final :"+live[start]); |
| |
| for (int i = 0; i < numInput; i++) { |
| StateSet nextState = closure(table[start][i]); |
| StateSetEnumerator states = nextState.states(); |
| while (states.hasMoreElements()) { |
| int next = states.nextElement(); |
| |
| if (next != start) { |
| removeDead(next,end); |
| |
| if (live[next]) |
| live[start] = true; |
| else |
| table[start][i] = null; |
| } |
| } |
| } |
| |
| StateSet nextState = closure(epsilon[start]); |
| StateSetEnumerator states = nextState.states(); |
| while (states.hasMoreElements()) { |
| int next = states.nextElement(); |
| |
| if (next != start) { |
| removeDead(next,end); |
| |
| if (live[next]) |
| live[start] = true; |
| } |
| } |
| |
| // Out.debug("state "+start+" is live :"+live[start]); |
| } |
| |
| |
| /** |
| * Constructs a two state NFA for char class regexps, |
| * such that the NFA has |
| * |
| * exactly one start state, |
| * exactly one end state, |
| * no transitions leading out of the end state |
| * no transitions leading into the start state |
| * |
| * Assumes that regExp.isCharClass(macros) == true |
| * |
| * @param regExp the regular expression to construct the |
| * NFA for |
| * |
| * @return a pair of integers denoting the index of start |
| * and end state of the NFA. |
| */ |
| private void insertCCLNFA(RegExp regExp, int start, int end) { |
| switch (regExp.type) { |
| |
| case sym.BAR: |
| RegExp2 r = (RegExp2) regExp; |
| insertCCLNFA(r.r1, start, end); |
| insertCCLNFA(r.r2, start, end); |
| return; |
| |
| case sym.CCLASS: |
| insertClassNFA( (Vector) ((RegExp1) regExp).content, start, end); |
| return; |
| |
| case sym.CCLASSNOT: |
| insertNotClassNFA( (Vector) ((RegExp1) regExp).content, start, end); |
| return; |
| |
| case sym.CHAR: |
| insertLetterNFA( |
| false, ((Character) ((RegExp1) regExp).content).charValue(), |
| start, end); |
| return; |
| |
| case sym.CHAR_I: |
| insertLetterNFA( |
| true, ((Character) ((RegExp1) regExp).content).charValue(), |
| start, end); |
| return; |
| |
| case sym.MACROUSE: |
| insertCCLNFA(macros.getDefinition((String) ((RegExp1) regExp).content), |
| start, end); |
| return; |
| } |
| |
| throw new Error("Unknown expression type "+regExp.type+" in NFA construction"); |
| } |
| |
| |
| /** |
| * Constructs an NFA for regExp such that the NFA has |
| * |
| * exactly one start state, |
| * exactly one end state, |
| * no transitions leading out of the end state |
| * no transitions leading into the start state |
| * |
| * @param regExp the regular expression to construct the |
| * NFA for |
| * |
| * @return a pair of integers denoting the index of start |
| * and end state of the NFA. |
| */ |
| public IntPair insertNFA(RegExp regExp) { |
| |
| IntPair nfa1, nfa2; |
| int start, end; |
| RegExp2 r; |
| |
| if (Options.DEBUG) |
| Out.debug("Inserting RegExp : "+regExp); |
| |
| if (regExp.isCharClass(macros)) { |
| start = numStates; |
| end = numStates+1; |
| |
| ensureCapacity(end+1); |
| if (end+1 > numStates) numStates = end+1; |
| |
| insertCCLNFA(regExp, start, end); |
| |
| return new IntPair(start, end); |
| } |
| |
| switch (regExp.type) { |
| |
| case sym.BAR: |
| |
| r = (RegExp2) regExp; |
| |
| nfa1 = insertNFA(r.r1); |
| nfa2 = insertNFA(r.r2); |
| |
| start = nfa2.end+1; |
| end = nfa2.end+2; |
| |
| addEpsilonTransition(start, nfa1.start); |
| addEpsilonTransition(start, nfa2.start); |
| addEpsilonTransition(nfa1.end, end); |
| addEpsilonTransition(nfa2.end, end); |
| |
| return new IntPair(start, end); |
| |
| case sym.CONCAT: |
| |
| r = (RegExp2) regExp; |
| |
| nfa1 = insertNFA(r.r1); |
| nfa2 = insertNFA(r.r2); |
| |
| addEpsilonTransition(nfa1.end, nfa2.start); |
| |
| return new IntPair(nfa1.start, nfa2.end); |
| |
| case sym.STAR: |
| nfa1 = insertNFA( (RegExp) ((RegExp1) regExp).content ); |
| |
| start = nfa1.end+1; |
| end = nfa1.end+2; |
| |
| addEpsilonTransition(nfa1.end, end); |
| addEpsilonTransition(start, nfa1.start); |
| |
| addEpsilonTransition(start, end); |
| addEpsilonTransition(nfa1.end, nfa1.start); |
| |
| return new IntPair(start, end); |
| |
| case sym.PLUS: |
| nfa1 = insertNFA( (RegExp) ((RegExp1) regExp).content ); |
| |
| start = nfa1.end+1; |
| end = nfa1.end+2; |
| |
| addEpsilonTransition(nfa1.end, end); |
| addEpsilonTransition(start, nfa1.start); |
| |
| addEpsilonTransition(nfa1.end, nfa1.start); |
| |
| return new IntPair(start, end); |
| |
| case sym.QUESTION: |
| nfa1 = insertNFA( (RegExp) ((RegExp1) regExp).content ); |
| |
| addEpsilonTransition(nfa1.start, nfa1.end); |
| |
| return new IntPair(nfa1.start, nfa1.end); |
| |
| case sym.BANG: |
| return complement(insertNFA((RegExp) ((RegExp1) regExp).content)); |
| |
| case sym.TILDE: |
| return insertNFA(regExp.resolveTilde(macros)); |
| |
| case sym.STRING: |
| return insertStringNFA(false, (String) ((RegExp1) regExp).content ); |
| |
| case sym.STRING_I: |
| return insertStringNFA(true, (String) ((RegExp1) regExp).content ); |
| |
| case sym.MACROUSE: |
| return insertNFA(macros.getDefinition((String) ((RegExp1) regExp).content)); |
| } |
| |
| throw new Error("Unknown expression type "+regExp.type+" in NFA construction"); |
| } |
| } |
