1 /** Support functions for traversing cyclic DFA states as laid
\r
2 * out in static initialized structures by the code generator.
\r
4 * A DFA implemented as a set of transition tables.
\r
6 * Any state that has a semantic predicate edge is special; those states
\r
7 * are generated with if-then-else structures in a ->specialStateTransition()
\r
8 * which is generated by cyclicDFA template.
\r
10 * There are at most 32767 states (16-bit signed short).
\r
11 * Could get away with byte sometimes but would have to generate different
\r
12 * types and the simulation code too. For a point of reference, the Java
\r
13 * lexer's Tokens rule DFA has 326 states roughly.
\r
16 // [The "BSD licence"]
\r
17 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
\r
18 // http://www.temporal-wave.com
\r
19 // http://www.linkedin.com/in/jimidle
\r
21 // All rights reserved.
\r
23 // Redistribution and use in source and binary forms, with or without
\r
24 // modification, are permitted provided that the following conditions
\r
26 // 1. Redistributions of source code must retain the above copyright
\r
27 // notice, this list of conditions and the following disclaimer.
\r
28 // 2. Redistributions in binary form must reproduce the above copyright
\r
29 // notice, this list of conditions and the following disclaimer in the
\r
30 // documentation and/or other materials provided with the distribution.
\r
31 // 3. The name of the author may not be used to endorse or promote products
\r
32 // derived from this software without specific prior written permission.
\r
34 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
\r
35 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
\r
36 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
\r
37 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
\r
38 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
\r
39 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
\r
40 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
\r
41 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
\r
42 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
\r
43 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\r
45 #include <antlr3defs.h>
\r
46 #include <antlr3cyclicdfa.h>
\r
48 #ifdef ANTLR3_WINDOWS
\r
49 #pragma warning( disable : 4100 )
\r
53 noViableAlt(pANTLR3_BASE_RECOGNIZER rec, pANTLR3_CYCLIC_DFA cdfa, ANTLR3_UINT32 s)
\r
55 // In backtracking mode, we just set the failed flag so that the
\r
56 // alt can just exit right now. If we are parsing though, then
\r
57 // we want the exception to be raised.
\r
59 if (rec->state->backtracking > 0)
\r
61 rec->state->failed = ANTLR3_TRUE;
\r
65 rec->exConstruct(rec);
\r
66 rec->state->exception->type = ANTLR3_NO_VIABLE_ALT_EXCEPTION;
\r
67 rec->state->exception->message = cdfa->description;
\r
68 rec->state->exception->decisionNum = cdfa->decisionNumber;
\r
69 rec->state->exception->state = s;
\r
73 /** From the input stream, predict what alternative will succeed
\r
74 * using this DFA (representing the covering regular approximation
\r
75 * to the underlying CFL). Return an alternative number 1..n. Throw
\r
76 * an exception upon error.
\r
78 ANTLR3_API ANTLR3_INT32
\r
79 antlr3dfapredict (void * ctx, pANTLR3_BASE_RECOGNIZER rec, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA cdfa)
\r
83 ANTLR3_INT32 specialState;
\r
86 mark = is->mark(is); /* Store where we are right now */
\r
87 s = 0; /* Always start with state 0 */
\r
91 /* Pick out any special state entry for this state
\r
93 specialState = cdfa->special[s];
\r
95 /* Transition the special state and consume an input token
\r
97 if (specialState >= 0)
\r
99 s = cdfa->specialStateTransition(ctx, rec, is, cdfa, specialState);
\r
105 // If the predicate/rule raised an exception then we leave it
\r
106 // in tact, else we have an NVA.
\r
108 if (rec->state->error != ANTLR3_TRUE)
\r
110 noViableAlt(rec,cdfa, s);
\r
112 is->rewind(is, mark);
\r
121 if (cdfa->accept[s] >= 1)
\r
123 is->rewind(is, mark);
\r
124 return cdfa->accept[s];
\r
127 /* Look for a normal transition state based upon the input token element
\r
129 c = is->_LA(is, 1);
\r
131 /* Check against min and max for this state
\r
133 if (c>= cdfa->min[s] && c <= cdfa->max[s])
\r
135 ANTLR3_INT32 snext;
\r
137 /* What is the next state?
\r
139 snext = cdfa->transition[s][c - cdfa->min[s]];
\r
143 /* Was in range but not a normal transition
\r
144 * must check EOT, which is like the else clause.
\r
145 * eot[s]>=0 indicates that an EOT edge goes to another
\r
148 if (cdfa->eot[s] >= 0)
\r
154 noViableAlt(rec,cdfa, s);
\r
155 is->rewind(is, mark);
\r
159 /* New current state - move to it
\r
167 if (cdfa->eot[s] >= 0)
\r
173 /* EOF transition to accept state?
\r
175 if ( c == ANTLR3_TOKEN_EOF && cdfa->eof[s] >= 0)
\r
177 is->rewind(is, mark);
\r
178 return cdfa->accept[cdfa->eof[s]];
\r
183 noViableAlt(rec, cdfa, s);
\r
184 is->rewind(is, mark);
\r
190 /** Default special state implementation
\r
192 ANTLR3_API ANTLR3_INT32
\r
193 antlr3dfaspecialStateTransition (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
\r
198 /* Default special transition implementation
\r
200 ANTLR3_API ANTLR3_INT32
\r
201 antlr3dfaspecialTransition (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
\r