[antlr-interest] Confused about backtracking

Kirby Bohling kirby.bohling at gmail.com
Mon Nov 28 08:17:31 PST 2011


On Mon, Nov 28, 2011 at 9:02 AM, Christian <chwchw at gmx.de> wrote:
> Mh, I am with you. I also do not understand backtracking in this
> situation ;)
>
> Could anyone else explain it, please?

Pretty sure you are having problems because you have '.' as an
inline/generated token in your rules.  I've said it dozens of times on
this list, hopefully long time reader's don't think I'm irritating,
but if you aren't Dr. Parr, I'd highly recommend forcing generating
all tokens with Lexer rules, and never, ever generate them with inline
tokens.  I'm pretty confident that your problem is that the '.' is
generating the token in the "sep" rule, which won't match the token
generated in the "expr" rule (and only one of them will ever be
generated).  I really like the conciseness of the examples when the
inline lex rules are used, but every time I try them, it because a
problem for me.

So, the first rule is, never use inline tokens.  The second rule is
print the tokens out, and manually parse walk them through the parser.
 Every time I get stuck, and am sure the ANTLR has a bug, I remember
these rules, and then realize that I did something silly.  I don't
have an ANTLR toolchain handy so I can't try it, but I'm pretty sure
that's what is wrong.

I believe one step forward is to add a lex rule:

DOT: '.';

Then replace your inline '.' in sep and expr with that token.  I'll be
that moves you forward (not sure it will solve it).

Finally, remember, in ANTLR the lexer logically (even if it doesn't
actually) runs start to finish and generates all of the tokens.  Then
the stream of tokens are handed the parsers.  There is no backtracking
where the parser gives up, and the lexer tries other alternatives.

Kirby


>
> Am 28.11.2011 15:18, schrieb franck102:
>> Christian wrote
>>> Hi,
>>>
>>> what is the error/exception message?
>>>
>>> Regards,
>>> Christian
>>>
>>>
>> MissingTokenException at the second '=', after parsing a=b.c as an
>> expression. The tail recursion on expr is causing it it seems, but that's a
>> real issue for me... here is a slightly modified version with the recursion
>> made explicit that has the same problem:
>>
>> program
>>         : statement* EOF
>>         ;
>>
>> statement
>>         : ID '=' expr
>>         | sep
>>         ;
>>
>> expr : ID ( '.' expr )*;
>>
>> sep : ';' | '.';
>>
>> --
>> View this message in context: http://antlr.1301665.n2.nabble.com/Confused-about-backtracking-tp7033712p7038881.html
>> Sent from the ANTLR mailing list archive at Nabble.com.
>>
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>>
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>


More information about the antlr-interest mailing list