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
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 which proves that "The class of langauges accepted by pushdown automata is exactly the class of context-free langauges".
Re:Proof of context-free-ness
robin on 2002-04-02T09:21:45
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.)
