[antlr-interest] Re: Local lookahead depth

[Oliver Zeigermann]

John D. Mitchell wrote:
>>>>>>"Oliver" == Oliver Zeigermann <oliver at zeigermann.de> writes:
> 
> 
> [...necessity of guarded predicates...]
> 
> 
>>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.
> 
> 
> You still haven't shown how the "guarded predicates" are *necessary* to
> understanding that type of language.  

Ooops, I though I had shown necessity?! Where is the missing piece?

 > Now, you may be getting at an example
 > where you need them iff you need to do all of this in the parser (i.e.,
 > without using any later stages).

What do you mean with later stages? ASTs? A turing machine? Of course 
when you augment your system with a turing machine it can parse any 
phrase structure language with - say - a DFA ;) See what I mean?

Oliver



 

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