[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