Re: "Regular expressions" for stack automata?

[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 non-greedy closure operators *? and +? to be
> utterly inefficient with this construct.


Why?


Ilya

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