[antlr-interest] Re: Local lookahead depth

Mon Nov 10 12:16:09 PST 2003

I'm kinda lost catching up in this discussion but I would like to clarify a
few things:

"Guarded predicates" are simply semantic predicates "guarded" or "gated" by
a syntactic predicate.  These are in ANTLR 2 as well as PCCTS.  They are not
for allowing semantic actions during predicates.  They have the form
()=>{}?.  Unguarded predicates are much more common.

Orthogonal to the above, a prediate may be disambiguating or validating.

"Disambiguating predicates," the most common use for predicates, are
predicates used to choose between alternatives.  If the predicate fails then
try the next alternative.

"Validating predicates" are predicates that aren't in an alternative block.
Therefore if they fail you can't choose anything else.  So they throw an
exception.

The trick for having semantic actions during a predicate is to make a method
call (with side effects) as part of your test.  This is dangerous because
the predicate may still fail and you will have to undo whatever you did but
you have no easy hooks for that.  You must override mark() and rewind() to
accomplish that.

Predicates, by design, are supposed to be side effect free and execute no
actions because their reason for being is to choose the correct path to
execute.

Monty

-----Original Message-----
From: Oliver Zeigermann [mailto:oliver at zeigermann.de] 
Sent: Sunday, November 09, 2003 11:38 PM
To: antlr-interest at yahoogroups.com
Subject: [antlr-interest] Re: Local lookahead depth

--- In antlr-interest at yahoogroups.com, Oliver Zeigermann <oliver at z...>
wrote:
> John D. Mitchell wrote:
> 
> >>>>>>"Oliver" == Oliver Zeigermann <oliver at z...> writes:
> >>>>>>
> >>>>>>>lgcraymer wrote:
> > 
> > [...]
> > 
> > 
> >>>Also, as to actions in lookahead code: this is something that Ter
> >>>supported in PCCTS under the name "guarded predicates" or some
such.  I
> >>>don't know that it saw much use, and I suspect that usage
indicates a
> >>>too early incorporation of semantic information into the
> >>>translator--tree transformation helps avoid that.
> > 
> > 
> >>1.) You might really increase the set of parseable languages using
this
> >>technique
> > 
> > 
> >>From a theoretical standpoint? Nope, I can't see how you've
increased the
> > power at all.
> > 
> >>From a "what's easiest/most-efficient to do with
tool/framework/etc. XYZ"?
> > Okay.
> 
> I have to admit I really do not recall my example of a language that
can 
> not be parsed without it, but can with it. Maybe I am mistaken, but
have 
> to think about it and will deliver it as soon as I have got it :)

Still can not remember my example, but here is some illustration that
there really are languages that can not be parsed without that
extension:

1.) Using semantic predicates you can increase the set of parseable
languages. This is easy to see when you think of the symbol table
stuff: in some programming languages undeclared variables are invalid
and thus the programm you have written is. This way you have a
stronger device to tell the words in your languages from those that
are not.
2.) A bit less obvious: As I had to admit, persuaded by Terence, for
every lookahead k > 0 there are languages that can be parsed with
LL(k), but not with LL(k-1). This means no matter how big a fixed k is
there still is an infinite number of languages that can not be parsed
with LL(k), but still can with syntactic predicates.

Now, imagine a language that is so weird it needs full syntactic
predicated lookahead and additionally has context-sensitive features.
This means the symbol table must be *set* and checked inside syntactic
predicates.

If you can not set the symbol table, you can not parse a language, you
otherwise could. Thus this stuff augments the set of parseable
languages with ANTLR.

As a sidenote: I really can not imagine any *practical* application of
this, but my other example might be worth considering.

Oliver

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 