81

I'm not asking where to learn. I've found lots of good resources online, and books etc.

But how the heck do I tackle them. Where is the start of it, the end? When does the regexp processor advance on the text, when does it hold its stand and tries another match? etc.

I feel like trying to figure out hieroglyphs on the Egyptian pyramids.

6
  • 2
    Sort of on topic - regular-expressions.info . Use this and @Jalayn's suggestion below. Learn by doing!
    – Freiheit
    Sep 22, 2011 at 13:53
  • 6
    gskinner.com/RegExr is the best tool for developing regexs i've found. Sep 22, 2011 at 16:15
  • A little at a time. Start with the simple stuff ("aaa", "aa.", "a*b", etc.) and work your way up to implementation-specific components (i.e. PCRE). Then come up with a pattern and try to make a regex that fits it.
    – tylerl
    Sep 23, 2011 at 9:08
  • I learned by trial and error with the great program RegexBuddy. regexbuddy.com (I get no credit for advertising this, this program really made it easy to learn) Sep 23, 2011 at 13:57
  • rubular.com is a good tool for developing regexs.
    – Gazler
    Sep 25, 2011 at 9:29

18 Answers 18

69

I think that the knowledge of the Automata theory is critical for understanding.

Once you understand what an automaton is, and how regular languages are defined, understanding the regular expressions will be much easier.

As to the specific syntax and differences between the various implementations... Well, some things you just have to remember. There are aids for that, too.

Edit

Some of the comments below raised important points:

  1. Don't forget that regular expressions (as implemented in most programming languages) are a superset of regular expressions in automata theory. While a good theoretical background is a useful place to start, it won't tell you everything. (Thanks, David Thornley)

  2. Multiple commenters say that it is possible to learn the various regex syntax without learning the theoretical basis. While it is true that you can learn syntax without fully understanding how it works, it was my impression that the full understanding is what the OP was after. The question was about the actual basis: when does the processor advance? When does it stop? How it decides that its a match? That's the basis, that's the theory, and it is based on the Automata Theory. Sure, you can drive a car without knowing how the engine works. But if you're being asked "how does the gas actually make it drive" - you have to talk about how the engine is built, don't you?

5
  • Commenters: if you want to discuss the finer points of this question, please use chat. Otherwise, please consider leaving an answer or voting on the answers that you find to be the most correct.
    – user8
    Sep 23, 2011 at 6:02
  • Thanks for the edit. This makes this answer far more near to the truth. Though I still don't think that you really need to know Automata Theory (I don't know that, but I still can write complex regular expressions), I do agree that some knowledge of the theory may help. Especially knowing how backtracking works and is controlled by greedy/ungreedy/possessive quantifiers may really help your understanding.
    – NikiC
    Sep 23, 2011 at 6:16
  • Just my 2 cents: in a recent video series about C++ STL regex library in MSDN's Channel 9, the presenter, which is also a maintainer of STL, said that they implement it as a an automata. So knowing this theory should really give the OP some insights on how regex's works.
    – korbes
    Sep 27, 2011 at 14:52
  • 5
    I don't agree with the opening statement at all. When I learned regular expressions I knew nothing about automata theory. Three decades later I still don't. What I did know was how to read a man page, take it literally, and how to experiment at a prompt. Apr 17, 2014 at 23:20
  • 1
    @Bryan well... Your experience kindof proves the point. You maybe know how to use it, but you don't really understand how it works. If you do - then you do know something about automata theory, even if you don't know to name it. But you cannot understand regular expressions fully without knowing automata theory, and no amount of reading man pages can help you there (unless you're reading man pages explaining the automata theory, of course).
    – littleadv
    Apr 17, 2014 at 23:24
36

By practicing.

I learned by having fun with web scraping. I'm sure I wasn't alone doing that just for fun.

One example: Write some code that retrieves the latest football, tennis (the sport you like in fact) scores from your favorite sports website. Do it by writing some code to load the page, extract the scores with regular expressions and output them to the console or to some text file. Make sure that with the regular expression you choose you only retrieve the scores, and nothing else. Sometimes this can be quite challenging :-)

