# Recursive brace matching with Ruby regexp

**URL:** <https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612>\
**Category:** ruby-talk\
**Created:** [5 November 2004 00:04 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612 "2004-11-05T00:04:30Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jason\_Sweat](https://avatars.discourse-cdn.com/v4/letter/j/53a042/32.png) [@Jason\_Sweat](https://rubytalk.org/u/Jason_Sweat)\
**Post date:** [5 November 2004 00:04 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/1 "2004-11-05T00:04:30Z")

</div>

I wanted to learn Ruby, so I picked a small task of trying to write a  
command line script to parse PHP classes and shell out some unit test  
cases. I have it working for the most part, but I ran across a  
problem trying to use Ruby regexp to find a set of matching curly  
braces.

Please forgive the intrusion of this PHP code onto the list, but I  
wanted to give you the flavor of what I am attempting to do, that can  
be easily done with recursive regular expression available in the Perl  
compatiable regexp engine.

\<php\>  
$test = \<\<\<EOS  
/\* some stuff \*/  
class foo {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public \$var;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function \_\_construct() {}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function bar() {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (false) {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}

}  
// some other stuff  
EOS;

$re = \<\<\<EOS  
~(class\s+\w+\s+({((?\>[^{}]+)|(?2))\*}))~xms  
EOS;  
preg\_match($re, $test, $match);  
echo "your class matched:\n", $match[1];

\</php\>

Now it appears the regexp engine in Ruby does not support recursion  
(at least in Ruby ruby 1.8.2 (2004-07-29) [i686-linux] that I am  
working on, and with what I know how to test), thus the only  
workaround I found was very ugly, model the nesting of braces to a  
fixed depth, i.e.

open = '\{'  
close = '\}'  
other = '[^\{\}]\*'  
l1 = other+open+other+close+other  
l2 = other+open+'('+l1 +')+'+other+close+other  
l3 = other+open+'('+l2 +')+'+other+close+other  
l4 = other+open+'('+l3 +')+'+other+close+other  
l5 = other+open+'('+l4 +')+'+other+close+other  
re = Regexp.new('class\s+'+@name+'\s+'+open+'((?:'+l5+')|(?:'+l4+')|(?:'+l3+')|(?:'+l2+')|(?:'+l1+')|(?:'+other+  
'))+'+close, 'ixm')

This code did work, but sometimes timed out on valid real classes.

I expect I am probably missing some facet of Ruby that eaily allows me  
to next regexp inside of the Ruby code in some fasion to achieve the  
result I am looking for, but how to do so eludes me. Can anyone  
provide some insight for me on this situation?

Thanks,

Regards,  
Jason

> **···**
>
> --  
> [http://blog.casey-sweat.us/](http://blog.casey-sweat.us/)

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [5 November 2004 00:49 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/2 "2004-11-05T00:49:41Z")

</div>

Ruby's regex engine doesn't yet support this, but will in future versions.

Hope that helps.

James Edward Gray II

> **···**
>
> On Nov 4, 2004, at 6:04 PM, Jason Sweat wrote:
> 
> > I expect I am probably missing some facet of Ruby that eaily allows me  
> > to next regexp inside of the Ruby code in some fasion to achieve the  
> > result I am looking for, but how to do so eludes me. Can anyone  
> > provide some insight for me on this situation?

---

<div class="post-metadata">

**Author:** ![Mark\_Hubbart1](https://avatars.discourse-cdn.com/v4/letter/m/a3d4f5/32.png) [@Mark\_Hubbart1](https://rubytalk.org/u/Mark_Hubbart1)\
**Post date:** [5 November 2004 02:04 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/3 "2004-11-05T02:04:08Z")

</div>

Hi,

> I wanted to learn Ruby, so I picked a small task of trying to write a  
> command line script to parse PHP classes and shell out some unit test  
> cases. I have it working for the most part, but I ran across a  
> problem trying to use Ruby regexp to find a set of matching curly  
> braces.
> 
> Please forgive the intrusion of this PHP code onto the list, but I  
> wanted to give you the flavor of what I am attempting to do, that can  
> be easily done with recursive regular expression available in the Perl  
> compatiable regexp engine.
> 
> \<php\>  
> $test = \<\<\<EOS  
> /\* some stuff \*/  
> class foo {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public \$var;  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function \_\_construct() {}  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function bar() {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (false) {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
> 
> }  
> // some other stuff  
> EOS;
> 
> $re = \<\<\<EOS  
> ~(class\s+\w+\s+({((?\>[^{}]+)|(?2))\*}))~xms  
> EOS;  
> preg\_match($re, $test, $match);  
> echo "your class matched:\n", $match[1];
> 
> \</php\>
> 
> Now it appears the regexp engine in Ruby does not support recursion  
> (at least in Ruby ruby 1.8.2 (2004-07-29) [i686-linux] that I am  
> working on, and with what I know how to test), thus the only  
> workaround I found was very ugly, model the nesting of braces to a  
> fixed depth, i.e.
> 
> open = '\{'  
> close = '\}'  
> other = '[^\{\}]\*'  
> l1 = other+open+other+close+other  
> l2 = other+open+'('+l1 +')+'+other+close+other  
> l3 = other+open+'('+l2 +')+'+other+close+other  
> l4 = other+open+'('+l3 +')+'+other+close+other  
> l5 = other+open+'('+l4 +')+'+other+close+other  
> re = Regexp.new('class\s+'+@name+'\s+'+open+'((?:'+l5+')|(?:'+l4+')|(?:'+l3+')|(?:'+l2+')|(?:'+l1+')|(?:'+other+  
> '))+'+close, 'ixm')
> 
> This code did work, but sometimes timed out on valid real classes.
> 
> I expect I am probably missing some facet of Ruby that eaily allows me  
> to next regexp inside of the Ruby code in some fasion to achieve the  
> result I am looking for, but how to do so eludes me. Can anyone  
> provide some insight for me on this situation?

Regular expressions, by all standard definitions, aren't recursive.  
Perl's regexen have been extended to allow it, but it really isn't  
considered a standard regex feature. You might try using a simple  
tokenizer... here's a quick attempt:

def parse(code)  
&nbsp;&nbsp;chunks =   
&nbsp;&nbsp;loop do  
&nbsp;&nbsp;&nbsp;&nbsp;chunks \<\< text.slice!(/\A.\*?(?=[{}])/m) # match start of string to  
before next bracket  
&nbsp;&nbsp;&nbsp;&nbsp;bracket = text.slice! 0  
&nbsp;&nbsp;&nbsp;&nbsp;chunks \<\< parse(text) if bracket == ?{  
&nbsp;&nbsp;&nbsp;&nbsp;return chunks if bracket == ?}  
&nbsp;&nbsp;&nbsp;&nbsp;return chunks if text.size == 0  
&nbsp;&nbsp;end  
end

This returns a recursive array that holds all the text chunks around  
the brackets. here's some sample code (can't remember exactly what php  
looks like ATM) and sample output:

PHP code:

class Foo {  
&nbsp;&nbsp;def bar(){  
&nbsp;&nbsp;&nbsp;&nbsp;if true{  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do\_stuff()  
&nbsp;&nbsp;&nbsp;&nbsp;}else{  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do\_nothing()  
&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;clean\_up()  
&nbsp;&nbsp;}  
}

Then, after recursively stripping whitespace from strings, the  
pretty-printed array:

["class Foo",  
["def bar()",  
&nbsp;&nbsp;["if true", ["do\_stuff()"], "else", ["do\_nothing()"], "clean\_up()"],  
&nbsp;&nbsp;""],  
nil]

uh, yeah, I know it drops off the last piece of text (reads it as nil)  
but I don't want to figure that out just yet. Dinner calls 🙂

HTH,  
Mark

> **···**
>
> On Fri, 5 Nov 2004 09:04:30 +0900, Jason Sweat \<jason.sweat@gmail.com\> wrote:
> 
> > Thanks,
> > 
> > Regards,  
> > Jason  
> > --  
> > [http://blog.casey-sweat.us/](http://blog.casey-sweat.us/)

---

<div class="post-metadata">

**Author:** ![Bill\_Kelly](https://avatars.discourse-cdn.com/v4/letter/b/cc9497/32.png) [@Bill\_Kelly](https://rubytalk.org/u/Bill_Kelly)\
**Post date:** [5 November 2004 01:39 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/4 "2004-11-05T01:39:11Z")

</div>

> \> I expect I am probably missing some facet of Ruby that eaily allows me  
> \> to next regexp inside of the Ruby code in some fasion to achieve the  
> \> result I am looking for, but how to do so eludes me. Can anyone  
> \> provide some insight for me on this situation?
> 
> Ruby's regex engine doesn't yet support this, but will in future  
> versions.

Just for fun,

dat = \<\<-"END\_TEXT"  
/\* some stuff \*/  
class foo {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public \$var;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function \_\_construct() {}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function bar() {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (false) {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}

}  
// some other stuff  
END\_TEXT

repl =   
true while dat.gsub!(/\([^(){}]\*\)|\{[^(){}]\*\}/) do |str|  
&nbsp;&nbsp;repl.push(str)  
&nbsp;&nbsp;"\0#{repl.length - 1}\0"  
end  
dat.scan(/class\s+\w+\s+\0\d+\0/) do  
&nbsp;&nbsp;match = $&  
&nbsp;&nbsp;true while match.gsub!(/\0(\d+)\0/) { repl[$1.to\_i] }  
&nbsp;&nbsp;puts "Your class matched:", match  
end

The above matches arbitrarily deeply nested ( ) and { }  
blocks... but all the "classes" it matches have to be  
at toplevel, can't be inside a { } or ( ) themselves...

I don't think it would be hard to modify to handle nested  
classes, but I haven't thought it through...

In case it's not obvious how it works... It replaces,  
from innermost to outermost, () and {} spans with a  
token, and saves the original span in an array.

When it finds a class match followed by one of these  
tokens, it expands it back out to its original  
representation.

Regards,

Bill

> **···**
>
> From: "James Edward Gray II" \<james@grayproductions.net\>
> 
> > On Nov 4, 2004, at 6:04 PM, Jason Sweat wrote:

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [5 November 2004 03:17 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/5 "2004-11-05T03:17:01Z")

</div>

Of course, you are correct. However, recursive "Regular Expressions" are becoming fairly common place now. Ruby's next regex engine will support them as well.

Regular Expression has evolved considerably from the original definition, with recursive capabilities being just another change in a long line of added usefulness. Does that really means they cease to be Regular Expressions? Longhorn will still be Windows, right?

I think of it more in terms of supersets or, for a programming slant, subclassing. The spirit of Regular Expressions, patterns to locate/breakdown text, is intact, I believe. They're just even more handy now.

Just my two cents.

James Edward Gray II

P.S. Proving whether or not Perl 6 changes will still be "Regular Expression" is left as an exercise for the reader. 😉

> **···**
>
> On Nov 4, 2004, at 8:04 PM, Mark Hubbart wrote:
> 
> > Regular expressions, by all standard definitions, aren't recursive.  
> > Perl's regexen have been extended to allow it, but it really isn't  
> > considered a standard regex feature.

---

<div class="post-metadata">

**Author:** ![gabriele\_renzi](https://avatars.discourse-cdn.com/v4/letter/g/e19b73/32.png) [@gabriele\_renzi](https://rubytalk.org/u/gabriele_renzi)\
**Post date:** [5 November 2004 09:53 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/6 "2004-11-05T09:53:46Z")

</div>

Mark Hubbart ha scritto:

> Hi,
> 
> > I wanted to learn Ruby, so I picked a small task of trying to write a  
> > command line script to parse PHP classes and shell out some unit test  
> > cases. I have it working for the most part, but I ran across a  
> > problem trying to use Ruby regexp to find a set of matching curly  
> > braces.
> > 
> > Please forgive the intrusion of this PHP code onto the list, but I  
> > wanted to give you the flavor of what I am attempting to do, that can  
> > be easily done with recursive regular expression available in the Perl  
> > compatiable regexp engine.
> > 
> > \<php\>  
> > $test = \<\<\<EOS  
> > /\* some stuff \*/  
> > class foo {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public \$var;  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function \_\_construct() {}  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function bar() {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (false) {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
> > 
> > }  
> > // some other stuff  
> > EOS;
> > 
> > $re = \<\<\<EOS  
> > ~(class\s+\w+\s+({((?\>[^{}]+)|(?2))\*}))~xms  
> > EOS;  
> > preg\_match($re, $test, $match);  
> > echo "your class matched:\n", $match[1];
> > 
> > \</php\>
> > 
> > Now it appears the regexp engine in Ruby does not support recursion  
> > (at least in Ruby ruby 1.8.2 (2004-07-29) [i686-linux] that I am  
> > working on, and with what I know how to test), thus the only  
> > workaround I found was very ugly, model the nesting of braces to a  
> > fixed depth, i.e.
> > 
> > open = '\{'  
> > close = '\}'  
> > other = '[^\{\}]\*'  
> > l1 = other+open+other+close+other  
> > l2 = other+open+'('+l1 +')+'+other+close+other  
> > l3 = other+open+'('+l2 +')+'+other+close+other  
> > l4 = other+open+'('+l3 +')+'+other+close+other  
> > l5 = other+open+'('+l4 +')+'+other+close+other  
> > re = Regexp.new('class\s+'+@name+'\s+'+open+'((?:'+l5+')|(?:'+l4+')|(?:'+l3+')|(?:'+l2+')|(?:'+l1+')|(?:'+other+  
> > '))+'+close, 'ixm')
> > 
> > This code did work, but sometimes timed out on valid real classes.
> > 
> > I expect I am probably missing some facet of Ruby that eaily allows me  
> > to next regexp inside of the Ruby code in some fasion to achieve the  
> > result I am looking for, but how to do so eludes me. Can anyone  
> > provide some insight for me on this situation?
> 
> Regular expressions, by all standard definitions, aren't recursive.  
> Perl's regexen have been extended to allow it, but it really isn't  
> considered a standard regex feature. You might try using a simple  
> tokenizer... here's a quick attempt:

I wonder if someone ever looked at the ABNF module on raa. It is a tool to generate a parser for a grammar in augmented backus naur form... the parser is a Regexp object, so it seem thgere is some general way to handle recursive parsing needs..

> **···**
>
> > On Fri, 5 Nov 2004 09:04:30 +0900, Jason Sweat \<jason.sweat@gmail.com\> wrote:

---

<div class="post-metadata">

**Author:** ![Jason\_Sweat](https://avatars.discourse-cdn.com/v4/letter/j/53a042/32.png) [@Jason\_Sweat](https://rubytalk.org/u/Jason_Sweat)\
**Post date:** [5 November 2004 02:41 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/7 "2004-11-05T02:41:07Z")

</div>

Thanks Bill,

I think I see how that works. I will play with it and see if it  
solves my problem. I knew there had to be a much cleaner way than  
what I was doing 🙂

Regards,  
Jason

> **···**
>
> On Fri, 5 Nov 2004 10:39:11 +0900, Bill Kelly \<billk@cts.com\> wrote:
> 
> > repl =   
> > true while dat.gsub!(/\([^(){}]\*\)|\{[^(){}]\*\}/) do |str|  
> > &nbsp;&nbsp;repl.push(str)  
> > &nbsp;&nbsp;"\0#{repl.length - 1}\0"  
> > end  
> > dat.scan(/class\s+\w+\s+\0\d+\0/) do  
> > &nbsp;&nbsp;match = $&  
> > &nbsp;&nbsp;true while match.gsub!(/\0(\d+)\0/) { repl[$1.to\_i] }  
> > &nbsp;&nbsp;puts "Your class matched:", match  
> > end
> > 
> > The above matches arbitrarily deeply nested ( ) and { }  
> > blocks... but all the "classes" it matches have to be  
> > at toplevel, can't be inside a { } or ( ) themselves...
> > 
> > In case it's not obvious how it works... It replaces,  
> > from innermost to outermost, () and {} spans with a  
> > token, and saves the original span in an array.
> 
> --  
> [http://blog.casey-sweat.us/](http://blog.casey-sweat.us/)

---

<div class="post-metadata">

**Author:** ![Mark\_Hubbart1](https://avatars.discourse-cdn.com/v4/letter/m/a3d4f5/32.png) [@Mark\_Hubbart1](https://rubytalk.org/u/Mark_Hubbart1)\
**Post date:** [5 November 2004 03:59 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/8 "2004-11-05T03:59:11Z")

</div>

Hi,

> \> Regular expressions, by all standard definitions, aren't recursive.  
> \> Perl's regexen have been extended to allow it, but it really isn't  
> \> considered a standard regex feature.
> 
> Of course, you are correct. However, recursive "Regular Expressions"  
> are becoming fairly common place now. Ruby's next regex engine will  
> support them as well.

Are you saying Oniguruma \*will\* support it, or \*does\* support it? It  
would be nice if it already does 😃

> Regular Expression has evolved considerably from the original  
> definition, with recursive capabilities being just another change in a  
> long line of added usefulness. Does that really means they cease to be  
> Regular Expressions? Longhorn will still be Windows, right?
> 
> I think of it more in terms of supersets or, for a programming slant,  
> subclassing. The spirit of Regular Expressions, patterns to  
> locate/breakdown text, is intact, I believe. They're just even more  
> handy now.

My statement wasn't supposed to insinuate that adding recursion is  
bad, or turns regular expressions into something else; I was just  
pointing out that (last time I checked) you can't \*expect\* to be able  
to use recursion in regexen in a particular language. Perl's regexen  
are \*more\* than regexen; you can even embed perl code in them. Also,  
I'm pretty sure the recursive matching wasn't in Perl when I last used  
it, a couple years back.

> Just my two cents.
> 
> James Edward Gray II
> 
> P.S. Proving whether or not Perl 6 changes will still be "Regular  
> Expression" is left as an exercise for the reader. 😉

🙂

cheers,  
Mark

> **···**
>
> On Fri, 5 Nov 2004 12:17:01 +0900, James Edward Gray II \<james@grayproductions.net\> wrote:
> 
> > On Nov 4, 2004, at 8:04 PM, Mark Hubbart wrote:

---

<div class="post-metadata">

**Author:** ![Eivind\_Eklund](https://avatars.discourse-cdn.com/v4/letter/e/f17d59/32.png) [@Eivind\_Eklund](https://rubytalk.org/u/Eivind_Eklund)\
**Post date:** [5 November 2004 08:19 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/9 "2004-11-05T08:19:27Z")

</div>

Yes.

It very specifically mean that they stop being regular expressions,  
because the "regular" actually has a specific meaning (coming from  
regular sets/context free language theory), and has the nice property  
of compiling to a Deterministic Finite Automation with only linear  
increase in size of the DFA compared to the regular expression.

The true regular expressions consists of ^, $, characters, \*, and (|)  
(alternation). Most of the "original" extensions compile cleanly to  
this, and can still be considered regular. When you start using  
backrefs in matching or recursion, the expression is no longer regular  
(which, among other things, will almost certainly force your poor  
regexp engine into Non-deterministic Finite Automation mode - unless  
you've got exponential amounts of RAM, of course 😉

[Regular expression - Wikipedia](http://en.wikipedia.org/wiki/Regular_expression) gives a bit more background.

Eivind.

> **···**
>
> On Fri, 5 Nov 2004 12:17:01 +0900, James Edward Gray II \<james@grayproductions.net\> wrote:
> 
> > On Nov 4, 2004, at 8:04 PM, Mark Hubbart wrote:
> > 
> > \> Regular expressions, by all standard definitions, aren't recursive.  
> > \> Perl's regexen have been extended to allow it, but it really isn't  
> > \> considered a standard regex feature.
> > 
> > Of course, you are correct. However, recursive "Regular Expressions"  
> > are becoming fairly common place now. Ruby's next regex engine will  
> > support them as well.
> > 
> > Regular Expression has evolved considerably from the original  
> > definition, with recursive capabilities being just another change in a  
> > long line of added usefulness. Does that really means they cease to be  
> > Regular Expressions?
> 
> --  
> Hazzle free packages for Ruby?  
> RPA is available from [http://www.rubyarchive.org/](http://www.rubyarchive.org/)

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [5 November 2004 04:06 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/10 "2004-11-05T04:06:40Z")

</div>

Sure does.

James Edward Gray II

> **···**
>
> On Nov 4, 2004, at 9:59 PM, Mark Hubbart wrote:
> 
> > Are you saying Oniguruma \*will\* support it, or \*does\* support it? It  
> > would be nice if it already does 😃

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [5 November 2004 14:32 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/11 "2004-11-05T14:32:19Z")

</div>

Okay Eivind, what would you prefer we call Regular Expression from now on?

James Edward Gray II

P.S. You better copy Jeffrey E. F. Friedl in you answer since his "Mastering Regular Expressions" covers considerably more NFA than DFA.

> **···**
>
> On Nov 5, 2004, at 2:19 AM, Eivind Eklund wrote:
> 
> > Yes.
> > 
> > It very specifically mean that they stop being regular expressions,

---

<div class="post-metadata">

**Author:** ![Nikolai\_Weibull3](https://avatars.discourse-cdn.com/v4/letter/n/48db29/32.png) [@Nikolai\_Weibull3](https://rubytalk.org/u/Nikolai_Weibull3)\
**Post date:** [6 November 2004 13:43 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/12 "2004-11-06T13:43:05Z")

</div>

\* Eivind Eklund \<eeklund@gmail.com\> [Nov 05, 2004 16:11]:

> \> \> Regular expressions, by all standard definitions, aren't  
> \> \> recursive. Perl's regexen have been extended to allow it, but it  
> \> \> really isn't considered a standard regex feature.

> \> Of course, you are correct. However, recursive "Regular  
> \> Expressions" are becoming fairly common place now. Ruby's next  
> \> regex engine will support them as well.

> \> Regular Expression has evolved considerably from the original  
> \> definition, with recursive capabilities being just another change in  
> \> a long line of added usefulness. Does that really means they cease  
> \> to be Regular Expressions?

> It very specifically mean that they stop being regular expressions,  
> because the "regular" actually has a specific meaning (coming from  
> regular sets/context free language theory), and has the nice property  
> of compiling to a Deterministic Finite Automation with only linear  
> increase in size of the DFA compared to the regular expression.

Well, that's not quite true. They compile to NFAs that are linear in  
size of the input regular expression. The DFA constructed from the  
resulting NFA can be exponential in the size of that input. This is, of  
course, only the case for pathological cases, but DFAs are considerably  
larger than NFAs, even after minimizing them.

> The true regular expressions consists of ^, $, characters, \*, and (|)  
> (alternation).

Well, not really true either. True regular expressions don't include  
zero-width assertions, such as ^ and $. They include characters from  
some alphabet, \* - Kleene closure, . - concatenation (which is implicit  
in most syntaxes), and | - alternation.

> Most of the "original" extensions compile cleanly to this, and can  
> still be considered regular.

Yes.

> When you start using backrefs in matching or recursion, the expression  
> is no longer regular (which, among other things, will almost certainly  
> force your poor regexp engine into Non-deterministic Finite Automation  
> mode -

And backtracking mode as well. Regular Expressions With Backreferences  
are an NP-complete problem and have none of the nice properties of  
regular expressions.

> unless you've got exponential amounts of RAM, of course 😉

?

All in all, backreferencing is an addition that doesn't really add very  
much yet ruins a lot of the whole deal with regular expressions. When  
people now start to try to add recursion to regular expressions (which  
would have been nice if they could have easily been included - but they  
can't) one has to shiver a bit. If you wan't recursion, use something  
suitable - like context-free languages; don't expect to solve everything  
with only one tool.  
&nbsp;&nbsp;nikolai

> **···**
>
> --  
> ::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::  
> ::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::  
> ::: page: [www.pcppopper.org](http://www.pcppopper.org) :: fun atm: gf,lps,ruby,lisp,war3 :::  
> main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

---

<div class="post-metadata">

**Author:** ![Mark\_Hubbart1](https://avatars.discourse-cdn.com/v4/letter/m/a3d4f5/32.png) [@Mark\_Hubbart1](https://rubytalk.org/u/Mark_Hubbart1)\
**Post date:** [5 November 2004 05:05 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/13 "2004-11-05T05:05:00Z")

</div>

Indeed it does! I just tried it out. And named subexpressions work too  
🙂 many new features since I last checked it out:

[http://www.geocities.jp/kosako1/oniguruma/doc/RE.txt](http://www.geocities.jp/kosako1/oniguruma/doc/RE.txt)

Thanks for pointing it out.

cheers,  
Mark

> **···**
>
> On Fri, 5 Nov 2004 13:06:40 +0900, James Edward Gray II \<james@grayproductions.net\> wrote:
> 
> > On Nov 4, 2004, at 9:59 PM, Mark Hubbart wrote:
> > 
> > \> Are you saying Oniguruma \*will\* support it, or \*does\* support it? It  
> > \> would be nice if it already does 😃
> > 
> > Sure does.

---

<div class="post-metadata">

**Author:** ![Matt\_Maycock](https://avatars.discourse-cdn.com/v4/letter/m/e9a140/32.png) [@Matt\_Maycock](https://rubytalk.org/u/Matt_Maycock)\
**Post date:** [5 November 2004 15:11 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/14 "2004-11-05T15:11:02Z")

</div>

> Okay Eivind, what would you prefer we call Regular Expression from now on?

Ruby Automata? Irregular Expressions? Irregardless Expressions?  
Syntax-Restricted-State-Machines (SRSM)? Susan/Jacob/Drew (depending  
on whether your language makes them female, male, or neuter)?

I vote for calling it something like "Police Academy" -- Steve  
Guttenberg really doesn't get enough credit for his impact on the  
programming community.

~Me!

> **···**
>
> --  
> There's no word in the English language for what you do to a dead  
> thing to make it stop chasing you.

---

<div class="post-metadata">

**Author:** ![Ara.T.Howard6](https://avatars.discourse-cdn.com/v4/letter/a/958977/32.png) [@Ara.T.Howard6](https://rubytalk.org/u/Ara.T.Howard6)\
**Post date:** [5 November 2004 15:23 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/15 "2004-11-05T15:23:48Z")

</div>

but both of those recognize only regular languages (those one can describe  
with a regular expression). it seems this new type must be called

&nbsp;&nbsp;&nbsp;'context-free expressions'

which would be the next class i think - that is unless this new type does  
considerably more.

-a

> **···**
>
> On Fri, 5 Nov 2004, James Edward Gray II wrote:
> 
> > On Nov 5, 2004, at 2:19 AM, Eivind Eklund wrote:
> > 
> > > Yes.
> > > 
> > > It very specifically mean that they stop being regular expressions,
> > 
> > Okay Eivind, what would you prefer we call Regular Expression from now  
> > on?
> > 
> > James Edward Gray II
> > 
> > P.S. You better copy Jeffrey E. F. Friedl in you answer since his  
> > "Mastering Regular Expressions" covers considerably more NFA than DFA.
> 
> # --
> 
> > EMAIL :: Ara [dot] T [dot] Howard [at] noaa [dot] gov  
> > PHONE :: 303.497.6469  
> > When you do something, you should burn yourself completely, like a good  
> > bonfire, leaving no trace of yourself. --Shunryu Suzuki
> 
> ===============================================================================

---

<div class="post-metadata">

**Author:** ![Nikolai\_Weibull3](https://avatars.discourse-cdn.com/v4/letter/n/48db29/32.png) [@Nikolai\_Weibull3](https://rubytalk.org/u/Nikolai_Weibull3)\
**Post date:** [6 November 2004 13:44 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/16 "2004-11-06T13:44:15Z")

</div>

\* James Edward Gray II \<james@grayproductions.net\> [Nov 05, 2004 16:11]:

> \> It very specifically mean that they stop being regular expressions,

> Okay Eivind, what would you prefer we call Regular Expression from now  
> on?

Call them regular expressions and stop using them for context-free  
language matching.  
&nbsp;&nbsp;nikolai

> **···**
>
> --  
> ::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::  
> ::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::  
> ::: page: [www.pcppopper.org](http://www.pcppopper.org) :: fun atm: gf,lps,ruby,lisp,war3 :::  
> main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

---

<div class="post-metadata">

**Author:** ![Jos\_Backus1](https://avatars.discourse-cdn.com/v4/letter/j/7feea3/32.png) [@Jos\_Backus1](https://rubytalk.org/u/Jos_Backus1)\
**Post date:** [5 November 2004 07:21 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/17 "2004-11-05T07:21:03Z")

</div>

A-1. Syntax depend options

&nbsp;&nbsp;&nbsp;+ ONIG\_SYNTAX\_RUBY  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(?m): dot(.) match newline

&nbsp;&nbsp;&nbsp;+ ONIG\_SYNTAX\_PERL and ONIG\_SYNTAX\_JAVA  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(?s): dot(.) match newline  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(?m): ^ match after newline, $ match before newline

Any idea why Ruby was chosen to behave differently from Perl here?

> **···**
>
> On Fri, Nov 05, 2004 at 02:05:00PM +0900, Mark Hubbart wrote:
> 
> > [http://www.geocities.jp/kosako1/oniguruma/doc/RE.txt](http://www.geocities.jp/kosako1/oniguruma/doc/RE.txt)
> 
> --  
> Jos Backus \_/ \_/\_/\_/ Sunnyvale, CA  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\_/ \_/ \_/  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\_/ \_/\_/\_/  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\_/ \_/ \_/ \_/  
> jos at catnook.com \_/\_/ \_/\_/\_/ require 'std/disclaimer'

---

<div class="post-metadata">

**Author:** ![Jason\_Sweat](https://avatars.discourse-cdn.com/v4/letter/j/53a042/32.png) [@Jason\_Sweat](https://rubytalk.org/u/Jason_Sweat)\
**Post date:** [5 November 2004 14:04 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/18 "2004-11-05T14:04:50Z")

</div>

Great!! Just comiled ruby from cvs (ruby 1.9.0 (2004-11-04)  
[i686-linux]) and was able to match using:

dat = \<\<-"END\_TEXT"  
/\* some stuff \*/  
class foo {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public $var;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function \_\_construct() {}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public function bar() {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (false) {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}

}  
// some other stuff  
END\_TEXT

dat.match(/(class\s+\w+\s\*(\{(?:[^\{\}]\*|\g\<2\>)\*\}))/)  
print $1

Thank you very much for your help!!

Regards,  
Jason

> **···**
>
> On Fri, 5 Nov 2004 14:05:00 +0900, Mark Hubbart \<discordantus@gmail.com\> wrote:
> 
> > \> \> Are you saying Oniguruma \*will\* support it, or \*does\* support it? It  
> > \> \> would be nice if it already does 😃  
> > \>  
> > \> Sure does.
> > 
> > Indeed it does! I just tried it out. And named subexpressions work too  
> > 🙂 many new features since I last checked it out:
> > 
> > [http://www.geocities.jp/kosako1/oniguruma/doc/RE.txt](http://www.geocities.jp/kosako1/oniguruma/doc/RE.txt)
> > 
> > Thanks for pointing it out.
> 
> --  
> [http://blog.casey-sweat.us/](http://blog.casey-sweat.us/)

---

<div class="post-metadata">

**Author:** ![gabriele\_renzi](https://avatars.discourse-cdn.com/v4/letter/g/e19b73/32.png) [@gabriele\_renzi](https://rubytalk.org/u/gabriele_renzi)\
**Post date:** [5 November 2004 16:08 UTC](https://rubytalk.org/t/recursive-brace-matching-with-ruby-regexp/14612/19 "2004-11-05T16:08:41Z")

</div>

Matt Maycock ha scritto:

> > Okay Eivind, what would you prefer we call Regular Expression from now on?
> 
> Ruby Automata? Irregular Expressions? Irregardless Expressions? Syntax-Restricted-State-Machines (SRSM)? Susan/Jacob/Drew (depending  
> on whether your language makes them female, male, or neuter)?

pattern matching 🙂