1/* 2 * [The "BSD licence"] 3 * Copyright (c) 2005-2008 Terence Parr 4 * All rights reserved. 5 * 6 * Conversion to C#: 7 * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33namespace Antlr.Runtime { 34 using ConditionalAttribute = System.Diagnostics.ConditionalAttribute; 35 using Console = System.Console; 36 using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener; 37 38 public delegate int SpecialStateTransitionHandler(DFA dfa, int s, IIntStream input); 39 40 /** <summary>A DFA implemented as a set of transition tables.</summary> 41 * 42 * <remarks> 43 * Any state that has a semantic predicate edge is special; those states 44 * are generated with if-then-else structures in a specialStateTransition() 45 * which is generated by cyclicDFA template. 46 * 47 * There are at most 32767 states (16-bit signed short). 48 * Could get away with byte sometimes but would have to generate different 49 * types and the simulation code too. For a point of reference, the Java 50 * lexer's Tokens rule DFA has 326 states roughly. 51 * </remarks> 52 */ 53 public class DFA { 54 public DFA() 55 : this(new SpecialStateTransitionHandler(SpecialStateTransitionDefault)) { 56 } 57 public DFA(SpecialStateTransitionHandler specialStateTransition) { 58 this.SpecialStateTransition = specialStateTransition ?? new SpecialStateTransitionHandler(SpecialStateTransitionDefault); 59 } 60 61 protected short[] eot; 62 protected short[] eof; 63 protected char[] min; 64 protected char[] max; 65 protected short[] accept; 66 protected short[] special; 67 protected short[][] transition; 68 69 protected int decisionNumber; 70 71 /** <summary>Which recognizer encloses this DFA? Needed to check backtracking</summary> */ 72 protected BaseRecognizer recognizer; 73 74 public readonly bool debug = false; 75 76 /** <summary> 77 * From the input stream, predict what alternative will succeed 78 * using this DFA (representing the covering regular approximation 79 * to the underlying CFL). Return an alternative number 1..n. Throw 80 * an exception upon error. 81 * </summary> 82 */ 83 public virtual int Predict(IIntStream input) { 84 if (debug) { 85 Console.Error.WriteLine("Enter DFA.predict for decision " + decisionNumber); 86 } 87 int mark = input.Mark(); // remember where decision started in input 88 int s = 0; // we always start at s0 89 try { 90 for (; ; ) { 91 if (debug) 92 Console.Error.WriteLine("DFA " + decisionNumber + " state " + s + " LA(1)=" + (char)input.LA(1) + "(" + input.LA(1) + 93 "), index=" + input.Index); 94 int specialState = special[s]; 95 if (specialState >= 0) { 96 if (debug) { 97 Console.Error.WriteLine("DFA " + decisionNumber + 98 " state " + s + " is special state " + specialState); 99 } 100 s = SpecialStateTransition(this, specialState, input); 101 if (debug) { 102 Console.Error.WriteLine("DFA " + decisionNumber + 103 " returns from special state " + specialState + " to " + s); 104 } 105 if (s == -1) { 106 NoViableAlt(s, input); 107 return 0; 108 } 109 input.Consume(); 110 continue; 111 } 112 if (accept[s] >= 1) { 113 if (debug) 114 Console.Error.WriteLine("accept; predict " + accept[s] + " from state " + s); 115 return accept[s]; 116 } 117 // look for a normal char transition 118 char c = (char)input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space 119 if (c >= min[s] && c <= max[s]) { 120 int snext = transition[s][c - min[s]]; // move to next state 121 if (snext < 0) { 122 // was in range but not a normal transition 123 // must check EOT, which is like the else clause. 124 // eot[s]>=0 indicates that an EOT edge goes to another 125 // state. 126 if (eot[s] >= 0) { // EOT Transition to accept state? 127 if (debug) 128 Console.Error.WriteLine("EOT transition"); 129 s = eot[s]; 130 input.Consume(); 131 // TODO: I had this as return accept[eot[s]] 132 // which assumed here that the EOT edge always 133 // went to an accept...faster to do this, but 134 // what about predicated edges coming from EOT 135 // target? 136 continue; 137 } 138 NoViableAlt(s, input); 139 return 0; 140 } 141 s = snext; 142 input.Consume(); 143 continue; 144 } 145 if (eot[s] >= 0) { // EOT Transition? 146 if (debug) 147 Console.Error.WriteLine("EOT transition"); 148 s = eot[s]; 149 input.Consume(); 150 continue; 151 } 152 if (c == unchecked((char)TokenTypes.EndOfFile) && eof[s] >= 0) { // EOF Transition to accept state? 153 if (debug) 154 Console.Error.WriteLine("accept via EOF; predict " + accept[eof[s]] + " from " + eof[s]); 155 return accept[eof[s]]; 156 } 157 // not in range and not EOF/EOT, must be invalid symbol 158 if (debug) { 159 Console.Error.WriteLine("min[" + s + "]=" + min[s]); 160 Console.Error.WriteLine("max[" + s + "]=" + max[s]); 161 Console.Error.WriteLine("eot[" + s + "]=" + eot[s]); 162 Console.Error.WriteLine("eof[" + s + "]=" + eof[s]); 163 for (int p = 0; p < transition[s].Length; p++) { 164 Console.Error.Write(transition[s][p] + " "); 165 } 166 Console.Error.WriteLine(); 167 } 168 NoViableAlt(s, input); 169 return 0; 170 } 171 } finally { 172 input.Rewind(mark); 173 } 174 } 175 176 protected virtual void NoViableAlt(int s, IIntStream input) { 177 if (recognizer.state.backtracking > 0) { 178 recognizer.state.failed = true; 179 return; 180 } 181 NoViableAltException nvae = 182 new NoViableAltException(Description, 183 decisionNumber, 184 s, 185 input); 186 Error(nvae); 187 throw nvae; 188 } 189 190 /** <summary>A hook for debugging interface</summary> */ 191 public virtual void Error(NoViableAltException nvae) { 192 } 193 194 public SpecialStateTransitionHandler SpecialStateTransition { 195 get; 196 private set; 197 } 198 //public virtual int specialStateTransition( int s, IntStream input ) 199 //{ 200 // return -1; 201 //} 202 203 static int SpecialStateTransitionDefault(DFA dfa, int s, IIntStream input) { 204 return -1; 205 } 206 207 public virtual string Description { 208 get { 209 return "n/a"; 210 } 211 } 212 213 /** <summary> 214 * Given a String that has a run-length-encoding of some unsigned shorts 215 * like "\1\2\3\9", convert to short[] {2,9,9,9}. We do this to avoid 216 * static short[] which generates so much init code that the class won't 217 * compile. :( 218 * </summary> 219 */ 220 public static short[] UnpackEncodedString(string encodedString) { 221 // walk first to find how big it is. 222 int size = 0; 223 for (int i = 0; i < encodedString.Length; i += 2) { 224 size += encodedString[i]; 225 } 226 short[] data = new short[size]; 227 int di = 0; 228 for (int i = 0; i < encodedString.Length; i += 2) { 229 char n = encodedString[i]; 230 char v = encodedString[i + 1]; 231 // add v n times to data 232 for (int j = 1; j <= n; j++) { 233 data[di++] = (short)v; 234 } 235 } 236 return data; 237 } 238 239 /** <summary>Hideous duplication of code, but I need different typed arrays out :(</summary> */ 240 public static char[] UnpackEncodedStringToUnsignedChars(string encodedString) { 241 // walk first to find how big it is. 242 int size = 0; 243 for (int i = 0; i < encodedString.Length; i += 2) { 244 size += encodedString[i]; 245 } 246 char[] data = new char[size]; 247 int di = 0; 248 for (int i = 0; i < encodedString.Length; i += 2) { 249 char n = encodedString[i]; 250 char v = encodedString[i + 1]; 251 // add v n times to data 252 for (int j = 1; j <= n; j++) { 253 data[di++] = v; 254 } 255 } 256 return data; 257 } 258 259 [Conditional("ANTLR_DEBUG")] 260 protected virtual void DebugRecognitionException(RecognitionException ex) { 261 IDebugEventListener dbg = recognizer.DebugListener; 262 if (dbg != null) 263 dbg.RecognitionException(ex); 264 } 265 } 266} 267