Re: An Odd Grammar Question

Chris Dodd <>
18 May 1998 00:12:40 -0400

          From comp.compilers

Related articles
An Odd Grammar Question (1998-05-15)
Re: An Odd Grammar Question (Vadim Maslov) (1998-05-17)
Re: An Odd Grammar Question (Joachim Durchholz) (1998-05-18)
Re: An Odd Grammar Question (Chris Dodd) (1998-05-18)
Re: An Odd Grammar Question (1998-05-23)
| List of all articles for this month |

From: Chris Dodd <>
Newsgroups: comp.compilers
Date: 18 May 1998 00:12:40 -0400
Organization: ETC
References: 98-05-088
Keywords: yacc, parse

William Moran wrote:
> I have the following odd Yacc problem. Assume that we have three kinds of
> productions (key words are in caps):
> read -> READ some_stuff END-READ
> if -> IF some-stuff END-IF
> foo -> END-ALL FOO some-stuff END-FOO
> the problem is that the END-ALL terminates and replaces all of the other
> ENDs one would expect. So,
> READ ...
> READ ...
> READ ...
> i.e. we would have been expecting 3 END-READs, and instead we got 1 END-ALL,
> and this is legal. Anyone know of an easy way to express this sort of
> thing in Yacc?

One `trick' that you can do with YACC (specifically), is to just make
the END-SPECIFIC tokens optional and make the END-ALL token its own
(noop) statement that's only valid at the top level:

top_level: /* empty */ | top_level statement | top_level END_ALL ;

statment_list: /* empty */ | statement_list statement ;

statement: READ some_stuff statement_list opt_END_READ ;
opt_END_READ: /* empty */ | END_READ ;

...and so forth.

This will lead to LOTS of shift/reduce conflicts -- basically anywhere
an END_XXX could appear, you'll get a shift/reduce conflict between
reduce empty -> opt_END_XXX and some shift, but the default resolution
(shift) will do the right thing.

You'll also get the ability to `close off' multiple levels by using the
`wrong' END-XXX token, eg:

READ ...
READ ...
IF ...

The END-READ here will end the `IF' as well as the second `READ', but
not the first one. Of course, this may not be what you want -- it's
nice to require the matching END statements so as to avoid typos...

Chris Dodd

Post a followup to this message

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