Re: Extended CFGs

Ralph Boland asked:
> I am developing a parser generator tool which supports regular
> expressions on the lefthand side of productions. My task is made
> somewhat simpler if I disallow nullable production left hand sides. I
> have been trying to come up with reasons why this might be a bad idea.


As far as I can tell, regexp operator are good for lists, but don't do
as well for binary trees (e.g. expressions). Thus, one place one can
wnat a nullable rule is in a set of binary tree rules. For example,
consider the case where one has both binary and unary operators using
the same symbol.


expr: expr "-" expr | "-" expr | ...;


There are times one might want to write this as:


expr: expr "-" expr | /* empty */ | ...;


In the regexp version this might even be written:


expr: expr ("-" expr)+ | /* empty */ | ...;


Another situation worth considering is when the grammar writer has
some action they want performed in the null case. This works better
as:


foo : optbar bletch;
optbar: bar | /* empty */ {no-bar-action();} ;


than:


foo: bar? bletch; // where to put no-bar-action();


or even than:


for: ( bar | {no-bar-action();} ) bletch;


Note, in each of the above cases one can write the same grammar
without a nullable symbol (isn't there a proof, that the only case one
really needs is "goal: /* empty */;" and all else can be handled by
transformations). However, rewriting grammars is an error prone
activity. One of the points of using regexp's is to make life easier
for the grammar writer. It seems a little pointless to give with one
hand and take away with the other, unless there is no other choice.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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