dfa.java

antlr最新版本V3源代码

/*
 [The "BSD licence"]
 Copyright (c) 2005-2006 Terence Parr
 All rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions
 are met:
 1. Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
 2. Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in the
    documentation and/or other materials provided with the distribution.
 3. The name of the author may not be used to endorse or promote products
    derived from this software without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package org.antlr.analysis;

import org.antlr.Tool;
import org.antlr.codegen.CodeGenerator;
import org.antlr.misc.IntervalSet;
import org.antlr.misc.IntSet;
import org.antlr.misc.Utils;
import org.antlr.runtime.IntStream;
import org.antlr.stringtemplate.StringTemplate;
import org.antlr.tool.*;

import java.util.*;

/** A DFA (converted from a grammar's NFA).
 *  DFAs are used as prediction machine for alternative blocks in all kinds
 *  of recognizers (lexers, parsers, tree walkers).
 */
public class DFA {
	public static final int REACHABLE_UNKNOWN = -2;
	public static final int REACHABLE_BUSY = -1; // in process of computing
	public static final int REACHABLE_NO = 0;
	public static final int REACHABLE_YES = 1;

	/** Prevent explosion of DFA states during conversion. The max number
	 *  of states per alt in a single decision's DFA.
	 */
	public static final int MAX_STATES_PER_ALT_IN_DFA = 450;

	/** Set to 0 to not terminate early */
	public static int MAX_TIME_PER_DFA_CREATION = 1*1000;

	/** How many edges can each DFA state have before a "special" state
	 *  is created that uses IF expressions instead of a table?
	 */
	public static int MAX_STATE_TRANSITIONS_FOR_TABLE = 65534;

	/** What's the start state for this DFA? */
    public DFAState startState;

	/** This DFA is being built for which decision? */
	public int decisionNumber = 0;

    /** From what NFAState did we create the DFA? */
    public NFAState decisionNFAStartState;

	/** The printable grammar fragment associated with this DFA */
	public String description;

	/** A set of all uniquely-numbered DFA states.  Maps hash of DFAState
     *  to the actual DFAState object.  We use this to detect
     *  existing DFA states.  Map<DFAState,DFAState>.  Use Map so
	 *  we can get old state back (Set only allows you to see if it's there).
	 *  Not used during fixed k lookahead as it's a waste to fill it with
	 *  a dup of states array.
     */
    protected Map uniqueStates = new HashMap();

	/** Maps the state number to the actual DFAState.  Use a Vector as it
	 *  grows automatically when I set the ith element.  This contains all
	 *  states, but the states are not unique.  s3 might be same as s1 so
	 *  s3 -> s1 in this table.  This is how cycles occur.  If fixed k,
	 *  then these states will all be unique as states[i] always points
	 *  at state i when no cycles exist.
	 *
	 *  This is managed in parallel with uniqueStates and simply provides
	 *  a way to go from state number to DFAState rather than via a
	 *  hash lookup.
	 */
	protected Vector states = new Vector();

	/** Unique state numbers */
	protected int stateCounter = 0;

	/** count only new states not states that were rejected as already present */
	protected int numberOfStates = 0;

	/** User specified max fixed lookahead.  If 0, nothing specified.  -1
	 *  implies we have not looked at the options table yet to set k.
	 */
	protected int user_k = -1;

	/** While building the DFA, track max lookahead depth if not cyclic */
	protected int max_k = -1;

    /** Is this DFA reduced?  I.e., can all states lead to an accept state? */
    protected boolean reduced = true;

    /** Are there any loops in this DFA?
	 *  Computed by doesStateReachAcceptState()
	 */
    protected boolean cyclic = false;

    /** Each alt in an NFA derived from a grammar must have a DFA state that
     *  predicts it lest the parser not know what to do.  Nondeterminisms can
     *  lead to this situation (assuming no semantic predicates can resolve
     *  the problem) and when for some reason, I cannot compute the lookahead
     *  (which might arise from an error in the algorithm or from
     *  left-recursion etc...).  This list starts out with all alts contained
     *  and then in method doesStateReachAcceptState() I remove the alts I
     *  know to be uniquely predicted.
     */
    protected List unreachableAlts;

	protected int nAlts = 0;

	/** We only want one accept state per predicted alt; track here */
	protected DFAState[] altToAcceptState;

