001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.analysis;
029:
030: import org.antlr.tool.GrammarAST;
031:
032: /** A state within an NFA. At most 2 transitions emanate from any NFA state. */
033: public class NFAState extends State {
034: // I need to distinguish between NFA decision states for (...)* and (...)+
035: // during NFA interpretation.
036: public static final int LOOPBACK = 1;
037: public static final int BLOCK_START = 2;
038: public static final int OPTIONAL_BLOCK_START = 3;
039: public static final int BYPASS = 4;
040: public static final int RIGHT_EDGE_OF_BLOCK = 5;
041:
042: public static final int MAX_TRANSITIONS = 2;
043:
044: /** How many transitions; 0, 1, or 2 transitions */
045: int numTransitions = 0;
046: Transition[] transition = new Transition[MAX_TRANSITIONS];
047:
048: /** Which NFA are we in? */
049: public NFA nfa = null;
050:
051: /** What's its decision number from 1..n? */
052: protected int decisionNumber = 0;
053:
054: /** Subrules (...)* and (...)+ have more than one decision point in
055: * the NFA created for them. They both have a loop-exit-or-stay-in
056: * decision node (the loop back node). They both have a normal
057: * alternative block decision node at the left edge. The (...)* is
058: * worse as it even has a bypass decision (2 alts: stay in or bypass)
059: * node at the extreme left edge. This is not how they get generated
060: * in code as a while-loop or whatever deals nicely with either. For
061: * error messages (where I need to print the nondeterministic alts)
062: * and for interpretation, I need to use the single DFA that is created
063: * (for efficiency) but interpret the results differently depending
064: * on which of the 2 or 3 decision states uses the DFA. For example,
065: * the DFA will always report alt n+1 as the exit branch for n real
066: * alts, so I need to translate that depending on the decision state.
067: *
068: * If decisionNumber>0 then this var tells you what kind of decision
069: * state it is.
070: */
071: public int decisionStateType;
072:
073: /** What rule do we live in? */
074: protected String enclosingRule;
075:
076: /** During debugging and for nondeterminism warnings, it's useful
077: * to know what relationship this node has to the original grammar.
078: * For example, "start of alt 1 of rule a".
079: */
080: protected String description;
081:
082: /** Associate this NFAState with the corresponding GrammarAST node
083: * from which this node was created. This is useful not only for
084: * associating the eventual lookahead DFA with the associated
085: * Grammar position, but also for providing users with
086: * nondeterminism warnings. Mainly used by decision states to
087: * report line:col info. Could also be used to track line:col
088: * for elements such as token refs.
089: */
090: protected GrammarAST associatedASTNode;
091:
092: /** Is this state the sole target of an EOT transition? */
093: protected boolean EOTTargetState = false;
094:
095: /** Jean Bovet needs in the GUI to know which state pairs correspond
096: * to the start/stop of a block.
097: */
098: public int endOfBlockStateNumber = State.INVALID_STATE_NUMBER;
099:
100: public NFAState(NFA nfa) {
101: this .nfa = nfa;
102: }
103:
104: public int getNumberOfTransitions() {
105: return numTransitions;
106: }
107:
108: public void addTransition(Transition e) {
109: if (numTransitions > transition.length) {
110: throw new IllegalArgumentException("You can only have "
111: + transition.length + " transitions");
112: }
113: if (e != null) {
114: transition[numTransitions] = e;
115: numTransitions++;
116: }
117: }
118:
119: /** Used during optimization to reset a state to have the (single)
120: * transition another state has.
121: */
122: public void setTransition0(Transition e) {
123: transition[0] = e;
124: transition[1] = null;
125: numTransitions = 1;
126: }
127:
128: public Transition transition(int i) {
129: return transition[i];
130: }
131:
132: /** The DFA decision for this NFA decision state always has
133: * an exit path for loops as n+1 for n alts in the loop.
134: * That is really useful for displaying nondeterministic alts
135: * and so on, but for walking the NFA to get a sequence of edge
136: * labels or for actually parsing, we need to get the real alt
137: * number. The real alt number for exiting a loop is always 1
138: * as transition 0 points at the exit branch (we compute DFAs
139: * always for loops at the loopback state).
140: *
141: * For walking/parsing the loopback state:
142: * 1 2 3 display alt (for human consumption)
143: * 2 3 1 walk alt
144: *
145: * For walking the block start:
146: * 1 2 3 display alt
147: * 1 2 3
148: *
149: * For walking the bypass state of a (...)* loop:
150: * 1 2 3 display alt
151: * 1 1 2 all block alts map to entering loop exit means take bypass
152: *
153: * Non loop EBNF do not need to be translated; they are ignored by
154: * this method as decisionStateType==0.
155: *
156: * Return same alt if we can't translate.
157: */
158: public int translateDisplayAltToWalkAlt(DFA dfa, int displayAlt) {
159: if (decisionNumber == 0 || decisionStateType == 0) {
160: return displayAlt;
161: }
162: int walkAlt = 0;
163: // find the NFA loopback state associated with this DFA
164: // and count number of alts (all alt numbers are computed
165: // based upon the loopback's NFA state.
166: /*
167: DFA dfa = nfa.grammar.getLookaheadDFA(decisionNumber);
168: if ( dfa==null ) {
169: ErrorManager.internalError("can't get DFA for decision "+decisionNumber);
170: }
171: */
172: NFAState nfaStart = dfa.getNFADecisionStartState();
173: int nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(nfaStart);
174: switch (decisionStateType) {
175: case LOOPBACK:
176: walkAlt = displayAlt % nAlts + 1; // rotate right mod 1..3
177: break;
178: case BLOCK_START:
179: case OPTIONAL_BLOCK_START:
180: walkAlt = displayAlt; // identity transformation
181: break;
182: case BYPASS:
183: if (displayAlt == nAlts) {
184: walkAlt = 2; // bypass
185: } else {
186: walkAlt = 1; // any non exit branch alt predicts entering
187: }
188: break;
189: }
190: return walkAlt;
191: }
192:
193: // Setter/Getters
194:
195: /** What AST node is associated with this NFAState? When you
196: * set the AST node, I set the node to point back to this NFA state.
197: */
198: public void setDecisionASTNode(GrammarAST decisionASTNode) {
199: decisionASTNode.setNFAStartState(this );
200: this .associatedASTNode = decisionASTNode;
201: }
202:
203: public GrammarAST getAssociatedASTNode() {
204: return associatedASTNode;
205: }
206:
207: public void setAssociatedASTNode(GrammarAST ASTNode) {
208: this .associatedASTNode = ASTNode;
209: }
210:
211: public String getDescription() {
212: return description;
213: }
214:
215: public void setDescription(String description) {
216: this .description = description;
217: }
218:
219: public int getDecisionNumber() {
220: return decisionNumber;
221: }
222:
223: public void setDecisionNumber(int decisionNumber) {
224: this .decisionNumber = decisionNumber;
225: }
226:
227: public void setEnclosingRuleName(String rule) {
228: this .enclosingRule = rule;
229: }
230:
231: public String getEnclosingRule() {
232: return enclosingRule;
233: }
234:
235: public boolean isEOTTargetState() {
236: return EOTTargetState;
237: }
238:
239: public void setEOTTargetState(boolean eot) {
240: EOTTargetState = eot;
241: }
242:
243: public boolean isDecisionState() {
244: return decisionStateType > 0;
245: }
246:
247: public String toString() {
248: return String.valueOf(stateNumber);
249: }
250:
251: }
|