Recursive Regular Expressions

\"Yo The regular expressions we use in our daily lives are actually not that “regular.” Most of the languages support some kind of extended regular expressions that are computationally more powerful than the “regular” regular expressions as defined by the formal language theory.

For instance, the so often used capture buffers add auxiliary storage to the regular expressions that allow them to match an arbitrary pattern repeatedly. Or look-ahead assertions that allow the regular expression engine to peek ahead before it making a decision.

The Perl programming language has an especially rich with regex engine. One of the engine’s features is the lazy regular subexpressions. The lazy regular subexpressions are expressed as (??{ code }), where the “code” is arbitrary Perl code that gets executed when the moment this subexpression may match.

This allows us to construct something really interesting – we can define a regular expression that has itself in the “code” part. The result is a recursive regular expression!

One of the classical problems that a regular expression can’t match is the language 0n1n, i.e., a string with a number of zeroes followed by an equal number of ones. Surprisingly, using the lazy regular subexpressions this problem becomes tractable!

Here is a Perl regular expression that matches 0n1n:

 my $regex = qr/0(??{$regex})*1/;

This regular expression matches a 0 followed by itself zero or more times, followed by a one. If the itself part doesn’t match, then the string this regular expression matches is 01. If the itself part matches once, the string this regular expression matches is 0011. If it matches two times, the string is 000111, …, etc.

Read More:


Xoost – Search engine

Image via CrunchBase

Xoost is a community search engine. From Xoost page:

Imagine you are searching for a topic related to your favourite Music, Travel destinations, Events. With Xoost you will benefit from the exponential value of doing it much more productively together with your friends or family members. It’s all about sharing Search skills & Knowledge.

Xoost diaplays result from Google, Yahoo and Bing all in one page. If you like a page you can mark it or share it with others. So this is one good feature that is quite useful. Also there is a Search extension available for firefox for Xoost.



\"PerlThis is the third part of a seven-part article on famous Perl one-liners. In this part I will create various one-liners for calculations. See part one for introduction of the series.

Famous Perl one-liners is my attempt to create “perl1line.txt” that is similar to “awk1line.txt” and “sed1line.txt” that have been so popular among Awk and Sed programmers.

The article on famous Perl one-liners will consist of at least seven parts:

  • Part I: File spacing.
  • Part II: Line numbering.
  • Part III: Calculations (this part).
  • Part IV: String creation. Array creation.
  • Part V: Text conversion and substitution.
  • Part VI: Selective printing and deleting of certain lines.
  • Part VII: Release of perl1line.txt.

After I’m done explaining all these one-liners, I’ll publish an ebook. Everyone who’s subscribed to my blog will get a free copy! Subscribe now!

The one-liners will make heavy use of Perl special variables. A few years ago I compiled all the Perl special variables in a single file and called it Perl special variable cheat-sheet. Even tho it’s mostly copied out of perldoc perlvar, it’s still handy to have in front of you, so print it.

Read more…………