	/** Track whether an alt discovers recursion for each alt during
	 *  NFA to DFA conversion; >1 alt with recursion implies nonregular.
	 */
	protected IntSet recursiveAltSet = new IntervalSet();

	/** Which NFA are we converting (well, which piece of the NFA)? */
    public NFA nfa;

	protected NFAToDFAConverter nfaConverter;

	/** This probe tells you a lot about a decision and is useful even
	 *  when there is no error such as when a syntactic nondeterminism
	 *  is solved via semantic predicates.  Perhaps a GUI would want
	 *  the ability to show that.
	 */
	public DecisionProbe probe = new DecisionProbe(this);

	/** Track absolute time of the conversion so we can have a failsafe:
	 *  if it takes too long, then terminate.  Assume bugs are in the
	 *  analysis engine.
	 */
	protected long conversionStartTime;

	/** Map an edge transition table to a unique set number; ordered so
	 *  we can push into the output template as an ordered list of sets
	 *  and then ref them from within the transition[][] table.  Like this
	 *  for C# target:
	 *     public static readonly DFA30_transition0 =
	 *     	new short[] { 46, 46, -1, 46, 46, -1, -1, -1, -1, -1, -1, -1,...};
	 *         public static readonly DFA30_transition1 =
	 *     	new short[] { 21 };
	 *      public static readonly short[][] DFA30_transition = {
	 *     	  DFA30_transition0,
	 *     	  DFA30_transition0,
	 *     	  DFA30_transition1,
	 *     	  ...
	 *      };
	 */
	public Map edgeTransitionClassMap = new LinkedHashMap();

	/** The unique edge transition class number; every time we see a new
	 *  set of edges emanating from a state, we number it so we can reuse
	 *  if it's every seen again for another state.  For Java grammar,
	 *  some of the big edge transition tables are seen about 57 times.
	 */
	protected int edgeTransitionClass =0;

	/* This DFA can be converted to a transition[state][char] table and
	 * the following tables are filled by createStateTables upon request.
	 * These are injected into the templates for code generation.
	 * See March 25, 2006 entry for description:
	 *   http://www.antlr.org/blog/antlr3/codegen.tml
	 * Often using Vector as can't set ith position in a List and have
	 * it extend list size; bizarre.
	 */

	/** List of special DFAState objects */
	public List specialStates;
	/** List of ST for special states. */
	public List specialStateSTs;
	public Vector accept;
	public Vector eot;
	public Vector eof;
	public Vector min;
	public Vector max;
	public Vector special;
	public Vector transition;
	/** just the Vector<Integer> indicating which unique edge table is at
	 *  position i.
	 */
	public Vector transitionEdgeTables; // not used by java yet
	protected int uniqueCompressedSpecialStateNum = 0;

	public DFA(int decisionNumber, NFAState decisionStartState) {
		this.decisionNumber = decisionNumber;
        this.decisionNFAStartState = decisionStartState;
        nfa = decisionStartState.nfa;
        nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState);
        //setOptions( nfa.grammar.getDecisionOptions(getDecisionNumber()) );
        initAltRelatedInfo();

		//long start = System.currentTimeMillis();
        nfaConverter = new NFAToDFAConverter(this);
		nfaConverter.convert();

		// figure out if there are problems with decision
		verify();

		if ( !probe.isDeterministic() ||
			 probe.analysisAborted() ||
			 probe.analysisOverflowed() )
		{
			probe.issueWarnings();
		}

		// must be after verify as it computes cyclic, needed by this routine
		// should be after warnings because early termination or something
		// will not allow the reset to operate properly in some cases.
		resetStateNumbersToBeContiguous();

		//long stop = System.currentTimeMillis();
		//System.out.println("verify cost: "+(int)(stop-start)+" ms");

