/Users/parrt/antlr/code/antlr/main/runtime/Java/src/org/antlr/runtime/BaseRecognizer.java

Go to the documentation of this file.

/*
 [The "BSD licence"]
 Copyright (c) 2005-2008 Terence Parr
 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.
*/
package org.antlr.runtime;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public abstract class BaseRecognizer {
        public static final int MEMO_RULE_FAILED = -2;
        public static final int MEMO_RULE_UNKNOWN = -1;
        public static final int INITIAL_FOLLOW_STACK_SIZE = 100;

        // copies from Token object for convenience in actions
        public static final int DEFAULT_TOKEN_CHANNEL = Token.DEFAULT_CHANNEL;
        public static final int HIDDEN = Token.HIDDEN_CHANNEL;

        public static final String NEXT_TOKEN_RULE_NAME = "nextToken";

        protected RecognizerSharedState state;

        public BaseRecognizer() {
                state = new RecognizerSharedState();
        }

        public BaseRecognizer(RecognizerSharedState state) {
                if ( state==null ) {
                        state = new RecognizerSharedState();
                }
                this.state = state;
        }

        public void reset() {
                // wack everything related to error recovery
                if ( state==null ) {
                        return; // no shared state work to do
                }
                state._fsp = -1;
                state.errorRecovery = false;
                state.lastErrorIndex = -1;
                state.failed = false;
                state.syntaxErrors = 0;
                // wack everything related to backtracking and memoization
                state.backtracking = 0;
                for (int i = 0; state.ruleMemo!=null && i < state.ruleMemo.length; i++) { // wipe cache
                        state.ruleMemo[i] = null;
                }
        }


        public Object match(IntStream input, int ttype, BitSet follow)
                throws RecognitionException
        {
                //System.out.println("match "+((TokenStream)input).LT(1));
                Object matchedSymbol = getCurrentInputSymbol(input);
                if ( input.LA(1)==ttype ) {
                        input.consume();
                        state.errorRecovery = false;
                        state.failed = false;
                        return matchedSymbol;
                }
                if ( state.backtracking>0 ) {
                        state.failed = true;
                        return matchedSymbol;
                }
                matchedSymbol = recoverFromMismatchedToken(input, ttype, follow);
                return matchedSymbol;
        }

        public void matchAny(IntStream input) {
                state.errorRecovery = false;
                state.failed = false;
                input.consume();
        }

        public boolean mismatchIsUnwantedToken(IntStream input, int ttype) {
                return input.LA(2)==ttype;
        }

        public boolean mismatchIsMissingToken(IntStream input, BitSet follow) {
                if ( follow==null ) {
                        // we have no information about the follow; we can only consume
                        // a single token and hope for the best
                        return false;
                }
                // compute what can follow this grammar element reference
                if ( follow.member(Token.EOR_TOKEN_TYPE) ) {
                        BitSet viableTokensFollowingThisRule = computeContextSensitiveRuleFOLLOW();
                        follow = follow.or(viableTokensFollowingThisRule);
            if ( state._fsp>=0 ) { // remove EOR if we're not the start symbol
                follow.remove(Token.EOR_TOKEN_TYPE);
            }
                }
                // 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

                //System.out.println("viable tokens="+follow.toString(getTokenNames()));
                //System.out.println("LT(1)="+((TokenStream)input).LT(1));

                // 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 ( follow.member(input.LA(1)) || follow.member(Token.EOR_TOKEN_TYPE) ) {
                        //System.out.println("LT(1)=="+((TokenStream)input).LT(1)+" is consistent with what follows; inserting...");
                        return true;
                }
                return false;
        }

        protected void mismatch(IntStream input, int ttype, BitSet follow)
                throws RecognitionException
        {
                if ( mismatchIsUnwantedToken(input, ttype) ) {
                        throw new UnwantedTokenException(ttype, input);
                }
                else if ( mismatchIsMissingToken(input, follow) ) {
                        throw new MissingTokenException(ttype, input, null);
                }
                throw new MismatchedTokenException(ttype, input);
        }

        public void reportError(RecognitionException e) {
                // if we've already reported an error and have not matched a token
                // yet successfully, don't report any errors.
                if ( state.errorRecovery ) {
                        //System.err.print("[SPURIOUS] ");
                        return;
                }
                state.syntaxErrors++; // don't count spurious
                state.errorRecovery = true;

                displayRecognitionError(this.getTokenNames(), e);
        }

        public void displayRecognitionError(String[] tokenNames,
                                                                                RecognitionException e)
        {
                String hdr = getErrorHeader(e);
                String msg = getErrorMessage(e, tokenNames);
                emitErrorMessage(hdr+" "+msg);
        }

        public String getErrorMessage(RecognitionException e, String[] tokenNames) {
                String msg = e.getMessage();
                if ( e instanceof UnwantedTokenException ) {
                        UnwantedTokenException ute = (UnwantedTokenException)e;
                        String tokenName="<unknown>";
                        if ( ute.expecting== Token.EOF ) {
                                tokenName = "EOF";
                        }
                        else {
                                tokenName = tokenNames[ute.expecting];
                        }
                        msg = "extraneous input "+getTokenErrorDisplay(ute.getUnexpectedToken())+
                                " expecting "+tokenName;
                }
                else if ( e instanceof MissingTokenException ) {
                        MissingTokenException mte = (MissingTokenException)e;
                        String tokenName="<unknown>";
                        if ( mte.expecting== Token.EOF ) {
                                tokenName = "EOF";
                        }
                        else {
                                tokenName = tokenNames[mte.expecting];
                        }
                        msg = "missing "+tokenName+" at "+getTokenErrorDisplay(e.token);
                }
                else if ( e instanceof MismatchedTokenException ) {
                        MismatchedTokenException mte = (MismatchedTokenException)e;
                        String tokenName="<unknown>";
                        if ( mte.expecting== Token.EOF ) {
                                tokenName = "EOF";
                        }
                        else {
                                tokenName = tokenNames[mte.expecting];
                        }
                        msg = "mismatched input "+getTokenErrorDisplay(e.token)+
                                " expecting "+tokenName;
                }
                else if ( e instanceof MismatchedTreeNodeException ) {
                        MismatchedTreeNodeException mtne = (MismatchedTreeNodeException)e;
                        String tokenName="<unknown>";
                        if ( mtne.expecting==Token.EOF ) {
                                tokenName = "EOF";
                        }
                        else {
                                tokenName = tokenNames[mtne.expecting];
                        }
                        msg = "mismatched tree node: "+mtne.node+
                                " expecting "+tokenName;
                }
                else if ( e instanceof NoViableAltException ) {
                        NoViableAltException nvae = (NoViableAltException)e;
                        // for development, can add "decision=<<"+nvae.grammarDecisionDescription+">>"
                        // and "(decision="+nvae.decisionNumber+") and
                        // "state "+nvae.stateNumber
                        msg = "no viable alternative at input "+getTokenErrorDisplay(e.token);
                }
                else if ( e instanceof EarlyExitException ) {
                        EarlyExitException eee = (EarlyExitException)e;
                        // for development, can add "(decision="+eee.decisionNumber+")"
                        msg = "required (...)+ loop did not match anything at input "+
                                getTokenErrorDisplay(e.token);
                }
                else if ( e instanceof MismatchedSetException ) {
                        MismatchedSetException mse = (MismatchedSetException)e;
                        msg = "mismatched input "+getTokenErrorDisplay(e.token)+
                                " expecting set "+mse.expecting;
                }
                else if ( e instanceof MismatchedNotSetException ) {
                        MismatchedNotSetException mse = (MismatchedNotSetException)e;
                        msg = "mismatched input "+getTokenErrorDisplay(e.token)+
                                " expecting set "+mse.expecting;
                }
                else if ( e instanceof FailedPredicateException ) {
                        FailedPredicateException fpe = (FailedPredicateException)e;
                        msg = "rule "+fpe.ruleName+" failed predicate: {"+
                                fpe.predicateText+"}?";
                }
                return msg;
        }

        public int getNumberOfSyntaxErrors() {
                return state.syntaxErrors;
        }

        public String getErrorHeader(RecognitionException e) {
                return "line "+e.line+":"+e.charPositionInLine;
        }

        public String getTokenErrorDisplay(Token t) {
                String s = t.getText();
                if ( s==null ) {
                        if ( t.getType()==Token.EOF ) {
                                s = "<EOF>";
                        }
                        else {
                                s = "<"+t.getType()+">";
                        }
                }
                s = s.replaceAll("\n","\\\\n");
                s = s.replaceAll("\r","\\\\r");
                s = s.replaceAll("\t","\\\\t");
                return "'"+s+"'";
        }

        public void emitErrorMessage(String msg) {
                System.err.println(msg);
        }

        public void recover(IntStream input, RecognitionException re) {
                if ( state.lastErrorIndex==input.index() ) {
                        // uh oh, another error at same token index; 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.
                        input.consume();
                }
                state.lastErrorIndex = input.index();
                BitSet followSet = computeErrorRecoverySet();
                beginResync();
                consumeUntil(input, followSet);
                endResync();
        }

        public void beginResync() {
        }

        public void endResync() {
        }

        /*  Compute the error recovery set for the current rule.  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 cna 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.
         */
        protected BitSet computeErrorRecoverySet() {
                return combineFollows(false);
        }

        protected BitSet computeContextSensitiveRuleFOLLOW() {
                return combineFollows(true);
        }

        protected BitSet combineFollows(boolean exact) {
                int top = state._fsp;
                BitSet followSet = new BitSet();
                for (int i=top; i>=0; i--) {
                        BitSet localFollowSet = (BitSet)state.following[i];
                        /*
                        System.out.println("local follow depth "+i+"="+
                                                           localFollowSet.toString(getTokenNames())+")");
                         */
                        followSet.orInPlace(localFollowSet);
                        if ( exact ) {
                                // can we see end of rule?
                                if ( localFollowSet.member(Token.EOR_TOKEN_TYPE) ) {
                                        // Only leave EOR in set if at top (start rule); this lets
                                        // us know if have to include follow(start rule); i.e., EOF
                                        if ( i>0 ) {
                                                followSet.remove(Token.EOR_TOKEN_TYPE);
                                        }
                                }
                                else { // can't see end of rule, quit
                                        break;
                                }
                        }
                }
                return followSet;
        }

        protected Object recoverFromMismatchedToken(IntStream input, int ttype, BitSet follow)
                throws RecognitionException
        {
                RecognitionException e = null;
                // if next token is what we are looking for then "delete" this token
                if ( mismatchIsUnwantedToken(input, ttype) ) {
                        e = new UnwantedTokenException(ttype, input);
                        /*
                        System.err.println("recoverFromMismatchedToken deleting "+
                                                           ((TokenStream)input).LT(1)+
                                                           " since "+((TokenStream)input).LT(2)+" is what we want");
                         */
                        beginResync();
                        input.consume(); // simply delete extra token
                        endResync();
                        reportError(e);  // report after consuming so AW sees the token in the exception
                        // we want to return the token we're actually matching
                        Object matchedSymbol = getCurrentInputSymbol(input);
                        input.consume(); // move past ttype token as if all were ok
                        return matchedSymbol;
                }
                // can't recover with single token deletion, try insertion
                if ( mismatchIsMissingToken(input, follow) ) {
                        Object inserted = getMissingSymbol(input, e, ttype, follow);
                        e = new MissingTokenException(ttype, input, inserted);
                        reportError(e);  // report after inserting so AW sees the token in the exception
                        return inserted;
                }
                // even that didn't work; must throw the exception
                e = new MismatchedTokenException(ttype, input);
                throw e;
        }

        public Object recoverFromMismatchedSet(IntStream input,
                                                                                   RecognitionException e,
                                                                                   BitSet follow)
                throws RecognitionException
        {
                if ( mismatchIsMissingToken(input, follow) ) {
                        // System.out.println("missing token");
                        reportError(e);
                        // we don't know how to conjure up a token for sets yet
                        return getMissingSymbol(input, e, Token.INVALID_TOKEN_TYPE, follow);
                }
                // TODO do single token deletion like above for Token mismatch
                throw e;
        }

        protected Object getCurrentInputSymbol(IntStream input) { return null; }

        protected Object getMissingSymbol(IntStream input,
                                                                          RecognitionException e,
                                                                          int expectedTokenType,
                                                                          BitSet follow)
        {
                return null;
        }

        public void consumeUntil(IntStream input, int tokenType) {
                //System.out.println("consumeUntil "+tokenType);
                int ttype = input.LA(1);
                while (ttype != Token.EOF && ttype != tokenType) {
                        input.consume();
                        ttype = input.LA(1);
                }
        }

        public void consumeUntil(IntStream input, BitSet set) {
                //System.out.println("consumeUntil("+set.toString(getTokenNames())+")");
                int ttype = input.LA(1);
                while (ttype != Token.EOF && !set.member(ttype) ) {
                        //System.out.println("consume during recover LA(1)="+getTokenNames()[input.LA(1)]);
                        input.consume();
                        ttype = input.LA(1);
                }
        }

        protected void pushFollow(BitSet fset) {
                if ( (state._fsp +1)>=state.following.length ) {
                        BitSet[] f = new BitSet[state.following.length*2];
                        System.arraycopy(state.following, 0, f, 0, state.following.length);
                        state.following = f;
                }
                state.following[++state._fsp] = fset;
        }

        public List getRuleInvocationStack() {
                String parserClassName = getClass().getName();
                return getRuleInvocationStack(new Throwable(), parserClassName);
        }

        public static List getRuleInvocationStack(Throwable e,
                                                                                          String recognizerClassName)
        {
                List rules = new ArrayList();
                StackTraceElement[] stack = e.getStackTrace();
                int i = 0;
                for (i=stack.length-1; i>=0; i--) {
                        StackTraceElement t = stack[i];
                        if ( t.getClassName().startsWith("org.antlr.runtime.") ) {
                                continue; // skip support code such as this method
                        }
                        if ( t.getMethodName().equals(NEXT_TOKEN_RULE_NAME) ) {
                                continue;
                        }
                        if ( !t.getClassName().equals(recognizerClassName) ) {
                                continue; // must not be part of this parser
                        }
            rules.add(t.getMethodName());
                }
                return rules;
        }

        public int getBacktrackingLevel() {
                return state.backtracking;
        }

        public String[] getTokenNames() {
                return null;
        }

        public String getGrammarFileName() {
                return null;
        }

        public abstract String getSourceName();

        public List toStrings(List tokens) {
                if ( tokens==null ) return null;
                List strings = new ArrayList(tokens.size());
                for (int i=0; i<tokens.size(); i++) {
                        strings.add(((Token)tokens.get(i)).getText());
                }
                return strings;
        }

        public int getRuleMemoization(int ruleIndex, int ruleStartIndex) {
                if ( state.ruleMemo[ruleIndex]==null ) {
                        state.ruleMemo[ruleIndex] = new HashMap();
                }
                Integer stopIndexI =
                        (Integer)state.ruleMemo[ruleIndex].get(new Integer(ruleStartIndex));
                if ( stopIndexI==null ) {
                        return MEMO_RULE_UNKNOWN;
                }
                return stopIndexI.intValue();
        }

        public boolean alreadyParsedRule(IntStream input, int ruleIndex) {
                int stopIndex = getRuleMemoization(ruleIndex, input.index());
                if ( stopIndex==MEMO_RULE_UNKNOWN ) {
                        return false;
                }
                if ( stopIndex==MEMO_RULE_FAILED ) {
                        //System.out.println("rule "+ruleIndex+" will never succeed");
                        state.failed=true;
                }
                else {
                        //System.out.println("seen rule "+ruleIndex+" before; skipping ahead to @"+(stopIndex+1)+" failed="+state.failed);
                        input.seek(stopIndex+1); // jump to one past stop token
                }
                return true;
        }

        public void memoize(IntStream input,
                                                int ruleIndex,
                                                int ruleStartIndex)
        {
                int stopTokenIndex = state.failed?MEMO_RULE_FAILED:input.index()-1;
                if ( state.ruleMemo==null ) {
                        System.err.println("!!!!!!!!! memo array is null for "+ getGrammarFileName());
                }
                if ( ruleIndex >= state.ruleMemo.length ) {
                        System.err.println("!!!!!!!!! memo size is "+state.ruleMemo.length+", but rule index is "+ruleIndex);
                }
                if ( state.ruleMemo[ruleIndex]!=null ) {
                        state.ruleMemo[ruleIndex].put(
                                new Integer(ruleStartIndex), new Integer(stopTokenIndex)
                        );
                }
        }

        public int getRuleMemoizationCacheSize() {
                int n = 0;
                for (int i = 0; state.ruleMemo!=null && i < state.ruleMemo.length; i++) {
                        Map ruleMap = state.ruleMemo[i];
                        if ( ruleMap!=null ) {
                                n += ruleMap.size(); // how many input indexes are recorded?
                        }
                }
                return n;
        }

        public void traceIn(String ruleName, int ruleIndex, Object inputSymbol)  {
                System.out.print("enter "+ruleName+" "+inputSymbol);
                if ( state.failed ) {
                        System.out.println(" failed="+state.failed);
                }
                if ( state.backtracking>0 ) {
                        System.out.print(" backtracking="+state.backtracking);
                }
                System.out.println();
        }

        public void traceOut(String ruleName,
                                                 int ruleIndex,
                                                 Object inputSymbol)
        {
                System.out.print("exit "+ruleName+" "+inputSymbol);
                if ( state.failed ) {
                        System.out.println(" failed="+state.failed);
                }
                if ( state.backtracking>0 ) {
                        System.out.print(" backtracking="+state.backtracking);
                }
                System.out.println();
        }

}

---