Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
Sort of on topic - regular-expressions.info . Use this and @Jalayn's suggestion below. Learn by doing! –  Freiheit Sep 22 '11 at 13:53
6  
gskinner.com/RegExr is the best tool for developing regexs i've found. –  Callum Rogers Sep 22 '11 at 16:15
show 4 more comments

18 Answers

up vote 65 down vote accepted

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?

share|improve this answer
1  
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. –  Bryan Oakley 7 hours ago
show 4 more comments

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.

share|improve this answer
14  
Parsing HTML with regular expressions is generally a bad idea. –  Maxpm Sep 22 '11 at 18:29
7  
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 '11 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 '11 at 9:03
7  
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 '11 at 9:59
add comment

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.

share|improve this answer
2  
This should be the definitive answer. –  slim Sep 22 '11 at 14:50
1  
+100,000 One of the best technical books ever, and conveniently about the topic of the question. –  Affe Sep 22 '11 at 17:19
show 2 more comments

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.

share|improve this answer
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. –  Eric Lippert Sep 22 '11 at 19:38
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. –  Eric Lippert Oct 27 '11 at 4:27
show 5 more comments

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
1  
+1, "Regex Hero" is nice too: regexhero.net/tester –  Angelo Sep 22 '11 at 21:05
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. –  Kevin Cathcart Sep 23 '11 at 15:01
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
Thanks for the tip about Expresso. I tried it out and it is awesome! –  Jim In Texas Sep 25 '11 at 18:39
add comment

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.

share|improve this answer
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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/

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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:

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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