		if ( Tool.internalOption_PrintDFA ) {
			System.out.println("DFA d="+decisionNumber);
			FASerializer serializer = new FASerializer(nfa.grammar);
			String result = serializer.serialize(startState);
			System.out.println(result);
		}
    }

	/** Walk all states and reset their numbers to be a contiguous sequence
	 *  of integers starting from 0.  Only cyclic DFA can have unused positions
	 *  in states list.  State i might be identical to a previous state j and
	 *  will result in states[i] == states[j].  We don't want to waste a state
	 *  number on this.  Useful mostly for code generation in tables.
	 *
	 *  At the start of this routine, states[i].stateNumber <= i by definition.
	 *  If states[50].stateNumber is 50 then a cycle during conversion may
	 *  try to add state 103, but we find that an identical DFA state, named
	 *  50, already exists, hence, states[103]==states[50] and both have
	 *  stateNumber 50 as they point at same object.  Afterwards, the set
	 *  of state numbers from all states should represent a contiguous range
	 *  from 0..n-1 where n is the number of unique states.
	 */
	public void resetStateNumbersToBeContiguous() {
		if ( getUserMaxLookahead()>0 ) {
			// all numbers are unique already; no states are thrown out.
			return;
		}
        /*
        if ( decisionNumber==14 ) {
			System.out.println("DFA :"+decisionNumber+" "+this);
            //System.out.println("DFA start state :"+startState);
			System.out.println("unique state numbers: ");
			Set s = getUniqueStates().keySet();
			for (Iterator it = s.iterator(); it.hasNext();) {
				DFAState d = (DFAState) it.next();
				System.out.print(d.stateNumber+" ");
			}
			System.out.println();

			System.out.println("size="+s.size());
			System.out.println("continguous states: ");
			for (Iterator it = states.iterator(); it.hasNext();) {
				DFAState d = (DFAState) it.next();
				if ( d!=null ) {
                    System.out.print(d.stateNumber+" ");
                }
			}
			System.out.println();

			//Set a = new HashSet();
			List a = new ArrayList();
			System.out.println("unique set from states table: ");
			for (int i = 0; i <= getMaxStateNumber(); i++) {
				DFAState d = getState(i);
                if ( d==null ) {
                    continue;
                }
                boolean found=false;
				for (int j=0; j<a.size(); j++) {
					DFAState old = (DFAState)a.get(j);
					if ( old.equals(d) ) {
						if ( old.stateNumber!=d.stateNumber ) {
							System.out.println("WHAT! state["+i+"]="+d+" prev in list as "+old);
						}
						found=true;
					}
				}
				if ( !found ) {
					a.add(d);
				}
			}
			for (Iterator it = a.iterator(); it.hasNext();) {
				DFAState d = (DFAState) it.next();
                if ( d!=null ) {
                    System.out.print(d.stateNumber+" ");
                }
            }
			System.out.println();
			System.out.println("size="+a.size());

			if ( a.equals(s) ) {
				System.out.println("both sets same");
			}
			else {
				System.out.println("sets NOT same");
			}
			System.out.println("stateCounter="+stateCounter);
		}
        */

        // walk list of DFAState objects by state number,
		// setting state numbers to 0..n-1
		int snum=0;
		for (int i = 0; i <= getMaxStateNumber(); i++) {
			DFAState s = getState(i);
            // some states are unused after creation most commonly due to cycles
            // or conflict resolution.
            if ( s==null ) {
                continue;
            }
			// state i is mapped to DFAState with state number set to i originally
			// so if it's less than i, then we renumbered it already; that
			// happens when states have been merged or cycles occurred I think.
			// states[50] will point to DFAState with s50 in it but
			// states[103] might also point at this same DFAState.  Since
			// 50 < 103 then it's already been renumbered as it points downwards.
			boolean alreadyRenumbered = s.stateNumber<i;
			if ( !alreadyRenumbered ) {
				// state i is a valid state, reset it's state number
				s.stateNumber = snum; // rewrite state numbers to be 0..n-1
				snum++;
			}
		}
        /*
        if ( decisionNumber==14 ) {
			//System.out.println("max state num: "+maxStateNumber);
			System.out.println("after renum, DFA :"+decisionNumber+" "+this);
			System.out.println("uniq states.size="+uniqueStates.size());

			Set a = new HashSet();
			System.out.println("after renumber; unique set from states table: ");
			for (int i = 0; i <= getMaxStateNumber(); i++) {
				DFAState d = getState(i);
				a.add(d);
			}
			for (Iterator it = a.iterator(); it.hasNext();) {
				DFAState d = (DFAState) it.next();
				if ( d!=null ) {
                    System.out.print(d.stateNumber+" ");
                }
			}