Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!compilers-sender
From: bliss@sp64.csrd.uiuc.edu (Brian Bliss)
Newsgroups: comp.compilers
Subject: Re: Technical question about yacc and LALR parsers
Keywords: yacc, parse, errors
Message-ID: <1991Apr22.233526.28890@csrd.uiuc.edu>
Date: 22 Apr 91 23:35:26 GMT
References: <9104210204.AA07587@florida.HQ.Ileaf.COM>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: bliss@sp64.csrd.uiuc.edu (Brian Bliss)
Organization: Center for Supercomputing Research and Development
Lines: 24
Approved: compilers@iecc.cambridge.ma.us

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 
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.