Re: An Odd Grammar Question

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 ...
> END-ALL
>
> 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 ...
END-READ


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
chrisd@etcons.com
--

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