1 /** A DFA implemented as a set of transition tables. 2 * 3 * Any state that has a semantic predicate edge is special; those states 4 * are generated with if-then-else structures in a specialStateTransition() 5 * which is generated by cyclicDFA template. 6 * 7 * There are at most 32767 states (16-bit signed short). 8 * Could get away with byte sometimes but would have to generate different 9 * types and the simulation code too. For a point of reference, the Java 10 * lexer's Tokens rule DFA has 326 states roughly. 11 */ 12 org.antlr.runtime.DFA = function() {}; 13 14 org.antlr.runtime.DFA.prototype = { 15 /** From the input stream, predict what alternative will succeed 16 * using this DFA (representing the covering regular approximation 17 * to the underlying CFL). Return an alternative number 1..n. Throw 18 * an exception upon error. 19 */ 20 predict: function(input) { 21 var mark = input.mark(), // remember where decision started in input 22 s = 0, // we always start at s0 23 specialState, 24 c, 25 snext; 26 27 try { 28 while ( true ) { 29 specialState = this.special[s]; 30 if ( specialState>=0 ) { 31 s = this.specialStateTransition(specialState,input); 32 if (s===-1) { 33 this.noViableAlt(s, input); 34 return 0; 35 } 36 input.consume(); 37 continue; 38 } 39 if ( this.accept[s] >= 1 ) { 40 return this.accept[s]; 41 } 42 // look for a normal char transition 43 c = input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space 44 45 if (c===org.antlr.runtime.Token.EOF) { 46 c = -1; 47 } else if (org.antlr.lang.isString(c)) { 48 c = c.charCodeAt(0); 49 } 50 51 if (c>=this.min[s] && c<=this.max[s]) { 52 snext = this.transition[s][c-this.min[s]]; // move to next state 53 if ( snext < 0 ) { 54 // was in range but not a normal transition 55 // must check EOT, which is like the else clause. 56 // eot[s]>=0 indicates that an EOT edge goes to another 57 // state. 58 if ( this.eot[s]>=0 ) { // EOT Transition to accept state? 59 s = this.eot[s]; 60 input.consume(); 61 // TODO: I had this as return accept[eot[s]] 62 // which assumed here that the EOT edge always 63 // went to an accept...faster to do this, but 64 // what about predicated edges coming from EOT 65 // target? 66 continue; 67 } 68 this.noViableAlt(s,input); 69 return 0; 70 } 71 s = snext; 72 input.consume(); 73 continue; 74 } 75 if ( this.eot[s]>=0 ) { // EOT Transition? 76 s = this.eot[s]; 77 input.consume(); 78 continue; 79 } 80 if ( c==org.antlr.runtime.Token.EOF && this.eof[s]>=0 ) { // EOF Transition to accept state? 81 return this.accept[this.eof[s]]; 82 } 83 // not in range and not EOF/EOT, must be invalid symbol 84 this.noViableAlt(s,input); 85 return 0; 86 } 87 } 88 finally { 89 input.rewind(mark); 90 } 91 }, 92 93 noViableAlt: function(s, input) { 94 if (this.recognizer.state.backtracking>0) { 95 this.recognizer.state.failed=true; 96 return; 97 } 98 var nvae = 99 new org.antlr.runtime.NoViableAltException(this.getDescription(), 100 this.decisionNumber, 101 s, 102 input); 103 this.error(nvae); 104 throw nvae; 105 }, 106 107 /** A hook for debugging interface */ 108 error: function(nvae) { }, 109 110 specialStateTransition: function(s, input) { 111 return -1; 112 }, 113 114 getDescription: function() { 115 return "n/a"; 116 } 117 }; 118 119 org.antlr.lang.augmentObject(org.antlr.runtime.DFA, { 120 /** Given a String that has a run-length-encoding of some unsigned shorts 121 * like "\1\2\3\9", convert to short[] {2,9,9,9}. 122 */ 123 unpackEncodedString: function(encodedString) { 124 // walk first to find how big it is. 125 var i, 126 data = [], 127 di = 0, 128 n, 129 v, 130 j; 131 for (i=0; i<encodedString.length; i+=2) { 132 n = encodedString.charCodeAt(i); 133 v = encodedString.charCodeAt(i+1); 134 if (v===0xffff) { 135 v = -1; // overflow at 16 bits 136 } 137 // add v n times to data 138 for (j=1; j<=n; j++) { 139 data[di++] = v; 140 } 141 } 142 return data; 143 }, 144 145 // alias 146 unpackEncodedStringToUnsignedChars: function(encodedString) { 147 return org.antlr.runtime.DFA.unpackEncodedString(encodedString); 148 } 149 }); 150