Second example: Write some code that retrieves the picture of your favorite webcomic, (I like Sinfest a lot for example) and that stores it somewhere on your hard drive. Use only regular expressions to retrieve the "img" tag and its content. Optionally also retrieve its title if it's stored somewhere.

4
  • 15
    Parsing HTML with regular expressions is generally a bad idea.
    – Maxpm
    Sep 22, 2011 at 18:29
  • 10
    Of course it is a bad idea. Using DOM/Sax parsers or other dedicated XML readers is what should be used "generally". But the topic here is about learning regular expressions, and I shared how I learned about regular expressions in what I thought was a "fun" way.
    – Jalayn
    Sep 22, 2011 at 18:57
  • 3
    Using XML parsers for HTML web pages is an even worse idea than scraping them with regular expressions.
    – skolima
    Sep 23, 2011 at 9:03
  • 8
    Ah well, I wanted to be more precise on what I thought about that but I was lazy and I just reacted on the comment... I think we can all agree that 1. using regular expressions to parse the entire document is a bad idea 2. using XML parsers to parse HTML is a bad idea 3. using XML parsers to parse XHTML is right 4. using regular expressions to retrieve one-liners or some very specific information from HTML is right. Or I may just sum it up: the right tool for the right job...
    – Jalayn
    Sep 23, 2011 at 9:59
23

I know you're not asking for resources but Mastering Regular Expressions by Jeffrey E.F. Friedl was how I learned how they work and how to use them. Even after getting to the point of using a lot of them to parse different things the first chapter had new things for me.

You want to understand those damn regexp? Read this book.

4
  • 2
    This should be the definitive answer.
    – slim
    Sep 22, 2011 at 14:50
  • 1
    +100,000 One of the best technical books ever, and conveniently about the topic of the question.
    – Affe
    Sep 22, 2011 at 17:19
  • Loved this book. Key point being that it helped me understand all the different functionalities available in Regex. You won't be able to memorize all the syntax from reading a book, but the book will show you all the things that exist so you know what tools you have to solve a problem when it comes along.
    – Kibbee
    Sep 23, 2011 at 0:54
  • Absolutely +1 for this answer. I flailed away at regex until I finally sat down and read this essential volume line-by-line. Now Friedl gave me enough of a foundation that I can reason my way through all of the many non-standard variations that plague us today! I highly recommend this reference to the OP and everyone else. +1 to @slim for his comment, also! Sep 26, 2011 at 20:08
19

Where is the start of it, the end? When does the regexp processor advance on the text, when does it hold its stand and tries another match? etc.

I would start by clarifying your goals and then figuring out your learning style.

What struck me about your question is that you ask "how do I learn regular expressions?" and then immediately follow that up with the question "how does the regular expression engine work internally?" You seem to be implying that those two things have something to do with each other, which is a telling point. Maybe you are a person who learns how something works by taking it apart, or by building it yourself.

For beginner applications, there is usually no need to understand how a tool works in order to use it effectively. You don't need to know how a drill motor works in order to put holes in wood; you need to understand how to use the drill, not how to build a drill.

So what is your goal? Are you intending to learn how to build a regular expression engine? or are you intending to learn how to effectively use regular expressions to solve business problems? Achieving those different goals likely requires different learning techniques.

To address your specific question about how the regular expression engine works: it depends. The "classic" theoretical approach to regular expressions is to use the regular expression as a blueprint for a nondeterministic finite automaton, then build the equivalent deterministic finite automaton, and then execute that automaton against the input.

Almost no one actually does this for several reasons. First, the number of states multiplied by the number of possible input characters yields a state transition table that is freakin' enormous even for small regular expressions. Sure, most of that can be compressed, but still, it's a lot of transition rules. Second, other approaches are usually faster. Third, so-called "regular" expressions are in modern regexp libraries, nothing of the sort. They are not regular languages at all; they're often recognized by pushdown automata, not finite automata languages.

