1 /** Support functions for traversing cyclic DFA states as laid 2 * out in static initialized structures by the code generator. 3 * 4 * A DFA implemented as a set of transition tables. 5 * 6 * Any state that has a semantic predicate edge is special; those states 7 * are generated with if-then-else structures in a ->specialStateTransition() 8 * which is generated by cyclicDFA template. 9 * 10 * There are at most 32767 states (16-bit signed short). 11 * Could get away with byte sometimes but would have to generate different 12 * types and the simulation code too. For a point of reference, the Java 13 * lexer's Tokens rule DFA has 326 states roughly. 14 */ 15 16 // [The "BSD licence"] 17 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC 18 // http://www.temporal-wave.com 19 // http://www.linkedin.com/in/jimidle 20 // 21 // All rights reserved. 22 // 23 // Redistribution and use in source and binary forms, with or without 24 // modification, are permitted provided that the following conditions 25 // are met: 26 // 1. Redistributions of source code must retain the above copyright 27 // notice, this list of conditions and the following disclaimer. 28 // 2. Redistributions in binary form must reproduce the above copyright 29 // notice, this list of conditions and the following disclaimer in the 30 // documentation and/or other materials provided with the distribution. 31 // 3. The name of the author may not be used to endorse or promote products 32 // derived from this software without specific prior written permission. 33 // 34 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 35 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 36 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 37 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 38 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 39 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 40 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 41 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 42 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 43 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 44 45 #include <antlr3defs.h> 46 #include <antlr3cyclicdfa.h> 47 48 #ifdef ANTLR3_WINDOWS 49 #pragma warning( disable : 4100 ) 50 #endif 51 52 static void 53 noViableAlt(pANTLR3_BASE_RECOGNIZER rec, pANTLR3_CYCLIC_DFA cdfa, ANTLR3_UINT32 s) 54 { 55 // In backtracking mode, we just set the failed flag so that the 56 // alt can just exit right now. If we are parsing though, then 57 // we want the exception to be raised. 58 // 59 if (rec->state->backtracking > 0) 60 { 61 rec->state->failed = ANTLR3_TRUE; 62 } 63 else 64 { 65 rec->exConstruct(rec); 66 rec->state->exception->type = ANTLR3_NO_VIABLE_ALT_EXCEPTION; 67 rec->state->exception->message = cdfa->description; 68 rec->state->exception->decisionNum = cdfa->decisionNumber; 69 rec->state->exception->state = s; 70 } 71 } 72 73 /** From the input stream, predict what alternative will succeed 74 * using this DFA (representing the covering regular approximation 75 * to the underlying CFL). Return an alternative number 1..n. Throw 76 * an exception upon error. 77 */ 78 ANTLR3_API ANTLR3_INT32 79 antlr3dfapredict (void * ctx, pANTLR3_BASE_RECOGNIZER rec, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA cdfa) 80 { 81 ANTLR3_MARKER mark; 82 ANTLR3_INT32 s; 83 ANTLR3_INT32 specialState; 84 ANTLR3_INT32 c; 85 86 mark = is->mark(is); /* Store where we are right now */ 87 s = 0; /* Always start with state 0 */ 88 89 for (;;) 90 { 91 /* Pick out any special state entry for this state 92 */ 93 specialState = cdfa->special[s]; 94 95 /* Transition the special state and consume an input token 96 */ 97 if (specialState >= 0) 98 { 99 s = cdfa->specialStateTransition(ctx, rec, is, cdfa, specialState); 100 101 // Error? 102 // 103 if (s<0) 104 { 105 // If the predicate/rule raised an exception then we leave it 106 // in tact, else we have an NVA. 107 // 108 if (rec->state->error != ANTLR3_TRUE) 109 { 110 noViableAlt(rec,cdfa, s); 111 } 112 is->rewind(is, mark); 113 return 0; 114 } 115 is->consume(is); 116 continue; 117 } 118 119 /* Accept state? 120 */ 121 if (cdfa->accept[s] >= 1) 122 { 123 is->rewind(is, mark); 124 return cdfa->accept[s]; 125 } 126 127 /* Look for a normal transition state based upon the input token element 128 */ 129 c = is->_LA(is, 1); 130 131 /* Check against min and max for this state 132 */ 133 if (c>= cdfa->min[s] && c <= cdfa->max[s]) 134 { 135 ANTLR3_INT32 snext; 136 137 /* What is the next state? 138 */ 139 snext = cdfa->transition[s][c - cdfa->min[s]]; 140 141 if (snext < 0) 142 { 143 /* Was in range but not a normal transition 144 * must check EOT, which is like the else clause. 145 * eot[s]>=0 indicates that an EOT edge goes to another 146 * state. 147 */ 148 if (cdfa->eot[s] >= 0) 149 { 150 s = cdfa->eot[s]; 151 is->consume(is); 152 continue; 153 } 154 noViableAlt(rec,cdfa, s); 155 is->rewind(is, mark); 156 return 0; 157 } 158 159 /* New current state - move to it 160 */ 161 s = snext; 162 is->consume(is); 163 continue; 164 } 165 /* EOT Transition? 166 */ 167 if (cdfa->eot[s] >= 0) 168 { 169 s = cdfa->eot[s]; 170 is->consume(is); 171 continue; 172 } 173 /* EOF transition to accept state? 174 */ 175 if ( c == ANTLR3_TOKEN_EOF && cdfa->eof[s] >= 0) 176 { 177 is->rewind(is, mark); 178 return cdfa->accept[cdfa->eof[s]]; 179 } 180 181 /* No alt, so bomb 182 */ 183 noViableAlt(rec, cdfa, s); 184 is->rewind(is, mark); 185 return 0; 186 } 187 188 } 189 190 /** Default special state implementation 191 */ 192 ANTLR3_API ANTLR3_INT32 193 antlr3dfaspecialStateTransition (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s) 194 { 195 return -1; 196 } 197 198 /* Default special transition implementation 199 */ 200 ANTLR3_API ANTLR3_INT32 201 antlr3dfaspecialTransition (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s) 202 { 203 return 0; 204 } 205
