|Can this grammar be modified for lookahead of 1 ? email@example.com (1994-08-15)|
|Can this grammar be modified for lookahead of 1 ? firstname.lastname@example.org (1994-08-18)|
|Re: Can this grammar be modified for lookahead of 1 ? email@example.com (1994-08-18)|
|Re: Can this grammar be modified for lookahead of 1 ? David=Cook%Diag%Mfg=Hou@bangate.compaq.com (1994-08-19)|
|From:||firstname.lastname@example.org (Daniel J. Salomon)|
|Organization:||Computer Science, University of Manitoba, Winnipeg, Canada|
|Date:||Thu, 18 Aug 1994 17:27:41 GMT|
> 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
Search the comp.compilers archives again.