Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

robin (1821)

robin
  (email not shown publicly)
about:blank

Journal of robin (1821)

Monday April 01, 2002
05:01 PM

Regex power!

[ #3909 ]
I've been hacking on PCRE. I love coding in C, it's so clean and crisp and quick.

I've added an interesting extension to the syntax. Would this be a good idea for Perl?

/^\W*(?:((.)\W*(?1)\W*\2|)|((.)\W*(?3)\W*\4|\W*.\W*))\W*$/i


List all Journal entries
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Regex power! 2 Comments More | Login | Reply /

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Okay, I think you're making my brain flow out of my ears. Ow.

    You're right about it being able to match anything that a context-free grammer can match. By allowing recursion you're adding a stack to your traditional regular expression engine - basically a Finite State Automata with a stack. This is what is known as a Push Down Automata.

    Take a look at section 3.4 of the second edition of The Elements Of The Theory of Computation [amazon.co.uk] which proves that "The class of langauges accepted by pushdown automata is

    • Interesting. The bit that wasn't (and still isn't) obvious to me is that the limited kind of stack storage provided by recursion is as powerful as a full PDA. On the face of it, a PDA has more freedom with its stack. Is there a simple argument to show that it doesn't really?

      (FWIW, I've been vaguely angling for an argument based on the Chomsky-Schützenberger theorem.)

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.