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
noViableAlt(pANTLR3_BASE_RECOGNIZER rec,pANTLR3_CYCLIC_DFA cdfa,ANTLR3_UINT32 s)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
antlr3dfapredict(void * ctx,pANTLR3_BASE_RECOGNIZER rec,pANTLR3_INT_STREAM is,pANTLR3_CYCLIC_DFA cdfa)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
antlr3dfaspecialStateTransition(void * ctx,pANTLR3_BASE_RECOGNIZER recognizer,pANTLR3_INT_STREAM is,pANTLR3_CYCLIC_DFA dfa,ANTLR3_INT32 s)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
antlr3dfaspecialTransition(void * ctx,pANTLR3_BASE_RECOGNIZER recognizer,pANTLR3_INT_STREAM is,pANTLR3_CYCLIC_DFA dfa,ANTLR3_INT32 s)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