|Is Yacc LR(1)? (was Re: Can Pascal be parsed by LR(1) ?) firstname.lastname@example.org (1990-10-11)|
|Summary:||Yacc parsing Yacc input|
|Keywords:||pascal, parse, yacc|
|Organization:||Technical University of Vienna, AUSTRIA|
|Date:||11 Oct 90 11:01:15 GMT|
In article <9010101445.AA06181@dynamo.ecn.purdue.edu>, email@example.com (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
| rule grammar
| rule ';' grammar
rule: 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).
Michael K. Gschwind, Institute for VLSI-Design, Technical University, Vienna
Voice: (++43).1.58801 8144
Return to the
Search the comp.compilers archives again.