Mastering Regular Expressions

gianluca writes "Having always been a heedful guy, I always duly did my homework, going through the lengthy manual pages of a number of regular expressions (regex) crunching tools. You name it: be it PERL, awk, emacs, sed or even one of the .NET framework languages -- any such program provides support for the same regex expressions (or at least, so they seem to the occasional observer). After some years of regex practice with these tools, I had the pretentious conviction that I knew my way through the intricacies of patterns, grouping, greediness, and the like. When I first stepped into Mastering Regular Expressions, looking at the nearly 500 pages which build up Friedl's book, I wondered what could someone ever have to say about regexes to fill so many pages." Gianluca ended up finding plenty of worthwhile content; read below for his review. Mastering Regular Expressions, 2nd edition author Jeffrey E. Friedl pages 460 publisher O'Reilly rating 9.5 reviewer Gianluca Insolvibile ISBN 0596002890 summary An in-depth guide to lead the apprentice to mastering regular expressions' wizardry

My first suspicion, I admit, was that I was facing one of the countless "man page reprints" that you find these days. It was only after reading the book that I eventually understood: before then, I had had no idea of what regexes were really about.

What it's about The book is logically divided into three parts: the first one (Chapters 1, 2 and 3) introduces the reader to the basic concepts of regexes, building a common ground upon which the subsequent chapters will be based. The introduction is clear and straightforward, and lets the readers quickly grasp the key points in the regex business. This part is more or less a good summary, presenting information that can be found also in existing manual pages (albeit presented in a distilled form, which lets you perceive that the author has very clear ideas about the matter). If you already know something about regexes, you could skip this part entirely -- even if reading it turns out to be a nice occasion to brush up and overhaul your knowledge.

The second part (Chapters 4, 5 and 6), is the one that struck me most for the depth of provided information and the richness of though. Rather than throwing at the reader usage dictates on one or another regex flavour, the author explains with a wealth of details the inward mechanisms which make regexes run and how you can exploit such knowledge to write better expressions.

Chapter 4 presents the different families of regex processing engines (namely, DFA, traditional and POSIX NFA), whose internal behavior differs so greatly that writing a regex in the appropriate way can make a substantial difference in both efficacy and efficiency. If you thought you knew it all about greedy and lazy regex operators, possessive quantifiers, backreferences and lookaround, you'd better think again: I was pleasantly surprised to discover how ignorant I was (to be honest, I had never heard of lookaround operators before!).

Chapter 5 slows down a little bit to let the reader absorb the massive previous chapter. Some simple (but still tricky) examples are presented, showing how to apply the techniques explained up to this point. A couple of examples are perhaps too contrived (ever needed to match aligned groups of 5 digits in an unspaced stream of characters?), but it is instructive anyway to follow the reasoning behind the construction of a complex regex.

Chapter 6 focuses on efficiency, considering how backtracking and matching can drive your regex engine to exponential complexities. Optimization techniques are then presented, first by explaining the automatic optimizations performed by the most common regex engines and then by giving a practical list of hints that you can follow to be sure that your expression will run as fast as possible. Again, I was quite surprised to find out how small changes in a regex can make such a big difference to the engine (and give rise to noticeable performance penalties if ignored).

What I absolutely liked most was that the author explains exactly why a certain optimization works, based on the information given in Chapter 4 (and provided that you have been able to assimilate it in the first pass). Finally, a paragraph entitled "Unrolling the loop" really put me in a good mood, reminding me of the past times of "old school" asm programming.

The third part of the book devotes three chapters to PERL, Java and .NET, respectively. Each chapter goes through the syntax and features of regexes for each language: while the information provided on Java and (VB).NET is quite commonplace, in the case of PERL the author deals with aspects rarely covered elsewhere, like dynamic regexes, embedded-code constructs, regex-literal overloading and specific optimization techniques.

What's to like In one word: insight. The author is definitely knowledgeable of regular expressions and the whole book is filled with thoughtful suggestions and hints. Still, a friendly and straightforward writing style makes reading pleasant and seldom boring (well, you wanted details, didn't you?) while you learn internal regex mechanics rarely available elsewhere.

