[antlr-interest] FailedPredicateException leads to infinite loop - bug in the Lexer?

Cliff Hudson cliff.s.hudson at gmail.com
Mon Mar 29 20:19:46 PDT 2010


I have been trying to work through an issue with an infinite loop caused
when no tokens can be matched because a predicate has failed its test.  The
problem appears to be in the Lexer.NextToken() (looking at CSharp2 sources)
method, which I have copied here for reference:

		/// <summary>
		/// Return a token from this source; i.e., Match a token on the char stream.
		/// </summary>
		public virtual IToken NextToken()
		{
			while (true)
			{
				state.token = null;
				state.channel = Token.DEFAULT_CHANNEL;
				state.tokenStartCharIndex = input.Index;
				state.tokenStartCharPositionInLine = input.CharPositionInLine;
				state.tokenStartLine = input.Line;
				state.text = null;
				if (input.LA(1) == (int)CharStreamConstants.EOF)
				{
					return Token.EOF_TOKEN;
				}
				try
				{
					mTokens();
					if (state.token == null)
					{
						Emit();
					}
					else if (state.token == Token.SKIP_TOKEN)
					{
						continue;
					}
					return state.token;
				}
				catch (NoViableAltException nva) {
					ReportError(nva);
					Recover(nva); // throw out current char and try again
				}
				catch (RecognitionException re) {
					ReportError(re);
					// Match() routine has already called Recover()
				}
			}
		}

Note the RecognitionException clause.  This is the clause which will
catch the FailedPredicateException().  Unfortunately, because the
FailedPredicateException gets thrown just before Match() occurs in the
rule, Recover will *not* have been called by the rule or its callees,
and therefore the DFA will continue to try processing the same token.
It would appear that there should instead be a specific
FailedPredicateException clause which does the same thing as the
NoViableAltException clause.

I have seen two other people ask questions about this error, and in
neither case was a suitable response given.  Has this bug been fixed
in non-released builds?  Can someone give me an up-or-down on whether
this is a correct and appropriate fix?

Thanks.

- Cliff


More information about the antlr-interest mailing list