• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
NFAState(NFA nfa)108 	public NFAState(NFA nfa) {
109 		this.nfa = nfa;
110 	}
111 
112 	@Override
getNumberOfTransitions()113 	public int getNumberOfTransitions() {
114 		return numTransitions;
115 	}
116 
117 	@Override
addTransition(Transition e)118 	public void addTransition(Transition e) {
119 		if ( e==null ) {
120 			throw new IllegalArgumentException("You can't add a null transition");
121 		}
122 		if ( numTransitions>transition.length ) {
123 			throw new IllegalArgumentException("You can only have "+transition.length+" transitions");
124 		}
125 		if ( e!=null ) {
126 			transition[numTransitions] = e;
127 			numTransitions++;
128 			// Set the "back pointer" of the target state so that it
129 			// knows about the label of the incoming edge.
130 			Label label = e.label;
131 			if ( label.isAtom() || label.isSet() ) {
132 				if ( ((NFAState)e.target).incidentEdgeLabel!=null ) {
133 					ErrorManager.internalError("Clobbered incident edge");
134 				}
135 				((NFAState)e.target).incidentEdgeLabel = e.label;
136 			}
137 		}
138 	}
139 
140 	/** Used during optimization to reset a state to have the (single)
141 	 *  transition another state has.
142 	 */
setTransition0(Transition e)143 	public void setTransition0(Transition e) {
144 		if ( e==null ) {
145 			throw new IllegalArgumentException("You can't use a solitary null transition");
146 		}
147 		transition[0] = e;
148 		transition[1] = null;
149 		numTransitions = 1;
150 	}
151 
152 	@Override
transition(int i)153 	public Transition transition(int i) {
154 		return transition[i];
155 	}
156 
157 	/** The DFA decision for this NFA decision state always has
158 	 *  an exit path for loops as n+1 for n alts in the loop.
159 	 *  That is really useful for displaying nondeterministic alts
160 	 *  and so on, but for walking the NFA to get a sequence of edge
161 	 *  labels or for actually parsing, we need to get the real alt
162 	 *  number.  The real alt number for exiting a loop is always 1
163 	 *  as transition 0 points at the exit branch (we compute DFAs
164 	 *  always for loops at the loopback state).
165 	 *
166 	 *  For walking/parsing the loopback state:
167 	 * 		1 2 3 display alt (for human consumption)
168 	 * 		2 3 1 walk alt
169 	 *
170 	 *  For walking the block start:
171 	 * 		1 2 3 display alt
172 	 * 		1 2 3
173 	 *
174 	 *  For walking the bypass state of a (...)* loop:
175 	 * 		1 2 3 display alt
176 	 * 		1 1 2 all block alts map to entering loop exit means take bypass
177 	 *
178 	 *  Non loop EBNF do not need to be translated; they are ignored by
179 	 *  this method as decisionStateType==0.
180 	 *
181 	 *  Return same alt if we can't translate.
182 	 */
translateDisplayAltToWalkAlt(int displayAlt)183 	public int translateDisplayAltToWalkAlt(int displayAlt) {
184 		NFAState nfaStart = this;
185 		if ( decisionNumber==0 || decisionStateType==0 ) {
186 			return displayAlt;
187 		}
188 		int walkAlt = 0;
189 		// find the NFA loopback state associated with this DFA
190 		// and count number of alts (all alt numbers are computed
191 		// based upon the loopback's NFA state.
192 		/*
193 		DFA dfa = nfa.grammar.getLookaheadDFA(decisionNumber);
194 		if ( dfa==null ) {
195 			ErrorManager.internalError("can't get DFA for decision "+decisionNumber);
196 		}
197 		*/
198 		int nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(nfaStart);
199 		switch ( nfaStart.decisionStateType ) {
200 			case LOOPBACK :
201 				walkAlt = displayAlt % nAlts + 1; // rotate right mod 1..3
202 				break;
203 			case BLOCK_START :
204 			case OPTIONAL_BLOCK_START :
205 				walkAlt = displayAlt; // identity transformation
206 				break;
207 			case BYPASS :
208 				if ( displayAlt == nAlts ) {
209 					walkAlt = 2; // bypass
210 				}
211 				else {
212 					walkAlt = 1; // any non exit branch alt predicts entering
213 				}
214 				break;
215 		}
216 		return walkAlt;
217 	}
218 
219 	// Setter/Getters
220 
221 	/** What AST node is associated with this NFAState?  When you
222 	 *  set the AST node, I set the node to point back to this NFA state.
223 	 */
setDecisionASTNode(GrammarAST decisionASTNode)224 	public void setDecisionASTNode(GrammarAST decisionASTNode) {
225 		decisionASTNode.setNFAStartState(this);
226 		this.associatedASTNode = decisionASTNode;
227 	}
228 
getDescription()229 	public String getDescription() {
230 		return description;
231 	}
232 
setDescription(String description)233 	public void setDescription(String description) {
234 		this.description = description;
235 	}
236 
getDecisionNumber()237 	public int getDecisionNumber() {
238 		return decisionNumber;
239 	}
240 
setDecisionNumber(int decisionNumber)241 	public void setDecisionNumber(int decisionNumber) {
242 		this.decisionNumber = decisionNumber;
243 	}
244 
isEOTTargetState()245 	public boolean isEOTTargetState() {
246 		return EOTTargetState;
247 	}
248 
setEOTTargetState(boolean eot)249 	public void setEOTTargetState(boolean eot) {
250 		EOTTargetState = eot;
251 	}
252 
isDecisionState()253 	public boolean isDecisionState() {
254 		return decisionStateType>0;
255 	}
256 
257 	@Override
toString()258 	public String toString() {
259 		return String.valueOf(stateNumber);
260 	}
261 
262 }
263 
264