[antlr-interest] predicate question

Mark Wright markwright at internode.on.net
Tue May 6 23:53:06 PDT 2008


>  >> For example, what about this case:
>  >>    rule: A {bar();} b=B ({foo($b)}? C D)? E;
> [...]
>  >Likewise for foo() needing to look at B:
>  >
>  >- An action could be introduced after consuming token B to store
>  >information about B in the symbol table, then foo() could look
>  >up the information about B in the symbol table.
>  >
>  >- foo() could scan backwards looking for B.
>  >
>  >- An action could be introduced after consuming token B to store
>  >information about B in the symbol table, and a pointer to the
>  >symbol table information could be stored in token B.  Then foo()
>  >foo() could scan backwards looking for B.
> 
> On Wed, 07 May 2008 08:24:16 +1200
> Gavin Lambert <antlr at mirality.co.nz> wrote:
>
> I don't think that will work, since if foo() is hoisted then B 
> will not yet have been consumed, and may be arbitrarily far ahead 
> in the input stream (depends on how far it got hoisted).
> 
> Mind you, it's possible ANTLR avoids this by not hoisting this 
> kind of predicate at all.  As I said, this was a bit of a 
> contrived example and I'm not entirely sure how ANTLR reacts to it.

ANTLR will only consider dis-ambiguating semantic predicates for
the alternatives starting at the current token.

So when ANTLR is trying to figure out if the alternative:

  A {bar();} b=B ({foo($b)}? C D)? E;

is the one to take amongst other ambiguous alternatives,
ANTLR does not consider the dis-ambiguating semantic predicate
{foo($B)} that is 2 tokens ahead in the input stream (unless
syntactic predicates or backtracking are used, then I am not
sure, see note below).

This can be handled with dis-ambiguating semantic predicates.
Another dis-ambiguating semantic predicate can be written,
something like:

rule:
  {(isABfooOptE()}?
  A {bar();} b=B ({foo($b)}? C D)? E;

Where isABfooOptE() looks ahead for A followed by B, possibly
looking stuff up in the symbol table, calls a method that is
shared with the foo() dis-ambiguating sempred, and looks ahead
for E.

Since dis-ambiguating semantic predicates can call arbitrary
code, they are very powerful if you do not mind writing thousands
of lines of code.

I have thousands of lines of dis-ambiguating semantic predicates
that do things like:

- scan ahead looking for tokens, while matching things like
parentheses, etc.

- looking up stuff in the symbol table.

- doing stuff like this with hand coded recursive descent
compilers.  The dis-ambiguating semantic predicates are written
in little functions that correspond to the parser rules,
they call each other while scanning ahead.

- sometimes they scan backwards one or 2 tokens, looking for a pointer
into the symbol table that was earlier stored in a token if the
token is present.

Note: Maybe you were thinking of a situation with syntactic
predicates or backtracking as well as dis-ambiguating semantic
predicates.  I am not using syntactic predicates or backtracking,
so I don't have any experience with them.  Instead I have written lots
of dis-ambiguating semantic predicates using hand coded recursive
descent compilers, which is like hand coded backtracking.  The
hand coded recursive descent compilers have the option of cheating:
they can loosely decide to match an alternative, then a compiler
error can be generated if the alternative does not really match
while it is being parsed.

Regards, Mark

--


More information about the antlr-interest mailing list