1/* 2 * [The "BSD licence"] 3 * Copyright (c) 2005-2008 Terence Parr 4 * All rights reserved. 5 * 6 * Conversion to C#: 7 * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33namespace Antlr.Runtime { 34 using System.Collections.Generic; 35 36 using ArgumentNullException = System.ArgumentNullException; 37 using Array = System.Array; 38 using Conditional = System.Diagnostics.ConditionalAttribute; 39 using Exception = System.Exception; 40 using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener; 41 using MethodBase = System.Reflection.MethodBase; 42 using NotSupportedException = System.NotSupportedException; 43 using Regex = System.Text.RegularExpressions.Regex; 44 using StackFrame = System.Diagnostics.StackFrame; 45 using StackTrace = System.Diagnostics.StackTrace; 46 using TextWriter = System.IO.TextWriter; 47 using Type = System.Type; 48 49 /** <summary> 50 * A generic recognizer that can handle recognizers generated from 51 * lexer, parser, and tree grammars. This is all the parsing 52 * support code essentially; most of it is error recovery stuff and 53 * backtracking. 54 * </summary> 55 */ 56 public abstract class BaseRecognizer { 57 public const int MemoRuleFailed = -2; 58 public const int MemoRuleUnknown = -1; 59 public const int InitialFollowStackSize = 100; 60 61 // copies from Token object for convenience in actions 62 public const int DefaultTokenChannel = TokenChannels.Default; 63 public const int Hidden = TokenChannels.Hidden; 64 65 public const string NextTokenRuleName = "nextToken"; 66 67 /** <summary> 68 * State of a lexer, parser, or tree parser are collected into a state 69 * object so the state can be shared. This sharing is needed to 70 * have one grammar import others and share same error variables 71 * and other state variables. It's a kind of explicit multiple 72 * inheritance via delegation of methods and shared state. 73 * </summary> 74 */ 75 protected internal RecognizerSharedState state; 76 77 public BaseRecognizer() 78 : this(new RecognizerSharedState()) { 79 } 80 81 public BaseRecognizer(RecognizerSharedState state) { 82 if (state == null) { 83 state = new RecognizerSharedState(); 84 } 85 this.state = state; 86 InitDFAs(); 87 } 88 89 public TextWriter TraceDestination { 90 get; 91 set; 92 } 93 94 protected virtual void InitDFAs() { 95 } 96 97 /** <summary>reset the parser's state; subclasses must rewinds the input stream</summary> */ 98 public virtual void Reset() { 99 // wack everything related to error recovery 100 if (state == null) { 101 return; // no shared state work to do 102 } 103 state._fsp = -1; 104 state.errorRecovery = false; 105 state.lastErrorIndex = -1; 106 state.failed = false; 107 state.syntaxErrors = 0; 108 // wack everything related to backtracking and memoization 109 state.backtracking = 0; 110 for (int i = 0; state.ruleMemo != null && i < state.ruleMemo.Length; i++) { // wipe cache 111 state.ruleMemo[i] = null; 112 } 113 } 114 115 116 /** <summary> 117 * Match current input symbol against ttype. Attempt 118 * single token insertion or deletion error recovery. If 119 * that fails, throw MismatchedTokenException. 120 * </summary> 121 * 122 * <remarks> 123 * To turn off single token insertion or deletion error 124 * recovery, override recoverFromMismatchedToken() and have it 125 * throw an exception. See TreeParser.recoverFromMismatchedToken(). 126 * This way any error in a rule will cause an exception and 127 * immediate exit from rule. Rule would recover by resynchronizing 128 * to the set of symbols that can follow rule ref. 129 * </remarks> 130 */ 131 public virtual object Match(IIntStream input, int ttype, BitSet follow) { 132 //System.out.println("match "+((TokenStream)input).LT(1)); 133 object matchedSymbol = GetCurrentInputSymbol(input); 134 if (input.LA(1) == ttype) { 135 input.Consume(); 136 state.errorRecovery = false; 137 state.failed = false; 138 return matchedSymbol; 139 } 140 if (state.backtracking > 0) { 141 state.failed = true; 142 return matchedSymbol; 143 } 144 matchedSymbol = RecoverFromMismatchedToken(input, ttype, follow); 145 return matchedSymbol; 146 } 147 148 /** <summary>Match the wildcard: in a symbol</summary> */ 149 public virtual void MatchAny(IIntStream input) { 150 state.errorRecovery = false; 151 state.failed = false; 152 input.Consume(); 153 } 154 155 public virtual bool MismatchIsUnwantedToken(IIntStream input, int ttype) { 156 return input.LA(2) == ttype; 157 } 158 159 public virtual bool MismatchIsMissingToken(IIntStream input, BitSet follow) { 160 if (follow == null) { 161 // we have no information about the follow; we can only consume 162 // a single token and hope for the best 163 return false; 164 } 165 // compute what can follow this grammar element reference 166 if (follow.Member(TokenTypes.EndOfRule)) { 167 BitSet viableTokensFollowingThisRule = ComputeContextSensitiveRuleFOLLOW(); 168 follow = follow.Or(viableTokensFollowingThisRule); 169 if (state._fsp >= 0) { // remove EOR if we're not the start symbol 170 follow.Remove(TokenTypes.EndOfRule); 171 } 172 } 173 // if current token is consistent with what could come after set 174 // then we know we're missing a token; error recovery is free to 175 // "insert" the missing token 176 177 //System.out.println("viable tokens="+follow.toString(getTokenNames())); 178 //System.out.println("LT(1)="+((TokenStream)input).LT(1)); 179 180 // BitSet cannot handle negative numbers like -1 (EOF) so I leave EOR 181 // in follow set to indicate that the fall of the start symbol is 182 // in the set (EOF can follow). 183 if (follow.Member(input.LA(1)) || follow.Member(TokenTypes.EndOfRule)) { 184 //System.out.println("LT(1)=="+((TokenStream)input).LT(1)+" is consistent with what follows; inserting..."); 185 return true; 186 } 187 return false; 188 } 189 190 /** <summary>Report a recognition problem.</summary> 191 * 192 * <remarks> 193 * This method sets errorRecovery to indicate the parser is recovering 194 * not parsing. Once in recovery mode, no errors are generated. 195 * To get out of recovery mode, the parser must successfully match 196 * a token (after a resync). So it will go: 197 * 198 * 1. error occurs 199 * 2. enter recovery mode, report error 200 * 3. consume until token found in resynch set 201 * 4. try to resume parsing 202 * 5. next match() will reset errorRecovery mode 203 * 204 * If you override, make sure to update syntaxErrors if you care about that. 205 * </remarks> 206 */ 207 public virtual void ReportError(RecognitionException e) { 208 // if we've already reported an error and have not matched a token 209 // yet successfully, don't report any errors. 210 if (state.errorRecovery) { 211 //System.err.print("[SPURIOUS] "); 212 return; 213 } 214 state.syntaxErrors++; // don't count spurious 215 state.errorRecovery = true; 216 217 DisplayRecognitionError(this.TokenNames, e); 218 } 219 220 public virtual void DisplayRecognitionError(string[] tokenNames, 221 RecognitionException e) { 222 string hdr = GetErrorHeader(e); 223 string msg = GetErrorMessage(e, tokenNames); 224 EmitErrorMessage(hdr + " " + msg); 225 } 226 227 /** <summary>What error message should be generated for the various exception types?</summary> 228 * 229 * <remarks> 230 * Not very object-oriented code, but I like having all error message 231 * generation within one method rather than spread among all of the 232 * exception classes. This also makes it much easier for the exception 233 * handling because the exception classes do not have to have pointers back 234 * to this object to access utility routines and so on. Also, changing 235 * the message for an exception type would be difficult because you 236 * would have to subclassing exception, but then somehow get ANTLR 237 * to make those kinds of exception objects instead of the default. 238 * This looks weird, but trust me--it makes the most sense in terms 239 * of flexibility. 240 * 241 * For grammar debugging, you will want to override this to add 242 * more information such as the stack frame with 243 * getRuleInvocationStack(e, this.getClass().getName()) and, 244 * for no viable alts, the decision description and state etc... 245 * 246 * Override this to change the message generated for one or more 247 * exception types. 248 * </remarks> 249 */ 250 public virtual string GetErrorMessage(RecognitionException e, string[] tokenNames) { 251 string msg = e.Message; 252 if (e is UnwantedTokenException) { 253 UnwantedTokenException ute = (UnwantedTokenException)e; 254 string tokenName = "<unknown>"; 255 if (ute.Expecting == TokenTypes.EndOfFile) { 256 tokenName = "EndOfFile"; 257 } else { 258 tokenName = tokenNames[ute.Expecting]; 259 } 260 msg = "extraneous input " + GetTokenErrorDisplay(ute.UnexpectedToken) + 261 " expecting " + tokenName; 262 } else if (e is MissingTokenException) { 263 MissingTokenException mte = (MissingTokenException)e; 264 string tokenName = "<unknown>"; 265 if (mte.Expecting == TokenTypes.EndOfFile) { 266 tokenName = "EndOfFile"; 267 } else { 268 tokenName = tokenNames[mte.Expecting]; 269 } 270 msg = "missing " + tokenName + " at " + GetTokenErrorDisplay(e.Token); 271 } else if (e is MismatchedTokenException) { 272 MismatchedTokenException mte = (MismatchedTokenException)e; 273 string tokenName = "<unknown>"; 274 if (mte.Expecting == TokenTypes.EndOfFile) { 275 tokenName = "EndOfFile"; 276 } else { 277 tokenName = tokenNames[mte.Expecting]; 278 } 279 msg = "mismatched input " + GetTokenErrorDisplay(e.Token) + 280 " expecting " + tokenName; 281 } else if (e is MismatchedTreeNodeException) { 282 MismatchedTreeNodeException mtne = (MismatchedTreeNodeException)e; 283 string tokenName = "<unknown>"; 284 if (mtne.Expecting == TokenTypes.EndOfFile) { 285 tokenName = "EndOfFile"; 286 } else { 287 tokenName = tokenNames[mtne.Expecting]; 288 } 289 // workaround for a .NET framework bug (NullReferenceException) 290 string nodeText = (mtne.Node != null) ? mtne.Node.ToString() ?? string.Empty : string.Empty; 291 msg = "mismatched tree node: " + nodeText + " expecting " + tokenName; 292 } else if (e is NoViableAltException) { 293 //NoViableAltException nvae = (NoViableAltException)e; 294 // for development, can add "decision=<<"+nvae.grammarDecisionDescription+">>" 295 // and "(decision="+nvae.decisionNumber+") and 296 // "state "+nvae.stateNumber 297 msg = "no viable alternative at input " + GetTokenErrorDisplay(e.Token); 298 } else if (e is EarlyExitException) { 299 //EarlyExitException eee = (EarlyExitException)e; 300 // for development, can add "(decision="+eee.decisionNumber+")" 301 msg = "required (...)+ loop did not match anything at input " + 302 GetTokenErrorDisplay(e.Token); 303 } else if (e is MismatchedSetException) { 304 MismatchedSetException mse = (MismatchedSetException)e; 305 msg = "mismatched input " + GetTokenErrorDisplay(e.Token) + 306 " expecting set " + mse.Expecting; 307 } else if (e is MismatchedNotSetException) { 308 MismatchedNotSetException mse = (MismatchedNotSetException)e; 309 msg = "mismatched input " + GetTokenErrorDisplay(e.Token) + 310 " expecting set " + mse.Expecting; 311 } else if (e is FailedPredicateException) { 312 FailedPredicateException fpe = (FailedPredicateException)e; 313 msg = "rule " + fpe.RuleName + " failed predicate: {" + 314 fpe.PredicateText + "}?"; 315 } 316 return msg; 317 } 318 319 /** <summary> 320 * Get number of recognition errors (lexer, parser, tree parser). Each 321 * recognizer tracks its own number. So parser and lexer each have 322 * separate count. Does not count the spurious errors found between 323 * an error and next valid token match 324 * </summary> 325 * 326 * <seealso cref="reportError()"/> 327 */ 328 public virtual int NumberOfSyntaxErrors { 329 get { 330 return state.syntaxErrors; 331 } 332 } 333 334 /** <summary>What is the error header, normally line/character position information?</summary> */ 335 public virtual string GetErrorHeader(RecognitionException e) { 336 return "line " + e.Line + ":" + (e.CharPositionInLine + 1); 337 } 338 339 /** <summary> 340 * How should a token be displayed in an error message? The default 341 * is to display just the text, but during development you might 342 * want to have a lot of information spit out. Override in that case 343 * to use t.ToString() (which, for CommonToken, dumps everything about 344 * the token). This is better than forcing you to override a method in 345 * your token objects because you don't have to go modify your lexer 346 * so that it creates a new Java type. 347 * </summary> 348 */ 349 public virtual string GetTokenErrorDisplay(IToken t) { 350 string s = t.Text; 351 if (s == null) { 352 if (t.Type == TokenTypes.EndOfFile) { 353 s = "<EOF>"; 354 } else { 355 s = "<" + t.Type + ">"; 356 } 357 } 358 s = Regex.Replace(s, "\n", "\\\\n"); 359 s = Regex.Replace(s, "\r", "\\\\r"); 360 s = Regex.Replace(s, "\t", "\\\\t"); 361 return "'" + s + "'"; 362 } 363 364 /** <summary>Override this method to change where error messages go</summary> */ 365 public virtual void EmitErrorMessage(string msg) { 366 if (TraceDestination != null) 367 TraceDestination.WriteLine(msg); 368 } 369 370 /** <summary> 371 * Recover from an error found on the input stream. This is 372 * for NoViableAlt and mismatched symbol exceptions. If you enable 373 * single token insertion and deletion, this will usually not 374 * handle mismatched symbol exceptions but there could be a mismatched 375 * token that the match() routine could not recover from. 376 * </summary> 377 */ 378 public virtual void Recover(IIntStream input, RecognitionException re) { 379 if (state.lastErrorIndex == input.Index) { 380 // uh oh, another error at same token index; must be a case 381 // where LT(1) is in the recovery token set so nothing is 382 // consumed; consume a single token so at least to prevent 383 // an infinite loop; this is a failsafe. 384 input.Consume(); 385 } 386 state.lastErrorIndex = input.Index; 387 BitSet followSet = ComputeErrorRecoverySet(); 388 BeginResync(); 389 ConsumeUntil(input, followSet); 390 EndResync(); 391 } 392 393 /** <summary> 394 * A hook to listen in on the token consumption during error recovery. 395 * The DebugParser subclasses this to fire events to the listenter. 396 * </summary> 397 */ 398 public virtual void BeginResync() { 399 } 400 401 public virtual void EndResync() { 402 } 403 404 /* Compute the error recovery set for the current rule. During 405 * rule invocation, the parser pushes the set of tokens that can 406 * follow that rule reference on the stack; this amounts to 407 * computing FIRST of what follows the rule reference in the 408 * enclosing rule. This local follow set only includes tokens 409 * from within the rule; i.e., the FIRST computation done by 410 * ANTLR stops at the end of a rule. 411 * 412 * EXAMPLE 413 * 414 * When you find a "no viable alt exception", the input is not 415 * consistent with any of the alternatives for rule r. The best 416 * thing to do is to consume tokens until you see something that 417 * can legally follow a call to r *or* any rule that called r. 418 * You don't want the exact set of viable next tokens because the 419 * input might just be missing a token--you might consume the 420 * rest of the input looking for one of the missing tokens. 421 * 422 * Consider grammar: 423 * 424 * a : '[' b ']' 425 * | '(' b ')' 426 * ; 427 * b : c '^' INT ; 428 * c : ID 429 * | INT 430 * ; 431 * 432 * At each rule invocation, the set of tokens that could follow 433 * that rule is pushed on a stack. Here are the various "local" 434 * follow sets: 435 * 436 * FOLLOW(b1_in_a) = FIRST(']') = ']' 437 * FOLLOW(b2_in_a) = FIRST(')') = ')' 438 * FOLLOW(c_in_b) = FIRST('^') = '^' 439 * 440 * Upon erroneous input "[]", the call chain is 441 * 442 * a -> b -> c 443 * 444 * and, hence, the follow context stack is: 445 * 446 * depth local follow set after call to rule 447 * 0 <EOF> a (from main()) 448 * 1 ']' b 449 * 3 '^' c 450 * 451 * Notice that ')' is not included, because b would have to have 452 * been called from a different context in rule a for ')' to be 453 * included. 454 * 455 * For error recovery, we cannot consider FOLLOW(c) 456 * (context-sensitive or otherwise). We need the combined set of 457 * all context-sensitive FOLLOW sets--the set of all tokens that 458 * could follow any reference in the call chain. We need to 459 * resync to one of those tokens. Note that FOLLOW(c)='^' and if 460 * we resync'd to that token, we'd consume until EOF. We need to 461 * sync to context-sensitive FOLLOWs for a, b, and c: {']','^'}. 462 * In this case, for input "[]", LA(1) is in this set so we would 463 * not consume anything and after printing an error rule c would 464 * return normally. It would not find the required '^' though. 465 * At this point, it gets a mismatched token error and throws an 466 * exception (since LA(1) is not in the viable following token 467 * set). The rule exception handler tries to recover, but finds 468 * the same recovery set and doesn't consume anything. Rule b 469 * exits normally returning to rule a. Now it finds the ']' (and 470 * with the successful match exits errorRecovery mode). 471 * 472 * So, you cna see that the parser walks up call chain looking 473 * for the token that was a member of the recovery set. 474 * 475 * Errors are not generated in errorRecovery mode. 476 * 477 * ANTLR's error recovery mechanism is based upon original ideas: 478 * 479 * "Algorithms + Data Structures = Programs" by Niklaus Wirth 480 * 481 * and 482 * 483 * "A note on error recovery in recursive descent parsers": 484 * http://portal.acm.org/citation.cfm?id=947902.947905 485 * 486 * Later, Josef Grosch had some good ideas: 487 * 488 * "Efficient and Comfortable Error Recovery in Recursive Descent 489 * Parsers": 490 * ftp://www.cocolab.com/products/cocktail/doca4.ps/ell.ps.zip 491 * 492 * Like Grosch I implemented local FOLLOW sets that are combined 493 * at run-time upon error to avoid overhead during parsing. 494 */ 495 protected virtual BitSet ComputeErrorRecoverySet() { 496 return CombineFollows(false); 497 } 498 499 /** <summary> 500 * Compute the context-sensitive FOLLOW set for current rule. 501 * This is set of token types that can follow a specific rule 502 * reference given a specific call chain. You get the set of 503 * viable tokens that can possibly come next (lookahead depth 1) 504 * given the current call chain. Contrast this with the 505 * definition of plain FOLLOW for rule r: 506 * </summary> 507 * 508 * FOLLOW(r)={x | S=>*alpha r beta in G and x in FIRST(beta)} 509 * 510 * where x in T* and alpha, beta in V*; T is set of terminals and 511 * V is the set of terminals and nonterminals. In other words, 512 * FOLLOW(r) is the set of all tokens that can possibly follow 513 * references to r in *any* sentential form (context). At 514 * runtime, however, we know precisely which context applies as 515 * we have the call chain. We may compute the exact (rather 516 * than covering superset) set of following tokens. 517 * 518 * For example, consider grammar: 519 * 520 * stat : ID '=' expr ';' // FOLLOW(stat)=={EOF} 521 * | "return" expr '.' 522 * ; 523 * expr : atom ('+' atom)* ; // FOLLOW(expr)=={';','.',')'} 524 * atom : INT // FOLLOW(atom)=={'+',')',';','.'} 525 * | '(' expr ')' 526 * ; 527 * 528 * The FOLLOW sets are all inclusive whereas context-sensitive 529 * FOLLOW sets are precisely what could follow a rule reference. 530 * For input input "i=(3);", here is the derivation: 531 * 532 * stat => ID '=' expr ';' 533 * => ID '=' atom ('+' atom)* ';' 534 * => ID '=' '(' expr ')' ('+' atom)* ';' 535 * => ID '=' '(' atom ')' ('+' atom)* ';' 536 * => ID '=' '(' INT ')' ('+' atom)* ';' 537 * => ID '=' '(' INT ')' ';' 538 * 539 * At the "3" token, you'd have a call chain of 540 * 541 * stat -> expr -> atom -> expr -> atom 542 * 543 * What can follow that specific nested ref to atom? Exactly ')' 544 * as you can see by looking at the derivation of this specific 545 * input. Contrast this with the FOLLOW(atom)={'+',')',';','.'}. 546 * 547 * You want the exact viable token set when recovering from a 548 * token mismatch. Upon token mismatch, if LA(1) is member of 549 * the viable next token set, then you know there is most likely 550 * a missing token in the input stream. "Insert" one by just not 551 * throwing an exception. 552 */ 553 protected virtual BitSet ComputeContextSensitiveRuleFOLLOW() { 554 return CombineFollows(true); 555 } 556 557 // what is exact? it seems to only add sets from above on stack 558 // if EOR is in set i. When it sees a set w/o EOR, it stops adding. 559 // Why would we ever want them all? Maybe no viable alt instead of 560 // mismatched token? 561 protected virtual BitSet CombineFollows(bool exact) { 562 int top = state._fsp; 563 BitSet followSet = new BitSet(); 564 for (int i = top; i >= 0; i--) { 565 BitSet localFollowSet = (BitSet)state.following[i]; 566 /* 567 System.out.println("local follow depth "+i+"="+ 568 localFollowSet.toString(getTokenNames())+")"); 569 */ 570 followSet.OrInPlace(localFollowSet); 571 if (exact) { 572 // can we see end of rule? 573 if (localFollowSet.Member(TokenTypes.EndOfRule)) { 574 // Only leave EOR in set if at top (start rule); this lets 575 // us know if have to include follow(start rule); i.e., EOF 576 if (i > 0) { 577 followSet.Remove(TokenTypes.EndOfRule); 578 } 579 } else { // can't see end of rule, quit 580 break; 581 } 582 } 583 } 584 return followSet; 585 } 586 587 /** <summary>Attempt to recover from a single missing or extra token.</summary> 588 * 589 * EXTRA TOKEN 590 * 591 * LA(1) is not what we are looking for. If LA(2) has the right token, 592 * however, then assume LA(1) is some extra spurious token. Delete it 593 * and LA(2) as if we were doing a normal match(), which advances the 594 * input. 595 * 596 * MISSING TOKEN 597 * 598 * If current token is consistent with what could come after 599 * ttype then it is ok to "insert" the missing token, else throw 600 * exception For example, Input "i=(3;" is clearly missing the 601 * ')'. When the parser returns from the nested call to expr, it 602 * will have call chain: 603 * 604 * stat -> expr -> atom 605 * 606 * and it will be trying to match the ')' at this point in the 607 * derivation: 608 * 609 * => ID '=' '(' INT ')' ('+' atom)* ';' 610 * ^ 611 * match() will see that ';' doesn't match ')' and report a 612 * mismatched token error. To recover, it sees that LA(1)==';' 613 * is in the set of tokens that can follow the ')' token 614 * reference in rule atom. It can assume that you forgot the ')'. 615 */ 616 protected virtual object RecoverFromMismatchedToken(IIntStream input, int ttype, BitSet follow) { 617 RecognitionException e = null; 618 // if next token is what we are looking for then "delete" this token 619 if (MismatchIsUnwantedToken(input, ttype)) { 620 e = new UnwantedTokenException(ttype, input, TokenNames); 621 /* 622 System.err.println("recoverFromMismatchedToken deleting "+ 623 ((TokenStream)input).LT(1)+ 624 " since "+((TokenStream)input).LT(2)+" is what we want"); 625 */ 626 BeginResync(); 627 input.Consume(); // simply delete extra token 628 EndResync(); 629 ReportError(e); // report after consuming so AW sees the token in the exception 630 // we want to return the token we're actually matching 631 object matchedSymbol = GetCurrentInputSymbol(input); 632 input.Consume(); // move past ttype token as if all were ok 633 return matchedSymbol; 634 } 635 // can't recover with single token deletion, try insertion 636 if (MismatchIsMissingToken(input, follow)) { 637 object inserted = GetMissingSymbol(input, e, ttype, follow); 638 e = new MissingTokenException(ttype, input, inserted); 639 ReportError(e); // report after inserting so AW sees the token in the exception 640 return inserted; 641 } 642 // even that didn't work; must throw the exception 643 e = new MismatchedTokenException(ttype, input, TokenNames); 644 throw e; 645 } 646 647 /** Not currently used */ 648 public virtual object RecoverFromMismatchedSet(IIntStream input, 649 RecognitionException e, 650 BitSet follow) { 651 if (MismatchIsMissingToken(input, follow)) { 652 // System.out.println("missing token"); 653 ReportError(e); 654 // we don't know how to conjure up a token for sets yet 655 return GetMissingSymbol(input, e, TokenTypes.Invalid, follow); 656 } 657 // TODO do single token deletion like above for Token mismatch 658 throw e; 659 } 660 661 /** <summary> 662 * Match needs to return the current input symbol, which gets put 663 * into the label for the associated token ref; e.g., x=ID. Token 664 * and tree parsers need to return different objects. Rather than test 665 * for input stream type or change the IntStream interface, I use 666 * a simple method to ask the recognizer to tell me what the current 667 * input symbol is. 668 * </summary> 669 * 670 * <remarks>This is ignored for lexers.</remarks> 671 */ 672 protected virtual object GetCurrentInputSymbol(IIntStream input) { 673 return null; 674 } 675 676 /** <summary>Conjure up a missing token during error recovery.</summary> 677 * 678 * <remarks> 679 * The recognizer attempts to recover from single missing 680 * symbols. But, actions might refer to that missing symbol. 681 * For example, x=ID {f($x);}. The action clearly assumes 682 * that there has been an identifier matched previously and that 683 * $x points at that token. If that token is missing, but 684 * the next token in the stream is what we want we assume that 685 * this token is missing and we keep going. Because we 686 * have to return some token to replace the missing token, 687 * we have to conjure one up. This method gives the user control 688 * over the tokens returned for missing tokens. Mostly, 689 * you will want to create something special for identifier 690 * tokens. For literals such as '{' and ',', the default 691 * action in the parser or tree parser works. It simply creates 692 * a CommonToken of the appropriate type. The text will be the token. 693 * If you change what tokens must be created by the lexer, 694 * override this method to create the appropriate tokens. 695 * </remarks> 696 */ 697 protected virtual object GetMissingSymbol(IIntStream input, 698 RecognitionException e, 699 int expectedTokenType, 700 BitSet follow) { 701 return null; 702 } 703 704 public virtual void ConsumeUntil(IIntStream input, int tokenType) { 705 //System.out.println("consumeUntil "+tokenType); 706 int ttype = input.LA(1); 707 while (ttype != TokenTypes.EndOfFile && ttype != tokenType) { 708 input.Consume(); 709 ttype = input.LA(1); 710 } 711 } 712 713 /** <summary>Consume tokens until one matches the given token set</summary> */ 714 public virtual void ConsumeUntil(IIntStream input, BitSet set) { 715 //System.out.println("consumeUntil("+set.toString(getTokenNames())+")"); 716 int ttype = input.LA(1); 717 while (ttype != TokenTypes.EndOfFile && !set.Member(ttype)) { 718 //System.out.println("consume during recover LA(1)="+getTokenNames()[input.LA(1)]); 719 input.Consume(); 720 ttype = input.LA(1); 721 } 722 } 723 724 /** <summary>Push a rule's follow set using our own hardcoded stack</summary> */ 725 protected void PushFollow(BitSet fset) { 726 if ((state._fsp + 1) >= state.following.Length) { 727 Array.Resize(ref state.following, state.following.Length * 2); 728 } 729 state.following[++state._fsp] = fset; 730 } 731 732 protected void PopFollow() { 733 state._fsp--; 734 } 735 736 /** <summary> 737 * Return List<String> of the rules in your parser instance 738 * leading up to a call to this method. You could override if 739 * you want more details such as the file/line info of where 740 * in the parser java code a rule is invoked. 741 * </summary> 742 * 743 * <remarks> 744 * This is very useful for error messages and for context-sensitive 745 * error recovery. 746 * </remarks> 747 */ 748 public virtual IList<string> GetRuleInvocationStack() { 749 return GetRuleInvocationStack(new StackTrace(true)); 750 } 751 752 /** <summary> 753 * A more general version of GetRuleInvocationStack where you can 754 * pass in the StackTrace of, for example, a RecognitionException 755 * to get it's rule stack trace. 756 * </summary> 757 */ 758 public static IList<string> GetRuleInvocationStack(StackTrace trace) { 759 if (trace == null) 760 throw new ArgumentNullException("trace"); 761 762 List<string> rules = new List<string>(); 763 StackFrame[] stack = trace.GetFrames() ?? new StackFrame[0]; 764 765 for (int i = stack.Length - 1; i >= 0; i--) { 766 StackFrame frame = stack[i]; 767 MethodBase method = frame.GetMethod(); 768 GrammarRuleAttribute[] attributes = (GrammarRuleAttribute[])method.GetCustomAttributes(typeof(GrammarRuleAttribute), true); 769 if (attributes != null && attributes.Length > 0) 770 rules.Add(attributes[0].Name); 771 } 772 773 return rules; 774 } 775 776 public virtual int BacktrackingLevel { 777 get { 778 return state.backtracking; 779 } 780 set { 781 state.backtracking = value; 782 } 783 } 784 785 /** <summary>Return whether or not a backtracking attempt failed.</summary> */ 786 public virtual bool Failed { 787 get { 788 return state.failed; 789 } 790 } 791 792 /** <summary> 793 * Used to print out token names like ID during debugging and 794 * error reporting. The generated parsers implement a method 795 * that overrides this to point to their String[] tokenNames. 796 * </summary> 797 */ 798 public virtual string[] TokenNames { 799 get { 800 return null; 801 } 802 } 803 804 /** <summary> 805 * For debugging and other purposes, might want the grammar name. 806 * Have ANTLR generate an implementation for this method. 807 * </summary> 808 */ 809 public virtual string GrammarFileName { 810 get { 811 return null; 812 } 813 } 814 815 public abstract string SourceName { 816 get; 817 } 818 819 /** <summary> 820 * A convenience method for use most often with template rewrites. 821 * Convert a List<Token> to List<String> 822 * </summary> 823 */ 824 public virtual List<string> ToStrings(ICollection<IToken> tokens) { 825 if (tokens == null) 826 return null; 827 828 List<string> strings = new List<string>(tokens.Count); 829 foreach (IToken token in tokens) { 830 strings.Add(token.Text); 831 } 832 833 return strings; 834 } 835 836 /** <summary> 837 * Given a rule number and a start token index number, return 838 * MEMO_RULE_UNKNOWN if the rule has not parsed input starting from 839 * start index. If this rule has parsed input starting from the 840 * start index before, then return where the rule stopped parsing. 841 * It returns the index of the last token matched by the rule. 842 * </summary> 843 * 844 * <remarks> 845 * For now we use a hashtable and just the slow Object-based one. 846 * Later, we can make a special one for ints and also one that 847 * tosses out data after we commit past input position i. 848 * </remarks> 849 */ 850 public virtual int GetRuleMemoization(int ruleIndex, int ruleStartIndex) { 851 if (state.ruleMemo[ruleIndex] == null) { 852 state.ruleMemo[ruleIndex] = new Dictionary<int, int>(); 853 } 854 855 int stopIndex; 856 if (!state.ruleMemo[ruleIndex].TryGetValue(ruleStartIndex, out stopIndex)) 857 return MemoRuleUnknown; 858 859 return stopIndex; 860 } 861 862 /** <summary> 863 * Has this rule already parsed input at the current index in the 864 * input stream? Return the stop token index or MEMO_RULE_UNKNOWN. 865 * If we attempted but failed to parse properly before, return 866 * MEMO_RULE_FAILED. 867 * </summary> 868 * 869 * <remarks> 870 * This method has a side-effect: if we have seen this input for 871 * this rule and successfully parsed before, then seek ahead to 872 * 1 past the stop token matched for this rule last time. 873 * </remarks> 874 */ 875 public virtual bool AlreadyParsedRule(IIntStream input, int ruleIndex) { 876 int stopIndex = GetRuleMemoization(ruleIndex, input.Index); 877 if (stopIndex == MemoRuleUnknown) { 878 return false; 879 } 880 if (stopIndex == MemoRuleFailed) { 881 //System.out.println("rule "+ruleIndex+" will never succeed"); 882 state.failed = true; 883 } else { 884 //System.out.println("seen rule "+ruleIndex+" before; skipping ahead to @"+(stopIndex+1)+" failed="+state.failed); 885 input.Seek(stopIndex + 1); // jump to one past stop token 886 } 887 return true; 888 } 889 890 /** <summary> 891 * Record whether or not this rule parsed the input at this position 892 * successfully. Use a standard java hashtable for now. 893 * </summary> 894 */ 895 public virtual void Memoize(IIntStream input, 896 int ruleIndex, 897 int ruleStartIndex) { 898 int stopTokenIndex = state.failed ? MemoRuleFailed : input.Index - 1; 899 if (state.ruleMemo == null) { 900 if (TraceDestination != null) 901 TraceDestination.WriteLine("!!!!!!!!! memo array is null for " + GrammarFileName); 902 } 903 if (ruleIndex >= state.ruleMemo.Length) { 904 if (TraceDestination != null) 905 TraceDestination.WriteLine("!!!!!!!!! memo size is " + state.ruleMemo.Length + ", but rule index is " + ruleIndex); 906 } 907 if (state.ruleMemo[ruleIndex] != null) { 908 state.ruleMemo[ruleIndex][ruleStartIndex] = stopTokenIndex; 909 } 910 } 911 912 /** <summary>return how many rule/input-index pairs there are in total.</summary> 913 * TODO: this includes synpreds. :( 914 */ 915 public virtual int GetRuleMemoizationCacheSize() { 916 int n = 0; 917 for (int i = 0; state.ruleMemo != null && i < state.ruleMemo.Length; i++) { 918 var ruleMap = state.ruleMemo[i]; 919 if (ruleMap != null) { 920 n += ruleMap.Count; // how many input indexes are recorded? 921 } 922 } 923 return n; 924 } 925 926 [Conditional("ANTLR_TRACE")] 927 public virtual void TraceIn(string ruleName, int ruleIndex, object inputSymbol) { 928 if (TraceDestination == null) 929 return; 930 931 TraceDestination.Write("enter " + ruleName + " " + inputSymbol); 932 if (state.backtracking > 0) { 933 TraceDestination.Write(" backtracking=" + state.backtracking); 934 } 935 TraceDestination.WriteLine(); 936 } 937 938 [Conditional("ANTLR_TRACE")] 939 public virtual void TraceOut(string ruleName, int ruleIndex, object inputSymbol) { 940 if (TraceDestination == null) 941 return; 942 943 TraceDestination.Write("exit " + ruleName + " " + inputSymbol); 944 if (state.backtracking > 0) { 945 TraceDestination.Write(" backtracking=" + state.backtracking); 946 if (state.failed) 947 TraceDestination.Write(" failed"); 948 else 949 TraceDestination.Write(" succeeded"); 950 } 951 TraceDestination.WriteLine(); 952 } 953 954 #region Debugging support 955 public virtual IDebugEventListener DebugListener { 956 get { 957 return null; 958 } 959 } 960 961 [Conditional("ANTLR_DEBUG")] 962 protected virtual void DebugEnterRule(string grammarFileName, string ruleName) { 963 IDebugEventListener dbg = DebugListener; 964 if (dbg != null) 965 dbg.EnterRule(grammarFileName, ruleName); 966 } 967 968 [Conditional("ANTLR_DEBUG")] 969 protected virtual void DebugExitRule(string grammarFileName, string ruleName) { 970 IDebugEventListener dbg = DebugListener; 971 if (dbg != null) 972 dbg.ExitRule(grammarFileName, ruleName); 973 } 974 975 [Conditional("ANTLR_DEBUG")] 976 protected virtual void DebugEnterSubRule(int decisionNumber) { 977 IDebugEventListener dbg = DebugListener; 978 if (dbg != null) 979 dbg.EnterSubRule(decisionNumber); 980 } 981 982 [Conditional("ANTLR_DEBUG")] 983 protected virtual void DebugExitSubRule(int decisionNumber) { 984 IDebugEventListener dbg = DebugListener; 985 if (dbg != null) 986 dbg.ExitSubRule(decisionNumber); 987 } 988 989 [Conditional("ANTLR_DEBUG")] 990 protected virtual void DebugEnterAlt(int alt) { 991 IDebugEventListener dbg = DebugListener; 992 if (dbg != null) 993 dbg.EnterAlt(alt); 994 } 995 996 [Conditional("ANTLR_DEBUG")] 997 protected virtual void DebugEnterDecision(int decisionNumber, bool couldBacktrack) { 998 IDebugEventListener dbg = DebugListener; 999 if (dbg != null) 1000 dbg.EnterDecision(decisionNumber, couldBacktrack); 1001 } 1002 1003 [Conditional("ANTLR_DEBUG")] 1004 protected virtual void DebugExitDecision(int decisionNumber) { 1005 IDebugEventListener dbg = DebugListener; 1006 if (dbg != null) 1007 dbg.ExitDecision(decisionNumber); 1008 } 1009 1010 [Conditional("ANTLR_DEBUG")] 1011 protected virtual void DebugLocation(int line, int charPositionInLine) { 1012 IDebugEventListener dbg = DebugListener; 1013 if (dbg != null) 1014 dbg.Location(line, charPositionInLine); 1015 } 1016 1017 [Conditional("ANTLR_DEBUG")] 1018 protected virtual void DebugSemanticPredicate(bool result, string predicate) { 1019 IDebugEventListener dbg = DebugListener; 1020 if (dbg != null) 1021 dbg.SemanticPredicate(result, predicate); 1022 } 1023 1024 [Conditional("ANTLR_DEBUG")] 1025 protected virtual void DebugBeginBacktrack(int level) { 1026 IDebugEventListener dbg = DebugListener; 1027 if (dbg != null) 1028 dbg.BeginBacktrack(level); 1029 } 1030 1031 [Conditional("ANTLR_DEBUG")] 1032 protected virtual void DebugEndBacktrack(int level, bool successful) { 1033 IDebugEventListener dbg = DebugListener; 1034 if (dbg != null) 1035 dbg.EndBacktrack(level, successful); 1036 } 1037 1038 [Conditional("ANTLR_DEBUG")] 1039 protected virtual void DebugRecognitionException(RecognitionException ex) { 1040 IDebugEventListener dbg = DebugListener; 1041 if (dbg != null) 1042 dbg.RecognitionException(ex); 1043 } 1044 #endregion 1045 } 1046} 1047