1/*
2 [The "BSD license"]
3 Copyright (c) 2005-2009 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 */
28package org.antlr.runtime;
29
30/** A DFA implemented as a set of transition tables.
31 *
32 *  Any state that has a semantic predicate edge is special; those states
33 *  are generated with if-then-else structures in a specialStateTransition()
34 *  which is generated by cyclicDFA template.
35 *
36 *  There are at most 32767 states (16-bit signed short).
37 *  Could get away with byte sometimes but would have to generate different
38 *  types and the simulation code too.  For a point of reference, the Java
39 *  lexer's Tokens rule DFA has 326 states roughly.
40 */
41public class DFA {
42	protected short[] eot;
43	protected short[] eof;
44	protected char[] min;
45    protected char[] max;
46    protected short[] accept;
47    protected short[] special;
48    protected short[][] transition;
49
50	protected int decisionNumber;
51
52	/** Which recognizer encloses this DFA?  Needed to check backtracking */
53	protected BaseRecognizer recognizer;
54
55	public static final boolean debug = false;
56
57	/** From the input stream, predict what alternative will succeed
58	 *  using this DFA (representing the covering regular approximation
59	 *  to the underlying CFL).  Return an alternative number 1..n.  Throw
60	 *  an exception upon error.
61	 */
62	public int predict(IntStream input)
63		throws RecognitionException
64	{
65		if ( debug ) {
66			System.err.println("Enter DFA.predict for decision "+decisionNumber);
67		}
68		int mark = input.mark(); // remember where decision started in input
69		int s = 0; // we always start at s0
70		try {
71			while ( true ) {
72				if ( debug ) System.err.println("DFA "+decisionNumber+" state "+s+" LA(1)="+(char)input.LA(1)+"("+input.LA(1)+
73												"), index="+input.index());
74				int specialState = special[s];
75				if ( specialState>=0 ) {
76					if ( debug ) {
77						System.err.println("DFA "+decisionNumber+
78							" state "+s+" is special state "+specialState);
79					}
80					s = specialStateTransition(specialState,input);
81					if ( debug ) {
82						System.err.println("DFA "+decisionNumber+
83							" returns from special state "+specialState+" to "+s);
84					}
85					if ( s==-1 ) {
86						noViableAlt(s,input);
87						return 0;
88					}
89					input.consume();
90					continue;
91				}
92				if ( accept[s] >= 1 ) {
93					if ( debug ) System.err.println("accept; predict "+accept[s]+" from state "+s);
94					return accept[s];
95				}
96				// look for a normal char transition
97				char c = (char)input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space
98				if (c>=min[s] && c<=max[s]) {
99					int snext = transition[s][c-min[s]]; // move to next state
100					if ( snext < 0 ) {
101						// was in range but not a normal transition
102						// must check EOT, which is like the else clause.
103						// eot[s]>=0 indicates that an EOT edge goes to another
104						// state.
105						if ( eot[s]>=0 ) {  // EOT Transition to accept state?
106							if ( debug ) System.err.println("EOT transition");
107							s = eot[s];
108							input.consume();
109							// TODO: I had this as return accept[eot[s]]
110							// which assumed here that the EOT edge always
111							// went to an accept...faster to do this, but
112							// what about predicated edges coming from EOT
113							// target?
114							continue;
115						}
116						noViableAlt(s,input);
117						return 0;
118					}
119					s = snext;
120					input.consume();
121					continue;
122				}
123				if ( eot[s]>=0 ) {  // EOT Transition?
124					if ( debug ) System.err.println("EOT transition");
125					s = eot[s];
126					input.consume();
127					continue;
128				}
129				if ( c==(char)Token.EOF && eof[s]>=0 ) {  // EOF Transition to accept state?
130					if ( debug ) System.err.println("accept via EOF; predict "+accept[eof[s]]+" from "+eof[s]);
131					return accept[eof[s]];
132				}
133				// not in range and not EOF/EOT, must be invalid symbol
134				if ( debug ) {
135					System.err.println("min["+s+"]="+min[s]);
136					System.err.println("max["+s+"]="+max[s]);
137					System.err.println("eot["+s+"]="+eot[s]);
138					System.err.println("eof["+s+"]="+eof[s]);
139					for (int p=0; p<transition[s].length; p++) {
140						System.err.print(transition[s][p]+" ");
141					}
142					System.err.println();
143				}
144				noViableAlt(s,input);
145				return 0;
146			}
147		}
148		finally {
149			input.rewind(mark);
150		}
151	}
152
153	protected void noViableAlt(int s, IntStream input) throws NoViableAltException {
154		if (recognizer.state.backtracking>0) {
155			recognizer.state.failed=true;
156			return;
157		}
158		NoViableAltException nvae =
159			new NoViableAltException(getDescription(),
160									 decisionNumber,
161									 s,
162									 input);
163		error(nvae);
164		throw nvae;
165	}
166
167	/** A hook for debugging interface */
168	protected void error(NoViableAltException nvae) { ; }
169
170	public int specialStateTransition(int s, IntStream input)
171		throws NoViableAltException
172	{
173		return -1;
174	}
175
176	public String getDescription() {
177		return "n/a";
178	}
179
180	/** Given a String that has a run-length-encoding of some unsigned shorts
181	 *  like "\1\2\3\9", convert to short[] {2,9,9,9}.  We do this to avoid
182	 *  static short[] which generates so much init code that the class won't
183	 *  compile. :(
184	 */
185	public static short[] unpackEncodedString(String encodedString) {
186		// walk first to find how big it is.
187		int size = 0;
188		for (int i=0; i<encodedString.length(); i+=2) {
189			size += encodedString.charAt(i);
190		}
191		short[] data = new short[size];
192		int di = 0;
193		for (int i=0; i<encodedString.length(); i+=2) {
194			char n = encodedString.charAt(i);
195			char v = encodedString.charAt(i+1);
196			// add v n times to data
197			for (int j=1; j<=n; j++) {
198				data[di++] = (short)v;
199			}
200		}
201		return data;
202	}
203
204	/** Hideous duplication of code, but I need different typed arrays out :( */
205	public static char[] unpackEncodedStringToUnsignedChars(String encodedString) {
206		// walk first to find how big it is.
207		int size = 0;
208		for (int i=0; i<encodedString.length(); i+=2) {
209			size += encodedString.charAt(i);
210		}
211		char[] data = new char[size];
212		int di = 0;
213		for (int i=0; i<encodedString.length(); i+=2) {
214			char n = encodedString.charAt(i);
215			char v = encodedString.charAt(i+1);
216			// add v n times to data
217			for (int j=1; j<=n; j++) {
218				data[di++] = v;
219			}
220		}
221		return data;
222	}
223
224	/*
225	public int specialTransition(int state, int symbol) {
226		return 0;
227	}
228	*/
229}
230