Re: Lexical feedback and lookahead

[Hans Aberg]

On 20 Jul 2005, at 09:21, Evan Lavelle wrote:
> > It seems me that you know that a function has been completed when  
> > the  function body top level "{" ... "}" has completed. This can  
> > be kept  track of by a bracket depth count in the lexer.
>
> Unfortunately, the real grammar is much more complex and counting  
> brackets normally isn't adequate. Besides, if I could do this, it  
> would be easier just to use start states in the lexer: I need  
> StartStates++, which is lexical feedback from the parser.

Only you can decide what method works best for you.


> > > Any ideas? It seems to me that I need an 'unget' implementation.
> > In Bison, it is called %glr.
>
> They don't do the same thing. Feedback, if it worked, could be used  
> as a general solution to eliminate keywords.

If you want something like that, I guess you will have work out how  
it should be implemented into Bison. The parser isn't easy to tweak.  
It stacks states, not tokens, so you will have to reverse that process.

> GLR/unlimited lookahead could, in principle, do the same thing, but  
> it's much less general, much less efficient, and it's more  
> difficult to design the language in the first place. Consider this  
> pseudo-grammar:
>
> top : keywords_top ;
> keywords_top : lots_of_keywords | NAME ;
> keyword1 : more_keywords | NAME ;
> keyword2 : even_more_keywords | NAME ;
> ...
>
> How do you do this in GLR? It's trivial with working feedback, and  
> you can recycle keywords at different levels of the grammar.

I am not sure what you are saying here. You should just plug it in,  
and then you will have to merge some actions at suitable places. The  
point with GLR, relative pother forms of non-deterministic parsing,  
is that it is fairly efficient, as it merges parse splits as soon as  
possible. I haven't used it, though, so some other fellow will have  
to help yu on more details.

I had a grammar, where the two methods I indicated came up: EIther  
use a context sensitive switch, and within that use bracket depth or  
some tweak like that. Or the alternative would have been to use GLR.  
But as it happened, I made a different grammar, where these  
constructs are no longer present, though the question may arise again.

You may also ask in the newsgroup comp.compilers for more inputs.

  Hans Aberg