Re: Technical question about yacc and LALR parsers

jar@florida.HQ.Ileaf.COM (Jim Roskind x5570) write:
>... all shifts/goto's into state k are made on the same
>terminal/nonterminal.


Not only that, but one may deduce information about tokens to the
left of the previous one also.


If we are in state N with input token t, and the action is to reduce on
lookahead token t, by a rule Y -> X1 X2 X3 ... Xn, then obviously the last
n tokens are the same for all items in state N. Likewise, for all states
with a transition to state N (whose are would be labelled Xn), the last
n-1 tokens are the same in all items in all such states. (By tokens, I
mean terminals or nonterminals, grammar symbols in general.)


This means one never needs to keep a stack of grammar symbols as described
in the Dragon Book (well, their algorithm interleaves the grammar symbols
with the states, i.e. every other stack element is a grammar symbol), it
is sufficient to keep only a stack of states, the grammar symbol stack may
be uniquely derived from there.


bb
--

Return to the comp.compilers page.
Search the comp.compilers archives again.