[antlr-interest] Failed Predicate Infinite Loop

Mark Mandel mark.mandel at gmail.com
Tue Jan 25 15:04:45 PST 2011


For anyone else in a similar position, this is how I solved it in my Lexer:

Originally, my 'DESCRIPTOR' token looked like this:

DESCRIPTOR
    : {expressionStart}?=> (('a'..'z'|'A'..'Z'|'_'|'*')
('a'..'z'|'A'..'Z'|'0'..'9'|'_'|'.'|'*'|':')*)
    ;

Which was the only place my Lexer could go if 'expressionStart' was true,
and an invalid entry was entered, so it would end up getting into the
infinite loop here, as it had nowhere else to go. Hence the:
line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?

So I figured, why not give it a place to go? I switch this to:

DESCRIPTOR
    : {expressionStart}?=> (('a'..'z'|'A'..'Z'|'_'|'*')
('a'..'z'|'A'..'Z'|'0'..'9'|'_'|'.'|'*'|':')*)
    | /* give it another option so it doesn't infinite loop out when the
predicate fails */
    ;

This seemed to work well, but I can only assume it also infinite looped, as
I'd get a heap overflow.

So then I thought - well, if the predicate fails, let's just skip to the end
of the line (my inputs are always just 1 line long, so this makes it easy),
so I seek()'d the input forward to the end of the line:

DESCRIPTOR
    : {expressionStart}?=> (('a'..'z'|'A'..'Z'|'_'|'*')
('a'..'z'|'A'..'Z'|'0'..'9'|'_'|'.'|'*'|':')*)
    | /* give it another option so it doesn't infinite loop out when the
predicate fails */
    { input.seek(input.size()); }
    ;

No more infinite loops or heap overflows, and I get a nice error. Seems to
be working well for me :o)

Mark

On Tue, Jan 25, 2011 at 9:57 AM, Mark Mandel <mark.mandel at gmail.com> wrote:

> I'm trying to resolve this a different way, and catch the failed predicate,
> and handle it gracefully... however, for the life of me, I can't seem to
> catch it in any way.
>
> I tried adding a 'catch [FailedPredicateException fpe]' in my Lexer, under
> the failing token, but it seems this only works in the Parser section.
>
> I can't seem to catch this failed predicate infinite loop in the parser
> section of my grammar.
>
> So failing that, I'm attempting to find the right method in the Lexer to
> overwrite to catch the FailedPredicateException and handle it accordingly,
> but again, I can't seem to find the right place.
>
> I had thought that overwriting the recover() method on the Lexer, to
> intercept the FailedPredicate would work, but it does not seem to pass
> through there.
>
> Can anyone point me in the right direction, as to which method I should be
> overwriting to intercept the failed predicate?
>
> Mark
>
>
>
>
>
>
>
> On Mon, Jan 24, 2011 at 5:05 PM, Mark Mandel <mark.mandel at gmail.com>wrote:
>
>> Reading through the (great) ANTLR book, I see there is code in there to
>> use if you want to exit the recogniser on first error. It's not 100% ideal
>> (in case I want to ever report more than 1 error in a row in the future),
>> but I may try that out shortly.
>>
>> I would still be interested to work out how to avoid this issue in future
>> grammars.
>>
>> Mark
>>
>>
>> On Mon, Jan 24, 2011 at 4:44 PM, Mark Mandel <mark.mandel at gmail.com>wrote:
>>
>>> Hey guys,
>>>
>>> My grammar can be seen here:
>>>
>>> http://coldspring.git.sourceforge.net/git/gitweb.cgi?p=coldspring/coldspring;a=blob;f=antlr/com/coldspring/aop/expression/AopExpression.g;h=b80ef8a7ddd854458791e4e044a8f09461b66c50;hb=HEAD
>>>
>>> It's a parser for a subset of AspectJ expressions, with some minor
>>> modifications (if anyone cares ;o) ).
>>>
>>> An example expression would be:
>>> @annotation(dostuff='true')
>>>
>>> I've used predicate in my lexer to work pick up the first item in the
>>> expression, i.e. an expression should always start with 'target', '@target',
>>> 'execution', 'within' or '@annotation'
>>>
>>> If I have a typo in the expression that is being entered, e.g.
>>>
>>> @annotaion(dostuff='true')
>>>
>>> I get the following output:
>>> line 1:7 mismatched character 'i' expecting 't'
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> line 1:8 rule DESCRIPTOR failed predicate: {expressionStart}?
>>> .... (infinite loop) ....
>>>
>>> The errors are perfectly correct, but the infinite loop is a bit of a
>>> problem, as I'm sure you can understand.
>>>
>>> Is this a bug in ANTLR, or is there a way I can fix/change my grammar (or
>>> add in some custom code), so that I don't fall into the infinite loop? (or
>>> escape out of it)
>>>
>>> I'm guessing this is because ANTLR tries to recover from an error
>>> whenever it encounters one. (Which I would also be happy to turn off, I only
>>> need the 1st error for my purposes at the moment).
>>>
>>> Any help would be appreciated.
>>>
>>> Mark
>>>
>>>
>>> --
>>> E: mark.mandel at gmail.com
>>> T: http://www.twitter.com/neurotic
>>> W: www.compoundtheory.com
>>>
>>> cf.Objective(ANZ) - Nov 18, 19 - Melbourne Australia
>>> http://www.cfobjective.com.au
>>>
>>> Hands-on ColdFusion ORM Training
>>> www.ColdFusionOrmTraining.com
>>>
>>
>>
>>
>> --
>> E: mark.mandel at gmail.com
>> T: http://www.twitter.com/neurotic
>> W: www.compoundtheory.com
>>
>> cf.Objective(ANZ) - Nov 18, 19 - Melbourne Australia
>> http://www.cfobjective.com.au
>>
>> Hands-on ColdFusion ORM Training
>> www.ColdFusionOrmTraining.com
>>
>
>
>
> --
> E: mark.mandel at gmail.com
> T: http://www.twitter.com/neurotic
> W: www.compoundtheory.com
>
> cf.Objective(ANZ) - Nov 18, 19 - Melbourne Australia
> http://www.cfobjective.com.au
>
> Hands-on ColdFusion ORM Training
> www.ColdFusionOrmTraining.com
>



-- 
E: mark.mandel at gmail.com
T: http://www.twitter.com/neurotic
W: www.compoundtheory.com

cf.Objective(ANZ) - Nov 18, 19 - Melbourne Australia
http://www.cfobjective.com.au

Hands-on ColdFusion ORM Training
www.ColdFusionOrmTraining.com


More information about the antlr-interest mailing list