16 Sep 1999 01:55:31 -0400

Related articles |
---|

"Regular expressions" for stack automata? Marko.Makela@HUT.FI (Marko =?ISO-8859-1?Q?M=E4kel=E4?=) (1999-09-10) |

Re: "Regular expressions" for stack automata? Marko.Makela@HUT.FI (Marko =?ISO-8859-1?Q?M=E4kel=E4?=) (1999-09-16) |

Re: "Regular expressions" for stack automata? world!cfc@uunet.uu.net (Chris F Clark) (1999-09-20) |

Re: "Regular expressions" for stack automata? ilya@math.ohio-state.edu (1999-09-24) |

Re: "Regular expressions" for stack automata? qjackson@wave.home.com (Quinn Tyler Jackson) (1999-10-04) |

From: | Marko =?ISO-8859-1?Q?M=E4kel=E4?= <Marko.Makela@HUT.FI> |

Newsgroups: | comp.compilers |

Date: | 16 Sep 1999 01:55:31 -0400 |

Organization: | Compilers Central |

References: | 99-09-030 |

Keywords: | parse, question |

*>>>>> "Marko" == Marko Mäkelä <Marko.Makela@HUT.FI> writes:*

Marko> Now, my questions: Has this field been researched? Is there

Marko> any grep-like tool that uses stack automata instead of finite

Marko> state automata?

I was pointed out in an e-mail message that QED (the ancestor of ed

and vi, and probably the first tool that introduced regular expression

based search and replace functions) has this. The construct is very

simple: named regular expressions. From the QED manual (see

<URL:http://cm.bell-labs.com/cm/cs/who/dmr/qed.html>):

The regular expression "\E(bal)" defined by

e(bal)/[^`']*(`\E(bal)')*[^`']*/

matches any string balanced with respect to single quotes "`" and "'".

By the way, I was very impressed that the regular expressions have

remained practically unchanged for a so long time.

John> [Many implementations of REs such as GNU grep extend the

John> REs in interesting ways with backreferences. -John]

True, but I haven't seen anything like the \E(re) construct of QED

anywhere, and \1..\9 cannot express the same thing. I wonder how well

Perl regular expressions would perform with this construct. I would

expect especially the non-greedy closure operators *? and +? to be

utterly inefficient with this construct.

Marko

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.