A further nice point is the broad view offered to the reader, starting from regexes in general and focusing on specific flavours only in the final part of the book. The second edition also offers up-to-date information, covering the .NET framework and the latest versions of PERL (5.8) and Java (1.4).

What's to consider Despite the book's reassuring conversational tone, dealing with such a specific topic with so many in-depth details might sometimes become boring, especially if you do not have a strong interest in getting the most out of regular expressions or in knowing how they internally work. If you are just an occasional regex user and dwell in manual pages, you can probably live without this book. Also, it is a pity that specific sections on Tcl, emacs and awk have disappeared in the second edition (maybe they were not as current as the .NET framework ?) and that pcre (a C regex library) is barely mentioned. The summary Regular expressions are tied so strongly to the *nix culture that everyone who has been exposed to that culture has come to use them in a more or less conscious way. Still, most of the documentation around lags on basic features and presents only the most common regex operators. Mastering Regular Expressions is the book to read if you want to go further and get serious about regexes: even if extreme optimization might not be a big concern today, understanding how regex engines work under the hood greatly helps also in creating everyday small expressions. Table of Contents Preface
Chapter 1. Introduction to Regular Expressions
Chapter 2. Extended Introductory Examples
Chapter 3. Overview of Regular Expression Features and Flavors
Chapter 4. The Mechanics of Expression Processing
Chapter 5. Practical regex techniques
Chapter 6. Crafting a Regular Expression
Chapter 7. Perl
Chapter 8. Java
Chapter 9. .NET

You can purchase the Mastering Regular Expressions, 2nd edition from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.

Comments

i mastered regular expressions

[Anonymous Coward]

when figuring out the lameness filter

Perl, Java, .NET.. oh my!

[Gortbusters.org]

This sounds like a nifty tool for those who have to switch programming environments quite often. I always find myself going back to the books when I either have to write a regex myself or decypher someone elses crazy looking expression.

Don't go overboard

[apsmith]

I read the first edition of this book - it was great, and completely changed the way I handled (and understood) perl regular expressions. It's tempting, after reading this book, to try to apply regex's to everything! Friedl had an example of a huge, horrible (but efficient) regex to parse mail headers in the first edition - my advice on that is, don't try that at home! Interspersing procedural logic with the regex's tends to make much cleaner and more readable code...

Re:Don't go overboard

[sharlskdy]

When all you have is a hammer, everything looks like a nail. And, REGEX is one HUGE hammer!

Re:Don't go overboard

[tshak]

Friedl had an example of a huge, horrible (but efficient) regex to parse mail headers in the first edition

And I'm pissed that it's NOT in the second edition (at least it couldn't easily be found). I was trying to impress this chick at B&N the other day by showing her how I understood that longass expression and low-and-behold, the back page where it's SUPPOSED to be is filled with a 3 line regex - not very impressive after you've made a huge deal about a full-page regex. Fortunately it all worked out since I had the original at home, and I was like "well, you'll just have to come over to MY place to check out the big regex". ;-)

Different than 1st Edition?

[khef]

Can anyone that's read this describe what's changed from the first edition? Is it worth shelling out the cash if you already have the first one?

Re:Different than 1st Edition?

[sharlskdy]

You can read about the differences by clicking here, which is an article by the author outlining the differences.

Re:Regular Expressions

[qorkfiend]

GNU regex

I was going to read this

[L. VeGas]

but instead I *

Re:I was going to read this

[nick_urbanik]

but instead I *

...read spaces to the end of the line, or the next non-space character :-)

Re:Regular Expressions

[rkz]

try this

Its caldera's c++ portable regex lib.

Cheap prices on Half.com

[cybermint]

I just purchased an almost new copy on Half.com for under $15 including shipping. There are still a few left at prices far lower than amazon.com or bn.com. Here is the half/ebay link.

Obligatory crap regexp joke

[BabyDave]

Regular expressions are tied so strongly to the *nix culture

Shouldn't that be .*nix instead?

Perl, not "PERL"

[carl67lp]

It's always surprised me when I see intelligent people write "PERL" when they refer to Larry Wall's programming language.

From the Perl FAQ, General Questions About Perl:

