Re: regular expression operators in CF grammars

"Ralph Boland" <rboland@unb.ca>17 Jun 2002 00:12:39 -0400

From comp.compilers

Related articles
Compiler books for beginners? bart@dynarec.com (2002-05-27)
Re: Compiler books for beginners? rboland@unb.ca (Ralph Boland) (2002-05-27)
Re: regular expression operators in CF grammars parsersinc@yahoo.com (SLK Parsers) (2002-06-13)
Re: regular expression operators in CF grammars neelk@alum.mit.edu (Neelakantan Krishnaswami) (2002-06-14)
Re: regular expression operators in CF grammars rboland@unb.ca (Ralph Boland) (2002-06-17)
Re: regular expression operators in CF grammars cfc@world.std.com (Chris F Clark) (2002-06-17)
Re: regular expression operators in CF grammars kgw-news@stiscan.com (2002-06-20)
Re: regular expression operators in CF grammars kgw-news@stiscan.com (2002-06-28)
Re: regular expression operators in CF grammars parsersinc@yahoo.com (SLK Parsers) (2002-06-28)
Re: regular expression operators in CF grammars parsersinc@yahoo.com (SLK Parsers) (2002-06-28)
Re: regular expression operators in CF grammars soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2002-06-28)
[14 later articles]
| List of all articles for this month |

 From: "Ralph Boland" Newsgroups: comp.compilers Date: 17 Jun 2002 00:12:39 -0400 Organization: University of New Brunswick References: 02-05-142 02-05-151 02-06-024 02-06-044 Keywords: parse Posted-Date: 17 Jun 2002 00:12:39 EDT

Neelakantan Krishnaswami wrote:

> For me, writing functions that encapsulated common patterns greatly
> simplified the parser and made it much more readable. All but one of
> those common patterns were the regular operators: +, *, ?. (The one
> was bracketed, delimited sequences, like '(x, y, z)' or '{foo; bar;
> baz}'.)

> I found that this also made the grammar easier to understand, because
> there were fewer productions in it.
> Neel Krishnaswami

Bracked delimited sequences could be simplified somewhat using the list
operator "a ^ b" ==> a (ba)*.

Thus id (',' id)* can be shortened to id ^ ','

and id ('*' id)* ('+' (id ('*' id)*) can be shortened to id ^ '*' ^ '+'.

Anybody want to guess what id ^ exp ^ '*' ^ '+' corresponds to.

The list operator can also be implemented very efficiently
since first, last, and follow sets are easy to compute for this operator.

What I don't know is the origin of this operator.
I am developing a parser generator tool that supports this operator and
I would like to reference the originator of this operator.

So who is he/she/they?

Meanwhile if there are other regular expression operators that are
useful for parsing I would be interested in knowing; I will consider
implementing them.

Neel's bracketed delimited sequence operator doesnt' seem common
enough to be worth implementing to me. However my parser generator
tool will (eventually) support the ability to add new regular expression
operators dynamically so Need could define it if he wanted to.

Hope this help Neels and thanks to those who can answer my questions.

Ralph Boland.

Post a followup to this message