# Re: Reverse the Polarity (#143)

**URL:** <https://www.ruby-forum.com/t/re-reverse-the-polarity-143/117202>\
**Category:** Ruby\
**Created:** [October 14, 2007, 6:24pm UTC](https://www.ruby-forum.com/t/re-reverse-the-polarity-143/117202 "2007-10-14T18:24:48Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [October 14, 2007, 6:24pm UTC](https://www.ruby-forum.com/t/re-reverse-the-polarity-143/117202/1 "2007-10-14T18:24:48Z")

</div>

I had fun with this quiz.

/Ruby (should be|better be|is) (very )\* fun[…!] (You see?)?/.generate

=\>["Ruby should be fun. ", “Ruby should be fun. You see?”, "Ruby  
should be fun! ", “Ruby should be fun! You see?”, "Ruby should be very  
fun. ", “Ruby should be very fun. You see?”, "Ruby should be very fun!  
", “Ruby should be very fun! You see?”, "Ruby should be very very fun.  
", “Ruby should be very very fun. You see?”, "Ruby should be very very  
fun! ", “Ruby should be very very fun! You see?”, "Ruby should be very  
very very fun. ", “Ruby should be very very very fun. You see?”, "Ruby  
should be very very very fun! ", “Ruby should be very very very fun!  
You see?”, "Ruby should be very very very very fun. ", “Ruby should be  
very very very very fun. You see?”, "Ruby should be very very very very  
fun! ", “Ruby should be very very very very fun! You see?”, "Ruby  
should be very very very very very fun. ", “Ruby should be very very  
very very very fun. You see?”, "Ruby should be very very very very very  
fun! ", “Ruby should be very very  
very very very fun! You see?”, "Ruby better be fun. ", “Ruby better  
be fun. You see?”, "Ruby better be fun! ", “Ruby better be fun! You  
see?”, "Ruby better be very fun. ", “Ruby better be very fun. You  
see?”, "Ruby better be very fun! ", “Ruby better be very fun! You  
see?”, "Ruby better be very very fun. ", “Ruby better be very very  
fun. You see?”, "Ruby better be very very fun! ", “Ruby better be very  
very fun! You see?”, "Ruby better be very very very fun. ", “Ruby  
better be very very very fun. You see?”, "Ruby better be very very very  
fun! ", “Ruby better be very very very fun! You see?”, "Ruby better be  
very very very very fun. ", “Ruby better be very very very very fun.  
You see?”, "Ruby better be very very very very fun! ", “Ruby better be  
very very very very fun! You see?”, "Ruby better be very very very very  
very fun. ", “Ruby better be very very very very very fun. You see?”,  
"Ruby better be very very very very very fun!  
", “Ruby better be very very very very very fun! You see?”, "Ruby is  
fun… ", “Ruby is fun. You see?”, "Ruby is fun! ", “Ruby is fun! You  
see?”, "Ruby is very fun. ", “Ruby is very fun. You see?”, "Ruby is  
very fun! ", “Ruby is very fun! You see?”, "Ruby is very very fun. ",  
“Ruby is very very fun. You see?”, "Ruby is very very fun! ", “Ruby is  
very very fun! You see?”, "Ruby is very very very fun. ", “Ruby is  
very very very fun. You see?”, "Ruby is very very very fun! ", “Ruby  
is very very very fun! You see?”, "Ruby is very very very very fun. ",  
“Ruby is very very very very fun. You see?”, "Ruby is very very very  
very fun! ", “Ruby is very very very very fun! You see?”, "Ruby is  
very very very very very fun. ", “Ruby is very very very very very  
fun. You see?”, "Ruby is very very very very very fun! ", “Ruby is very  
very very very very fun! You see?”]

Thank you to Evan for making the comment about nesting. My solution  
broke on nesting. Luckily, that was easy to fix.

/(a+(bc)?){1,2}/.generate  
=\>[“a”, “abc”, “aa”, “aabc”, “aaa”, “aaabc”, “aaaa”, “aaaabc”, “aaaaa”,  
“aaaaabc”, “aa”, “aabc”, “aaa”, “aaabc”, “aaaa”, “aaaabc”, “aaaaa”,  
“aaaaabc”, “aaaaaa”, “aaaaaabc”, “abca”, “abcabc”, “abcaa”, “abcaabc”,  
“abcaaa”, “abcaaabc”, “abcaaaa”, “abcaaaabc”, “abcaaaaa”, “abcaaaaabc”,  
“aaa”, “aaabc”, “aaaa”, “aaaabc”, “aaaaa”, “aaaaabc”, “aaaaaa”,  
“aaaaaabc”, “aaaaaaa”, “aaaaaaabc”, “aabca”, “aabcabc”, “aabcaa”,  
“aabcaabc”, “aabcaaa”, “aabcaaabc”, “aabcaaaa”, “aabcaaaabc”,  
“aabcaaaaa”, “aabcaaaaabc”, “aaaa”, “aaaabc”, “aaaaa”, “aaaaabc”,  
“aaaaaa”, “aaaaaabc”, “aaaaaaa”, “aaaaaaabc”, “aaaaaaaa”, “aaaaaaaabc”,  
“aaabca”, “aaabcabc”, “aaabcaa”, “aaabcaabc”, “aaabcaaa”, “aaabcaaabc”,  
“aaabcaaaa”, “aaabcaaaabc”, “aaabcaaaaa”, “aaabcaaaaabc”, “aaaaa”,  
“aaaaabc”, “aaaaaa”, “aaaaaabc”, “aaaaaaa”, “aaaaaaabc”, “aaaaaaaa”,  
“aaaaaaaabc”, “aaaaaaaaa”, “aaaaaaaaabc”, “aaaabca”, “aaaabcabc”,  
“aaaabcaa”, “aaaabcaabc”, “aaaabcaaa”, “aaaabcaaabc”, “aaaabcaaaa”,  
“aaaabcaaaabc”, “aaaabcaaaaa”, “aaaabcaaaaabc”, “aaaaaa”, “aaaaaabc”,  
“aaaaaaa”, “aaaaaaabc”, “aaaaaaaa”, “aaaaaaaabc”, “aaaaaaaaa”,  
“aaaaaaaaabc”, “aaaaaaaaaa”, “aaaaaaaaaabc”, “aaaaabca”, “aaaaabcabc”,  
“aaaaabcaa”, “aaaaabcaabc”, “aaaaabcaaa”, “aaaaabcaaabc”, “aaaaabcaaaa”,  
“aaaaabcaaaabc”, “aaaaabcaaaaa”, “aaaaabcaaaaabc”]

My solution uses a macro-character system inspired by the Lisp parser.  
Every time it encounters a special character, it calls a function  
associated with that character, passing in both the tree it’s  
encountered so far, and the reader. This tree isn’t actually a physical  
tree, however. Instead, it consists of functions that generate all  
possible combinations of a segment of the regex. Each function is  
curried with the relevant arguments so as to require no new arguments.  
For example, the regex-segment “a{1,2}” becomes quantified\_range curried  
with the range 1…2 and the method quote, which is in turn curried with  
“a”. The array that is passed in to the macro-character functions  
consists of all of those trees of curried functions that have been seen  
so far; these will eventually be curried into the capturing\_group method  
by the parse\_regex method. A capturing group, in this case, is not only  
anything between unescaped parentheses but also the top level of  
the regex itself.

My solutions supports most of regex syntax. Non-capturing groups should  
be an unmissed exception, as should be more exotic quoting.  
Unfortunately, I could not think of a way to add in backreferencing  
capturing groups. My first thoughts involved having a global array  
referencing all capturing groups and then having backreferencing refer  
to that, but I couldn’t think of a way so that each backreference would  
know which characters were matched by its capturing group in that  
particular match. Having the tree be evalutated sequentially rather  
than layer-by-layer as it is now (i.e.: rather than having the  
possibilities for each segment evaluated and then applying higher  
functions on those possibilities, do something more of an inorder  
traversal, so that all possibilities if a capturing group matches some  
characters are generated before the possibilities of the next  
possibility for the capturing group are encountered) was briefly thought  
of, but that would  
make this solution several times more complex (i.e.: needing actual  
tree nodes rather than curried methods).

A few notes: Since + and \* can match infinite amounts of characters, I  
just have them match upto the value of INF\_QUANTIFIER\_LEN, which is set  
to 5. Additionally, I anything along the lines of /|a/ will not work  
(though /a|/ does work); however, should I bother, I can make a  
work-around with ease.

Anyway, here’s the code:

INF\_QUANTIFIER\_LEN = 5

module Invokable  
def curry(\*largs)  
proc {|_args| self.call(_(largs+args))}  
end  
end  
class Method  
include Invokable  
end

$escape\_seqs = {  
?a =\> ?\a,  
?b =\> ?\b,  
?f =\> ?\f,  
?n =\> ?\n,  
?r =\> ?\r,  
?t =\> ?\t,  
?v =\> ?\v  
}

$predefined\_classes = {  
?d =\> (?0…?9).to\_a,  
?D =\> (0…255).to\_a - (?0…?9).to\_a,  
?s =\> [" “[0], ?\t,?\n,?\v,?\r],  
?S =\> (0…255).to\_a - [” "[0], ?\t,?\n,?\v,?\r],  
?w =\> (?a…?z).to\_a + (?A…?Z).to\_a + (?0…?9).to\_a + [?_],  
?W =\> (0…255).to\_a -  
((?a…?z).to\_a + (?A…?Z).to\_a + (?0…?9).to\_a + [?_])  
}

###Given a StringIO removes the next character if it’s a ?  
def remove\_reluctant(strio)  
return if strio.eof?  
if (ch=strio.getc) == ??  
#Do nothing  
else  
strio.ungetc(ch)  
end  
end

###Given a StringIO, returns the everything until an unnested closed  
parenthesis is read  
def get\_outer\_layer(strio)  
str = “”  
nest = 0  
until (ch=strio.read(1)) == ‘)’ and nest == 0  
str \<\< ch  
str \<\< strio.read(1) if ch == “\”  
nest += 1 if ch == ‘(’  
nest -= 1 if ch == ‘)’  
end  
str  
end

###Returns an array whose elements are subarrays containing all distinct  
###combinations of one element from each argument  
def all\_combinations(first, \*rest)  
return first if rest == []  
rest = all\_combinations(\*rest)  
combs = []  
first.each do |v1|  
rest.each do |v2|  
combs \<\< v1 + v2  
end  
end  
combs  
end

###The following methods return an array of all valid matches to the  
entity.

### 

###Note: The functions corresponding to regex operators that operate on  
###valid subregexes accept curried functions that return the values to  
operate on,  
###not the values themselves. (That’s why the quote function exists.)

def char\_class(ascii\_vals)  
ascii\_vals.map{|i|i.chr}  
end

def or(left, right)  
left.call+right.call  
end

def quantified\_range(range, vals)  
vals = [vals.call] \* range.end  
range.to\_a.map{|n|n == 0 ? “” :  
all\_combinations(\*vals[0…(n-1)])}.flatten  
end

def capturing\_group(vals)  
all\_combinations(\*vals.map{|f|f.call})  
end

def quote(val)  
[val]  
end

###Following is a hash that maps characters to procedures accepting the  
###previously-encountered entities and the StringIO of the regex-source  
reader.  
###These procedures add to prev curried functions that a form a tree of  
functions  
###that return all possible values  
$macro\_chars = {  
?\ =\> proc do |prev, strio|  
ch = strio.getc  
prev \<\< if $predefined\_classes.has\_key? ch  
method(:char\_class).curry($predefined\_classes[ch])  
elsif $escape\_seqs.has\_key? ch  
method(:quote).curry($escape\_seqs[ch])  
else  
method(:quote).curry(ch.chr)  
end  
end,  
?. =\> proc do |prev, strio|  
prev \<\< method(:char\_class).curry((0…255).to\_a)  
end,  
?[ =\> proc do |prev,strio|  
ascii\_vals = []

```
        char_str = strio.gets("]")[0...-1]

        neg = if char_str[0] == ?^
                  char_str = char_str[1..-1]
                  true
                else
                  false
                end

        ##The next three lines handle escape characters. \- is a 

```

special case  
char\_str.gsub!(/\-/) {ascii\_vals \<\< ?-; “”}  
char\_str.gsub!(/\(.)/) {  
$escape\_seqs.has\_key?($1[0]) ? $escape\_seqs[$1[0]] : $1}  
char\_str.scan(/.-.|./) do |seg|  
if seg =~ /(.)-(.)/  
ascii\_vals += (($1[0])…($2[0])).to\_a  
else  
ascii\_vals \<\< seg[0]  
end  
end  
prev \<\< method(:char\_class).curry(  
neg ? (0…255).to\_a - ascii\_vals : ascii\_vals)  
end,  
?( =\> proc do |prev,strio|  
prev \<\< parse\_regex(get\_outer\_layer(strio))  
end,  
?\* =\> proc do |prev, strio|  
remove\_reluctant(strio)  
prev[-1] = method(:quantified\_range).  
curry(0…INF\_QUANTIFIER\_LEN, prev[-1])  
end,  
?+ =\> proc do |prev, strio|  
remove\_reluctant(strio)  
prev[-1] = method(:quantified\_range).  
curry(1…INF\_QUANTIFIER\_LEN, prev[-1])  
end,  
?? =\> proc do |prev, strio|  
remove\_reluctant(strio)  
prev[-1] = method(:quantified\_range).  
curry(0…1, prev[-1])  
end,  
?{ =\> proc do |prev, strio|  
remove\_reluctant(strio)  
contents = strio.gets(“}”)  
prev[-1] = if contents =~ /(\d),(\d)/  
method(:quantified\_range).curry(($1.to\_i)…($2.to\_i),  
prev[-1])  
elsif contents=~ /(\d),/  
method(:quantified\_range).curry(  
($1.to\_i)…INF\_QUANTIFIER\_LEN,  
prev[-1])  
elsif contents =~ /(\d)/  
method(:quantified\_range).curry(($1.to\_i)…($1.to\_i),  
prev[-1])  
end  
end,  
?| =\> proc do |prev, strio|  
prev[0…-1] = method(:or).curry(  
method(:capturing\_group).curry(prev[0…-1]),  
parse\_regex(strio.gets(nil)))  
end  
}

def parse\_regex(src)  
return method(:quote).curry(“”) if src == “” or src.nil?  
func\_arr = []  
strio = StringIO.new(src)  
until strio.eof?  
ch = strio.getc  
if $macro\_chars.has\_key? ch  
$macro\_chars[ch].call(func\_arr, strio)  
else  
func\_arr \<\< method(:quote).curry(ch.chr)  
end  
end  
method(:capturing\_group).curry(func\_arr)  
end

class Regexp  
def generate  
parse\_regex(self.source).call  
end  
end

```
  ____________________________________________________________________________________

```

Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user  
panel and lay it on us.  
[http://surveylink.yahoo.com/gmrs/yahoo\_panel\_invite.asp?a=7](http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7)