Re: "Regular expressions" for stack automata?

>>>>> "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

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