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