Related articles 

"Regular expressions" for stack automata? Marko.Makela@HUT.FI (Marko =?ISO88591?Q?M=E4kel=E4?=) (19990910) 
Re: "Regular expressions" for stack automata? Marko.Makela@HUT.FI (Marko =?ISO88591?Q?M=E4kel=E4?=) (19990916) 
Re: "Regular expressions" for stack automata? world!cfc@uunet.uu.net (Chris F Clark) (19990920) 
Re: "Regular expressions" for stack automata? ilya@math.ohiostate.edu (19990924) 
Re: "Regular expressions" for stack automata? qjackson@wave.home.com (Quinn Tyler Jackson) (19991004) 
From:  ilya@math.ohiostate.edu (Ilya Zakharevich) 
Newsgroups:  comp.compilers 
Date:  24 Sep 1999 22:57:43 0400 
Organization:  Department of Mathematics, The Ohio State University 
References:  9909030 9909050 
Keywords:  parse 
[A complimentary Cc of this posting was sent to Marko Mäkelä
<Marko.Makela@HUT.FI>], who wrote:
> The regular expression "\E(bal)" defined by
>
> e(bal)/[^`']*(`\E(bal)')*[^`']*/
>
> matches any string balanced with respect to single quotes "`" and "'".
In Perl (starting from 5.005_53) it is
$bal = qr{ [^`']* ( ` (?p{ $bal }) ' )* [^`']* }x;
but in this form it is not very efficient. Probably you want
something like
$bal = qr{
(?>
(
(?> [^`']+ )

` (?p{ $bal }) '
)*
)
}x;
which would not backtrack.
> By the way, I was very impressed that the regular expressions have
> remained practically unchanged for a so long time.
Then you did not follow...
> 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 nongreedy closure operators *? and +? to be
> utterly inefficient with this construct.
Why?
Ilya
Return to the
comp.compilers page.
Search the
comp.compilers archives again.