Home | History | Annotate | Download | only in analysis 
      1 /*
      2  * [The "BSD license"]
      3  *  Copyright (c) 2010 Terence Parr
      4  *  All rights reserved.
      5  *
      6  *  Redistribution and use in source and binary forms, with or without
      7  *  modification, are permitted provided that the following conditions
      8  *  are met:
      9  *  1. Redistributions of source code must retain the above copyright
     10  *      notice, this list of conditions and the following disclaimer.
     11  *  2. Redistributions in binary form must reproduce the above copyright
     12  *      notice, this list of conditions and the following disclaimer in the
     13  *      documentation and/or other materials provided with the distribution.
     14  *  3. The name of the author may not be used to endorse or promote products
     15  *      derived from this software without specific prior written permission.
     16  *
     17  *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18  *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19  *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20  *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22  *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26  *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27  */
     28 package org.antlr.analysis;
     29 
     30 import org.antlr.tool.ErrorManager;
     31 import org.antlr.tool.GrammarAST;
     32 import org.antlr.tool.Rule;
     33 
     34 /** A state within an NFA. At most 2 transitions emanate from any NFA state. */
     35 public class NFAState extends State {
     36 	// I need to distinguish between NFA decision states for (...)* and (...)+
     37 	// during NFA interpretation.
     38 	public static final int LOOPBACK = 1;
     39 	public static final int BLOCK_START = 2;
     40 	public static final int OPTIONAL_BLOCK_START = 3;
     41 	public static final int BYPASS = 4;
     42 	public static final int RIGHT_EDGE_OF_BLOCK = 5;
     43 
     44 	public static final int MAX_TRANSITIONS = 2;
     45 
     46 	/** How many transitions; 0, 1, or 2 transitions */
     47 	int numTransitions = 0;
     48 	public Transition[] transition = new Transition[MAX_TRANSITIONS];
     49 
     50 	/** For o-A->o type NFA tranitions, record the label that leads to this
     51 	 *  state.  Useful for creating rich error messages when we find
     52 	 *  insufficiently (with preds) covered states.
     53 	 */
     54 	public Label incidentEdgeLabel;
     55 
     56 	/** Which NFA are we in? */
     57 	public NFA nfa = null;
     58 
     59 	/** What's its decision number from 1..n? */
     60 	protected int decisionNumber = 0;
     61 
     62 	/** Subrules (...)* and (...)+ have more than one decision point in
     63 	 *  the NFA created for them.  They both have a loop-exit-or-stay-in
     64 	 *  decision node (the loop back node).  They both have a normal
     65 	 *  alternative block decision node at the left edge.  The (...)* is
     66 	 *  worse as it even has a bypass decision (2 alts: stay in or bypass)
     67 	 *  node at the extreme left edge.  This is not how they get generated
     68 	 *  in code as a while-loop or whatever deals nicely with either.  For
     69 	 *  error messages (where I need to print the nondeterministic alts)
     70 	 *  and for interpretation, I need to use the single DFA that is created
     71 	 *  (for efficiency) but interpret the results differently depending
     72 	 *  on which of the 2 or 3 decision states uses the DFA.  For example,
     73 	 *  the DFA will always report alt n+1 as the exit branch for n real
     74 	 *  alts, so I need to translate that depending on the decision state.
     75 	 *
     76 	 *  If decisionNumber>0 then this var tells you what kind of decision
     77 	 *  state it is.
     78 	 */
     79 	public int decisionStateType;
     80 
     81 	/** What rule do we live in? */
     82 	public Rule enclosingRule;
     83 
     84 	/** During debugging and for nondeterminism warnings, it's useful
     85 	 *  to know what relationship this node has to the original grammar.
     86 	 *  For example, "start of alt 1 of rule a".
     87 	 */
     88 	protected String description;
     89 
     90 	/** Associate this NFAState with the corresponding GrammarAST node
     91 	 *  from which this node was created.  This is useful not only for
     92 	 *  associating the eventual lookahead DFA with the associated
     93 	 *  Grammar position, but also for providing users with
     94 	 *  nondeterminism warnings.  Mainly used by decision states to
     95 	 *  report line:col info.  Could also be used to track line:col
     96 	 *  for elements such as token refs.
     97 	 */
     98 	public GrammarAST associatedASTNode;
     99 
    100 	/** Is this state the sole target of an EOT transition? */
    101 	protected boolean EOTTargetState = false;
    102 
    103 	/** Jean Bovet needs in the GUI to know which state pairs correspond
    104 	 *  to the start/stop of a block.
    105 	  */
    106 	public int endOfBlockStateNumber = State.INVALID_STATE_NUMBER;
    107 
    108 	public NFAState(NFA nfa) {
    109 		this.nfa = nfa;
    110 	}
    111 
    112 	public int getNumberOfTransitions() {
    113 		return numTransitions;
    114 	}
    115 
    116 	public void addTransition(Transition e) {
    117 		if ( e==null ) {
    118 			throw new IllegalArgumentException("You can't add a null transition");
    119 		}
    120 		if ( numTransitions>transition.length ) {
    121 			throw new IllegalArgumentException("You can only have "+transition.length+" transitions");
    122 		}
    123 		if ( e!=null ) {
    124 			transition[numTransitions] = e;
    125 			numTransitions++;
    126 			// Set the "back pointer" of the target state so that it
    127 			// knows about the label of the incoming edge.
    128 			Label label = e.label;
    129 			if ( label.isAtom() || label.isSet() ) {
    130 				if ( ((NFAState)e.target).incidentEdgeLabel!=null ) {
    131 					ErrorManager.internalError("Clobbered incident edge");
    132 				}
    133 				((NFAState)e.target).incidentEdgeLabel = e.label;
    134 			}
    135 		}
    136 	}
    137 
    138 	/** Used during optimization to reset a state to have the (single)
    139 	 *  transition another state has.
    140 	 */
    141 	public void setTransition0(Transition e) {
    142 		if ( e==null ) {
    143 			throw new IllegalArgumentException("You can't use a solitary null transition");
    144 		}
    145 		transition[0] = e;
    146 		transition[1] = null;
    147 		numTransitions = 1;
    148 	}
    149 
    150 	public Transition transition(int i) {
    151 		return transition[i];
    152 	}
    153 
    154 	/** The DFA decision for this NFA decision state always has
    155 	 *  an exit path for loops as n+1 for n alts in the loop.
    156 	 *  That is really useful for displaying nondeterministic alts
    157 	 *  and so on, but for walking the NFA to get a sequence of edge
    158 	 *  labels or for actually parsing, we need to get the real alt
    159 	 *  number.  The real alt number for exiting a loop is always 1
    160 	 *  as transition 0 points at the exit branch (we compute DFAs
    161 	 *  always for loops at the loopback state).
    162 	 *
    163 	 *  For walking/parsing the loopback state:
    164 	 * 		1 2 3 display alt (for human consumption)
    165 	 * 		2 3 1 walk alt
    166 	 *
    167 	 *  For walking the block start:
    168 	 * 		1 2 3 display alt
    169 	 * 		1 2 3
    170 	 *
    171 	 *  For walking the bypass state of a (...)* loop:
    172 	 * 		1 2 3 display alt
    173 	 * 		1 1 2 all block alts map to entering loop exit means take bypass
    174 	 *
    175 	 *  Non loop EBNF do not need to be translated; they are ignored by
    176 	 *  this method as decisionStateType==0.
    177 	 *
    178 	 *  Return same alt if we can't translate.
    179 	 */
    180 	public int translateDisplayAltToWalkAlt(int displayAlt) {
    181 		NFAState nfaStart = this;
    182 		if ( decisionNumber==0 || decisionStateType==0 ) {
    183 			return displayAlt;
    184 		}
    185 		int walkAlt = 0;
    186 		// find the NFA loopback state associated with this DFA
    187 		// and count number of alts (all alt numbers are computed
    188 		// based upon the loopback's NFA state.
    189 		/*
    190 		DFA dfa = nfa.grammar.getLookaheadDFA(decisionNumber);
    191 		if ( dfa==null ) {
    192 			ErrorManager.internalError("can't get DFA for decision "+decisionNumber);
    193 		}
    194 		*/
    195 		int nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(nfaStart);
    196 		switch ( nfaStart.decisionStateType ) {
    197 			case LOOPBACK :
    198 				walkAlt = displayAlt % nAlts + 1; // rotate right mod 1..3
    199 				break;
    200 			case BLOCK_START :
    201 			case OPTIONAL_BLOCK_START :
    202 				walkAlt = displayAlt; // identity transformation
    203 				break;
    204 			case BYPASS :
    205 				if ( displayAlt == nAlts ) {
    206 					walkAlt = 2; // bypass
    207 				}
    208 				else {
    209 					walkAlt = 1; // any non exit branch alt predicts entering
    210 				}
    211 				break;
    212 		}
    213 		return walkAlt;
    214 	}
    215 
    216 	// Setter/Getters
    217 
    218 	/** What AST node is associated with this NFAState?  When you
    219 	 *  set the AST node, I set the node to point back to this NFA state.
    220 	 */
    221 	public void setDecisionASTNode(GrammarAST decisionASTNode) {
    222 		decisionASTNode.setNFAStartState(this);
    223 		this.associatedASTNode = decisionASTNode;
    224 	}
    225 
    226 	public String getDescription() {
    227 		return description;
    228 	}
    229 
    230 	public void setDescription(String description) {
    231 		this.description = description;
    232 	}
    233 
    234 	public int getDecisionNumber() {
    235 		return decisionNumber;
    236 	}
    237 
    238 	public void setDecisionNumber(int decisionNumber) {
    239 		this.decisionNumber = decisionNumber;
    240 	}
    241 
    242 	public boolean isEOTTargetState() {
    243 		return EOTTargetState;
    244 	}
    245 
    246 	public void setEOTTargetState(boolean eot) {
    247 		EOTTargetState = eot;
    248 	}
    249 
    250 	public boolean isDecisionState() {
    251 		return decisionStateType>0;
    252 	}
    253 
    254 	public String toString() {
    255 		return String.valueOf(stateNumber);
    256 	}
    257 
    258 }
    259 
    260