runtime/Cpp/include/antlr3baserecognizer.hpp - platform/external/antlr - Git at Google

 /** \file
  * Defines the basic structure to support recognizing by either a lexer,
  * parser, or tree parser.
  * \addtogroup BaseRecognizer
  * @{
  */
 #ifndef	_ANTLR3_BASERECOGNIZER_HPP
 #define	_ANTLR3_BASERECOGNIZER_HPP

 // [The "BSD licence"]
 // Copyright (c) 2005-2009 Gokulakannan Somasundaram, ElectronDB

 //
 // 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.hpp"
 #include    "antlr3collections.hpp"

 ANTLR_BEGIN_NAMESPACE()

 /** \brief Base tracking context structure for all types of
  * recognizers.
  */
 template< class ImplTraits, class StreamType >
 class BaseRecognizer : public ImplTraits::AllocPolicyType
 {
 public:
 	typedef typename ImplTraits::AllocPolicyType	AllocPolicyType;
 	typedef typename StreamType::IntStreamType	IntStreamType;
 	typedef typename ComponentTypeFinder<ImplTraits, StreamType>::ComponentType  SuperType;
 	typedef typename StreamType::UnitType		UnitType;
 	typedef typename ImplTraits::template ExceptionBaseType<StreamType> ExceptionBaseType;
 	typedef typename ImplTraits::BitsetType BitsetType;
 	typedef typename ImplTraits::BitsetListType		BitsetListType;
 	typedef typename ImplTraits::StringType	StringType;
 	typedef typename ImplTraits::template RecognizerSharedStateType<StreamType>  RecognizerSharedStateType;
 	typedef typename ImplTraits::DebugEventListenerType DebugEventListenerType;
 	typedef typename ImplTraits::LexerType LexerType;
 	typedef typename ImplTraits::ParserType ParserType;
 	typedef typename ImplTraits::TreeParserType TreeParserType;

 	typedef typename AllocPolicyType::template StackType<StringType>  StringStackType;
 	typedef typename AllocPolicyType::template ListType<StringType>  StringListType;

 private:
 	/// A pointer to the shared recognizer state, such that multiple
 	/// recognizers can use the same inputs streams and so on (in
 	/// the case of grammar inheritance for instance.
 	///
 	RecognizerSharedStateType*		m_state;

 	/// If set to something other than NULL, then this structure is
 	/// points to an instance of the debugger interface. In general, the
 	/// debugger is only referenced internally in recovery/error operations
 	/// so that it does not cause overhead by having to check this pointer
 	/// in every function/method
 	///
 	DebugEventListenerType*		m_debugger;


 public:
 	BaseRecognizer(ANTLR_UINT32 sizeHint, RecognizerSharedStateType* state);

 	SuperType* get_super();
 	RecognizerSharedStateType* get_state() const;
 	DebugEventListenerType* get_debugger() const;
 	void  set_state( RecognizerSharedStateType* state );
 	void  set_debugger( DebugEventListenerType* debugger );

     /// 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.
 	///
     const UnitType*	match(ANTLR_UINT32 ttype, BitsetListType* follow);

 	/// Consumes the next token, whatever it is, and resets the recognizer state
 	/// so that it is not in error.
 	///
 	/// \param recognizer
 	/// Recognizer context pointer
 	///
     void	matchAny();

 	/// function that decides if the token ahead of the current one is the
 	/// one we were loking for, in which case the curernt one is very likely extraneous
 	/// and can be reported that way.
 	///
 	bool mismatchIsUnwantedToken(IntStreamType* input, ANTLR_UINT32 ttype);

 	/// function that decides if the current token is one that can logically
 	/// follow the one we were looking for, in which case the one we were looking for is
 	/// probably missing from the input.
 	///
 	bool mismatchIsMissingToken(IntStreamType* input, BitsetListType* follow);

     /// 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.
 	///
     void mismatch(ANTLR_UINT32 ttype, BitsetListType* follow);

     /// 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.
 	///
     void	reportError();
 	void	reportError( ClassForwarder<LexerType> );
 	template<typename CompType>
 	void	reportError( ClassForwarder<CompType> );

     /** Function that is called to display a recognition error message. You may
      *  override this function independently of (*reportError)() above as that function calls
      *  this one to do the actual exception printing.
      */
     void	displayRecognitionError(ANTLR_UINT8** tokenNames);

 	/// Get number of recognition errors (lexer, parser, tree parser).  Each
 	/// recognizer tracks its own number.  So parser and lexer each have
 	/// separate count.  Does not count the spurious errors found between
 	/// an error and next valid token match
 	///
 	/// \see reportError()
 	///
 	ANTLR_UINT32 getNumberOfSyntaxErrors();

     /** Function that recovers from an error found in the input stream.
      *  Generally, this will be a #ANTLR3_EXCEPTION_NOVIABLE_ALT but it could also
      *  be from a mismatched token that the (*match)() could not recover from.
      */
     void	recover();

     /** function that is a hook to listen to token consumption during error recovery.
      *  This is mainly used by the debug parser to send events to the listener.
      */
     void	beginResync();

     /** function that is a hook to listen to token consumption during error recovery.
      *  This is mainly used by the debug parser to send events to the listener.
      */
     void	endResync();

 	/** function that is a hook to listen to token consumption during error recovery.
      *  This is mainly used by the debug parser to send events to the listener.
      */
     void	beginBacktrack(ANTLR_UINT32 level);

     /** function that is a hook to listen to token consumption during error recovery.
      *  This is mainly used by the debug parser to send events to the listener.
      */
     void	endBacktrack(ANTLR_UINT32 level, bool successful);

     /// 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.
 	///
     BitsetType*	computeErrorRecoverySet();

     /// 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.
 	///
     BitsetType*	computeCSRuleFollow();

     /// Compute the current followset for the input stream.
 	///
     BitsetType*	combineFollows(bool exact);

     /// 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.
 	///
     const UnitType* recoverFromMismatchedToken( ANTLR_UINT32	ttype, BitsetListType*	follow);

     /** Function that recovers from a mismatched set in the token stream, in a similar manner
      *  to (*recoverFromMismatchedToken)
      */
     const UnitType* recoverFromMismatchedSet(BitsetListType*	follow);

     /** common routine to handle single token insertion for recovery functions.
      */
 	/// 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.
 	///
     bool	recoverFromMismatchedElement(BitsetListType*	follow);

     /** function that consumes input until the next token matches
      *  the given token.
      */
     void	consumeUntil(ANTLR_UINT32   tokenType);

     /** function that consumes input until the next token matches
      *  one in the given set.
      */
     void	consumeUntilSet(BitsetType*	set);

     /** function that returns an ANTLR3_LIST of the strings that identify
      *  the rules in the parser that got you to this point. Can be overridden by installing your
      *	own function set.
      *
      * \todo Document how to override invocation stack functions.
      */
 	StringStackType	getRuleInvocationStack();
 	StringStackType	getRuleInvocationStackNamed(ANTLR_UINT8*    name);

     /** function that converts an ANLR3_LIST of tokens to an ANTLR3_LIST of
      *  string token names. As this is mostly used in string template processing it may not be useful
      *  in the C runtime.
      */
     StringListType	toStrings( const StringListType& );

     /** 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.
      */
     ANTLR_MARKER	getRuleMemoization( ANTLR_INTKEY	ruleIndex,
 												ANTLR_MARKER	ruleParseStart);

     /** function that determines whether the rule has parsed input at the current index
      *  in the input stream
      */
     bool	alreadyParsedRule(ANTLR_MARKER	ruleIndex);

     /** Function that records whether the rule has parsed the input at a
      *  current position successfully or not.
      */
     void	memoize(ANTLR_MARKER	ruleIndex,
 								ANTLR_MARKER	ruleParseStart);

 	/// Function that returns the current input symbol.
     /// The is placed into any label for the associated token ref; e.g., x=ID.  Token
 	/// and tree parsers need to return different objects. Rather than test
 	/// for input stream type or change the IntStream interface, I use
 	/// a simple method to ask the recognizer to tell me what the current
 	/// input symbol is.
 	///
 	/// This is ignored for lexers and the lexer implementation of this
 	/// function should return NULL.
 	///
 	const UnitType*	getCurrentInputSymbol(IntStreamType* istream);
 	const UnitType*	getCurrentInputSymbol(IntStreamType* istream, ClassForwarder<LexerType>);
 	const UnitType*	getCurrentInputSymbol(IntStreamType* istream, ClassForwarder<ParserType>);
 	const UnitType*	getCurrentInputSymbol(IntStreamType* istream, ClassForwarder<TreeParserType>);

 	/// Conjure up a missing token during error recovery.
 	///
 	/// The recognizer attempts to recover from single missing
 	/// symbols. But, actions might refer to that missing symbol.
 	/// For example, x=ID {f($x);}. The action clearly assumes
 	/// that there has been an identifier matched previously and that
 	/// $x points at that token. If that token is missing, but
 	/// the next token in the stream is what we want we assume that
 	/// this token is missing and we keep going. Because we
 	/// have to return some token to replace the missing token,
 	/// we have to conjure one up. This method gives the user control
 	/// over the tokens returned for missing tokens. Mostly,
 	/// you will want to create something special for identifier
 	/// tokens. For literals such as '{' and ',', the default
 	/// action in the parser or tree parser works. It simply creates
 	/// a CommonToken of the appropriate type. The text will be the token.
 	/// If you change what tokens must be created by the lexer,
 	/// override this method to create the appropriate tokens.
 	///
 	UnitType*	getMissingSymbol( IntStreamType*		istream, ExceptionBaseType*		e,
 												ANTLR_UINT32			expectedTokenType,
 												BitsetListType*		follow);

     /** Function that returns whether the supplied grammar function
      *  will parse the current input stream or not. This is the way that syntactic
      *  predicates are evaluated. Unlike java, C is perfectly happy to invoke code
      *  via a pointer to a function (hence that's what all the ANTLR3 C interfaces
      *  do.
      */
 	template<typename Predicate>
     bool  synpred( ClassForwarder<Predicate> );

 	//In place of exConstruct, just directly instantiate the Exception Object

     /** Reset the recognizer
      */
     void  reset();
 	void  reset( ClassForwarder<LexerType> );
 	template<typename CompType>
 	void  reset( ClassForwarder<CompType> );

 	void exConstruct();

     ~BaseRecognizer();

 };

 ANTLR_END_NAMESPACE()

 #include "antlr3baserecognizer.inl"

 /// @}
 ///

 #endif	    /* _ANTLR3_BASERECOGNIZER_H	*/
	/** \file
	* Defines the basic structure to support recognizing by either a lexer,
	* parser, or tree parser.
	* \addtogroup BaseRecognizer
	* @{
	*/
	#ifndef _ANTLR3_BASERECOGNIZER_HPP
	#define _ANTLR3_BASERECOGNIZER_HPP

	// [The "BSD licence"]
	// Copyright (c) 2005-2009 Gokulakannan Somasundaram, ElectronDB

	//
	// 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.hpp"
	#include "antlr3collections.hpp"

	ANTLR_BEGIN_NAMESPACE()

	/** \brief Base tracking context structure for all types of
	* recognizers.
	*/
	template< class ImplTraits, class StreamType >
	class BaseRecognizer : public ImplTraits::AllocPolicyType
	{
	public:
	typedef typename ImplTraits::AllocPolicyType AllocPolicyType;
	typedef typename StreamType::IntStreamType IntStreamType;
	typedef typename ComponentTypeFinder<ImplTraits, StreamType>::ComponentType SuperType;
	typedef typename StreamType::UnitType UnitType;
	typedef typename ImplTraits::template ExceptionBaseType<StreamType> ExceptionBaseType;
	typedef typename ImplTraits::BitsetType BitsetType;
	typedef typename ImplTraits::BitsetListType BitsetListType;
	typedef typename ImplTraits::StringType StringType;
	typedef typename ImplTraits::template RecognizerSharedStateType<StreamType> RecognizerSharedStateType;
	typedef typename ImplTraits::DebugEventListenerType DebugEventListenerType;
	typedef typename ImplTraits::LexerType LexerType;
	typedef typename ImplTraits::ParserType ParserType;
	typedef typename ImplTraits::TreeParserType TreeParserType;

	typedef typename AllocPolicyType::template StackType<StringType> StringStackType;
	typedef typename AllocPolicyType::template ListType<StringType> StringListType;

	private:
	/// A pointer to the shared recognizer state, such that multiple
	/// recognizers can use the same inputs streams and so on (in
	/// the case of grammar inheritance for instance.
	///
	RecognizerSharedStateType* m_state;

	/// If set to something other than NULL, then this structure is
	/// points to an instance of the debugger interface. In general, the
	/// debugger is only referenced internally in recovery/error operations
	/// so that it does not cause overhead by having to check this pointer
	/// in every function/method
	///
	DebugEventListenerType* m_debugger;


	public:
	BaseRecognizer(ANTLR_UINT32 sizeHint, RecognizerSharedStateType* state);

	SuperType* get_super();
	RecognizerSharedStateType* get_state() const;
	DebugEventListenerType* get_debugger() const;
	void set_state( RecognizerSharedStateType* state );
	void set_debugger( DebugEventListenerType* debugger );

	/// 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.
	///
	const UnitType* match(ANTLR_UINT32 ttype, BitsetListType* follow);

	/// Consumes the next token, whatever it is, and resets the recognizer state
	/// so that it is not in error.
	///
	/// \param recognizer
	/// Recognizer context pointer
	///
	void matchAny();

	/// function that decides if the token ahead of the current one is the
	/// one we were loking for, in which case the curernt one is very likely extraneous
	/// and can be reported that way.
	///
	bool mismatchIsUnwantedToken(IntStreamType* input, ANTLR_UINT32 ttype);

	/// function that decides if the current token is one that can logically
	/// follow the one we were looking for, in which case the one we were looking for is
	/// probably missing from the input.
	///
	bool mismatchIsMissingToken(IntStreamType* input, BitsetListType* follow);

	/// 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.
	///
	void mismatch(ANTLR_UINT32 ttype, BitsetListType* follow);

	/// 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.
	///
	void reportError();
	void reportError( ClassForwarder<LexerType> );
	template<typename CompType>
	void reportError( ClassForwarder<CompType> );

	/** Function that is called to display a recognition error message. You may
	* override this function independently of (*reportError)() above as that function calls
	* this one to do the actual exception printing.
	*/
	void displayRecognitionError(ANTLR_UINT8** tokenNames);

	/// Get number of recognition errors (lexer, parser, tree parser). Each
	/// recognizer tracks its own number. So parser and lexer each have
	/// separate count. Does not count the spurious errors found between
	/// an error and next valid token match
	///
	/// \see reportError()
	///
	ANTLR_UINT32 getNumberOfSyntaxErrors();

	/** Function that recovers from an error found in the input stream.
	* Generally, this will be a #ANTLR3_EXCEPTION_NOVIABLE_ALT but it could also
	* be from a mismatched token that the (*match)() could not recover from.
	*/
	void recover();

	/** function that is a hook to listen to token consumption during error recovery.
	* This is mainly used by the debug parser to send events to the listener.
	*/
	void beginResync();

	/** function that is a hook to listen to token consumption during error recovery.
	* This is mainly used by the debug parser to send events to the listener.
	*/
	void endResync();

	/** function that is a hook to listen to token consumption during error recovery.
	* This is mainly used by the debug parser to send events to the listener.
	*/
	void beginBacktrack(ANTLR_UINT32 level);

	/** function that is a hook to listen to token consumption during error recovery.
	* This is mainly used by the debug parser to send events to the listener.
	*/
	void endBacktrack(ANTLR_UINT32 level, bool successful);

	/// 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.
	///
	BitsetType* computeErrorRecoverySet();

	/// 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.
	///
	BitsetType* computeCSRuleFollow();

	/// Compute the current followset for the input stream.
	///
	BitsetType* combineFollows(bool exact);

	/// 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.
	///
	const UnitType* recoverFromMismatchedToken( ANTLR_UINT32 ttype, BitsetListType* follow);

	/** Function that recovers from a mismatched set in the token stream, in a similar manner
	* to (*recoverFromMismatchedToken)
	*/
	const UnitType* recoverFromMismatchedSet(BitsetListType* follow);

	/** common routine to handle single token insertion for recovery functions.
	*/
	/// 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.
	///
	bool recoverFromMismatchedElement(BitsetListType* follow);

	/** function that consumes input until the next token matches
	* the given token.
	*/
	void consumeUntil(ANTLR_UINT32 tokenType);

	/** function that consumes input until the next token matches
	* one in the given set.
	*/
	void consumeUntilSet(BitsetType* set);

	/** function that returns an ANTLR3_LIST of the strings that identify
	* the rules in the parser that got you to this point. Can be overridden by installing your
	* own function set.
	*
	* \todo Document how to override invocation stack functions.
	*/
	StringStackType getRuleInvocationStack();
	StringStackType getRuleInvocationStackNamed(ANTLR_UINT8* name);

	/** function that converts an ANLR3_LIST of tokens to an ANTLR3_LIST of
	* string token names. As this is mostly used in string template processing it may not be useful
	* in the C runtime.
	*/
	StringListType toStrings( const StringListType& );

	/** 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.
	*/
	ANTLR_MARKER getRuleMemoization( ANTLR_INTKEY ruleIndex,
	ANTLR_MARKER ruleParseStart);

	/** function that determines whether the rule has parsed input at the current index
	* in the input stream
	*/
	bool alreadyParsedRule(ANTLR_MARKER ruleIndex);

	/** Function that records whether the rule has parsed the input at a
	* current position successfully or not.
	*/
	void memoize(ANTLR_MARKER ruleIndex,
	ANTLR_MARKER ruleParseStart);

	/// Function that returns the current input symbol.
	/// The is placed into any label for the associated token ref; e.g., x=ID. Token
	/// and tree parsers need to return different objects. Rather than test
	/// for input stream type or change the IntStream interface, I use
	/// a simple method to ask the recognizer to tell me what the current
	/// input symbol is.
	///
	/// This is ignored for lexers and the lexer implementation of this
	/// function should return NULL.
	///
	const UnitType* getCurrentInputSymbol(IntStreamType* istream);
	const UnitType* getCurrentInputSymbol(IntStreamType* istream, ClassForwarder<LexerType>);
	const UnitType* getCurrentInputSymbol(IntStreamType* istream, ClassForwarder<ParserType>);
	const UnitType* getCurrentInputSymbol(IntStreamType* istream, ClassForwarder<TreeParserType>);

	/// Conjure up a missing token during error recovery.
	///
	/// The recognizer attempts to recover from single missing
	/// symbols. But, actions might refer to that missing symbol.
	/// For example, x=ID {f($x);}. The action clearly assumes
	/// that there has been an identifier matched previously and that
	/// $x points at that token. If that token is missing, but
	/// the next token in the stream is what we want we assume that
	/// this token is missing and we keep going. Because we
	/// have to return some token to replace the missing token,
	/// we have to conjure one up. This method gives the user control
	/// over the tokens returned for missing tokens. Mostly,
	/// you will want to create something special for identifier
	/// tokens. For literals such as '{' and ',', the default
	/// action in the parser or tree parser works. It simply creates
	/// a CommonToken of the appropriate type. The text will be the token.
	/// If you change what tokens must be created by the lexer,
	/// override this method to create the appropriate tokens.
	///
	UnitType* getMissingSymbol( IntStreamType* istream, ExceptionBaseType* e,
	ANTLR_UINT32 expectedTokenType,
	BitsetListType* follow);

	/** Function that returns whether the supplied grammar function
	* will parse the current input stream or not. This is the way that syntactic
	* predicates are evaluated. Unlike java, C is perfectly happy to invoke code
	* via a pointer to a function (hence that's what all the ANTLR3 C interfaces
	* do.
	*/
	template<typename Predicate>
	bool synpred( ClassForwarder<Predicate> );

	//In place of exConstruct, just directly instantiate the Exception Object

	/** Reset the recognizer
	*/
	void reset();
	void reset( ClassForwarder<LexerType> );
	template<typename CompType>
	void reset( ClassForwarder<CompType> );

	void exConstruct();

	~BaseRecognizer();

	};

	ANTLR_END_NAMESPACE()

	#include "antlr3baserecognizer.inl"

	/// @}
	///

	#endif /* _ANTLR3_BASERECOGNIZER_H */