Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!olivea!mintaka!spdcc!esegue!compilers-sender
From: mike@vlsivie.at
Newsgroups: comp.compilers
Subject: Is Yacc LR(1)? (was Re: Can Pascal be parsed by LR(1) ?)
Summary: Yacc parsing Yacc input
Keywords: pascal, parse, yacc
Message-ID: <1907@tuvie>
Date: 11 Oct 90 11:01:15 GMT
References: <9010091533.AA02386@apple.com> <9010101445.AA06181@dynamo.ecn.purdue.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: mike@vlsivie.at
Organization: Technical University of Vienna, AUSTRIA
Lines: 43
Approved: compilers@esegue.segue.boston.ma.us

In article <9010101445.AA06181@dynamo.ecn.purdue.edu>, hankd@dynamo.ecn.purdue.edu (Hank Dietz) writes:
> Also, YACC builds LALR(1) parsers, not LR(1).  I vaguely recall one of
> Johnson's own papers saying something about a YACC-generated parser
> not being able to parse YACC input because YACC input is LALR(2)...
> so I'm not so sure that LALR(1) is equivalent to LALR(k).  Or perhaps
> the "convolutions" are VERY "unpleasant"?

The problem with Yacc grammars is that the final ';' may be omitted. 
Now you get a shift reduce conflict on (the very simplified) Yacc input 
grammar: 
	| rule grammar
	| rule ';' grammar 

rule: symbol ':' symbols 

symbols: 
	symbol symbols

You can solve this by using look-ahead in the Lex specs: 

[a-z]+				return SYMBOL;
[a-z]+/:			return LEFT_SYMBOL;

and now change the 'rule' rule:

rule: left_symbol ':' symbols

Most non-LR(1) grammars are rather simple deviations from LR(1) -
(or they wouldn't be very readable) and can be handled by Lex 
look-ahead (or - worst case - Lex states).

				bye,
					mike

Michael K. Gschwind, Institute for VLSI-Design, Technical University, Vienna
mike@vlsivie.at
mike@vlsivie.uucp
e182202@awituw01.bitnet
Voice: (++43).1.58801 8144
Fax:   (++43).1.569697
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.