(I started writing a long series on how all this stuff works but I ran out of steam after only the first twelve articles. You might find them interesting if you would like a brief primer on the theoretical background of basic regular expressions.)

Real regular expression engines instead typically use a backtracking strategy. The regular expression engine we built for the JScript engine over a decade ago now compiles the regular expression into a bytecode language that includes primitives for recognizing sequences and backtracking to earlier states. We then built an interpreter for that bytecode language.

I would not try to understand how a regexp engine works before having a pretty solid understanding of how to use regular expressions. Concentrate on that before you start digging into the optimization strategies various different engines.

7
  • +1 because you address several things that are good to know when using regexes; I disagree however on your judgement that it's not necessary to know the insides. For drilling, you are totally right; in computers, I have found that sooner than I think at first, I get to the point where I have to understand something's insides to master its application – whether it's C++ (compilers), web servers (HTTP), or regexes (automata theory). Not to the point where I become an expert, but a good understanding of the underlying principles is often the quickest way to learn. Sep 22, 2011 at 19:35
  • 3
    @Felix: I think we actually agree. I said that for beginner applications there is usually no need to understand how a tool works in order to use it. Those weasel words were deliberate. For journeyman or masterful use of a tool it is very helpful to understand at least something about its internals so that you can accurately predict where the tool will have bad performance, say. Sep 22, 2011 at 19:38
  • Hmm, I'd have to disagree somewhat. Some of the most useful business programs I've built have used the theory I learned in lexx and yacc to solve problems efficiently. You are right though, a complete, phd level understanding isn't necessary. I'll have to read the blog posts, they look most interesting. Sep 23, 2011 at 1:08
  • You say that regular expressions are not regular - but I thought the world regular in the name was referring to the expressions it matches - e.g. the regular expression "[0-9]{3}" which can match any three digit number, and the three digit number 480 is an example for a regular expressions it matches. Oct 27, 2011 at 0:39
  • 1
    @configurator: A "regular" language is by definition a language that can be recognized by a finite automaton. Every regular language can be characterized by a "regular expression" consisting only of unions, alternatives, catenations, and the Kleene Star. But most "regular expression" engines these days recognize more complex languages than regular languages; for example, the language of "sentences with correctly matched parentheses" is not regular, but you can match it with a "regular expression" in some regexp engines. Oct 27, 2011 at 4:27
6

How the heck do I tackle them?

Like any new thing:

10 Study
20 Practice
30 goto 10

Study

I find that most successful teachers start teaching any subject by first providing a bit of background to the subject. It's important to have a context of what you're learning and, most importantly, why you're learning it.

It's all string matching

Regular Expressions are a means of matching patterns in text. It's a declarative language itself incorporated into numerous other programming language.

I'd like to emphasize that it's a declarative language, regular expressions are useful for expressing what string to match, but they do not in any way express how the program is to go about doing the matching. For this reason it's possible to use regular expressions very quickly and very slowly in the same programming language simply by using a different RegEx parser.

The reason for creating regular expressions are the same for the creation of most programming languages: programmers found themselves performing the same complicated task over and over and decided they wanted a simpler way of writing the code.

Some will (and should) complain about my previous sentence by saying something along the lines of:

RegEx doesn't make a program simpler.

it's true

RegEx doesn't make a program any simpler, RegEx makes writing the program simpler. You still need to be thorough in your testing to be certain that all correct cases are matched correctly, and all incorrect cases are not. It's really hard to test "all", and with complicated patterns, it's really hard to test "most". At worst, you should still be testing "some" cases.

lets incorporate some examples I've obligatorily chosen JavaScript's RegEx engine because I can test it live in the browser easily and because I won't have to do any string escaping while using RegEx literals.

When you do normal string matching, you test one string value against another. They can come from anywhere, but in the end it takes two strings being compared against one-another:

if ( 'foo' == 'bar' ) doSomething();

That example sucks because it will never do anything

if ( foo == 'bar' ) doSomething();

