Re: Extended CFGs

Chris F Clark <>
3 Feb 2006 18:37:18 -0500

          From comp.compilers

Related articles
Extended CFGs (Ralph Boland) (2006-02-02)
Re: Extended CFGs (Chris F Clark) (2006-02-03)
Re: Extended CFGs (SM Ryan) (2006-02-03)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:37:18 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 06-02-013
Keywords: parse
Posted-Date: 03 Feb 2006 18:37:18 EST

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

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


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 Clark Internet :
Compiler Resources, Inc. Web Site :
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

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