Re: Finding out when a token is consumed

[Frank Heckenbach]

Hans Aberg wrote:

> >> It would be nice with a feature that tells whether the lookahead is needed
> >> or not, so one can implement sure context switches. While at tweaking the
> >> skeleton files, there is a segment:
> >>
> >> yybackup:
> >>
> >>   // Try to make a decision without lookahead:
> >>   n_ = pact_[state_];
> >>   if (n_ == pact_ninf_)
> >>     goto yydefault;
> >>
> >>   // Read a lookahead token.
> >>   if (lookahead_ == empty_) {
> >>     YYCDEBUG << "Reading a token: ";
> >>     lex_();
> >>   }
> >>
> >> Here you can clearly determine whether a lookahead is used or not. So if
> >> you can find a good tweak for your purposes, it might be interesting for
> >> you to report to Bug Bison how you did it so that it can be used as a
> >> feature in Bison:
> >>
> >> I think it would be of general interest to get a better handling of this
> >> lookahead problem.
> >
> >Unless I'm missing something, `yychar == YYEMPTY' should do this,
> >doesn't it? I haven't tried this, except for the example in my
> >original mail, but from the description in the manual (Action
> >Features) I think it should work.
> 
> I only noticed that it should be possible to get the informatin out, but I
> do not see how that could be made a convenient feature.

Sorry, I don't understand what you mean. yychar is available to all
actions AFAIK, and checking for YYEMPTY is quite convenient, isn't
it? Am I missing something?

> >However, that's only true for parsers with at most one token of
> >look-ahead. OTOH, GRL can take an arbitrary amount of look-ahead
> >(from the prespective of the parser it's only one look-ahead token,
> >but to the semantic actions it appears like more because they're
> >delayed). So I guess this method generally won't work there.
> 
> I have not looked at it carefully, but Bison manual suggests that the GRL
> that Bison supplies is just LALR(1) with some additional branching for
> parsing ambiguities.

Yes, but exactly this makes an important difference here.

:    During the time that there are multiple parsers, semantic actions are
: recorded, but not performed. [...] Whenever the last two parsers
: merge, reverting to the single-parser case, Bison resolves all the
: outstanding actions either by precedences given to the grammar rules
: involved, or by performing both actions, and then calling a designated
: user-defined function on the resulting values to produce an arbitrary
: merged result.

So in this case, any information of look-aheads used while parsing
those rules is long gone, and the lexer may have returned many more
tokens already.

> Even though GLR is interesting, it is not as important for writing
> conventional computer languages.

Matter of definition, I guess. The manual gives an example for C++
(I'm not too familiar with the trickier aspects of C++ syntax, but
from what I read elsewhere I tend to believe that it does contain
some hard to resolve conflicts). I don't think you'd consider C++
too unconventional. ;-)

In fact, AFAIK, GLR is quite useful for such languages where the
conflicts are rather localized (i.e., they can't be decided with one
token look-ahead, but they don't spread too far, perhaps only for
one statement/declaration). In these cases, the parser is mostly
still O(n), but automatically resolves such problems which would
otherwise require rather complicated hand-written hacks. (I did the
latter in my own projects, and I know how ugly this can get, so I'm
considering GLR now.)

> >To sum it up, in case it was a little confusing: For an LALR(1)
> >parser (and probably many other ones), something like %preaction
> >should work, checking for look-ahead using `yychar == YYEMPTY'.
> 
> I think of the preaction suggestion as separate form any other feature that
> allows one to check whether the lookahead has been used. I do not see how
> this other feature might be implemented yet. This other feature should
> probably be somewhere in the yybackup segment indicated above.

I don't know exactly where you copied that from (I didn't find
`lookahead_ == empty_' in the source of 1.875 or 20030320), but both
src/parse-gram.c and data/yacc.c contain:

  /* YYCHAR is either YYEMPTY or YYEOF or a valid lookahead symbol.  */
  if (yychar == YYEMPTY)
    {
      YYDPRINTF ((stderr, "Reading a token: "));
      yychar = YYLEX;
    }

which is exactly what I've been saying all the time ...

Frank

-- 
Frank Heckenbach, address@hidden
http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)