You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1047 lines
45 KiB
1047 lines
45 KiB
/*
|
|
* [The "BSD licence"]
|
|
* Copyright (c) 2005-2008 Terence Parr
|
|
* All rights reserved.
|
|
*
|
|
* Conversion to C#:
|
|
* Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
|
|
* 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.
|
|
*/
|
|
|
|
namespace Antlr.Runtime {
|
|
using System.Collections.Generic;
|
|
|
|
using ArgumentNullException = System.ArgumentNullException;
|
|
using Array = System.Array;
|
|
using Conditional = System.Diagnostics.ConditionalAttribute;
|
|
using Exception = System.Exception;
|
|
using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener;
|
|
using MethodBase = System.Reflection.MethodBase;
|
|
using NotSupportedException = System.NotSupportedException;
|
|
using Regex = System.Text.RegularExpressions.Regex;
|
|
using StackFrame = System.Diagnostics.StackFrame;
|
|
using StackTrace = System.Diagnostics.StackTrace;
|
|
using TextWriter = System.IO.TextWriter;
|
|
using Type = System.Type;
|
|
|
|
/** <summary>
|
|
* A generic recognizer that can handle recognizers generated from
|
|
* lexer, parser, and tree grammars. This is all the parsing
|
|
* support code essentially; most of it is error recovery stuff and
|
|
* backtracking.
|
|
* </summary>
|
|
*/
|
|
public abstract class BaseRecognizer {
|
|
public const int MemoRuleFailed = -2;
|
|
public const int MemoRuleUnknown = -1;
|
|
public const int InitialFollowStackSize = 100;
|
|
|
|
// copies from Token object for convenience in actions
|
|
public const int DefaultTokenChannel = TokenChannels.Default;
|
|
public const int Hidden = TokenChannels.Hidden;
|
|
|
|
public const string NextTokenRuleName = "nextToken";
|
|
|
|
/** <summary>
|
|
* State of a lexer, parser, or tree parser are collected into a state
|
|
* object so the state can be shared. This sharing is needed to
|
|
* have one grammar import others and share same error variables
|
|
* and other state variables. It's a kind of explicit multiple
|
|
* inheritance via delegation of methods and shared state.
|
|
* </summary>
|
|
*/
|
|
protected internal RecognizerSharedState state;
|
|
|
|
public BaseRecognizer()
|
|
: this(new RecognizerSharedState()) {
|
|
}
|
|
|
|
public BaseRecognizer(RecognizerSharedState state) {
|
|
if (state == null) {
|
|
state = new RecognizerSharedState();
|
|
}
|
|
this.state = state;
|
|
InitDFAs();
|
|
}
|
|
|
|
public TextWriter TraceDestination {
|
|
get;
|
|
set;
|
|
}
|
|
|
|
protected virtual void InitDFAs() {
|
|
}
|
|
|
|
/** <summary>reset the parser's state; subclasses must rewinds the input stream</summary> */
|
|
public virtual 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;
|
|
}
|
|
}
|
|
|
|
|
|
/** <summary>
|
|
* Match current input symbol against ttype. Attempt
|
|
* single token insertion or deletion error recovery. If
|
|
* that fails, throw MismatchedTokenException.
|
|
* </summary>
|
|
*
|
|
* <remarks>
|
|
* To turn off single token insertion or deletion error
|
|
* recovery, override recoverFromMismatchedToken() and have it
|
|
* throw an exception. See TreeParser.recoverFromMismatchedToken().
|
|
* This way 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.
|
|
* </remarks>
|
|
*/
|
|
public virtual object Match(IIntStream input, int ttype, BitSet follow) {
|
|
//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;
|
|
}
|
|
|
|
/** <summary>Match the wildcard: in a symbol</summary> */
|
|
public virtual void MatchAny(IIntStream input) {
|
|
state.errorRecovery = false;
|
|
state.failed = false;
|
|
input.Consume();
|
|
}
|
|
|
|
public virtual bool MismatchIsUnwantedToken(IIntStream input, int ttype) {
|
|
return input.LA(2) == ttype;
|
|
}
|
|
|
|
public virtual bool MismatchIsMissingToken(IIntStream 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(TokenTypes.EndOfRule)) {
|
|
BitSet viableTokensFollowingThisRule = ComputeContextSensitiveRuleFOLLOW();
|
|
follow = follow.Or(viableTokensFollowingThisRule);
|
|
if (state._fsp >= 0) { // remove EOR if we're not the start symbol
|
|
follow.Remove(TokenTypes.EndOfRule);
|
|
}
|
|
}
|
|
// 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(TokenTypes.EndOfRule)) {
|
|
//System.out.println("LT(1)=="+((TokenStream)input).LT(1)+" is consistent with what follows; inserting...");
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/** <summary>Report a recognition problem.</summary>
|
|
*
|
|
* <remarks>
|
|
* 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 syntaxErrors if you care about that.
|
|
* </remarks>
|
|
*/
|
|
public virtual 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.TokenNames, e);
|
|
}
|
|
|
|
public virtual void DisplayRecognitionError(string[] tokenNames,
|
|
RecognitionException e) {
|
|
string hdr = GetErrorHeader(e);
|
|
string msg = GetErrorMessage(e, tokenNames);
|
|
EmitErrorMessage(hdr + " " + msg);
|
|
}
|
|
|
|
/** <summary>What error message should be generated for the various exception types?</summary>
|
|
*
|
|
* <remarks>
|
|
* Not very object-oriented code, but I like having all error message
|
|
* generation within one method rather than spread among all of the
|
|
* exception classes. This also makes it much easier for the exception
|
|
* handling because the exception classes do not have to have pointers back
|
|
* to this object to access utility routines and so on. Also, changing
|
|
* the message for an exception type would be difficult because you
|
|
* would have to subclassing exception, but then somehow get ANTLR
|
|
* to make those kinds of exception objects instead of the default.
|
|
* This looks weird, but trust me--it makes the most sense in terms
|
|
* of flexibility.
|
|
*
|
|
* For grammar debugging, you will want to override this to add
|
|
* more information such as the stack frame with
|
|
* getRuleInvocationStack(e, this.getClass().getName()) and,
|
|
* for no viable alts, the decision description and state etc...
|
|
*
|
|
* Override this to change the message generated for one or more
|
|
* exception types.
|
|
* </remarks>
|
|
*/
|
|
public virtual string GetErrorMessage(RecognitionException e, string[] tokenNames) {
|
|
string msg = e.Message;
|
|
if (e is UnwantedTokenException) {
|
|
UnwantedTokenException ute = (UnwantedTokenException)e;
|
|
string tokenName = "<unknown>";
|
|
if (ute.Expecting == TokenTypes.EndOfFile) {
|
|
tokenName = "EndOfFile";
|
|
} else {
|
|
tokenName = tokenNames[ute.Expecting];
|
|
}
|
|
msg = "extraneous input " + GetTokenErrorDisplay(ute.UnexpectedToken) +
|
|
" expecting " + tokenName;
|
|
} else if (e is MissingTokenException) {
|
|
MissingTokenException mte = (MissingTokenException)e;
|
|
string tokenName = "<unknown>";
|
|
if (mte.Expecting == TokenTypes.EndOfFile) {
|
|
tokenName = "EndOfFile";
|
|
} else {
|
|
tokenName = tokenNames[mte.Expecting];
|
|
}
|
|
msg = "missing " + tokenName + " at " + GetTokenErrorDisplay(e.Token);
|
|
} else if (e is MismatchedTokenException) {
|
|
MismatchedTokenException mte = (MismatchedTokenException)e;
|
|
string tokenName = "<unknown>";
|
|
if (mte.Expecting == TokenTypes.EndOfFile) {
|
|
tokenName = "EndOfFile";
|
|
} else {
|
|
tokenName = tokenNames[mte.Expecting];
|
|
}
|
|
msg = "mismatched input " + GetTokenErrorDisplay(e.Token) +
|
|
" expecting " + tokenName;
|
|
} else if (e is MismatchedTreeNodeException) {
|
|
MismatchedTreeNodeException mtne = (MismatchedTreeNodeException)e;
|
|
string tokenName = "<unknown>";
|
|
if (mtne.Expecting == TokenTypes.EndOfFile) {
|
|
tokenName = "EndOfFile";
|
|
} else {
|
|
tokenName = tokenNames[mtne.Expecting];
|
|
}
|
|
// workaround for a .NET framework bug (NullReferenceException)
|
|
string nodeText = (mtne.Node != null) ? mtne.Node.ToString() ?? string.Empty : string.Empty;
|
|
msg = "mismatched tree node: " + nodeText + " expecting " + tokenName;
|
|
} else if (e is 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 is 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 is MismatchedSetException) {
|
|
MismatchedSetException mse = (MismatchedSetException)e;
|
|
msg = "mismatched input " + GetTokenErrorDisplay(e.Token) +
|
|
" expecting set " + mse.Expecting;
|
|
} else if (e is MismatchedNotSetException) {
|
|
MismatchedNotSetException mse = (MismatchedNotSetException)e;
|
|
msg = "mismatched input " + GetTokenErrorDisplay(e.Token) +
|
|
" expecting set " + mse.Expecting;
|
|
} else if (e is FailedPredicateException) {
|
|
FailedPredicateException fpe = (FailedPredicateException)e;
|
|
msg = "rule " + fpe.RuleName + " failed predicate: {" +
|
|
fpe.PredicateText + "}?";
|
|
}
|
|
return msg;
|
|
}
|
|
|
|
/** <summary>
|
|
* 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
|
|
* </summary>
|
|
*
|
|
* <seealso cref="reportError()"/>
|
|
*/
|
|
public virtual int NumberOfSyntaxErrors {
|
|
get {
|
|
return state.syntaxErrors;
|
|
}
|
|
}
|
|
|
|
/** <summary>What is the error header, normally line/character position information?</summary> */
|
|
public virtual string GetErrorHeader(RecognitionException e) {
|
|
return "line " + e.Line + ":" + (e.CharPositionInLine + 1);
|
|
}
|
|
|
|
/** <summary>
|
|
* How should a token be displayed in an error message? The default
|
|
* is to display just the text, but during development you might
|
|
* want to have a lot of information spit out. Override in that case
|
|
* to use t.ToString() (which, for CommonToken, dumps everything about
|
|
* the token). This is better than forcing you to override a method in
|
|
* your token objects because you don't have to go modify your lexer
|
|
* so that it creates a new Java type.
|
|
* </summary>
|
|
*/
|
|
public virtual string GetTokenErrorDisplay(IToken t) {
|
|
string s = t.Text;
|
|
if (s == null) {
|
|
if (t.Type == TokenTypes.EndOfFile) {
|
|
s = "<EOF>";
|
|
} else {
|
|
s = "<" + t.Type + ">";
|
|
}
|
|
}
|
|
s = Regex.Replace(s, "\n", "\\\\n");
|
|
s = Regex.Replace(s, "\r", "\\\\r");
|
|
s = Regex.Replace(s, "\t", "\\\\t");
|
|
return "'" + s + "'";
|
|
}
|
|
|
|
/** <summary>Override this method to change where error messages go</summary> */
|
|
public virtual void EmitErrorMessage(string msg) {
|
|
if (TraceDestination != null)
|
|
TraceDestination.WriteLine(msg);
|
|
}
|
|
|
|
/** <summary>
|
|
* Recover from an error found on the input stream. This is
|
|
* for NoViableAlt and mismatched symbol exceptions. If you enable
|
|
* single token insertion and deletion, this will usually not
|
|
* handle mismatched symbol exceptions but there could be a mismatched
|
|
* token that the match() routine could not recover from.
|
|
* </summary>
|
|
*/
|
|
public virtual void Recover(IIntStream 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();
|
|
}
|
|
|
|
/** <summary>
|
|
* A hook to listen in on the token consumption during error recovery.
|
|
* The DebugParser subclasses this to fire events to the listenter.
|
|
* </summary>
|
|
*/
|
|
public virtual void BeginResync() {
|
|
}
|
|
|
|
public virtual 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 virtual BitSet ComputeErrorRecoverySet() {
|
|
return CombineFollows(false);
|
|
}
|
|
|
|
/** <summary>
|
|
* Compute the context-sensitive FOLLOW set for current rule.
|
|
* This is 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 (lookahead depth 1)
|
|
* given the current call chain. Contrast this with the
|
|
* definition of plain FOLLOW for rule r:
|
|
* </summary>
|
|
*
|
|
* 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 nonterminals. 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.
|
|
*/
|
|
protected virtual BitSet ComputeContextSensitiveRuleFOLLOW() {
|
|
return CombineFollows(true);
|
|
}
|
|
|
|
// what is exact? it seems to only add sets from above on stack
|
|
// if EOR is in set i. When it sees a set w/o EOR, it stops adding.
|
|
// Why would we ever want them all? Maybe no viable alt instead of
|
|
// mismatched token?
|
|
protected virtual BitSet CombineFollows(bool 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(TokenTypes.EndOfRule)) {
|
|
// 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(TokenTypes.EndOfRule);
|
|
}
|
|
} else { // can't see end of rule, quit
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
return followSet;
|
|
}
|
|
|
|
/** <summary>Attempt to recover from a single missing or extra token.</summary>
|
|
*
|
|
* 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 ')'.
|
|
*/
|
|
protected virtual object RecoverFromMismatchedToken(IIntStream input, int ttype, BitSet follow) {
|
|
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, TokenNames);
|
|
/*
|
|
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, TokenNames);
|
|
throw e;
|
|
}
|
|
|
|
/** Not currently used */
|
|
public virtual object RecoverFromMismatchedSet(IIntStream input,
|
|
RecognitionException e,
|
|
BitSet follow) {
|
|
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, TokenTypes.Invalid, follow);
|
|
}
|
|
// TODO do single token deletion like above for Token mismatch
|
|
throw e;
|
|
}
|
|
|
|
/** <summary>
|
|
* Match needs to return the current input symbol, which gets put
|
|
* into the 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.
|
|
* </summary>
|
|
*
|
|
* <remarks>This is ignored for lexers.</remarks>
|
|
*/
|
|
protected virtual object GetCurrentInputSymbol(IIntStream input) {
|
|
return null;
|
|
}
|
|
|
|
/** <summary>Conjure up a missing token during error recovery.</summary>
|
|
*
|
|
* <remarks>
|
|
* 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.
|
|
* </remarks>
|
|
*/
|
|
protected virtual object GetMissingSymbol(IIntStream input,
|
|
RecognitionException e,
|
|
int expectedTokenType,
|
|
BitSet follow) {
|
|
return null;
|
|
}
|
|
|
|
public virtual void ConsumeUntil(IIntStream input, int tokenType) {
|
|
//System.out.println("consumeUntil "+tokenType);
|
|
int ttype = input.LA(1);
|
|
while (ttype != TokenTypes.EndOfFile && ttype != tokenType) {
|
|
input.Consume();
|
|
ttype = input.LA(1);
|
|
}
|
|
}
|
|
|
|
/** <summary>Consume tokens until one matches the given token set</summary> */
|
|
public virtual void ConsumeUntil(IIntStream input, BitSet set) {
|
|
//System.out.println("consumeUntil("+set.toString(getTokenNames())+")");
|
|
int ttype = input.LA(1);
|
|
while (ttype != TokenTypes.EndOfFile && !set.Member(ttype)) {
|
|
//System.out.println("consume during recover LA(1)="+getTokenNames()[input.LA(1)]);
|
|
input.Consume();
|
|
ttype = input.LA(1);
|
|
}
|
|
}
|
|
|
|
/** <summary>Push a rule's follow set using our own hardcoded stack</summary> */
|
|
protected void PushFollow(BitSet fset) {
|
|
if ((state._fsp + 1) >= state.following.Length) {
|
|
Array.Resize(ref state.following, state.following.Length * 2);
|
|
}
|
|
state.following[++state._fsp] = fset;
|
|
}
|
|
|
|
protected void PopFollow() {
|
|
state._fsp--;
|
|
}
|
|
|
|
/** <summary>
|
|
* Return List<String> of the rules in your parser instance
|
|
* leading up to a call to this method. You could override if
|
|
* you want more details such as the file/line info of where
|
|
* in the parser java code a rule is invoked.
|
|
* </summary>
|
|
*
|
|
* <remarks>
|
|
* This is very useful for error messages and for context-sensitive
|
|
* error recovery.
|
|
* </remarks>
|
|
*/
|
|
public virtual IList<string> GetRuleInvocationStack() {
|
|
return GetRuleInvocationStack(new StackTrace(true));
|
|
}
|
|
|
|
/** <summary>
|
|
* A more general version of GetRuleInvocationStack where you can
|
|
* pass in the StackTrace of, for example, a RecognitionException
|
|
* to get it's rule stack trace.
|
|
* </summary>
|
|
*/
|
|
public static IList<string> GetRuleInvocationStack(StackTrace trace) {
|
|
if (trace == null)
|
|
throw new ArgumentNullException("trace");
|
|
|
|
List<string> rules = new List<string>();
|
|
StackFrame[] stack = trace.GetFrames() ?? new StackFrame[0];
|
|
|
|
for (int i = stack.Length - 1; i >= 0; i--) {
|
|
StackFrame frame = stack[i];
|
|
MethodBase method = frame.GetMethod();
|
|
GrammarRuleAttribute[] attributes = (GrammarRuleAttribute[])method.GetCustomAttributes(typeof(GrammarRuleAttribute), true);
|
|
if (attributes != null && attributes.Length > 0)
|
|
rules.Add(attributes[0].Name);
|
|
}
|
|
|
|
return rules;
|
|
}
|
|
|
|
public virtual int BacktrackingLevel {
|
|
get {
|
|
return state.backtracking;
|
|
}
|
|
set {
|
|
state.backtracking = value;
|
|
}
|
|
}
|
|
|
|
/** <summary>Return whether or not a backtracking attempt failed.</summary> */
|
|
public virtual bool Failed {
|
|
get {
|
|
return state.failed;
|
|
}
|
|
}
|
|
|
|
/** <summary>
|
|
* Used to print out token names like ID during debugging and
|
|
* error reporting. The generated parsers implement a method
|
|
* that overrides this to point to their String[] tokenNames.
|
|
* </summary>
|
|
*/
|
|
public virtual string[] TokenNames {
|
|
get {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
/** <summary>
|
|
* For debugging and other purposes, might want the grammar name.
|
|
* Have ANTLR generate an implementation for this method.
|
|
* </summary>
|
|
*/
|
|
public virtual string GrammarFileName {
|
|
get {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
public abstract string SourceName {
|
|
get;
|
|
}
|
|
|
|
/** <summary>
|
|
* A convenience method for use most often with template rewrites.
|
|
* Convert a List<Token> to List<String>
|
|
* </summary>
|
|
*/
|
|
public virtual List<string> ToStrings(ICollection<IToken> tokens) {
|
|
if (tokens == null)
|
|
return null;
|
|
|
|
List<string> strings = new List<string>(tokens.Count);
|
|
foreach (IToken token in tokens) {
|
|
strings.Add(token.Text);
|
|
}
|
|
|
|
return strings;
|
|
}
|
|
|
|
/** <summary>
|
|
* Given a rule number and a start token index number, return
|
|
* MEMO_RULE_UNKNOWN if the rule has not parsed input starting from
|
|
* start index. If this rule has parsed input starting from the
|
|
* start index before, then return where the rule stopped parsing.
|
|
* It returns the index of the last token matched by the rule.
|
|
* </summary>
|
|
*
|
|
* <remarks>
|
|
* For now we use a hashtable and just the slow Object-based one.
|
|
* Later, we can make a special one for ints and also one that
|
|
* tosses out data after we commit past input position i.
|
|
* </remarks>
|
|
*/
|
|
public virtual int GetRuleMemoization(int ruleIndex, int ruleStartIndex) {
|
|
if (state.ruleMemo[ruleIndex] == null) {
|
|
state.ruleMemo[ruleIndex] = new Dictionary<int, int>();
|
|
}
|
|
|
|
int stopIndex;
|
|
if (!state.ruleMemo[ruleIndex].TryGetValue(ruleStartIndex, out stopIndex))
|
|
return MemoRuleUnknown;
|
|
|
|
return stopIndex;
|
|
}
|
|
|
|
/** <summary>
|
|
* Has this rule already parsed input at the current index in the
|
|
* input stream? Return the stop token index or MEMO_RULE_UNKNOWN.
|
|
* If we attempted but failed to parse properly before, return
|
|
* MEMO_RULE_FAILED.
|
|
* </summary>
|
|
*
|
|
* <remarks>
|
|
* This method has a side-effect: if we have seen this input for
|
|
* this rule and successfully parsed before, then seek ahead to
|
|
* 1 past the stop token matched for this rule last time.
|
|
* </remarks>
|
|
*/
|
|
public virtual bool AlreadyParsedRule(IIntStream input, int ruleIndex) {
|
|
int stopIndex = GetRuleMemoization(ruleIndex, input.Index);
|
|
if (stopIndex == MemoRuleUnknown) {
|
|
return false;
|
|
}
|
|
if (stopIndex == MemoRuleFailed) {
|
|
//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;
|
|
}
|
|
|
|
/** <summary>
|
|
* Record whether or not this rule parsed the input at this position
|
|
* successfully. Use a standard java hashtable for now.
|
|
* </summary>
|
|
*/
|
|
public virtual void Memoize(IIntStream input,
|
|
int ruleIndex,
|
|
int ruleStartIndex) {
|
|
int stopTokenIndex = state.failed ? MemoRuleFailed : input.Index - 1;
|
|
if (state.ruleMemo == null) {
|
|
if (TraceDestination != null)
|
|
TraceDestination.WriteLine("!!!!!!!!! memo array is null for " + GrammarFileName);
|
|
}
|
|
if (ruleIndex >= state.ruleMemo.Length) {
|
|
if (TraceDestination != null)
|
|
TraceDestination.WriteLine("!!!!!!!!! memo size is " + state.ruleMemo.Length + ", but rule index is " + ruleIndex);
|
|
}
|
|
if (state.ruleMemo[ruleIndex] != null) {
|
|
state.ruleMemo[ruleIndex][ruleStartIndex] = stopTokenIndex;
|
|
}
|
|
}
|
|
|
|
/** <summary>return how many rule/input-index pairs there are in total.</summary>
|
|
* TODO: this includes synpreds. :(
|
|
*/
|
|
public virtual int GetRuleMemoizationCacheSize() {
|
|
int n = 0;
|
|
for (int i = 0; state.ruleMemo != null && i < state.ruleMemo.Length; i++) {
|
|
var ruleMap = state.ruleMemo[i];
|
|
if (ruleMap != null) {
|
|
n += ruleMap.Count; // how many input indexes are recorded?
|
|
}
|
|
}
|
|
return n;
|
|
}
|
|
|
|
[Conditional("ANTLR_TRACE")]
|
|
public virtual void TraceIn(string ruleName, int ruleIndex, object inputSymbol) {
|
|
if (TraceDestination == null)
|
|
return;
|
|
|
|
TraceDestination.Write("enter " + ruleName + " " + inputSymbol);
|
|
if (state.backtracking > 0) {
|
|
TraceDestination.Write(" backtracking=" + state.backtracking);
|
|
}
|
|
TraceDestination.WriteLine();
|
|
}
|
|
|
|
[Conditional("ANTLR_TRACE")]
|
|
public virtual void TraceOut(string ruleName, int ruleIndex, object inputSymbol) {
|
|
if (TraceDestination == null)
|
|
return;
|
|
|
|
TraceDestination.Write("exit " + ruleName + " " + inputSymbol);
|
|
if (state.backtracking > 0) {
|
|
TraceDestination.Write(" backtracking=" + state.backtracking);
|
|
if (state.failed)
|
|
TraceDestination.Write(" failed");
|
|
else
|
|
TraceDestination.Write(" succeeded");
|
|
}
|
|
TraceDestination.WriteLine();
|
|
}
|
|
|
|
#region Debugging support
|
|
public virtual IDebugEventListener DebugListener {
|
|
get {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugEnterRule(string grammarFileName, string ruleName) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.EnterRule(grammarFileName, ruleName);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugExitRule(string grammarFileName, string ruleName) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.ExitRule(grammarFileName, ruleName);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugEnterSubRule(int decisionNumber) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.EnterSubRule(decisionNumber);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugExitSubRule(int decisionNumber) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.ExitSubRule(decisionNumber);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugEnterAlt(int alt) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.EnterAlt(alt);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugEnterDecision(int decisionNumber, bool couldBacktrack) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.EnterDecision(decisionNumber, couldBacktrack);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugExitDecision(int decisionNumber) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.ExitDecision(decisionNumber);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugLocation(int line, int charPositionInLine) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.Location(line, charPositionInLine);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugSemanticPredicate(bool result, string predicate) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.SemanticPredicate(result, predicate);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugBeginBacktrack(int level) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.BeginBacktrack(level);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugEndBacktrack(int level, bool successful) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.EndBacktrack(level, successful);
|
|
}
|
|
|
|
[Conditional("ANTLR_DEBUG")]
|
|
protected virtual void DebugRecognitionException(RecognitionException ex) {
|
|
IDebugEventListener dbg = DebugListener;
|
|
if (dbg != null)
|
|
dbg.RecognitionException(ex);
|
|
}
|
|
#endregion
|
|
}
|
|
}
|