xref: /aosp_15_r20/external/antlr/runtime/Cpp/include/antlr3baserecognizer.hpp (revision 16467b971bd3e2009fad32dd79016f2c7e421deb)

/** \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	*/