dfa.java

antlr最新版本V3源代码

			System.out.println();
			System.out.println("size="+a.size());
		}
        */
        if ( snum!=getNumberOfStates() ) {
			ErrorManager.internalError("DFA "+decisionNumber+": "+
				decisionNFAStartState.getDescription()+" num unique states "+getNumberOfStates()+
				"!= num renumbered states "+snum);
		}
	}

	// JAVA-SPECIFIC Accessors!!!!!  It is so impossible to get arrays
	// or even consistently formatted strings acceptable to java that
	// I am forced to build the individual char elements here

	public List getJavaCompressedAccept() { return getRunLengthEncoding(accept); }
	public List getJavaCompressedEOT() { return getRunLengthEncoding(eot); }
	public List getJavaCompressedEOF() { return getRunLengthEncoding(eof); }
	public List getJavaCompressedMin() { return getRunLengthEncoding(min); }
	public List getJavaCompressedMax() { return getRunLengthEncoding(max); }
	public List getJavaCompressedSpecial() { return getRunLengthEncoding(special); }
	public List getJavaCompressedTransition() {
		if ( transition==null || transition.size()==0 ) {
			return null;
		}
		List encoded = new ArrayList(transition.size());
		// walk Vector<Vector<FormattedInteger>> which is the transition[][] table
		for (int i = 0; i < transition.size(); i++) {
			Vector transitionsForState = (Vector) transition.elementAt(i);
			encoded.add(getRunLengthEncoding(transitionsForState));
		}
		return encoded;
	}

	/** Compress the incoming data list so that runs of same number are
	 *  encoded as number,value pair sequences.  3 -1 -1 -1 28 is encoded
	 *  as 1 3 3 -1 1 28.  I am pretty sure this is the lossless compression
	 *  that GIF files use.  Transition tables are heavily compressed by
	 *  this technique.  I got the idea from JFlex http://jflex.de/
	 *
	 *  Return List<String> where each string is either \xyz for 8bit char
	 *  and \uFFFF for 16bit.  Hideous and specific to Java, but it is the
	 *  only target bad enough to need it.
	 */
	public List getRunLengthEncoding(List data) {
		if ( data==null || data.size()==0 ) {
			// for states with no transitions we want an empty string ""
			// to hold its place in the transitions array.
			List empty = new ArrayList();
			empty.add("");
			return empty;
		}
		int size = Math.max(2,data.size()/2);
		List encoded = new ArrayList(size); // guess at size
		// scan values looking for runs
		int i = 0;
		Integer emptyValue = Utils.integer(-1);
		while ( i < data.size() ) {
			Integer I = (Integer)data.get(i);
			if ( I==null ) {
				I = emptyValue;
			}
			// count how many v there are?
			int n = 0;
			for (int j = i; j < data.size(); j++) {
				Integer v = (Integer)data.get(j);
				if ( v==null ) {
					v = emptyValue;
				}
				if ( I.equals(v) ) {
					n++;
				}
				else {
					break;
				}
			}
			encoded.add(encodeIntAsCharEscape((char)n));
			encoded.add(encodeIntAsCharEscape((char)I.intValue()));
			i+=n;
		}
		return encoded;
	}

	public void createStateTables(CodeGenerator generator) {
		//System.out.println("createTables:\n"+this);

		description = getNFADecisionStartState().getDescription();
		description =
			generator.target.getTargetStringLiteralFromString(description);

		// create all the tables
		special = new Vector(this.getNumberOfStates()); // Vector<short>
		special.setSize(this.getNumberOfStates());
		specialStates = new ArrayList();				// List<DFAState>
		specialStateSTs = new ArrayList();				// List<ST>
		accept = new Vector(this.getNumberOfStates()); // Vector<int>
		accept.setSize(this.getNumberOfStates());
		eot = new Vector(this.getNumberOfStates()); // Vector<int>
		eot.setSize(this.getNumberOfStates());
		eof = new Vector(this.getNumberOfStates()); // Vector<int>
		eof.setSize(this.getNumberOfStates());
		min = new Vector(this.getNumberOfStates()); // Vector<int>
		min.setSize(this.getNumberOfStates());
		max = new Vector(this.getNumberOfStates()); // Vector<int>
		max.setSize(this.getNumberOfStates());
		transition = new Vector(this.getNumberOfStates()); // Vector<Vector<int>>
		transition.setSize(this.getNumberOfStates());
		transitionEdgeTables = new Vector(this.getNumberOfStates()); // Vector<Vector<int>>
		transitionEdgeTables.setSize(this.getNumberOfStates());

		// for each state in the DFA, fill relevant tables.
		Iterator it = null;
		if ( getUserMaxLookahead()>0 ) {
			it = states.iterator();
		}
		else {
			it = getUniqueStates().values().iterator();
		}
		while ( it.hasNext() ) {
			DFAState s = (DFAState)it.next();
			if ( s==null ) {
				// ignore null states; some acylic DFA see this condition
				// when inlining DFA (due to lacking of exit branch pruning?)
				continue;
			}
			if ( s.isAcceptState() ) {
				// can't compute min,max,special,transition on accepts
				accept.set(s.stateNumber,
						   Utils.integer(s.getUniquelyPredictedAlt()));
			}
			else {
				createMinMaxTables(s);
				createTransitionTableEntryForState(s);
				createSpecialTable(s);
				createEOTAndEOFTables(s);
			}
		}

		// now that we have computed list of specialStates, gen code for 'em
		for (int i = 0; i < specialStates.size(); i++) {
			DFAState ss = (DFAState) specialStates.get(i);
			StringTemplate stateST =
				generator.generateSpecialState(ss);
			specialStateSTs.add(stateST);
		}

		// check that the tables are not messed up by encode/decode
		/*
		testEncodeDecode(min);
		testEncodeDecode(max);
		testEncodeDecode(accept);
		testEncodeDecode(special);
		System.out.println("min="+min);
		System.out.println("max="+max);
		System.out.println("eot="+eot);
		System.out.println("eof="+eof);
		System.out.println("accept="+accept);
		System.out.println("special="+special);
		System.out.println("transition="+transition);
		*/
	}

	/*
	private void testEncodeDecode(List data) {
		System.out.println("data="+data);
		List encoded = getRunLengthEncoding(data);
		StringBuffer buf = new StringBuffer();
		for (int i = 0; i < encoded.size(); i++) {
			String I = (String)encoded.get(i);
			int v = 0;
			if ( I.startsWith("\\u") ) {
				v = Integer.parseInt(I.substring(2,I.length()), 16);
			}
			else {
				v = Integer.parseInt(I.substring(1,I.length()), 8);
			}
			buf.append((char)v);
		}
		String encodedS = buf.toString();
		short[] decoded = org.antlr.runtime.DFA.unpackEncodedString(encodedS);
		//System.out.println("decoded:");
		for (int i = 0; i < decoded.length; i++) {
			short x = decoded[i];
			if ( x!=((Integer)data.get(i)).intValue() ) {
				System.err.println("problem with encoding");
			}
			//System.out.print(", "+x);
		}
		//System.out.println();
	}
	*/

	protected void createMinMaxTables(DFAState s) {
		int smin = Label.MAX_CHAR_VALUE + 1;
		int smax = Label.MIN_ATOM_VALUE - 1;
		for (int j = 0; j < s.getNumberOfTransitions(); j++) {
			Transition edge = (Transition) s.transition(j);
			Label label = edge.label;
			if ( label.isAtom() ) {
				if ( label.getAtom()>=Label.MIN_CHAR_VALUE ) {
					if ( label.getAtom()<smin ) {
						smin = label.getAtom();
					}
					if ( label.getAtom()>smax ) {
						smax = label.getAtom();
					}
				}
			}
			else if ( label.isSet() ) {
				IntervalSet labels = (IntervalSet)label.getSet();
				int lmin = labels.getMinElement();
				// if valid char (don't do EOF) and less than current min
				if ( lmin<smin && lmin>=Label.MIN_CHAR_VALUE ) {
					smin = labels.getMinElement();
				}
				if ( labels.getMaxElement()>smax ) {
					smax = labels.getMaxElement();
				}
			}
		}

		if ( smax<0 ) {
			// must be predicates or pure EOT transition; just zero out min, max
			smin = Label.MIN_CHAR_VALUE;
			smax = Label.MIN_CHAR_VALUE;
		}

		min.set(s.stateNumber, Utils.integer((char)smin));
		max.set(s.stateNumber, Utils.integer((char)smax));

		if ( smax<0 || smin>Label.MAX_CHAR_VALUE || smin<0 ) {
			ErrorManager.internalError("messed up: min="+min+", max="+max);
		}
	}

	protected void createTransitionTableEntryForState(DFAState s) {
		/*
		System.out.println("createTransitionTableEntryForState s"+s.stateNumber+
			" dec "+s.dfa.decisionNumber+" cyclic="+s.dfa.isCyclic());
			*/
		int smax = ((Integer)max.get(s.stateNumber)).intValue();
		int smin = ((Integer)min.get(s.stateNumber)).intValue();

		Vector stateTransitions = new Vector(smax-smin+1);
		stateTransitions.setSize(smax-smin+1);
		transition.set(s.stateNumber, stateTransitions);
		for (int j = 0; j < s.getNumberOfTransitions(); j++) {
			Transition edge = (Transition) s.transition(j);
			Label label = edge.label;
			if ( label.isAtom() && label.getAtom()>=Label.MIN_CHAR_VALUE ) {
				int labelIndex = label.getAtom()-smin; // offset from 0
				stateTransitions.set(labelIndex,
									 Utils.integer(edge.target.stateNumber));
			}
			else if ( label.isSet() ) {
				IntervalSet labels = (IntervalSet)label.getSet();
				int[] atoms = labels.toArray();
				for (int a = 0; a < atoms.length; a++) {
					// set the transition if the label is valid (don't do EOF)
					if ( atoms[a]>=Label.MIN_CHAR_VALUE ) {
						int labelIndex = atoms[a]-smin; // offset from 0
						stateTransitions.set(labelIndex,
											 Utils.integer(edge.target.stateNumber));
					}
				}
			}
		}
		// track unique state transition tables so we can reuse
		Integer edgeClass = (Integer)edgeTransitionClassMap.get(stateTransitions);
		if ( edgeClass!=null ) {
			//System.out.println("we've seen this array before; size="+stateTransitions.size());
			transitionEdgeTables.set(s.stateNumber, edgeClass);
		}
		else {
			/*
			if ( stateTransitions.size()>255 ) {
				System.out.println("edge edgeTable "+stateTransitions.size()+" s"+s.stateNumber+": "+Utils.integer(edgeTransitionClass));
			}
			else {
				System.out.println("stateTransitions="+stateTransitions);
			}
			*/
			edgeClass = Utils.integer(edgeTransitionClass);
			transitionEdgeTables.set(s.stateNumber, edgeClass);
			edgeTransitionClassMap.put(stateTransitions, edgeClass);
			edgeTransitionClass++;
		}
	}

	/** Set up the EOT and EOF tables; we cannot put -1 min/max values so
	 *  we need another way to test that in the DFA transition function.
	 */
	protected void createEOTAndEOFTables(DFAState s) {
		for (int j = 0; j < s.getNumberOfTransitions(); j++) {
			Transition edge = (Transition) s.transition(j);
			Label label = edge.label;
			if ( label.isAtom() ) {
				if ( label.getAtom()==Label.EOT ) {
					// eot[s] points to accept state
					eot.set(s.stateNumber, Utils.integer(edge.target.stateNumber));
				}
				else if ( label.getAtom()==Label.EOF ) {
					// eof[s] points to accept state
					eof.set(s.stateNumber, Utils.integer(edge.target.stateNumber));
				}
			}
			else if ( label.isSet() ) {
				IntervalSet labels = (IntervalSet)label.getSet();
				int[] atoms = labels.toArray();
				for (int a = 0; a < atoms.length; a++) {
					if ( atoms[a]==Label.EOT ) {
						// eot[s] points to accept state
						eot.set(s.stateNumber, Utils.integer(edge.target.stateNumber));
					}
					else if ( atoms[a]==Label.EOF ) {
						eof.set(s.stateNumber, Utils.integer(edge.target.stateNumber));
					}
				}
			}
		}
	}

	protected void createSpecialTable(DFAState s) {
		// number all special states from 0...n-1 instead of their usual numbers
		boolean hasSemPred = false;

		// TODO this code is very similar to canGenerateSwitch.  Refactor to share
		for (int j = 0; j < s.getNumberOfTransitions(); j++) {
			Transition edge = (Transition) s.transition(j);
			Label label = edge.label;
			// can't do a switch if the edges have preds or are going to
			// require gated predicates
			if ( label.isSemanticPredicate() ||
				 ((DFAState)edge.target).getGatedPredicatesInNFAConfigurations()!=null)
			{
				hasSemPred = true;
				break;
			}
		}
		// if has pred or too big for table, make it special
		int smax = ((Integer)max.get(s.stateNumber)).intValue();
		int smin = ((Integer)min.get(s.stateNumber)).intValue();
		if ( hasSemPred || smax-smin>MAX_STATE_TRANSITIONS_FOR_TABLE ) {
			special.set(s.stateNumber,
						Utils.integer(uniqueCompressedSpecialStateNum));
			uniqueCompressedSpecialStateNum++;
			specialStates.add(s);
		}
		else {
			special.set(s.stateNumber, Utils.integer(-1)); // not special
		}
	}

	public static String encodeIntAsCharEscape(int v) {
		if ( v<=127 ) {
			return "\\"+Integer.toOctalString(v);
		}
		String hex = Integer.toHexString(v|0x10000).substring(1,5);
		return "\\u"+hex;
	}

	public int predict(IntStream input) {
		Interpreter interp = new Interpreter(nfa.grammar, input);
		return interp.predict(this);
	}

	/** Add a new DFA state to this DFA if not already present.
     *  To force an acyclic, fixed maximum depth DFA, just always
	 *  return the incoming state.  By not reusing old states,