[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Finding out when a token is consumed
From: |
Frank Heckenbach |
Subject: |
Re: Finding out when a token is consumed |
Date: |
Tue, 13 May 2003 01:38:59 +0200 |
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)
- Re: Finding out when a token is consumed, (continued)
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/10
- Message not available
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/09
- Re: Finding out when a token is consumed, Frank Heckenbach, 2003/05/09
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/10
- Re: Finding out when a token is consumed, Frank Heckenbach, 2003/05/10
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/10
- Re: Finding out when a token is consumed, Frank Heckenbach, 2003/05/10
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/11
- Re: Finding out when a token is consumed, Frank Heckenbach, 2003/05/11
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/12
- Re: Finding out when a token is consumed,
Frank Heckenbach <=
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/13
- Re: Finding out when a token is consumed, Frank Heckenbach, 2003/05/13
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/14
- Re: Finding out when a token is consumed, Frank Heckenbach, 2003/05/14
- Re: Finding out when a token is consumed, Hans Aberg, 2003/05/15
- include files in bison parser, Vitaliy Ziskin, 2003/05/10
- Re: include files in bison parser, Hans Aberg, 2003/05/10
Re: Finding out when a token is consumed, David Fletcher, 2003/05/09