Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I am teaching myself regular expressions, and I got stuck at »greedy« vs. »lazy« repeatings.

What I found out so far is that

  • »greedy« means that the RegExp looks for as many matches as possible, where
  • »lazy« means that the RegExp looks for as little matches as possible

Most articles I found deal with a) using it in a programming language, while I am stuck here with grep and egrep or b) use grep -P to activate Perl Mode; but as I don't have any knowledge about Perl yet this isn't very helpful for me.

My comprehension question: I came to this sledgehammer method:

  • lazy repetitions will look for the shortest possible match
  • if results are too long → tone down the repeater with ?
  • if results are still too long → look for another solution

This is what I was able to figure out through examples and experiments with HTML code where I got to some but not overwhelming results.

I would be grateful if somebody could tell me if and where I missed some important points with my summary.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

It's not the shortest possible match, just a short match. Greedy mode tries to find the last possible match, lazy mode the first possible match. But the first possible match is not necessarily the shortest one.

Take the input string foobarbaz and the regexp o.*a (greedy) or o.*?a (ungreedy).

The shortest possible match in this input string would be oba.

However the RegExp looks for matches from left to right, so the o finds the first o in foobarbaz. And if the rest of the pattern produces a match, that's where it stays.

Following the first o, .* (greedy) eats obarbaz (the entire string) and then backtracks in order to match the rest of the pattern (a). Thus it finds the last a in baz and ends up matching oobarba.

Following the first o, .*? (ungreedy) doesn't eat the entire string, instead it looks for the first occurance of the rest of the pattern. So first it sees the second o, which doesn't match a, then it sees b, which doesn't match a, then it sees a, which matches a, and because it's lazy that's where it stops. (and the result is ooba, but not oba)

So while it's not THE shortest possible one, it's a shorter one than the greedy version.

share|improve this answer
    
You're wrong: echo "foobarbaz" | grep -o -P "o.*?a" returns ooba (not oobarba as you claim), because that is the shortest match starting with the first 'o'. oba doesn't happen because matches will not overlap left to right. Non-greedy matches the shortest option, greedy the longest. –  goldilocks Apr 10 '13 at 19:31
    
You misread. o.*a matches oobarba, o.*?a matches ooba, and I never claimed otherwise. (edited and added a clarification for the non-greedy paragraph) –  frostschutz Apr 11 '13 at 11:00
    
All apologies. It still confuses the issue to say that is not the shortest match, if you are thinking like a regexp from left to right, as opposed to the semantic red herring of someone looking at the whole thing on a piece of paper (regexps are not good for problems of that sort), but nice explanation otherwise, +1. –  goldilocks Apr 11 '13 at 13:26
    
I guess it comes down to your definition of "the shortest possible match". I just wanted to make clear that it does not search for all possible matches and then just return whichever is shortest, since that's not what it does at all. To a programmer this is obvious but regexp are also used by average joe –  frostschutz Apr 11 '13 at 16:41

"Perl Mode" refers to perl compatible regular expressions (PCRE). Colloquially speaking, this is the regular expression style used natively by most modern languages, if they have built-in native regexps -- perl, python, ruby, php, javascript, java -- although there may be slight differences between them; technically, PCRE is derived from but not identical to the perl regexp engine, etc, but if you can use regexps in one of those languages, they're 99% the same in the others. It predominates where it is an option because it is an improvement on the older style now disguished as POSIX regexps which is the default mode of old school tools like grep.

The "non-greedy" aka. lazy modifier is not significant in the context of using grep to match lines. This is because there can be no complete line that matches a lazy expression that a greedy one will not also match, and vice versa. However, you can see the difference if you use the -o switch, which shows matched segment content and not whole lines (nb. this is slightly different than what --color does):

»echo "123 abc 456 def 789" > eg.txt
»grep -o -P "(\d+\s[A-Za-z]+\s)+" eg.txt
123 abc 456 def 
»grep -o -P "(\d+\s[A-Za-z]+\s)+?" eg.txt
123 abc 
456 def 
»grep -o -P "\d+\s[A-Za-z]+\s\d+" eg.txt
123 abc 456
»grep -o -P "\d+\s[A-Za-z]+\s\d+?" eg.txt
123 abc 4
56 def 7

If you are using grep this way (with -o), greediness makes a difference. If you are using grep to match complete lines that contain a pattern, non-greedy ? won't matter one way or the other.

In short: a greedy match matches as much as possible, a non-greedy match matches as little as possible.

share|improve this answer
    
Thanks for the short summary on Pearl and PCRE – this anticipated a question that lurked in the near future. As I [obviously] still struggle with the basics I want to stick to the most basic level where possible. Thanks a lot! –  erch Apr 10 '13 at 20:48

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.