xref: /external/antlr/antlr-3.4/runtime/C/src/antlr3cyclicdfa.c

/** Support functions for traversing cyclic DFA states as laid
 *  out in static initialized structures by the code generator.
 *
 * A DFA implemented as a set of transition tables.
 *
 *  Any state that has a semantic predicate edge is special; those states
 *  are generated with if-then-else structures in a ->specialStateTransition()
 *  which is generated by cyclicDFA template.
 *
 *  There are at most 32767 states (16-bit signed short).
 *  Could get away with byte sometimes but would have to generate different
 *  types and the simulation code too.  For a point of reference, the Java
 *  lexer's Tokens rule DFA has 326 states roughly.
 */

// [The "BSD licence"]
// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
// http://www.temporal-wave.com
// http://www.linkedin.com/in/jimidle
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
// 3. The name of the author may not be used to endorse or promote products
//    derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include    <antlr3defs.h>
#include    <antlr3cyclicdfa.h>

#ifdef	ANTLR3_WINDOWS
#pragma warning( disable : 4100 )
#endif

static void
noViableAlt(pANTLR3_BASE_RECOGNIZER rec, pANTLR3_CYCLIC_DFA cdfa, ANTLR3_UINT32	s)
{
	// In backtracking mode, we just set the failed flag so that the
	// alt can just exit right now. If we are parsing though, then
	// we want the exception to be raised.
	//
    if	(rec->state->backtracking > 0)
    {
		rec->state->failed = ANTLR3_TRUE;
    }
	else
	{
		rec->exConstruct(rec);
		rec->state->exception->type         = ANTLR3_NO_VIABLE_ALT_EXCEPTION;
		rec->state->exception->message      = cdfa->description;
		rec->state->exception->decisionNum  = cdfa->decisionNumber;
		rec->state->exception->state        = s;
	}
}

/** From the input stream, predict what alternative will succeed
 *  using this DFA (representing the covering regular approximation
 *  to the underlying CFL).  Return an alternative number 1..n.  Throw
 *  an exception upon error.
 */
ANTLR3_API ANTLR3_INT32
antlr3dfapredict (void * ctx, pANTLR3_BASE_RECOGNIZER rec, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA cdfa)
{
    ANTLR3_MARKER	mark;
    ANTLR3_INT32	s;
    ANTLR3_INT32	specialState;
    ANTLR3_INT32	c;

    mark	= is->mark(is);	    /* Store where we are right now	*/
    s		= 0;		    /* Always start with state 0	*/

	for (;;)
	{
		/* Pick out any special state entry for this state
		 */
		specialState	= cdfa->special[s];

		/* Transition the special state and consume an input token
		 */
		if  (specialState >= 0)
		{
			s = cdfa->specialStateTransition(ctx, rec, is, cdfa, specialState);

			// Error?
			//
			if	(s<0)
			{
				// If the predicate/rule raised an exception then we leave it
				// in tact, else we have an NVA.
				//
				if	(rec->state->error != ANTLR3_TRUE)
				{
					noViableAlt(rec,cdfa, s);
				}
				is->rewind(is, mark);
				return	0;
			}
			is->consume(is);
			continue;
		}

		/* Accept state?
		 */
		if  (cdfa->accept[s] >= 1)
		{
			is->rewind(is, mark);
			return  cdfa->accept[s];
		}

		/* Look for a normal transition state based upon the input token element
		 */
		c = is->_LA(is, 1);

		/* Check against min and max for this state
		 */
		if  (c>= cdfa->min[s] && c <= cdfa->max[s])
		{
			ANTLR3_INT32   snext;

			/* What is the next state?
			 */
			snext = cdfa->transition[s][c - cdfa->min[s]];

			if	(snext < 0)
			{
				/* Was in range but not a normal transition
				 * must check EOT, which is like the else clause.
				 * eot[s]>=0 indicates that an EOT edge goes to another
				 * state.
				 */
				if  (cdfa->eot[s] >= 0)
				{
					s = cdfa->eot[s];
					is->consume(is);
					continue;
				}
				noViableAlt(rec,cdfa, s);
				is->rewind(is, mark);
				return	0;
			}

			/* New current state - move to it
			 */
			s	= snext;
			is->consume(is);
			continue;
		}
		/* EOT Transition?
		 */
		if  (cdfa->eot[s] >= 0)
		{
			s	= cdfa->eot[s];
			is->consume(is);
			continue;
		}
		/* EOF transition to accept state?
		 */
		if  ( c == ANTLR3_TOKEN_EOF && cdfa->eof[s] >= 0)
		{
			is->rewind(is, mark);
			return  cdfa->accept[cdfa->eof[s]];
		}

		/* No alt, so bomb
		 */
		noViableAlt(rec, cdfa, s);
		is->rewind(is, mark);
		return 0;
	}

}

/** Default special state implementation
 */
ANTLR3_API ANTLR3_INT32
antlr3dfaspecialStateTransition   (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
{
    return -1;
}

/* Default special transition implementation
 */
ANTLR3_API ANTLR3_INT32
antlr3dfaspecialTransition    (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
{
    return 0;
}