What's the difference between "perl" and "Perl"?
One bit. Oh, you weren't talking ASCII? :-) Larry now uses ``Perl'' to signify the language proper and ``perl'' the implementation of it, i.e. the current interpreter. Hence Tom's quip that ``Nothing but perl can parse Perl.'' You may or may not choose to follow this usage. For example, parallelism means ``awk and perl'' and ``Python and Perl'' look ok, while ``awk and Perl'' and ``Python and perl'' do not. But never write ``PERL'', because perl isn't really an acronym, aprocryphal folklore and post-facto expansions notwithstanding.

You can read the entire FAQ if you like.

Re:Perl, not "PERL"

[br0ck]

From an interesting interview with Larry Wall - 1999..

Marjorie: Well, that certainly answered the question fully. I must admit I didn't expect you to go back as far as the beginning of the Universe. :-) How'd you come up with that name?

Larry: I wanted a short name with positive connotations. (I would never name a language ``Scheme'' or ``Python'', for instance.) I actually looked at every three- and four-letter word in the dictionary and rejected them all. I briefly toyed with the idea of naming it after my wife, Gloria, but that promised to be confusing on the domestic front. Eventually I came up with the name ``pearl'', with the gloss Practical Extraction and Report Language. The ``a'' was still in the name when I made that one up. But I heard rumors of some obscure graphics language named ``pearl'', so I shortened it to ``perl''. (The ``a'' had already disappeared by the time I gave Perl its alternate gloss, Pathologically Eclectic Rubbish Lister.)

Another interesting tidbit is that the name ``perl'' wasn't capitalized at first. UNIX was still very much a lower-case-only OS at the time. In fact, I think you could call it an anti-upper-case OS. It's a bit like the folks who start posting on the Net and affect not to capitalize anything. Eventually, most of them come back to the point where they realize occasional capitalization is useful for efficient communication. In Perl's case, we realized about the time of Perl 4 that it was useful to distinguish between ``perl'' the program and ``Perl'' the language. If you find a first edition of the Camel Book, you'll see that the title was Programming perl, with a small ``p''. Nowadays, the title is Programming Perl.

I concur

[Speare]

I completely concur with the poster's prejudices and pleasant surprise at the scope of the book. Having learned and used regex since 1986, and having worked on the internals of a couple lightweight C regex engines, I figured I knew all I needed to know. Having seen how many people just get hung up on the basic concept and syntax of regex, I assumed this was going to be a rehash.

This is no "Learn Regex in 21 Days" or "Regex for Dummies" book with lots of tips on page 400 about how the | is useful for finding Jones OR Smith. If you haven't gotten that down yet, this book's not for you.

As the reviewer says, this is a very worthwhile cover-to-cover read which will turn your empirical experiences with regex into a more structured understanding of the science and engineering of advanced regex. As a reference on my shelf, it sits comfortably next to Knuth's AoCP and Foley & van Damme.

netLibrary

[dboyles]

I first started reading this book via netLibrary through my school's library. Just the first two chapters are enough to explain regular expressions to the point where one can use them effectively in programs. The remaining chapters expand on this information and discuss language specifics. I bought a paper copy to have on my shelf, and I constantly find myself referencing it.

To those at universities, see if your school offers netLibrary-based books. It's easy to read and it's free.

I just can't fathom this

[Anonymous Coward]

Now, I thought I was reading a simple article about a programming book review. And here I come across this thread of epic mirth. Somehow you have single-handedly crafted a finely-tuned piece fun-joy from what was a rather mundane topic. I just have to page my boss back to the office to see this! Gather round the water cooler old salts and let me spin a comedic yarn I saw this day on Slashdot. Using an asterix to finish a sentence we would have all seen as being finished in a different manner? Well sir, someone set you up the bomb. You have taken that bomb, added the asterix into the mix and exploded laugh-shrapnel into Slashdot proper. I couldn't even scroll down without getting struck in the eye with a piece of your fun-bomb. Mods, mod this man's excursion into the comedy arena as +5 StopItHurts. Here we sit, emotionally spent and basking in the aftermath of your comedic genius. Thank you kind sir, thank you.

