Re: How do lexical tie-ins work?

[Zachary Carter]

I forgot to reply to the list, but Joel explained well what I was missing.

On Fri, Apr 23, 2010 at 3:28 PM, Martin Alexander David Neumann <
address@hidden> wrote:

> Hi Zach,
>
> please correct me if I am wrong, but I think that a parser generated by
> bison does not use the look-ahead symbol to decide when to reduce. I
> suppose, that when the right-hand side of a production has been pushed
> onto the stack, the parser recognizes this and reduces. (If there would
> be a look-ahead in this situation that could be shifted instead of
> reduced, there is a shift/reduce conflict present.)
>

Right, apologies for my poor wording. What I mean is, when the parser is in
a given state I use the upcoming token to decide on the action to take.
Depending on the token, a shift or reduction will occur. For a shift, the
token is shifted, and I assumed the next token would immediately be peeked
to determine the next action. As Joel explains, if there is only one action
possible from the state after the shift, the next token doesn't need to be
determined yet. If the action is a reduction, the semantic action may run
(and ultimately affect what token the scanner will emit next.)

So, a state may have multiple transitions as determined by the next token,
but if there is only one transition possible, and it is by a reduction, you
don't actually need the next token yet.


>
> I am also unsure what you mean by that the parser checks the lookahead
> and than may shift a different token. I guess the parser calls the
> scanner only once for each token and in this moment the scanner may look
> at a variable set by the parser and decide which token to return.
>

Yep.


>
> In case of [1]: I suppose that bison pushes for example HEX ( onto the
> stack and recognizes that it is time to reduce. Now the semantic action
> sets the variable and the new context for the next scanner-call is well
> defined.
>

Right. My method of recognizing "it is time to reduce" was too eager. I
think I understand now. Thanks.


>
> Cheers, Alex
>
> Zachary Carter wrote:
> > I'm curious on how Bison's algorithm works wrt lexical tie-ins[1]. The
> > situation appears to me as a bit of a catch-22. The parser checks the
> > lookahead token to decide when to reduce (right?) but the semantic action
> > may alter the scanner so that the next token shifted is actually
> different
> > than what the lookahead token had been. It seems counter intuitive, but
> is
> > that really how it works?
> >
> > [1]:
> http://www.gnu.org/software/bison/manual/bison.html#Lexical-Tie_002dins
>



-- 
Zach Carter