Much better; now, we don't actually know ahead of time whether or not something will be done. We can now start accepting user input:

if ( prompt( 'Say "bar" to do something.' ) == 'bar' ) doSomething();

Wonderful, now users can input bar and something will happen, until you get bug reports from users saying that "bar" isn't working, or that "BAR" isn't working, or that they've typed BRA 100 times and nothing ever happens.

Ignoring the misspellings and extra characters, 'bar' != 'BAR', and programmers need to think up a way of testing for where characters are the wrong case.

Simple solution, use toLowerCase. That works wonderfully, but what about our users who are using British English over American English when you're matching something == 'color'? Now you'll have to match something == 'color' || somthing == 'colour'.

Long story short, simple patterns turn into lots of repetitive code very quickly.

The color example can simply be matched with:

/colou?r/.test( something )

a solid understanding of the basics of regular expressions can significantly reduce the amount of time you waste reinventing the wheel.

Where to study

Most languages that implement regular expressions have at least one resource available for the specific syntax of using Regular expressions within that language. One for JavaScript can be found on MDN

read it.
all of it.
then read it again.

It takes time to learn, think of it as an investment: an hour to learn RegEx now saves an hour the next time you need to do some string pattern matching, and then another hour the next time after that.

Practice

After reading all about RegEx, you probably wont understand most of it. That's because you're not actually doing anything with it.

I mentioned why I chose JS for this example, I urge you to mess with it in your browser. It's quick, and you can do it right in your URL bar.

JS has a few different and simple ways of using RegEx:

string.match( regex )
regex.exec( string )
regex.test( string )

Starting with something simple like:

javascript:'color'.match(/colou?r/);

is an easy way to get your foot in the door. Play with it, break it see what matches, and what doesn't.

When you get stuck on practice, continue to 30. You need to read to learn more, but you need to practice to truly understand what you've learned.

1
  • +1 for recommending messing with JavaScript in the browser. Sep 26, 2011 at 20:20
5

Brian Kernighan writes a simple reg-ex processor in the book Beautiful Code. I realize you are not looking for resources, but it might help to see a basic implementation, on the inside.

1
  • The mentioned "regex processor" actually doesn't implement disjunctions, and with the given approach, it's very hard to add them. I like the book, but this is one thing I was disappointed with. Sep 22, 2011 at 19:26
4

In normal development, debugging code can provide very useful insights. Regular expressions aren't any different. So, at the risk of sounding like an advertisement, get RegexBuddy. It has a great tool to visually display what the engine is doing as it handles your expression and the input string.

3
  • 1
    +1, "Regex Hero" is nice too: regexhero.net/tester
    – Angelo
    Sep 22, 2011 at 21:05
  • Regexbuddy is one of my favourite tools. Seeing the tree view is incredibly helpful, as is being able to test instantly as you generate your regex. I've learned a lot more regex without trying to learn it just by using it.
    – Chao
    Sep 23, 2011 at 9:55
  • 1
    I have always found RegexBuddy interesting, but I dislike having to buy it. For basic regex testing, there are many other utilities. For seeing a textual description of the regex though there are fewer tools. Regex Hero's paid version does it too. One thing rather unique to RegexBuddy though is the Regex Debugger, which shows each acceptance or rejection of a character, and each backtrack in excrutiating detail, which can really help when debuuging a large and very complicated regex. I've not noticed any other tool that does that. Sep 23, 2011 at 15:01
3

Regular expressions can become very complicated very quickly, so I would recommend that you start learning it using tutorials. Know that the simplest form of regular expression is a string representing what you're searching for. Unfortunately, to be able to define special search rules, it requires certain characters, and these characters must be escaped or you'd be creating an invalid or incorrect regular expression.

