Re: regular expression operators in CF grammars

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.

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