that's the first edition

[SweetAndSourJesus]

Which isn't a big deal, I guess.

Mastering Regular Expressions is now in its second edition. Mr. Friedl has posted a nice writeup about what's different in the second edition.

Soviet Russia Regex

[TheFlyingGoat]

s/\A(.*?)\s+(.*)\Z/In soviet Russia, $2 $1s you!/i;

They can be hard

[DeadSea]

I know from my own experiences that writing a regular expression to describe something is not always as easy as it would seem at first glance. I found it difficult to write a regular expression to define a c-style comment: /* comment */ Well, not impossible, just more difficult that I thought it would be. I posted my thought process about how I constructed a regular expression to pick out a c-style comment on my website. It's the kind of thing I like to ask interview candidates.

Re:They can be hard

[dargaud]

Not to nitpick too much, but I think your regexp finds the following when it's actually not a comment:

printf("Comments in C are written like /* this */ although I prefer the // C++ style");

That's why we use parsers to write compilers and not regexps. I came back from Perl after a few months using it, being very disillusionned by its read-onlyness.

Re:They can be hard

[Otter]

It's probably worth mentioning: KDE comes with a GUI regexp constructor. Googling for alternatives shows a similar Windows app.

Re:They can be hard

[FroMan]

Nope, it wouldn't. Give it a try. I don't have access to a unix box here right now. But atleast the little java app I put together works correctly.

Assuming you wanted to capture "/* hello */" out of "/* hello */ hello */"

You see what you are missing is the '?' modifier that will cause the "(.*\r?\n)*" to not be greedy. Same with the ".*".

I think you are just missing the some of the functionality of regexes. You might want to pick up this book. ;-)

Regex Learning Tool

[johndiii]

Regex Coach is a great free tool for learning about regular expressions and constructing them interactively. Both Linux and Windows versions are available.

Online resource

[dema]

I'd be interested to check that book out as I use reg expressions a lot in PHP. But for those of you looking for a resouce online check out RegExLib. I use it often when I'm having trouble putting an expression together and have found it extremely helpful.

From Windows

[Quill_28]

Going from windows to unix one of the things I liked most about unix was the wide spread usage of regex in various applications. Quite powerful.

All i have to say is:

[jdew]

Thats a big regex
stupid filter wouldn't let me paste the regex here XD

C++ Regular Expressions

[TheOldBear]

The Boost C++ libraries have a regular expression package. Take a look at http://www.boost.org/libs/regex/index.htm

Regex rant

[Tablizer]

The problem with regex's is that if you don't use them often, you forget a lot of the finer details. They are not self-documenting at all. I think something like "generators" used in some of the compiler tools floating around are more intuative. For example, you can define a "LISP-lite" language like this:

statement -> (command params)
statement -> (command)
params -> params params
params -> constant
params -> variable
params -> statement

Re:My problem with regular expressions...

[Gabe Garza]

Amen!

I think a lot of the people who use RE's a lot would be well-served by brushing up on their recursive-descent parser writing skills. For only a little more time then it takes to write a regular expression, you can (if you know how) write a simple recursive-descent parser that:

• Is more readable (and thus maintainable)
• Is more efficient
• Has the potential to have much better error handling (e.g., a descriptive message instead of just "RE doesn't match! Ack!")
• Is much more scalable: recursive descent parsers can easily scale up to parsing an entire language (witness g++, which uses one to parse C++)
• Is likely to be a great deal more correct, because it forces you to actually define a language, instead of just iteratively building up an RE

errata

[Anonymous Coward]

The reviewer forgot to mention the wonderful errata list of the book! Can be found here.

And he's Qualified to review this book????

[CSG_SurferDude]

(to be honest, I had never heard of lookaround operators before!).

Gezzzz, This guy hasn't even heard of lookaround operators before? What a clueless fool! He should be driven from /. after being tarred and feathered!

Everyone knows that a lookaround operator is that guy that goes into the bank first to make sure that there aren't any armed guards or policemen/women getting their paychecks deposited.

/me runs and hides now! ;-)

Interpretting parser

[Frans Faase]

