Re: Can this grammar be modified for lookahead of 1 ?

> I am trying to generate a parser using yacc for the following grammar:
>
> s -> l (1)
> l -> L i F i e (2)
> i -> A | ACA | CA | AC | C (3)
> e -> C (4)


There are grammar rewritings possible, but they tend to destroy the
readability, or usability of the grammar. For instance, the following
grammar accepts the same language, and is LALR(1) consistent.


      s -> l
      l -> L i F i2
      i -> A | A C A | C A | A C | C
      i2 -> A C | A C A C | C A C | A C C | C C


In general, when you subsitute the alternative right parts for a
troublesome nonterminal back into the rules where it is used, then all
of the needed information to make a parsing decision can be shifted
onto the stack, and no extra lookahead information is needed. But as
you can see, this technique tends to generate a lot of long rules.


Also remember that when YACC has a hard time with a grammar, often
programmers do to. So a redesign of your language, rather than your
grammar may benefit both the programmers, and the parser generator.
--
Daniel J. Salomon -- salomon@cs.UManitoba.CA
              Dept. of Computer Science / University of Manitoba
              Winnipeg, Manitoba, Canada R3T 2N2 / (204) 474-8687
--

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