Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!compilers-sender
From: mauney@eos.ncsu.edu (Dr. Jon Mauney)
Newsgroups: comp.compilers
Subject: Re: Technical question about yacc and LALR parsers
Keywords: yacc, parse, errors
Message-ID: <1991Apr22.141854.21330@ncsu.edu>
Date: 22 Apr 91 14:18:54 GMT
References: <9104210204.AA07587@florida.HQ.Ileaf.COM>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: mauney@eos.ncsu.edu (Dr. Jon Mauney)
Organization: Project EOS - North Carolina State University
Lines: 33
Approved: compilers@iecc.cambridge.ma.us
Posted-Date: Mon, 22 Apr 1991 14:18:54 GMT

> ...  Note that the following is possible (I think):
> 
> state 747
> 	gathered_type : '[' VOID . ']'
>	gathered_type : '(' VOID . ')'

This is not possible using the normal LALR construction, for the
reason you mentioned: transition into a state is due to shifting
of a single symbol. Therefore all configurations must have the
same symbol to the right of the dot.  The same must be true of
the state previous to that:  The predecessor of the given state 747
would have had to contain
 	gathered_type : '[' . VOID  ']'
	gathered_type : '(' . VOID  ')'
which has been shown to be impossible.

The only way that items can differ in the left context is
for one to be contained in the other.  For example,
given the grammar
  A --> x B
  A --> x y z
  B --> y w
the CFSM wil l contain the state
  A --> x y . z
  B --> y . w

--
Jon Mauney,  parsing partisan
Computer Science Dept.
N.C. State University
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.