If you want to have something more powerful than regexprs, and still have it as an interpretter, you might have a look at an interpretting parser that I wrote: IParse.

Re:Why is it that people think regexps are hard?

[Abcd1234]

Someone just took a course on formal languages...

If you need a 500 page book on regexps, you might want to have a look at a good compiler book (red dragon, etc.) first.

And why would I want to learn about all the various automata (finite state machines, push-down automata, and Turing machines) not to mention all that language parsing crap (top-down versus bottom-up parsing, parse trees, etc, etc), when all I really want to learn is how to exploit a regular expression engine efficiently so I can solve real world problems?

Full non-CFG languages are so much more powerful than any regexp could ever dream of being, and more importantly they can have state.

Yeah, that's called a programming language. And yeah, I could implement any regular expression using a standard programming language, but why would I bother when a regular expression is far more concise and better suited to the job?

Geez, give someone a hammer...

re-builder for Emacs

[David Ishee]

The re-builder mode is great for debugging regexps in Emacs. This is the latest version as far as I can tell: re-builder 1.2

Re:Why is it that people think regexps are hard?

[muonzoo]

SkewlD00d writes:

Why is it that people think regexps are hard

All you have are zero-or-more "+", one-or-more "*", conditional "? or sometimes ...

...these bozos that think "regexp" sounds cool...

Just like the bozo who just finished a Formal Computation course, yet mixed up the meanings of "+" and "*" ? ;-)

From man grep:

A regular expression may be followed by one of several
repetition operators:
? The preceding item is optional and matched at most
once.
* The preceding item will be matched zero or more
times.

I hear they're serving humble pie at the school cafeteria today. ;-)

Re:Regexp's almost consistent across languages

[IpalindromeI]

Even though the perl regexp's tend to be the de-facto standard, the perl people are frequently adding stuff to their regexps.

Damn those Perl people and their innovations. Why can't they just be happy doing everything the familiar, crappy way? Why must they push the envelope to make things easier and better? I hate that.

PS. I hope you haven't seen this yet. It'll really boil your blood.

My Version...

[BinaryCodedDecimal]

Mastering Regular Expressions:

Repeat after me:

"I'm so hungry, I could eat a horse."

"It's been raining cats and dogs."

"I'll sleep with you when Hell freezes over."

And my personal favourite:

"Oh look, Hell just froze over!"

I've read the first edition and...

[RevMike]

I have to agree that this is a book that should be on everyone's shelf.

The very fact that both vi and emacs support regular expressions must mean they are a best-in-breed tool, because if there was a way for those two communities to disagree, they would have done it.

I love the fact that I can use the same expressions with grep, sed, vim, Perl, and Java. that being said, however, the critics are who warn that regex can be over used are correct: regex's are difficult to debug and to maintain, so don't go overboard.

Re:You actually liked this book?

[melonman]

I loved the first edition, probably for the reasons you didn't. I'd read several short overviews of regexes, including Larry Wall's one in the Camel book, and, while they got me doing simple stuff, they left me with lots of unanswered questions, and the more I experimented the more my "why doesn't that work?" list grew. The Friedl book is totally thorough, and, I thought, aggessively pedagogical, if you want to learn about how a regex engine works rather than pick up stuff in a cookbook fashion.

That said, I do wonder about the guy. The colophon was astounding: he wrote half the book using regexes on a computer on the other side of the world, using a 37.5 bit/hour connection by the sound of it, and then he proceeded to write his own typesetting system so he could produce a phoenetically alphabetical index in English, Japanese and probably some other languages that I missed. I think he ought to get out more...

contrived examples?

[anonymous loser]

(ever needed to match aligned groups of 5 digits in an unspaced stream of characters?)

Yes, actually. Older FORTRAN codes (that have been slowly added to/modified over time) especially exhibit this kind of behavior thanks to formats that allow you to specify columns for output. The numbers actually run into each other on the line, and the only way to read the file is to know which column the data you want is in. I would never discount any regular expression example as contrived. Somewhere, someone has developed a program that uses that formatting in an input or output file, and someone else might need to be able to speak it's language in an automated fashion.

what did one regular expression say to the other?

[jdew]

what did one regular expression say to the other?
.*