[antlr-interest] Problems with semantic predicates

Haralambi Haralambiev hharalambiev at gmail.com
Fri Apr 18 03:07:25 PDT 2008


Hello Gavin,

The problem is that the grammar that I am working on is far more complex and
the backtracking option is actually needed. Thus, I need to find a solution
that will not require disabling that option.

Using scope variables would be a great solution, but as I have stated in
another reply - how can I execute actions regardless whether the parser is
in backtracking mode or not. I.e. I need to have a similar generation as
with the @init actions, but during parsing.

So, with my initial grammar I will have something like that:
r
scope {
boolean flag;
}
: Token1^ Token2!
{$r::flag = true;}
r2
| Token1^
{$r::flag = false;}
r2
;

r2
: {$r::flag}? Token1 -> ^(NODE Token1)
| Token1
;

which generates compilable classes. But during the execution the flag is
never set, as actions such as "{$r::flag = true;}" will only execute when
"backtracking = 0".

So, a simple question - can I execute arbitrary action when
backtracking, but not on @init?


Hari

On 4/18/08, Gavin Lambert <antlr at mirality.co.nz> wrote:
>
> At 19:18 18/04/2008, Haralambi Haralambiev wrote:
>
> > However, with the syntax suggested by Gavin, the problem still persists
> > - the synpred2_fragment method still contains the "if (!flag)" statement. By
> > the way - is there somewhere I could read regarding why is this check added
> > into this method?
> >
>
> The synpreds themselves are only being generated because you have
> backtrack=true, so it's trying to hoist the predicate far enough to figure
> out whether it should be going down that path before it bothers trying (and
> possibly throwing an exception, which is bad for performance).
>
> By the way, why do you refer the flag in the predicate with "$flag"? This
> > renders an error on my side ("attribute is not a token, parameter, or return
> > value: flag"), but with "{flag}?" it doesn't fail.
> >
>
> That's because you're supposed to refer to parameters (and return values,
> and labels, etc) that way, because the code generator is free to rename it
> if it wants to.
>
> This error is actually telling you that the predicate is being hoisted
> somewhere where it won't work -- if you turn off backtracking (so that it
> doesn't create a synpred to hoist your sempred into), then this error goes
> away as well.
>
> Anyway, going back to your original grammar, there's another problem with
> it (which is presumably why you added backtracking in the first place).  In
> rule "r", you have a common left prefix, which hurts performance and
> sometimes causes incorrect behaviour (when ANTLR can't look ahead far enough
> to resolve the ambiguity).  Removing this (and disabling backtracking)
> yields a working grammar:
>
> grammar test;
>
> options {
>  output=AST;
>  ASTLabelType=CommonTree;
>  //backtrack=true;
>  //memoize=true;
> }
>
> tokens {
>  NODE;
> }
>
> r : Token1^
>    ( Token2! r2[true]
>    | r2[false]
>    )
>  ;
>
> r2[boolean flag]
>  : Token1
>    ( {$flag}? -> ^(NODE Token1)
>    | -> Token1
>    )
>  ;
>
> Token1 : 'TOKEN1';
> Token2 : 'TOKEN2';
>
>
> However even with this version, if backtracking is turned on then the
> parameter will get hoisted inappropriately again.  It looks like using
> scopes is the only answer after all, if you want to keep the backtracking
> and this particular rule structure.
>
> I'm not really sure why it still wants to hoist it in this case, since it
> has no bearing on the actual decision tree.
>
> Of course, another option is to remove the parameter altogether:
>
> r : Token1^
>    ( Token2! r2
>    | Token1
>    )
>  ;
>
> r2 : Token1 -> ^(NODE Token1) ;
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080418/17065a2d/attachment.html 


More information about the antlr-interest mailing list