Fun with regular expressions: part III

(The following text has been copypasted to the SAT/SMT by example book.)

(Part II.)

Like I stated before, RE often used for parsing. Here are more practical examples

"var1 +var2"

What it accepts? I'm going to try my utility again:

string matched: [var1 var2]
string matched: [var1  var2]
string matched: [var1   var2]
string matched: [var1    var2]
string matched: [var1     var2]
string matched: [var1      var2]
total: 6

Obviously, a set of input strings is infinite. So my utility has some limit and stopped after it is reached.

"var1[ \t]+var2"

(Extending this RE to whitespaces, i.e., tab symbol.)

" *var1 *= *var2 *"

Even more practical. A whitespace can surround input string and the equality sign. Kleene star is used here.

"(0|(1(01*0)*1))*"

This RE accepts input numbers (in binary form) that are divisible by 3. (More about it.) My book has a part about it, Ctrl-F: "DFA accepting a binary substring divisible by prime number".

My utility correctly enumerates such string. But only up to some length...

...
string matched: [000110]
string matched: [00011011]
string matched: [0001101111]
string matched: [000110111111]
string matched: [00011011111111]
string matched: [0001101111110]
string matched: [00011011111100]
string matched: [00011011111001]
string matched: [00011011110]
string matched: [0001101111011]
string matched: [00011011110110]
string matched: [000110111100]
string matched: [00011011110011]
...

Of course, the number of leading zeroes doesn't affect anything.

Proceed to part IV.

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.