[antlr-interest] Re: Local lookahead depth

[Oliver Zeigermann]

--- 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/