My advice is to start with an example of something you're searching for and escape it. So in other words, if you were looking for anything in parentheses, take an example of one such string in the text you're searching in: (this is an example of something you'd want to find)

Start by escaping characters so that you search for the literal character: \(this is an example of something you'd want to find\)

Test it, verify that it finds your example correctly. Then generalize the expression to find any such text, not just the example you found. So it would then become: \([^)]*\) (means any character that isn't ")" for any number of occurrences, including 0).

Test it again, and verify that not only does it find your example, but others like it. Search for more complicated but more frequent regular expressions on the internet and patch them with your existing regular expressions to avoid having to worry about every single possibility.

That's about it. And oh, learn and love \Q ... \E. In most regular expression languages, \Q indicates the beginning of a literal pattern and \E marks the end, in case you have to deal with searching for particularly sophisticated patterns and don't know how to escape them. That saved my life more than a couple occasions.

3

I'll give you a simple answer for a simple question. First, you need to understand what Regular Expressions (RegEx) are - what they do, what they are used for. Then, a great tool to get started.

  1. What Is It? RegEx is a language for expressing pattern matching. That is to say, using it, you can create a combination of characters that recognizes, or finds, patterns in text. How is this useful? In programming, you can tell computers to match text from some source (a user input, a web page, etc.) and detect whether or not specific patters of text are contained within it. For example, a period (.) represents any character - letter or number. Numbers in braces represent numbers of iterations, so ".{1,30}" indicates any character, repeated between 1 and 30 times - in other words, you can't have an empty string, and it can't be longer than 30 characters. And it goes on from there.

  2. How to get started learning? The absolute best tool I have seen is Expresso, but it is only for Windows. It has a very extensive GUI where you click through the elements you want to add to your expression, then a tester to check it against various input to see the results. I haven't seen anything good on the Mac (but I am running Windows on VMWare, so don't really need a Mac version), haven't spent a lot of time looking on Linux.

1
  • 1
    Thanks for the tip about Expresso. I tried it out and it is awesome! Sep 25, 2011 at 18:39
3

In addition to a good reference, the way you really learn is to use good learning tools. One is using the open-source Vim editor, with two options set:

  1. :set incsearch ...as you type in a search pattern on the command line, the editor on-the-fly jumps to the first piece of text that matches and highlights exactly what is matching. If you type something that makes it no longer match anything, Vim jumps your cursor back to where you were when you started.
  2. :set hlsearch ...this tells Vim to show a highlighted background on all text that matches the current RE search.

The other is to use a free tool call RegExCoach. You paste in text that you want to search, then in another window you develop your regular expression. Like Vim, it highlights successful matches on the fly.

1
  • RegExCoach is now shareware. I found it very helpful in developing complex Perl-style REs.
    – Firstrock
    Sep 22, 2011 at 21:59
2

You start out with a basic string comparison. Very easy, but also not that powerful.

Next, it may have occured to you, that you need case insesitive comparisions, so that "greek" and "GreeK" compare equal. This is a bit more powerful.

One day you notice small differences in spelling should not prevent 2 words from comparing equal: i.e. "organize" and "organise" should compare equal. You sit down and write some code that does this and you're happy.

Until you abstract a bit more and realize that you sometimes want all words that end in "ize" to compare equal with their brothers in british spelling. Or, repetitions of some strings a certain amount of times. And, of course, you need to combina all that.

And so on. Finally, you most likely end up with some notation where not every character stands for itself. Nothing else is a regexp. One can see it as description of a set of strings.

And then, it is fairly easy and comes down to the following 3 basic principles:

You have basic regexps: chars that stand for themselves, character classes, handy and not so handy abbreviations for character classes like \d or \p{Lu} for uppercase letters.

And then, you have some possibilities to combine them: if r1 and r2 are regexps, then so are r1r2 r1|r2 (r1).

Last, but not least the repetition modifiers: r? r* r+ r{n,m}

This is most you need to know. Anything else you can lookup when you need it.

2

Two good other answers tell you to learn the theory behind regexes, and to practice, which are both great advice. I'd also recommend getting a good visual regex tool to help you out if you're serious.

RegexBuddy, for example, has a visual debug mode that lets you step through a regex's execution, and shows you via highlights and explanatory text what the regex engine is doing at each step. There's a video demonstrating this debugging on their site.

2

Everything we can give you is more resources to learn. This question is itself a resource.

By the way, I've learned regular expressions quite easily from this site: http://www.regular-expressions.info/

1

For me, seeing what the regexp is matching as I am building it really helps makes my life easier and has helped me better understand them.

To do this, I will open up a file with the target text in Emacs, and then use the isearch-forward-regexp command. As you enter the regexp, Emacs shows you what it is matching (that's the "isearch" part).

To run the command, in Emacs, you can use <ESC>xisearch-forward-regexp.

1

I learned regular expressions by learning flex and bison, which are used to build lexical analyzers and parsers. You couldn't have a parser without regular expressions, and the book lexx and yacc is incredibly good at walking through the theory without moving too fast.

Fundamentally, practically all regex engines these days follow the same principles. They are all finite state machines and if you truly grok that, then you have a leg up on almost any code you write. It similar to learning recursion in that, once you get it, you apply it to problems instinctively. They're easy to solve with the right tool, but very hard without it.

Another thing about learning lexx and yacc, as compared to regular expressions, is you learn how they work internally. How the program does look ahead, why it finishes a match, how it holds the data, and so much more. Understanding pointers is an absolute must, but if you get lexx and yacc, and go through it from the beginning you'll learn everything you asked, and have a massively powerful tool for the rest of your career.

This question includes a bunch of resources for learning, and a flex skeleton I threw together.

1

Anymore, I first try to make sure there isn't an easier way to solve the problem/"tokenize" the string.

When you can't find one, I look at it as a problem not of trying to match what you want out of the string, rather, it's a matter of NOT matching what you don't want. This is mostly because regex's are greedy. But it has served me well as an approach for getting what I want.

Here's an example:

string = "Sep 22 19:57:38 host fcron[9137]: \
          Job fbsetbg -r $HOME/backgrounds/ \
          started for user user (pid 9138)"

to match the minute:

string.match /^\w+\s\d+\s\d+:(\d+):\d+\s\w+\s/ # correct but bad
string.match /\d+:([^:]+):\d+/                 # correct and good

Instead of trying to find the time along with everything else, try to find the distinct boundaries.

The example is a bit contrived, but all I could come up with.

1

One approach I used was to find a bunch of open source projects that needed syntax updates and then write a increasingly complex sed script, which was comprised of many regular expressions.

The script needed to run against many different files in each open source project. Then be run against many different projects with different styles. I started with something very simple like %s/before/after then I found that it matched too many cases. so I added more stuff to prevent that. Then I found different projects using different syntax styles that needed different changes.

In the end I ended up with

  • great skills and knowledge about regular expressions
  • good skills with sed
  • helping out many open source projects
  • getting a lot of contribution activity shown on my github profile
  • another good 'swiss-army knife' tool for the virtual toolbelt

and was helped in this approach by the need to

  • achieve actual goals without cheating
  • use the (regex) skills as part of a greater goal with greater motivation.
  • be able to show proof of the skills I learned by changing others code and then having the changes reviewed.

I will also pass along that there are a bunch of sites for the various languages - ruby, javascript, etc. that will let you play around with expressions and sample text for immediate gratification. These are:

regexes in multiple languages on one site

focus on the match groups:

0

I've found learning regular expressions similar to learning the multiplication tables - yes, you need to understand the ideas behind it, but ultimately, you just have to do it often and repeatedly.

When I was learning, I would set myself a goal of doing a few regex exercises per day. In practice, this meant at least once a day, I would try to look at a string or text on my screen, and come up with a challenge - "can I get all the email addresses out of here", or "find all the occurrences of the word 'code' used as a verb rather than a noun," stuff like that.

Doing that for a few weeks really paid off - and of course, periodic reviews and refreshers are needed. I'm about due for one.

I found this online tool helpful too, as it let's me test regex in real time: http://www.gethifi.com/tools/regex

Not the answer you're looking for? Browse other questions tagged or ask your own question.