/** \file
* Contains the base functions that all recognizers require.
* Any function can be overridden by a lexer/parser/tree parser or by the
* ANTLR3 programmer.
*
* \addtogroup pANTLR3_BASE_RECOGNIZER
* @{
*/
#include <antlr3baserecognizer.h>
// [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.
#ifdef ANTLR3_WINDOWS
#pragma warning( disable : 4100 )
#endif
/* Interface functions -standard implementations cover parser and treeparser
* almost completely but are overridden by the parser or tree parser as needed. Lexer overrides
* most of these functions.
*/
static void beginResync (pANTLR3_BASE_RECOGNIZER recognizer);
static pANTLR3_BITSET computeErrorRecoverySet (pANTLR3_BASE_RECOGNIZER recognizer);
static void endResync (pANTLR3_BASE_RECOGNIZER recognizer);
static void beginBacktrack (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 level);
static void endBacktrack (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 level, ANTLR3_BOOLEAN successful);
static void * match (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 ttype, pANTLR3_BITSET_LIST follow);
static void matchAny (pANTLR3_BASE_RECOGNIZER recognizer);
static void mismatch (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 ttype, pANTLR3_BITSET_LIST follow);
static ANTLR3_BOOLEAN mismatchIsUnwantedToken (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, ANTLR3_UINT32 ttype);
static ANTLR3_BOOLEAN mismatchIsMissingToken (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_BITSET_LIST follow);
static void reportError (pANTLR3_BASE_RECOGNIZER recognizer);
static pANTLR3_BITSET computeCSRuleFollow (pANTLR3_BASE_RECOGNIZER recognizer);
static pANTLR3_BITSET combineFollows (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_BOOLEAN exact);
static void displayRecognitionError (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_UINT8 * tokenNames);
static void recover (pANTLR3_BASE_RECOGNIZER recognizer);
static void * recoverFromMismatchedToken (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 ttype, pANTLR3_BITSET_LIST follow);
static void * recoverFromMismatchedSet (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_BITSET_LIST follow);
static ANTLR3_BOOLEAN recoverFromMismatchedElement(pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_BITSET_LIST follow);
static void consumeUntil (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 tokenType);
static void consumeUntilSet (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_BITSET set);
static pANTLR3_STACK getRuleInvocationStack (pANTLR3_BASE_RECOGNIZER recognizer);
static pANTLR3_STACK getRuleInvocationStackNamed (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_UINT8 name);
static pANTLR3_HASH_TABLE toStrings (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_HASH_TABLE);
static ANTLR3_MARKER getRuleMemoization (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_INTKEY ruleIndex, ANTLR3_MARKER ruleParseStart);
static ANTLR3_BOOLEAN alreadyParsedRule (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_MARKER ruleIndex);
static void memoize (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_MARKER ruleIndex, ANTLR3_MARKER ruleParseStart);
static ANTLR3_BOOLEAN synpred (pANTLR3_BASE_RECOGNIZER recognizer, void * ctx, void (*predicate)(void * ctx));
static void reset (pANTLR3_BASE_RECOGNIZER recognizer);
static void freeBR (pANTLR3_BASE_RECOGNIZER recognizer);
static void * getCurrentInputSymbol (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM istream);
static void * getMissingSymbol (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM istream, pANTLR3_EXCEPTION e,
ANTLR3_UINT32 expectedTokenType, pANTLR3_BITSET_LIST follow);
static ANTLR3_UINT32 getNumberOfSyntaxErrors (pANTLR3_BASE_RECOGNIZER recognizer);
ANTLR3_API pANTLR3_BASE_RECOGNIZER
antlr3BaseRecognizerNew(ANTLR3_UINT32 type, ANTLR3_UINT32 sizeHint, pANTLR3_RECOGNIZER_SHARED_STATE state)
{
pANTLR3_BASE_RECOGNIZER recognizer;
// Allocate memory for the structure
//
recognizer = (pANTLR3_BASE_RECOGNIZER) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BASE_RECOGNIZER));
if (recognizer == NULL)
{
// Allocation failed
//
return NULL;
}
// If we have been supplied with a pre-existing recognizer state
// then we just install it, otherwise we must create one from scratch
//
if (state == NULL)
{
recognizer->state = (pANTLR3_RECOGNIZER_SHARED_STATE) ANTLR3_CALLOC(1, (size_t)sizeof(ANTLR3_RECOGNIZER_SHARED_STATE));
if (recognizer->state == NULL)
{
ANTLR3_FREE(recognizer);
return NULL;
}
// Initialize any new recognizer state
//
recognizer->state->errorRecovery = ANTLR3_FALSE;
recognizer->state->lastErrorIndex = -1;
recognizer->state->failed = ANTLR3_FALSE;
recognizer->state->errorCount = 0;
recognizer->state->backtracking = 0;
recognizer->state->following = NULL;
recognizer->state->ruleMemo = NULL;
recognizer->state->tokenNames = NULL;
recognizer->state->sizeHint = sizeHint;
recognizer->state->tokSource = NULL;
recognizer->state->tokFactory = NULL;
// Rather than check to see if we must initialize
// the stack every time we are asked for an new rewrite stream
// we just always create an empty stack and then just
// free it when the base recognizer is freed.
//
recognizer->state->rStreams = antlr3VectorNew(0); // We don't know the size.
if (recognizer->state->rStreams == NULL)
{
// Out of memory
//
ANTLR3_FREE(recognizer->state);
ANTLR3_FREE(recognizer);
return NULL;
}
}
else
{
// Install the one we were given, and do not reset it here
// as it will either already have been initialized or will
// be in a state that needs to be preserved.
//
recognizer->state = state;
}
// Install the BR API
//
recognizer->alreadyParsedRule = alreadyParsedRule;
recognizer->beginResync = beginResync;
recognizer->combineFollows = combineFollows;
recognizer->beginBacktrack = beginBacktrack;
recognizer->endBacktrack = endBacktrack;
recognizer->computeCSRuleFollow = computeCSRuleFollow;
recognizer->computeErrorRecoverySet = computeErrorRecoverySet;
recognizer->consumeUntil = consumeUntil;
recognizer->consumeUntilSet = consumeUntilSet;
recognizer->displayRecognitionError = displayRecognitionError;
recognizer->endResync = endResync;
recognizer->exConstruct = antlr3MTExceptionNew;
recognizer->getRuleInvocationStack = getRuleInvocationStack;
recognizer->getRuleInvocationStackNamed = getRuleInvocationStackNamed;
recognizer->getRuleMemoization = getRuleMemoization;
recognizer->match = match;
recognizer->matchAny = matchAny;
recognizer->memoize = memoize;
recognizer->mismatch = mismatch;
recognizer->mismatchIsUnwantedToken = mismatchIsUnwantedToken;
recognizer->mismatchIsMissingToken = mismatchIsMissingToken;
recognizer->recover = recover;
recognizer->recoverFromMismatchedElement= recoverFromMismatchedElement;
recognizer->recoverFromMismatchedSet = recoverFromMismatchedSet;
recognizer->recoverFromMismatchedToken = recoverFromMismatchedToken;
recognizer->getNumberOfSyntaxErrors = getNumberOfSyntaxErrors;
recognizer->reportError = reportError;
recognizer->reset = reset;
recognizer->synpred = synpred;
recognizer->toStrings = toStrings;
recognizer->getCurrentInputSymbol = getCurrentInputSymbol;
recognizer->getMissingSymbol = getMissingSymbol;
recognizer->debugger = NULL;
recognizer->free = freeBR;
/* Initialize variables
*/
recognizer->type = type;
return recognizer;
}
static void
freeBR (pANTLR3_BASE_RECOGNIZER recognizer)
{
pANTLR3_EXCEPTION thisE;
// Did we have a state allocated?
//
if (recognizer->state != NULL)
{
// Free any rule memoization we set up
//
if (recognizer->state->ruleMemo != NULL)
{
recognizer->state->ruleMemo->free(recognizer->state->ruleMemo);
recognizer->state->ruleMemo = NULL;
}
// Free any exception space we have left around
//
thisE = recognizer->state->exception;
if (thisE != NULL)
{
thisE->freeEx(thisE);
}
// Free any rewrite streams we have allocated
//
if (recognizer->state->rStreams != NULL)
{
recognizer->state->rStreams->free(recognizer->state->rStreams);
}
// Free up any token factory we created (error recovery for instance)
//
if (recognizer->state->tokFactory != NULL)
{
recognizer->state->tokFactory->close(recognizer->state->tokFactory);
}
// Free the shared state memory
//
ANTLR3_FREE(recognizer->state);
}
// Free the actual recognizer space
//
ANTLR3_FREE(recognizer);
}
/**
* Creates a new Mismatched Token Exception and inserts in the recognizer
* exception stack.
*
* \param recognizer
* Context pointer for this recognizer
*
*/
ANTLR3_API void
antlr3MTExceptionNew(pANTLR3_BASE_RECOGNIZER recognizer)
{
/* Create a basic recognition exception structure
*/
antlr3RecognitionExceptionNew(recognizer);
/* Now update it to indicate this is a Mismatched token exception
*/
recognizer->state->exception->name = ANTLR3_MISMATCHED_EX_NAME;
recognizer->state->exception->type = ANTLR3_MISMATCHED_TOKEN_EXCEPTION;
return;
}
ANTLR3_API void
antlr3RecognitionExceptionNew(pANTLR3_BASE_RECOGNIZER recognizer)
{
pANTLR3_EXCEPTION ex;
pANTLR3_LEXER lexer;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INPUT_STREAM ins;
pANTLR3_INT_STREAM is;
pANTLR3_COMMON_TOKEN_STREAM cts;
pANTLR3_TREE_NODE_STREAM tns;
ins = NULL;
cts = NULL;
tns = NULL;
is = NULL;
lexer = NULL;
parser = NULL;
tparser = NULL;
switch (recognizer->type)
{
case ANTLR3_TYPE_LEXER:
lexer = (pANTLR3_LEXER) (recognizer->super);
ins = lexer->input;
is = ins->istream;
break;
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
cts = (pANTLR3_COMMON_TOKEN_STREAM)(parser->tstream->super);
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
tns = tparser->ctnstream->tnstream;
is = tns->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function antlr3RecognitionExceptionNew called by unknown parser type - provide override for this function\n");
return;
break;
}
/* Create a basic exception structure
*/
ex = antlr3ExceptionNew(ANTLR3_RECOGNITION_EXCEPTION,
(void *)ANTLR3_RECOGNITION_EX_NAME,
NULL,
ANTLR3_FALSE);
/* Rest of information depends on the base type of the
* input stream.
*/
switch (is->type & ANTLR3_INPUT_MASK)
{
case ANTLR3_CHARSTREAM:
ex->c = is->_LA (is, 1); /* Current input character */
ex->line = ins->getLine (ins); /* Line number comes from stream */
ex->charPositionInLine = ins->getCharPositionInLine (ins); /* Line offset also comes from the stream */
ex->index = is->index (is);
ex->streamName = ins->fileName;
ex->message = "Unexpected character";
break;
case ANTLR3_TOKENSTREAM:
ex->token = cts->tstream->_LT (cts->tstream, 1); /* Current input token */
ex->line = ((pANTLR3_COMMON_TOKEN)(ex->token))->getLine (ex->token);
ex->charPositionInLine = ((pANTLR3_COMMON_TOKEN)(ex->token))->getCharPositionInLine (ex->token);
ex->index = cts->tstream->istream->index (cts->tstream->istream);
if (((pANTLR3_COMMON_TOKEN)(ex->token))->type == ANTLR3_TOKEN_EOF)
{
ex->streamName = NULL;
}
else
{
ex->streamName = ((pANTLR3_COMMON_TOKEN)(ex->token))->input->fileName;
}
ex->message = "Unexpected token";
break;
case ANTLR3_COMMONTREENODE:
ex->token = tns->_LT (tns, 1); /* Current input tree node */
ex->line = ((pANTLR3_BASE_TREE)(ex->token))->getLine (ex->token);
ex->charPositionInLine = ((pANTLR3_BASE_TREE)(ex->token))->getCharPositionInLine (ex->token);
ex->index = tns->istream->index (tns->istream);
// Are you ready for this? Deep breath now...
//
{
pANTLR3_COMMON_TREE tnode;
tnode = ((pANTLR3_COMMON_TREE)(((pANTLR3_BASE_TREE)(ex->token))->super));
if (tnode->token == NULL)
{
ex->streamName = ((pANTLR3_BASE_TREE)(ex->token))->strFactory->newStr(((pANTLR3_BASE_TREE)(ex->token))->strFactory, (pANTLR3_UINT8)"-unknown source-");
}
else
{
if (tnode->token->input == NULL)
{
ex->streamName = NULL;
}
else
{
ex->streamName = tnode->token->input->fileName;
}
}
ex->message = "Unexpected node";
}
break;
}
ex->input = is;
ex->nextException = recognizer->state->exception; /* So we don't leak the memory */
recognizer->state->exception = ex;
recognizer->state->error = ANTLR3_TRUE; /* Exception is outstanding */
return;
}
/// Match current input symbol against ttype. Upon error, do one token
/// insertion or deletion if possible.
/// To turn off single token insertion or deletion error
/// recovery, override mismatchRecover() and have it call
/// plain mismatch(), which does not recover. Then any error
/// in a rule will cause an exception and immediate exit from
/// rule. Rule would recover by resynchronizing to the set of
/// symbols that can follow rule ref.
///
static void *
match( pANTLR3_BASE_RECOGNIZER recognizer,
ANTLR3_UINT32 ttype, pANTLR3_BITSET_LIST follow)
{
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
void * matchedSymbol;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'match' called by unknown parser type - provide override for this function\n");
return ANTLR3_FALSE;
break;
}
// Pick up the current input token/node for assignment to labels
//
matchedSymbol = recognizer->getCurrentInputSymbol(recognizer, is);
if (is->_LA(is, 1) == ttype)
{
// The token was the one we were told to expect
//
is->consume(is); // Consume that token from the stream
recognizer->state->errorRecovery = ANTLR3_FALSE; // Not in error recovery now (if we were)
recognizer->state->failed = ANTLR3_FALSE; // The match was a success
return matchedSymbol; // We are done
}
// We did not find the expected token type, if we are backtracking then
// we just set the failed flag and return.
//
if (recognizer->state->backtracking > 0)
{
// Backtracking is going on
//
recognizer->state->failed = ANTLR3_TRUE;
return matchedSymbol;
}
// We did not find the expected token and there is no backtracking
// going on, so we mismatch, which creates an exception in the recognizer exception
// stack.
//
matchedSymbol = recognizer->recoverFromMismatchedToken(recognizer, ttype, follow);
return matchedSymbol;
}
/// Consumes the next token, whatever it is, and resets the recognizer state
/// so that it is not in error.
///
/// \param recognizer
/// Recognizer context pointer
///
static void
matchAny(pANTLR3_BASE_RECOGNIZER recognizer)
{
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'matchAny' called by unknown parser type - provide override for this function\n");
return;
break;
}
recognizer->state->errorRecovery = ANTLR3_FALSE;
recognizer->state->failed = ANTLR3_FALSE;
is->consume(is);
return;
}
///
///
static ANTLR3_BOOLEAN
mismatchIsUnwantedToken(pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, ANTLR3_UINT32 ttype)
{
ANTLR3_UINT32 nextt;
nextt = is->_LA(is, 2);
if (nextt == ttype)
{
if (recognizer->state->exception != NULL)
{
recognizer->state->exception->expecting = nextt;
}
return ANTLR3_TRUE; // This token is unknown, but the next one is the one we wanted
}
else
{
return ANTLR3_FALSE; // Neither this token, nor the one following is the one we wanted
}
}
///
///
static ANTLR3_BOOLEAN
mismatchIsMissingToken(pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_BITSET_LIST follow)
{
ANTLR3_BOOLEAN retcode;
pANTLR3_BITSET followClone;
pANTLR3_BITSET viableTokensFollowingThisRule;
if (follow == NULL)
{
// There is no information about the tokens that can follow the last one
// hence we must say that the current one we found is not a member of the
// follow set and does not indicate a missing token. We will just consume this
// single token and see if the parser works it out from there.
//
return ANTLR3_FALSE;
}
followClone = NULL;
viableTokensFollowingThisRule = NULL;
// The C bitset maps are laid down at compile time by the
// C code generation. Hence we cannot remove things from them
// and so on. So, in order to remove EOR (if we need to) then
// we clone the static bitset.
//
followClone = antlr3BitsetLoad(follow);
if (followClone == NULL)
{
return ANTLR3_FALSE;
}
// Compute what can follow this grammar reference
//
if (followClone->isMember(followClone, ANTLR3_EOR_TOKEN_TYPE))
{
// EOR can follow, but if we are not the start symbol, we
// need to remove it.
//
if (recognizer->state->following->vector->count >= 0)
{
followClone->remove(followClone, ANTLR3_EOR_TOKEN_TYPE);
}
// Now compute the visiable tokens that can follow this rule, according to context
// and make them part of the follow set.
//
viableTokensFollowingThisRule = recognizer->computeCSRuleFollow(recognizer);
followClone->borInPlace(followClone, viableTokensFollowingThisRule);
}
/// if current token is consistent with what could come after set
/// then we know we're missing a token; error recovery is free to
/// "insert" the missing token
///
/// BitSet cannot handle negative numbers like -1 (EOF) so I leave EOR
/// in follow set to indicate that the fall of the start symbol is
/// in the set (EOF can follow).
///
if ( followClone->isMember(followClone, is->_LA(is, 1))
|| followClone->isMember(followClone, ANTLR3_EOR_TOKEN_TYPE)
)
{
retcode = ANTLR3_TRUE;
}
else
{
retcode = ANTLR3_FALSE;
}
if (viableTokensFollowingThisRule != NULL)
{
viableTokensFollowingThisRule->free(viableTokensFollowingThisRule);
}
if (followClone != NULL)
{
followClone->free(followClone);
}
return retcode;
}
/// Factor out what to do upon token mismatch so tree parsers can behave
/// differently. Override and call mismatchRecover(input, ttype, follow)
/// to get single token insertion and deletion. Use this to turn off
/// single token insertion and deletion. Override mismatchRecover
/// to call this instead.
///
/// \remark mismatch only works for parsers and must be overridden for anything else.
///
static void
mismatch(pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 ttype, pANTLR3_BITSET_LIST follow)
{
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
// Install a mismatched token exception in the exception stack
//
antlr3MTExceptionNew(recognizer);
recognizer->state->exception->expecting = ttype;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'mismatch' called by unknown parser type - provide override for this function\n");
return;
break;
}
if (mismatchIsUnwantedToken(recognizer, is, ttype))
{
// Create a basic recognition exception structure
//
antlr3RecognitionExceptionNew(recognizer);
// Now update it to indicate this is an unwanted token exception
//
recognizer->state->exception->name = ANTLR3_UNWANTED_TOKEN_EXCEPTION_NAME;
recognizer->state->exception->type = ANTLR3_UNWANTED_TOKEN_EXCEPTION;
return;
}
if (mismatchIsMissingToken(recognizer, is, follow))
{
// Create a basic recognition exception structure
//
antlr3RecognitionExceptionNew(recognizer);
// Now update it to indicate this is an unwanted token exception
//
recognizer->state->exception->name = ANTLR3_MISSING_TOKEN_EXCEPTION_NAME;
recognizer->state->exception->type = ANTLR3_MISSING_TOKEN_EXCEPTION;
return;
}
// Just a mismatched token is all we can dtermine
//
antlr3MTExceptionNew(recognizer);
return;
}
/// Report a recognition problem.
///
/// This method sets errorRecovery to indicate the parser is recovering
/// not parsing. Once in recovery mode, no errors are generated.
/// To get out of recovery mode, the parser must successfully match
/// a token (after a resync). So it will go:
///
/// 1. error occurs
/// 2. enter recovery mode, report error
/// 3. consume until token found in resynch set
/// 4. try to resume parsing
/// 5. next match() will reset errorRecovery mode
///
/// If you override, make sure to update errorCount if you care about that.
///
static void
reportError (pANTLR3_BASE_RECOGNIZER recognizer)
{
// Invoke the debugger event if there is a debugger listening to us
//
if (recognizer->debugger != NULL)
{
recognizer->debugger->recognitionException(recognizer->debugger, recognizer->state->exception);
}
if (recognizer->state->errorRecovery == ANTLR3_TRUE)
{
// Already in error recovery so don't display another error while doing so
//
return;
}
// Signal we are in error recovery now
//
recognizer->state->errorRecovery = ANTLR3_TRUE;
// Indicate this recognizer had an error while processing.
//
recognizer->state->errorCount++;
// Call the error display routine
//
recognizer->displayRecognitionError(recognizer, recognizer->state->tokenNames);
}
static void
beginBacktrack (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 level)
{
if (recognizer->debugger != NULL)
{
recognizer->debugger->beginBacktrack(recognizer->debugger, level);
}
}
static void
endBacktrack (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 level, ANTLR3_BOOLEAN successful)
{
if (recognizer->debugger != NULL)
{
recognizer->debugger->endBacktrack(recognizer->debugger, level, successful);
}
}
static void
beginResync (pANTLR3_BASE_RECOGNIZER recognizer)
{
if (recognizer->debugger != NULL)
{
recognizer->debugger->beginResync(recognizer->debugger);
}
}
static void
endResync (pANTLR3_BASE_RECOGNIZER recognizer)
{
if (recognizer->debugger != NULL)
{
recognizer->debugger->endResync(recognizer->debugger);
}
}
/// Compute the error recovery set for the current rule.
/// Documentation below is from the Java implementation.
///
/// During rule invocation, the parser pushes the set of tokens that can
/// follow that rule reference on the stack; this amounts to
/// computing FIRST of what follows the rule reference in the
/// enclosing rule. This local follow set only includes tokens
/// from within the rule; i.e., the FIRST computation done by
/// ANTLR stops at the end of a rule.
//
/// EXAMPLE
//
/// When you find a "no viable alt exception", the input is not
/// consistent with any of the alternatives for rule r. The best
/// thing to do is to consume tokens until you see something that
/// can legally follow a call to r *or* any rule that called r.
/// You don't want the exact set of viable next tokens because the
/// input might just be missing a token--you might consume the
/// rest of the input looking for one of the missing tokens.
///
/// Consider grammar:
///
/// a : '[' b ']'
/// | '(' b ')'
/// ;
/// b : c '^' INT ;
/// c : ID
/// | INT
/// ;
///
/// At each rule invocation, the set of tokens that could follow
/// that rule is pushed on a stack. Here are the various "local"
/// follow sets:
///
/// FOLLOW(b1_in_a) = FIRST(']') = ']'
/// FOLLOW(b2_in_a) = FIRST(')') = ')'
/// FOLLOW(c_in_b) = FIRST('^') = '^'
///
/// Upon erroneous input "[]", the call chain is
///
/// a -> b -> c
///
/// and, hence, the follow context stack is:
///
/// depth local follow set after call to rule
/// 0 <EOF> a (from main())
/// 1 ']' b
/// 3 '^' c
///
/// Notice that ')' is not included, because b would have to have
/// been called from a different context in rule a for ')' to be
/// included.
///
/// For error recovery, we cannot consider FOLLOW(c)
/// (context-sensitive or otherwise). We need the combined set of
/// all context-sensitive FOLLOW sets--the set of all tokens that
/// could follow any reference in the call chain. We need to
/// resync to one of those tokens. Note that FOLLOW(c)='^' and if
/// we resync'd to that token, we'd consume until EOF. We need to
/// sync to context-sensitive FOLLOWs for a, b, and c: {']','^'}.
/// In this case, for input "[]", LA(1) is in this set so we would
/// not consume anything and after printing an error rule c would
/// return normally. It would not find the required '^' though.
/// At this point, it gets a mismatched token error and throws an
/// exception (since LA(1) is not in the viable following token
/// set). The rule exception handler tries to recover, but finds
/// the same recovery set and doesn't consume anything. Rule b
/// exits normally returning to rule a. Now it finds the ']' (and
/// with the successful match exits errorRecovery mode).
///
/// So, you can see that the parser walks up call chain looking
/// for the token that was a member of the recovery set.
///
/// Errors are not generated in errorRecovery mode.
///
/// ANTLR's error recovery mechanism is based upon original ideas:
///
/// "Algorithms + Data Structures = Programs" by Niklaus Wirth
///
/// and
///
/// "A note on error recovery in recursive descent parsers":
/// http://portal.acm.org/citation.cfm?id=947902.947905
///
/// Later, Josef Grosch had some good ideas:
///
/// "Efficient and Comfortable Error Recovery in Recursive Descent
/// Parsers":
/// ftp://www.cocolab.com/products/cocktail/doca4.ps/ell.ps.zip
///
/// Like Grosch I implemented local FOLLOW sets that are combined
/// at run-time upon error to avoid overhead during parsing.
///
static pANTLR3_BITSET
computeErrorRecoverySet (pANTLR3_BASE_RECOGNIZER recognizer)
{
return recognizer->combineFollows(recognizer, ANTLR3_FALSE);
}
/// Compute the context-sensitive FOLLOW set for current rule.
/// Documentation below is from the Java runtime.
///
/// This is the set of token types that can follow a specific rule
/// reference given a specific call chain. You get the set of
/// viable tokens that can possibly come next (look ahead depth 1)
/// given the current call chain. Contrast this with the
/// definition of plain FOLLOW for rule r:
///
/// FOLLOW(r)={x | S=>*alpha r beta in G and x in FIRST(beta)}
///
/// where x in T* and alpha, beta in V*; T is set of terminals and
/// V is the set of terminals and non terminals. In other words,
/// FOLLOW(r) is the set of all tokens that can possibly follow
/// references to r in///any* sentential form (context). At
/// runtime, however, we know precisely which context applies as
/// we have the call chain. We may compute the exact (rather
/// than covering superset) set of following tokens.
///
/// For example, consider grammar:
///
/// stat : ID '=' expr ';' // FOLLOW(stat)=={EOF}
/// | "return" expr '.'
/// ;
/// expr : atom ('+' atom)* ; // FOLLOW(expr)=={';','.',')'}
/// atom : INT // FOLLOW(atom)=={'+',')',';','.'}
/// | '(' expr ')'
/// ;
///
/// The FOLLOW sets are all inclusive whereas context-sensitive
/// FOLLOW sets are precisely what could follow a rule reference.
/// For input input "i=(3);", here is the derivation:
///
/// stat => ID '=' expr ';'
/// => ID '=' atom ('+' atom)* ';'
/// => ID '=' '(' expr ')' ('+' atom)* ';'
/// => ID '=' '(' atom ')' ('+' atom)* ';'
/// => ID '=' '(' INT ')' ('+' atom)* ';'
/// => ID '=' '(' INT ')' ';'
///
/// At the "3" token, you'd have a call chain of
///
/// stat -> expr -> atom -> expr -> atom
///
/// What can follow that specific nested ref to atom? Exactly ')'
/// as you can see by looking at the derivation of this specific
/// input. Contrast this with the FOLLOW(atom)={'+',')',';','.'}.
///
/// You want the exact viable token set when recovering from a
/// token mismatch. Upon token mismatch, if LA(1) is member of
/// the viable next token set, then you know there is most likely
/// a missing token in the input stream. "Insert" one by just not
/// throwing an exception.
///
static pANTLR3_BITSET
computeCSRuleFollow (pANTLR3_BASE_RECOGNIZER recognizer)
{
return recognizer->combineFollows(recognizer, ANTLR3_FALSE);
}
/// Compute the current followset for the input stream.
///
static pANTLR3_BITSET
combineFollows (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_BOOLEAN exact)
{
pANTLR3_BITSET followSet;
pANTLR3_BITSET localFollowSet;
ANTLR3_UINT32 top;
ANTLR3_UINT32 i;
top = recognizer->state->following->size(recognizer->state->following);
followSet = antlr3BitsetNew(0);
localFollowSet = NULL;
for (i = top; i>0; i--)
{
localFollowSet = antlr3BitsetLoad((pANTLR3_BITSET_LIST) recognizer->state->following->get(recognizer->state->following, i-1));
if (localFollowSet != NULL)
{
followSet->borInPlace(followSet, localFollowSet);
if (exact == ANTLR3_TRUE)
{
if (localFollowSet->isMember(localFollowSet, ANTLR3_EOR_TOKEN_TYPE) == ANTLR3_FALSE)
{
// Only leave EOR in the set if at top (start rule); this lets us know
// if we have to include the follow(start rule); I.E., EOF
//
if (i>1)
{
followSet->remove(followSet, ANTLR3_EOR_TOKEN_TYPE);
}
}
else
{
break; // Cannot see End Of Rule from here, just drop out
}
}
localFollowSet->free(localFollowSet);
localFollowSet = NULL;
}
}
if (localFollowSet != NULL)
{
localFollowSet->free(localFollowSet);
}
return followSet;
}
/// Standard/Example error display method.
/// No generic error message display funciton coudl possibly do everything correctly
/// for all possible parsers. Hence you are provided with this example routine, which
/// you should override in your parser/tree parser to do as you will.
///
/// Here we depart somewhat from the Java runtime as that has now split up a lot
/// of the error display routines into spearate units. However, ther is little advantage
/// to this in the C version as you will probably implement all such routines as a
/// separate translation unit, rather than install them all as pointers to functions
/// in the base recognizer.
///
static void
displayRecognitionError (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_UINT8 * tokenNames)
{
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
pANTLR3_STRING ttext;
pANTLR3_STRING ftext;
pANTLR3_EXCEPTION ex;
pANTLR3_COMMON_TOKEN theToken;
pANTLR3_BASE_TREE theBaseTree;
pANTLR3_COMMON_TREE theCommonTree;
// Retrieve some info for easy reading.
//
ex = recognizer->state->exception;
ttext = NULL;
// See if there is a 'filename' we can use
//
if (ex->streamName == NULL)
{
if (((pANTLR3_COMMON_TOKEN)(ex->token))->type == ANTLR3_TOKEN_EOF)
{
ANTLR3_FPRINTF(stderr, "-end of input-(");
}
else
{
ANTLR3_FPRINTF(stderr, "-unknown source-(");
}
}
else
{
ftext = ex->streamName->to8(ex->streamName);
ANTLR3_FPRINTF(stderr, "%s(", ftext->chars);
}
// Next comes the line number
//
ANTLR3_FPRINTF(stderr, "%d) ", recognizer->state->exception->line);
ANTLR3_FPRINTF(stderr, " : error %d : %s",
recognizer->state->exception->type,
(pANTLR3_UINT8) (recognizer->state->exception->message));
// How we determine the next piece is dependent on which thing raised the
// error.
//
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
// Prepare the knowledge we know we have
//
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
theToken = (pANTLR3_COMMON_TOKEN)(recognizer->state->exception->token);
ttext = theToken->toString(theToken);
ANTLR3_FPRINTF(stderr, ", at offset %d", recognizer->state->exception->charPositionInLine);
if (theToken != NULL)
{
if (theToken->type == ANTLR3_TOKEN_EOF)
{
ANTLR3_FPRINTF(stderr, ", at <EOF>");
}
else
{
// Guard against null text in a token
//
ANTLR3_FPRINTF(stderr, "\n near %s\n ", ttext == NULL ? (pANTLR3_UINT8)"<no text for the token>" : ttext->chars);
}
}
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
theBaseTree = (pANTLR3_BASE_TREE)(recognizer->state->exception->token);
ttext = theBaseTree->toStringTree(theBaseTree);
if (theBaseTree != NULL)
{
theCommonTree = (pANTLR3_COMMON_TREE) theBaseTree->super;
if (theCommonTree != NULL)
{
theToken = (pANTLR3_COMMON_TOKEN) theBaseTree->getToken(theBaseTree);
}
ANTLR3_FPRINTF(stderr, ", at offset %d", theBaseTree->getCharPositionInLine(theBaseTree));
ANTLR3_FPRINTF(stderr, ", near %s", ttext->chars);
}
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function displayRecognitionError called by unknown parser type - provide override for this function\n");
return;
break;
}
// Although this function should generally be provided by the implementation, this one
// should be as helpful as possible for grammar developers and serve as an example
// of what you can do with each exception type. In general, when you make up your
// 'real' handler, you should debug the routine with all possible errors you expect
// which will then let you be as specific as possible about all circumstances.
//
// Note that in the general case, errors thrown by tree parsers indicate a problem
// with the output of the parser or with the tree grammar itself. The job of the parser
// is to produce a perfect (in traversal terms) syntactically correct tree, so errors
// at that stage should really be semantic errors that your own code determines and handles
// in whatever way is appropriate.
//
switch (ex->type)
{
case ANTLR3_UNWANTED_TOKEN_EXCEPTION:
// Indicates that the recognizer was fed a token which seesm to be
// spurious input. We can detect this when the token that follows
// this unwanted token would normally be part of the syntactically
// correct stream. Then we can see that the token we are looking at
// is just something that should not be there and throw this exception.
//
if (tokenNames == NULL)
{
ANTLR3_FPRINTF(stderr, " : Extraneous input...");
}
else
{
if (ex->expecting == ANTLR3_TOKEN_EOF)
{
ANTLR3_FPRINTF(stderr, " : Extraneous input - expected <EOF>\n");
}
else
{
ANTLR3_FPRINTF(stderr, " : Extraneous input - expected %s ...\n", tokenNames[ex->expecting]);
}
}
break;
case ANTLR3_MISSING_TOKEN_EXCEPTION:
// Indicates that the recognizer detected that the token we just
// hit would be valid syntactically if preceeded by a particular
// token. Perhaps a missing ';' at line end or a missing ',' in an
// expression list, and such like.
//
if (tokenNames == NULL)
{
ANTLR3_FPRINTF(stderr, " : Missing token (%d)...\n", ex->expecting);
}
else
{
if (ex->expecting == ANTLR3_TOKEN_EOF)
{
ANTLR3_FPRINTF(stderr, " : Missing <EOF>\n");
}
else
{
ANTLR3_FPRINTF(stderr, " : Missing %s \n", tokenNames[ex->expecting]);
}
}
break;
case ANTLR3_RECOGNITION_EXCEPTION:
// Indicates that the recognizer received a token
// in the input that was not predicted. This is the basic exception type
// from which all others are derived. So we assume it was a syntax error.
// You may get this if there are not more tokens and more are needed
// to complete a parse for instance.
//
ANTLR3_FPRINTF(stderr, " : syntax error...\n");
break;
case ANTLR3_MISMATCHED_TOKEN_EXCEPTION:
// We were expecting to see one thing and got another. This is the
// most common error if we coudl not detect a missing or unwanted token.
// Here you can spend your efforts to
// derive more useful error messages based on the expected
// token set and the last token and so on. The error following
// bitmaps do a good job of reducing the set that we were looking
// for down to something small. Knowing what you are parsing may be
// able to allow you to be even more specific about an error.
//
if (tokenNames == NULL)
{
ANTLR3_FPRINTF(stderr, " : syntax error...\n");
}
else
{
if (ex->expecting == ANTLR3_TOKEN_EOF)
{
ANTLR3_FPRINTF(stderr, " : expected <EOF>\n");
}
else
{
ANTLR3_FPRINTF(stderr, " : expected %s ...\n", tokenNames[ex->expecting]);
}
}
break;
case ANTLR3_NO_VIABLE_ALT_EXCEPTION:
// We could not pick any alt decision from the input given
// so god knows what happened - however when you examine your grammar,
// you should. It means that at the point where the current token occurred
// that the DFA indicates nowhere to go from here.
//
ANTLR3_FPRINTF(stderr, " : cannot match to any predicted input...\n");
break;
case ANTLR3_MISMATCHED_SET_EXCEPTION:
{
ANTLR3_UINT32 count;
ANTLR3_UINT32 bit;
ANTLR3_UINT32 size;
ANTLR3_UINT32 numbits;
pANTLR3_BITSET errBits;
// This means we were able to deal with one of a set of
// possible tokens at this point, but we did not see any
// member of that set.
//
ANTLR3_FPRINTF(stderr, " : unexpected input...\n expected one of : ");
// What tokens could we have accepted at this point in the
// parse?
//
count = 0;
errBits = antlr3BitsetLoad (ex->expectingSet);
numbits = errBits->numBits (errBits);
size = errBits->size (errBits);
if (size > 0)
{
// However many tokens we could have dealt with here, it is usually
// not useful to print ALL of the set here. I arbitrarily chose 8
// here, but you should do whatever makes sense for you of course.
// No token number 0, so look for bit 1 and on.
//
for (bit = 1; bit < numbits && count < 8 && count < size; bit++)
{
// TODO: This doesn;t look right - should be asking if the bit is set!!
//
if (tokenNames[bit])
{
ANTLR3_FPRINTF(stderr, "%s%s", count > 0 ? ", " : "", tokenNames[bit]);
count++;
}
}
ANTLR3_FPRINTF(stderr, "\n");
}
else
{
ANTLR3_FPRINTF(stderr, "Actually dude, we didn't seem to be expecting anything here, or at least\n");
ANTLR3_FPRINTF(stderr, "I could not work out what I was expecting, like so many of us these days!\n");
}
}
break;
case ANTLR3_EARLY_EXIT_EXCEPTION:
// We entered a loop requiring a number of token sequences
// but found a token that ended that sequence earlier than
// we should have done.
//
ANTLR3_FPRINTF(stderr, " : missing elements...\n");
break;
default:
// We don't handle any other exceptions here, but you can
// if you wish. If we get an exception that hits this point
// then we are just going to report what we know about the
// token.
//
ANTLR3_FPRINTF(stderr, " : syntax not recognized...\n");
break;
}
// Here you have the token that was in error which if this is
// the standard implementation will tell you the line and offset
// and also record the address of the start of the line in the
// input stream. You could therefore print the source line and so on.
// Generally though, I would expect that your lexer/parser will keep
// its own map of lines and source pointers or whatever as there
// are a lot of specific things you need to know about the input
// to do something like that.
// Here is where you do it though :-).
//
}
/// Return how many syntax errors were detected by this recognizer
///
static ANTLR3_UINT32
getNumberOfSyntaxErrors(pANTLR3_BASE_RECOGNIZER recognizer)
{
return recognizer->state->errorCount;
}
/// Recover from an error found on the input stream. Mostly this is
/// NoViableAlt exceptions, but could be a mismatched token that
/// the match() routine could not recover from.
///
static void
recover (pANTLR3_BASE_RECOGNIZER recognizer)
{
// Used to compute the follow set of tokens
//
pANTLR3_BITSET followSet;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function recover called by unknown parser type - provide override for this function\n");
return;
break;
}
// Are we about to repeat the same error?
//
if (recognizer->state->lastErrorIndex == is->index(is))
{
// The last error was at the same token index point. This must be a case
// where LT(1) is in the recovery token set so nothing is
// consumed. Consume a single token so at least to prevent
// an infinite loop; this is a failsafe.
//
is->consume(is);
}
// Record error index position
//
recognizer->state->lastErrorIndex = is->index(is);
// Work out the follows set for error recovery
//
followSet = recognizer->computeErrorRecoverySet(recognizer);
// Call resync hook (for debuggers and so on)
//
recognizer->beginResync(recognizer);
// Consume tokens until we have resynced to something in the follows set
//
recognizer->consumeUntilSet(recognizer, followSet);
// End resync hook
//
recognizer->endResync(recognizer);
// Destroy the temporary bitset we produced.
//
followSet->free(followSet);
// Reset the inError flag so we don't re-report the exception
//
recognizer->state->error = ANTLR3_FALSE;
recognizer->state->failed = ANTLR3_FALSE;
}
/// Attempt to recover from a single missing or extra token.
///
/// EXTRA TOKEN
///
/// LA(1) is not what we are looking for. If LA(2) has the right token,
/// however, then assume LA(1) is some extra spurious token. Delete it
/// and LA(2) as if we were doing a normal match(), which advances the
/// input.
///
/// MISSING TOKEN
///
/// If current token is consistent with what could come after
/// ttype then it is ok to "insert" the missing token, else throw
/// exception For example, Input "i=(3;" is clearly missing the
/// ')'. When the parser returns from the nested call to expr, it
/// will have call chain:
///
/// stat -> expr -> atom
///
/// and it will be trying to match the ')' at this point in the
/// derivation:
///
/// => ID '=' '(' INT ')' ('+' atom)* ';'
/// ^
/// match() will see that ';' doesn't match ')' and report a
/// mismatched token error. To recover, it sees that LA(1)==';'
/// is in the set of tokens that can follow the ')' token
/// reference in rule atom. It can assume that you forgot the ')'.
///
/// The exception that was passed in, in the java implementation is
/// sorted in the recognizer exception stack in the C version. To 'throw' it we set the
/// error flag and rules cascade back when this is set.
///
static void *
recoverFromMismatchedToken (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 ttype, pANTLR3_BITSET_LIST follow)
{
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
void * matchedSymbol;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function recoverFromMismatchedToken called by unknown parser type - provide override for this function\n");
return NULL;
break;
}
// Create an exception if we need one
//
if (recognizer->state->exception == NULL)
{
antlr3RecognitionExceptionNew(recognizer);
}
// If the next token after the one we are looking at in the input stream
// is what we are looking for then we remove the one we have discovered
// from the stream by consuming it, then consume this next one along too as
// if nothing had happened.
//
if ( recognizer->mismatchIsUnwantedToken(recognizer, is, ttype) == ANTLR3_TRUE)
{
recognizer->state->exception->type = ANTLR3_UNWANTED_TOKEN_EXCEPTION;
recognizer->state->exception->message = ANTLR3_UNWANTED_TOKEN_EXCEPTION_NAME;
// Call resync hook (for debuggers and so on)
//
if (recognizer->debugger != NULL)
{
recognizer->debugger->beginResync(recognizer->debugger);
}
// "delete" the extra token
//
recognizer->beginResync(recognizer);
is->consume(is);
recognizer->endResync(recognizer);
// End resync hook
//
if (recognizer->debugger != NULL)
{
recognizer->debugger->endResync(recognizer->debugger);
}
// Print out the error after we consume so that ANTLRWorks sees the
// token in the exception.
//
recognizer->reportError(recognizer);
// Return the token we are actually matching
//
matchedSymbol = recognizer->getCurrentInputSymbol(recognizer, is);
// Consume the token that the rule actually expected to get as if everything
// was hunky dory.
//
is->consume(is);
recognizer->state->error = ANTLR3_FALSE; // Exception is not outstanding any more
return matchedSymbol;
}
// Single token deletion (Unwanted above) did not work
// so we see if we can insert a token instead by calculating which
// token would be missing
//
if (mismatchIsMissingToken(recognizer, is, follow))
{
// We can fake the missing token and proceed
//
matchedSymbol = recognizer->getMissingSymbol(recognizer, is, recognizer->state->exception, ttype, follow);
recognizer->state->exception->type = ANTLR3_MISSING_TOKEN_EXCEPTION;
recognizer->state->exception->message = ANTLR3_MISSING_TOKEN_EXCEPTION_NAME;
recognizer->state->exception->token = matchedSymbol;
recognizer->state->exception->expecting = ttype;
// Print out the error after we insert so that ANTLRWorks sees the
// token in the exception.
//
recognizer->reportError(recognizer);
recognizer->state->error = ANTLR3_FALSE; // Exception is not outstanding any more
return matchedSymbol;
}
// Neither deleting nor inserting tokens allows recovery
// must just report the exception.
//
recognizer->state->error = ANTLR3_TRUE;
return NULL;
}
static void *
recoverFromMismatchedSet (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_BITSET_LIST follow)
{
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
pANTLR3_COMMON_TOKEN matchedSymbol;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function recoverFromMismatchedSet called by unknown parser type - provide override for this function\n");
return NULL;
break;
}
if (recognizer->mismatchIsMissingToken(recognizer, is, follow) == ANTLR3_TRUE)
{
// We can fake the missing token and proceed
//
matchedSymbol = recognizer->getMissingSymbol(recognizer, is, recognizer->state->exception, ANTLR3_TOKEN_INVALID, follow);
recognizer->state->exception->type = ANTLR3_MISSING_TOKEN_EXCEPTION;
recognizer->state->exception->token = matchedSymbol;
// Print out the error after we insert so that ANTLRWorks sees the
// token in the exception.
//
recognizer->reportError(recognizer);
recognizer->state->error = ANTLR3_FALSE; // Exception is not outstanding any more
return matchedSymbol;
}
// TODO - Single token deletion like in recoverFromMismatchedToken()
//
recognizer->state->error = ANTLR3_TRUE;
recognizer->state->failed = ANTLR3_TRUE;
return NULL;
}
/// This code is factored out from mismatched token and mismatched set
/// recovery. It handles "single token insertion" error recovery for
/// both. No tokens are consumed to recover from insertions. Return
/// true if recovery was possible else return false.
///
static ANTLR3_BOOLEAN
recoverFromMismatchedElement (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_BITSET_LIST followBits)
{
pANTLR3_BITSET viableToksFollowingRule;
pANTLR3_BITSET follow;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function recover called by unknown parser type - provide override for this function\n");
return ANTLR3_FALSE;
break;
}
follow = antlr3BitsetLoad(followBits);
if (follow == NULL)
{
/* The follow set is NULL, which means we don't know what can come
* next, so we "hit and hope" by just signifying that we cannot
* recover, which will just cause the next token to be consumed,
* which might dig us out.
*/
return ANTLR3_FALSE;
}
/* We have a bitmap for the follow set, hence we can compute
* what can follow this grammar element reference.
*/
if (follow->isMember(follow, ANTLR3_EOR_TOKEN_TYPE) == ANTLR3_TRUE)
{
/* First we need to know which of the available tokens are viable
* to follow this reference.
*/
viableToksFollowingRule = recognizer->computeCSRuleFollow(recognizer);
/* Remove the EOR token, which we do not wish to compute with
*/
follow->remove(follow, ANTLR3_EOR_TOKEN_TYPE);
viableToksFollowingRule->free(viableToksFollowingRule);
/* We now have the computed set of what can follow the current token
*/
}
/* We can now see if the current token works with the set of tokens
* that could follow the current grammar reference. If it looks like it
* is consistent, then we can "insert" that token by not throwing
* an exception and assuming that we saw it.
*/
if ( follow->isMember(follow, is->_LA(is, 1)) == ANTLR3_TRUE)
{
/* report the error, but don't cause any rules to abort and stuff
*/
recognizer->reportError(recognizer);
if (follow != NULL)
{
follow->free(follow);
}
recognizer->state->error = ANTLR3_FALSE;
recognizer->state->failed = ANTLR3_FALSE;
return ANTLR3_TRUE; /* Success in recovery */
}
if (follow != NULL)
{
follow->free(follow);
}
/* We could not find anything viable to do, so this is going to
* cause an exception.
*/
return ANTLR3_FALSE;
}
/// Eat tokens from the input stream until we get one of JUST the right type
///
static void
consumeUntil (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_UINT32 tokenType)
{
ANTLR3_UINT32 ttype;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'consumeUntil' called by unknown parser type - provide override for this function\n");
return;
break;
}
// What do have at the moment?
//
ttype = is->_LA(is, 1);
// Start eating tokens until we get to the one we want.
//
while (ttype != ANTLR3_TOKEN_EOF && ttype != tokenType)
{
is->consume(is);
ttype = is->_LA(is, 1);
}
}
/// Eat tokens from the input stream until we find one that
/// belongs to the supplied set.
///
static void
consumeUntilSet (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_BITSET set)
{
ANTLR3_UINT32 ttype;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'consumeUntilSet' called by unknown parser type - provide override for this function\n");
return;
break;
}
// What do have at the moment?
//
ttype = is->_LA(is, 1);
// Start eating tokens until we get to one we want.
//
while (ttype != ANTLR3_TOKEN_EOF && set->isMember(set, ttype) == ANTLR3_FALSE)
{
is->consume(is);
ttype = is->_LA(is, 1);
}
}
/** Return the rule invocation stack (how we got here in the parse.
* In the java version Ter just asks the JVM for all the information
* but in C we don't get this information, so I am going to do nothing
* right now.
*/
static pANTLR3_STACK
getRuleInvocationStack (pANTLR3_BASE_RECOGNIZER recognizer)
{
return NULL;
}
static pANTLR3_STACK
getRuleInvocationStackNamed (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_UINT8 name)
{
return NULL;
}
/** Convenience method for template rewrites - NYI.
*/
static pANTLR3_HASH_TABLE
toStrings (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_HASH_TABLE tokens)
{
return NULL;
}
static void ANTLR3_CDECL
freeIntTrie (void * trie)
{
((pANTLR3_INT_TRIE)trie)->free((pANTLR3_INT_TRIE)trie);
}
/** Pointer to a function to return whether the rule has parsed input starting at the supplied
* start index before. If the rule has not parsed input starting from the supplied start index,
* then it will return ANTLR3_MEMO_RULE_UNKNOWN. If it has parsed from the suppled start point
* then it will return the point where it last stopped parsing after that start point.
*
* \remark
* The rule memos are an ANTLR3_LIST of ANTLR3_LISTS, however if this becomes any kind of performance
* issue (it probably won't, the hash tables are pretty quick) then we could make a special int only
* version of the table.
*/
static ANTLR3_MARKER
getRuleMemoization (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_INTKEY ruleIndex, ANTLR3_MARKER ruleParseStart)
{
/* The rule memos are an ANTLR3_LIST of ANTLR3_LIST.
*/
pANTLR3_INT_TRIE ruleList;
ANTLR3_MARKER stopIndex;
pANTLR3_TRIE_ENTRY entry;
/* See if we have a list in the ruleMemos for this rule, and if not, then create one
* as we will need it eventually if we are being asked for the memo here.
*/
entry = recognizer->state->ruleMemo->get(recognizer->state->ruleMemo, (ANTLR3_INTKEY)ruleIndex);
if (entry == NULL)
{
/* Did not find it, so create a new one for it, with a bit depth based on the
* size of the input stream. We need the bit depth to incorporate the number if
* bits required to represent the largest possible stop index in the input, which is the
* last character. An int stream is free to return the largest 64 bit offset if it has
* no idea of the size, but you should remember that this will cause the leftmost
* bit match algorithm to run to 63 bits, which will be the whole time spent in the trie ;-)
*/
ruleList = antlr3IntTrieNew(63); /* Depth is theoretically 64 bits, but probably not ;-) */
if (ruleList != NULL)
{
recognizer->state->ruleMemo->add(recognizer->state->ruleMemo, (ANTLR3_INTKEY)ruleIndex, ANTLR3_HASH_TYPE_STR, 0, ANTLR3_FUNC_PTR(ruleList), freeIntTrie);
}
/* We cannot have a stopIndex in a trie we have just created of course
*/
return MEMO_RULE_UNKNOWN;
}
ruleList = (pANTLR3_INT_TRIE) (entry->data.ptr);
/* See if there is a stop index associated with the supplied start index.
*/
stopIndex = 0;
entry = ruleList->get(ruleList, ruleParseStart);
if (entry != NULL)
{
stopIndex = (ANTLR3_MARKER)(entry->data.intVal);
}
if (stopIndex == 0)
{
return MEMO_RULE_UNKNOWN;
}
return stopIndex;
}
/** Has this rule already parsed input at the current index in the
* input stream? Return ANTLR3_TRUE if we have and ANTLR3_FALSE
* if we have not.
*
* This method has a side-effect: if we have seen this input for
* this rule and successfully parsed before, then seek ahead to
* 1 past the stop token matched for this rule last time.
*/
static ANTLR3_BOOLEAN
alreadyParsedRule (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_MARKER ruleIndex)
{
ANTLR3_MARKER stopIndex;
pANTLR3_LEXER lexer;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
lexer = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
lexer = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
case ANTLR3_TYPE_LEXER:
lexer = (pANTLR3_LEXER) (recognizer->super);
parser = NULL;
tparser = NULL;
is = lexer->input->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'alreadyParsedRule' called by unknown parser type - provide override for this function\n");
return ANTLR3_FALSE;
break;
}
/* See if we have a memo marker for this.
*/
stopIndex = recognizer->getRuleMemoization(recognizer, ruleIndex, is->index(is));
if (stopIndex == MEMO_RULE_UNKNOWN)
{
return ANTLR3_FALSE;
}
if (stopIndex == MEMO_RULE_FAILED)
{
recognizer->state->failed = ANTLR3_TRUE;
}
else
{
is->seek(is, stopIndex+1);
}
/* If here then the rule was executed for this input already
*/
return ANTLR3_TRUE;
}
/** Record whether or not this rule parsed the input at this position
* successfully.
*/
static void
memoize (pANTLR3_BASE_RECOGNIZER recognizer, ANTLR3_MARKER ruleIndex, ANTLR3_MARKER ruleParseStart)
{
/* The rule memos are an ANTLR3_LIST of ANTLR3_LIST.
*/
pANTLR3_INT_TRIE ruleList;
pANTLR3_TRIE_ENTRY entry;
ANTLR3_MARKER stopIndex;
pANTLR3_LEXER lexer;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
case ANTLR3_TYPE_LEXER:
lexer = (pANTLR3_LEXER) (recognizer->super);
parser = NULL;
tparser = NULL;
is = lexer->input->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function consumeUntilSet called by unknown parser type - provide override for this function\n");
return;
break;
}
stopIndex = recognizer->state->failed == ANTLR3_TRUE ? MEMO_RULE_FAILED : is->index(is) - 1;
entry = recognizer->state->ruleMemo->get(recognizer->state->ruleMemo, (ANTLR3_INTKEY)ruleIndex);
if (entry != NULL)
{
ruleList = (pANTLR3_INT_TRIE)(entry->data.ptr);
/* If we don't already have this entry, append it. The memoize trie does not
* accept duplicates so it won't add it if already there and we just ignore the
* return code as we don't care if it is there already.
*/
ruleList->add(ruleList, ruleParseStart, ANTLR3_HASH_TYPE_INT, stopIndex, NULL, NULL);
}
}
/** A syntactic predicate. Returns true/false depending on whether
* the specified grammar fragment matches the current input stream.
* This resets the failed instance var afterwards.
*/
static ANTLR3_BOOLEAN
synpred (pANTLR3_BASE_RECOGNIZER recognizer, void * ctx, void (*predicate)(void * ctx))
{
ANTLR3_MARKER start;
pANTLR3_PARSER parser;
pANTLR3_TREE_PARSER tparser;
pANTLR3_INT_STREAM is;
switch (recognizer->type)
{
case ANTLR3_TYPE_PARSER:
parser = (pANTLR3_PARSER) (recognizer->super);
tparser = NULL;
is = parser->tstream->istream;
break;
case ANTLR3_TYPE_TREE_PARSER:
tparser = (pANTLR3_TREE_PARSER) (recognizer->super);
parser = NULL;
is = tparser->ctnstream->tnstream->istream;
break;
default:
ANTLR3_FPRINTF(stderr, "Base recognizer function 'synPred' called by unknown parser type - provide override for this function\n");
return ANTLR3_FALSE;
break;
}
/* Begin backtracking so we can get back to where we started after trying out
* the syntactic predicate.
*/
start = is->mark(is);
recognizer->state->backtracking++;
/* Try the syntactical predicate
*/
predicate(ctx);
/* Reset
*/
is->rewind(is, start);
recognizer->state->backtracking--;
if (recognizer->state->failed == ANTLR3_TRUE)
{
/* Predicate failed
*/
recognizer->state->failed = ANTLR3_FALSE;
return ANTLR3_FALSE;
}
else
{
/* Predicate was successful
*/
recognizer->state->failed = ANTLR3_FALSE;
return ANTLR3_TRUE;
}
}
static void
reset(pANTLR3_BASE_RECOGNIZER recognizer)
{
if (recognizer->state->following != NULL)
{
recognizer->state->following->free(recognizer->state->following);
}
// Reset the state flags
//
recognizer->state->errorRecovery = ANTLR3_FALSE;
recognizer->state->lastErrorIndex = -1;
recognizer->state->failed = ANTLR3_FALSE;
recognizer->state->errorCount = 0;
recognizer->state->backtracking = 0;
recognizer->state->following = NULL;
if (recognizer->state != NULL)
{
if (recognizer->state->ruleMemo != NULL)
{
recognizer->state->ruleMemo->free(recognizer->state->ruleMemo);
recognizer->state->ruleMemo = antlr3IntTrieNew(15); /* 16 bit depth is enough for 32768 rules! */
}
}
// Install a new following set
//
recognizer->state->following = antlr3StackNew(8);
}
// Default implementation is for parser and assumes a token stream as supplied by the runtime.
// You MAY need override this function if the standard TOKEN_STREAM is not what you are using.
//
static void *
getCurrentInputSymbol (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM istream)
{
return ((pANTLR3_TOKEN_STREAM)istream->super)->_LT((pANTLR3_TOKEN_STREAM)istream->super, 1);
}
// Default implementation is for parser and assumes a token stream as supplied by the runtime.
// You MAY need override this function if the standard COMMON_TOKEN_STREAM is not what you are using.
//
static void *
getMissingSymbol (pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM istream, pANTLR3_EXCEPTION e,
ANTLR3_UINT32 expectedTokenType, pANTLR3_BITSET_LIST follow)
{
pANTLR3_TOKEN_STREAM ts;
pANTLR3_COMMON_TOKEN_STREAM cts;
pANTLR3_COMMON_TOKEN token;
pANTLR3_COMMON_TOKEN current;
pANTLR3_STRING text;
// Dereference the standard pointers
//
ts = (pANTLR3_TOKEN_STREAM)istream->super;
cts = (pANTLR3_COMMON_TOKEN_STREAM)ts->super;
// Work out what to use as the current symbol to make a line and offset etc
// If we are at EOF, we use the token before EOF
//
current = ts->_LT(ts, 1);
if (current->getType(current) == ANTLR3_TOKEN_EOF)
{
current = ts->_LT(ts, -1);
}
// Create a new empty token
//
if (recognizer->state->tokFactory == NULL)
{
// We don't yet have a token factory for making tokens
// we just need a fake one using the input stream of the current
// token.
//
recognizer->state->tokFactory = antlr3TokenFactoryNew(current->input);
}
token = recognizer->state->tokFactory->newToken(recognizer->state->tokFactory);
// Set some of the token properties based on the current token
//
token->setLine (token, current->getLine(current));
token->setCharPositionInLine (token, current->getCharPositionInLine(current));
token->setChannel (token, ANTLR3_TOKEN_DEFAULT_CHANNEL);
token->setType (token, expectedTokenType);
token->user1 = current->user1;
token->user2 = current->user2;
token->user3 = current->user3;
token->custom = current->custom;
token->lineStart = current->lineStart;
// Create the token text that shows it has been inserted
//
token->setText8(token, (pANTLR3_UINT8)"<missing ");
text = token->getText(token);
if (text != NULL)
{
text->append8(text, (const char *)recognizer->state->tokenNames[expectedTokenType]);
text->append8(text, (const char *)">");
}
// Finally return the pointer to our new token
//
return token;
}
#ifdef ANTLR3_WINDOWS
#pragma warning( default : 4100 )
#endif
/// @}
///