1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.runtime { 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A DFA implemented as a set of transition tables. 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Any state that has a semantic predicate edge is special; those states 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are generated with if-then-else structures in a specialStateTransition() 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * which is generated by cyclicDFA template. 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * There are at most 32767 states (16-bit signed short). 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Could get away with byte sometimes but would have to generate different 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * types and the simulation code too. For a point of reference, the Java 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * lexer's Tokens rule DFA has 326 states roughly. 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class DFA { 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var eot:Array; // short[] 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var eof:Array; // short[] 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var min:Array; // char[] 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var max:Array; // char[] 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var accept:Array; //short[] 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var special:Array; // short[] 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var transition:Array; // short[][] 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var decisionNumber:int; 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Which recognizer encloses this DFA? Needed to check backtracking */ 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var recognizer:BaseRecognizer; 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private var _description:String; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static const debug:Boolean = false; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function DFA(recognizer:BaseRecognizer, decisionNumber:int, description:String, 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver eot:Array, eof:Array, min:Array, max:Array, accept:Array, special:Array, transition:Array, 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver specialStateTransitionFunction:Function = null, errorFunction:Function = null) { 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.recognizer = recognizer; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.decisionNumber = decisionNumber; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this._description = description; 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.eot = eot; 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.eof = eof; 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.min = min; 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.max = max; 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.accept = accept; 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.special = special; 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.transition = transition; 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (specialStateTransitionFunction != null) { 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver specialStateTransition = specialStateTransitionFunction; 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (errorFunction != null) { 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver error = errorFunction; 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From the input stream, predict what alternative will succeed 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * using this DFA (representing the covering regular approximation 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to the underlying CFL). Return an alternative number 1..n. Throw 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * an exception upon error. 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function predict(input:IntStream):int { 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("Enter DFA.predict for decision "+decisionNumber); 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var mark:int = input.mark(); // remember where decision started in input 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var s:int = 0; // we always start at s0 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver try { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( true ) { 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) trace("DFA "+decisionNumber+" state "+s+" LA(1)="+String.fromCharCode(input.LA(1))+"("+input.LA(1)+ 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "), index="+input.index); 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var specialState:int = special[s]; 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( specialState>=0 ) { 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("DFA "+decisionNumber+ 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " state "+s+" is special state "+specialState); 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s = specialStateTransition(this, specialState,input); 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("DFA "+decisionNumber+ 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " returns from special state "+specialState+" to "+s); 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s==-1 ) { 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver noViableAlt(s,input); 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input.consume(); 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( accept[s] >= 1 ) { 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) trace("accept; predict "+accept[s]+" from state "+s); 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return accept[s]; 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // look for a normal char transition 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var c:int = input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (c>=min[s] && c<=max[s]) { 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var snext:int = transition[s][c-min[s]]; // move to next state 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( snext < 0 ) { 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // was in range but not a normal transition 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // must check EOT, which is like the else clause. 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // eot[s]>=0 indicates that an EOT edge goes to another 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // state. 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( eot[s]>=0 ) { // EOT Transition to accept state? 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) trace("EOT transition"); 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s = eot[s]; 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input.consume(); 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: I had this as return accept[eot[s]] 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // which assumed here that the EOT edge always 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // went to an accept...faster to do this, but 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // what about predicated edges coming from EOT 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // target? 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver noViableAlt(s,input); 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s = snext; 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input.consume(); 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( eot[s]>=0 ) { // EOT Transition? 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) trace("EOT transition"); 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s = eot[s]; 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input.consume(); 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( c==TokenConstants.EOF && eof[s]>=0 ) { // EOF Transition to accept state? 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) trace("accept via EOF; predict "+accept[eof[s]]+" from "+eof[s]); 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return accept[eof[s]]; 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // not in range and not EOF/EOT, must be invalid symbol 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("min["+s+"]="+min[s]); 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("max["+s+"]="+max[s]); 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("eot["+s+"]="+eot[s]); 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace("eof["+s+"]="+eof[s]); 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var p:int=0; p<transition[s].length; p++) { 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace(transition[s][p]+" "); 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver trace(); 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver noViableAlt(s,input); 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver finally { 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input.rewindTo(mark); 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // not reached -- added due to bug in Flex compiler reachability analysis of while loop with no breaks 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return -1; 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected function noViableAlt(s:int, input:IntStream):void { 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (recognizer.state.backtracking>0) { 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver recognizer.state.failed=true; 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var nvae:NoViableAltException = 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new NoViableAltException(description, 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver decisionNumber, 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s, 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver input); 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver error(nvae); 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw nvae; 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A hook for debugging interface */ 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public var error:Function = function(nvae:NoViableAltException):NoViableAltException { return nvae; } 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public var specialStateTransition:Function = function(dfa:DFA, s:int, input:IntStream):int { 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return -1; 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get description():String { 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _description; 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given a String that has a run-length-encoding of some unsigned shorts 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * like "\1\2\3\9", convert to short[] {2,9,9,9}. We do this to avoid 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * static short[] which generates so much init code that the class won't 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * compile. :( 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static function unpackEncodedString(encodedString:String, unsigned:Boolean = false):Array { 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk first to find how big it is. 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* Don't pre-allocate 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var size:int = 0; 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int=0; i<encodedString.length; i+=2) { 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver size += encodedString.charCodeAt(i); 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var data:Array = new Array(); 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var di:int = 0; 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int=0; i<encodedString.length; i+=2) { 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var n:int = encodedString.charCodeAt(i); 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n > 0x8000) { 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // need to read another byte 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var lowBits:int = encodedString.charCodeAt(i); 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n &= 0xff; 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n <<= 8; 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n |= lowBits; 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var v:int = encodedString.charCodeAt(i+1); 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (v > 0x8000) { 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // need to read another byte 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lowBits = encodedString.charCodeAt(i); 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver v &= 0xff; 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver v <<= 8; 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver v |= lowBits; 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!unsigned && v > 0x7fff) { 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver v = -(0xffff - v + 1); 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add v n times to data 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var j:int=1; j<=n; j++) { 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver data[di++] = v; 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return data; 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}