Is Yacc LR(1)? (was Re: Can Pascal be parsed by LR(1) ?)

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
--

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