Is Yacc LR(1)? (was Re: Can Pascal be parsed by LR(1) ?)
11 Oct 90 11:01:15 GMT

          From comp.compilers

Related articles
Is Yacc LR(1)? (was Re: Can Pascal be parsed by LR(1) ?) (1990-10-11)
| List of all articles for this month |

Newsgroups: comp.compilers
Summary: Yacc parsing Yacc input
Keywords: pascal, parse, yacc
Organization: Technical University of Vienna, AUSTRIA
References: <> <>
Date: 11 Oct 90 11:01:15 GMT

In article <>, (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

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
Fax: (++43).1.569697

Post a followup to this message

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