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 33 namespace Antlr.Runtime 34 { 35 using ConditionalAttribute = System.Diagnostics.ConditionalAttribute; 36 using Console = System.Console; 37 using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener; 38 SpecialStateTransitionHandler( DFA dfa, int s, IIntStream input )39 public delegate int SpecialStateTransitionHandler( DFA dfa, int s, IIntStream input ); 40 41 /** <summary>A DFA implemented as a set of transition tables.</summary> 42 * 43 * <remarks> 44 * Any state that has a semantic predicate edge is special; those states 45 * are generated with if-then-else structures in a specialStateTransition() 46 * which is generated by cyclicDFA template. 47 * 48 * There are at most 32767 states (16-bit signed short). 49 * Could get away with byte sometimes but would have to generate different 50 * types and the simulation code too. For a point of reference, the Java 51 * lexer's Tokens rule DFA has 326 states roughly. 52 * </remarks> 53 */ 54 public class DFA 55 { 56 protected short[] eot; 57 protected short[] eof; 58 protected char[] min; 59 protected char[] max; 60 protected short[] accept; 61 protected short[] special; 62 protected short[][] transition; 63 64 protected int decisionNumber; 65 66 /** <summary>Which recognizer encloses this DFA? Needed to check backtracking</summary> */ 67 protected BaseRecognizer recognizer; 68 69 public readonly bool debug = false; 70 DFA()71 public DFA() 72 : this( new SpecialStateTransitionHandler( SpecialStateTransitionDefault ) ) 73 { 74 } 75 DFA( SpecialStateTransitionHandler specialStateTransition )76 public DFA( SpecialStateTransitionHandler specialStateTransition ) 77 { 78 this.SpecialStateTransition = specialStateTransition ?? new SpecialStateTransitionHandler( SpecialStateTransitionDefault ); 79 } 80 81 public virtual string Description 82 { 83 get 84 { 85 return "n/a"; 86 } 87 } 88 89 /** <summary> 90 * From the input stream, predict what alternative will succeed 91 * using this DFA (representing the covering regular approximation 92 * to the underlying CFL). Return an alternative number 1..n. Throw 93 * an exception upon error. 94 * </summary> 95 */ Predict( IIntStream input )96 public virtual int Predict( IIntStream input ) 97 { 98 if ( debug ) 99 { 100 Console.Error.WriteLine( "Enter DFA.predict for decision " + decisionNumber ); 101 } 102 int mark = input.Mark(); // remember where decision started in input 103 int s = 0; // we always start at s0 104 try 105 { 106 for ( ; ; ) 107 { 108 if ( debug ) 109 Console.Error.WriteLine( "DFA " + decisionNumber + " state " + s + " LA(1)=" + (char)input.LA( 1 ) + "(" + input.LA( 1 ) + 110 "), index=" + input.Index ); 111 int specialState = special[s]; 112 if ( specialState >= 0 ) 113 { 114 if ( debug ) 115 { 116 Console.Error.WriteLine( "DFA " + decisionNumber + 117 " state " + s + " is special state " + specialState ); 118 } 119 s = SpecialStateTransition( this, specialState, input ); 120 if ( debug ) 121 { 122 Console.Error.WriteLine( "DFA " + decisionNumber + 123 " returns from special state " + specialState + " to " + s ); 124 } 125 if ( s == -1 ) 126 { 127 NoViableAlt( s, input ); 128 return 0; 129 } 130 input.Consume(); 131 continue; 132 } 133 if ( accept[s] >= 1 ) 134 { 135 if ( debug ) 136 Console.Error.WriteLine( "accept; predict " + accept[s] + " from state " + s ); 137 return accept[s]; 138 } 139 // look for a normal char transition 140 char c = (char)input.LA( 1 ); // -1 == \uFFFF, all tokens fit in 65000 space 141 if ( c >= min[s] && c <= max[s] ) 142 { 143 int snext = transition[s][c - min[s]]; // move to next state 144 if ( snext < 0 ) 145 { 146 // was in range but not a normal transition 147 // must check EOT, which is like the else clause. 148 // eot[s]>=0 indicates that an EOT edge goes to another 149 // state. 150 if ( eot[s] >= 0 ) 151 { // EOT Transition to accept state? 152 if ( debug ) 153 Console.Error.WriteLine( "EOT transition" ); 154 s = eot[s]; 155 input.Consume(); 156 // TODO: I had this as return accept[eot[s]] 157 // which assumed here that the EOT edge always 158 // went to an accept...faster to do this, but 159 // what about predicated edges coming from EOT 160 // target? 161 continue; 162 } 163 NoViableAlt( s, input ); 164 return 0; 165 } 166 s = snext; 167 input.Consume(); 168 continue; 169 } 170 if ( eot[s] >= 0 ) 171 { // EOT Transition? 172 if ( debug ) 173 Console.Error.WriteLine( "EOT transition" ); 174 s = eot[s]; 175 input.Consume(); 176 continue; 177 } 178 if ( c == unchecked( (char)TokenTypes.EndOfFile ) && eof[s] >= 0 ) 179 { // EOF Transition to accept state? 180 if ( debug ) 181 Console.Error.WriteLine( "accept via EOF; predict " + accept[eof[s]] + " from " + eof[s] ); 182 return accept[eof[s]]; 183 } 184 // not in range and not EOF/EOT, must be invalid symbol 185 if ( debug ) 186 { 187 Console.Error.WriteLine( "min[" + s + "]=" + min[s] ); 188 Console.Error.WriteLine( "max[" + s + "]=" + max[s] ); 189 Console.Error.WriteLine( "eot[" + s + "]=" + eot[s] ); 190 Console.Error.WriteLine( "eof[" + s + "]=" + eof[s] ); 191 for ( int p = 0; p < transition[s].Length; p++ ) 192 { 193 Console.Error.Write( transition[s][p] + " " ); 194 } 195 Console.Error.WriteLine(); 196 } 197 NoViableAlt( s, input ); 198 return 0; 199 } 200 } 201 finally 202 { 203 input.Rewind( mark ); 204 } 205 } 206 NoViableAlt( int s, IIntStream input )207 protected virtual void NoViableAlt( int s, IIntStream input ) 208 { 209 if ( recognizer.state.backtracking > 0 ) 210 { 211 recognizer.state.failed = true; 212 return; 213 } 214 NoViableAltException nvae = 215 new NoViableAltException( Description, 216 decisionNumber, 217 s, 218 input ); 219 Error( nvae ); 220 throw nvae; 221 } 222 223 /** <summary>A hook for debugging interface</summary> */ Error( NoViableAltException nvae )224 public virtual void Error( NoViableAltException nvae ) 225 { 226 } 227 228 public SpecialStateTransitionHandler SpecialStateTransition 229 { 230 get; 231 private set; 232 } 233 //public virtual int specialStateTransition( int s, IntStream input ) 234 //{ 235 // return -1; 236 //} 237 SpecialStateTransitionDefault( DFA dfa, int s, IIntStream input )238 static int SpecialStateTransitionDefault( DFA dfa, int s, IIntStream input ) 239 { 240 return -1; 241 } 242 243 /** <summary> 244 * Given a String that has a run-length-encoding of some unsigned shorts 245 * like "\1\2\3\9", convert to short[] {2,9,9,9}. We do this to avoid 246 * static short[] which generates so much init code that the class won't 247 * compile. :( 248 * </summary> 249 */ UnpackEncodedString( string encodedString )250 public static short[] UnpackEncodedString( string encodedString ) 251 { 252 // walk first to find how big it is. 253 int size = 0; 254 for ( int i = 0; i < encodedString.Length; i += 2 ) 255 { 256 size += encodedString[i]; 257 } 258 short[] data = new short[size]; 259 int di = 0; 260 for ( int i = 0; i < encodedString.Length; i += 2 ) 261 { 262 char n = encodedString[i]; 263 char v = encodedString[i + 1]; 264 // add v n times to data 265 for ( int j = 1; j <= n; j++ ) 266 { 267 data[di++] = (short)v; 268 } 269 } 270 return data; 271 } 272 273 /** <summary>Hideous duplication of code, but I need different typed arrays out :(</summary> */ UnpackEncodedStringToUnsignedChars( string encodedString )274 public static char[] UnpackEncodedStringToUnsignedChars( string encodedString ) 275 { 276 // walk first to find how big it is. 277 int size = 0; 278 for ( int i = 0; i < encodedString.Length; i += 2 ) 279 { 280 size += encodedString[i]; 281 } 282 char[] data = new char[size]; 283 int di = 0; 284 for ( int i = 0; i < encodedString.Length; i += 2 ) 285 { 286 char n = encodedString[i]; 287 char v = encodedString[i + 1]; 288 // add v n times to data 289 for ( int j = 1; j <= n; j++ ) 290 { 291 data[di++] = v; 292 } 293 } 294 return data; 295 } 296 297 [Conditional("ANTLR_DEBUG")] DebugRecognitionException(RecognitionException ex)298 protected virtual void DebugRecognitionException(RecognitionException ex) 299 { 300 IDebugEventListener dbg = recognizer.DebugListener; 301 if (dbg != null) 302 dbg.RecognitionException(ex); 303 } 304 } 305 } 306