In this post we will look at the greedy nature of common quantifiers (* and +).
\n
\n <\/p>\n
We’re so used with the * quantifier that we almost forget its fundamental greedy nature.\u00a0 A quantifier is considered “greedy” when it tries to match the longest text chain possible before bactracking if the pattern does not match. Its counterpart is a reluctant quantifier.<\/p>\n
Example is better that words, let’s see how we can extract the root directory in an Unix system given the complete path of a file:<\/p>\n
Input: \/home\/data\/ebooks\/JavaForDummies.pdf<\/span><\/p>\n Pattern:\u00a0 ^(.+)\/.+$<\/span><\/em><\/p>\n Not surprisingly the console would display:<\/p>\n Matches : true<\/p>\n Group 1 : home\/data\/books\/JavaForDummies.pdf<\/p><\/blockquote>\n What the heck ? But we did clearly isolate the first part \/(.+)<\/span><\/em> of the pattern from the remaining trail, how comes ?<\/p>\n This is a very common mistake when you just happen to forget the greedy nature of the quantifier (greedy is their default behavior). First the regexp engine tries to match the pattern\/(.+)<\/span><\/em> with the longest possible text.\u00a0The regexp engine starts by consuming all the text:<\/p>\n \/(.+)<\/span><\/em> :\u00a0\u00a0\u00a0\u00a0 \/home\/data\/books\/JavaForDummies.pdf<\/span>\u2191<\/p>\n The first part of the pattern does match, and the engine will stop here, reporting the entire text as the match. The last part of the pattern (?:\/.+)*<\/span><\/em> did indeed match with .. nothing because the * quantifier means nothing or more and it this case it matched nothing.<\/p>\n To circumvent this issue, one can thing to turn the * into + to force the regexp engine to match. The result is no even close to what we expect:<\/p>\n Matches : true<\/p>\n Group 1 : home\/data\/books<\/p><\/blockquote>\n We did get rid of the last matching block (\/JavaForDummies.pdf<\/span>) but it’s still not satisfactory.<\/p>\n But ? Wasn’t the + in (?:\/.+)+<\/span><\/em>\u00a0supposed to be greedy ? Why didn’t it match \/data\/books\/JavaForDummies.pdf<\/span> but only the last part ?<\/p>\n Well, first come, first served. The regexp engine starts processing the \/(.+) <\/span><\/em>part first and since it is greedy it will consume all the string. But by doing so, there is nothing left to be matched with (?:\/.+)+<\/span><\/em> so the regexp engine is forced to give up as many characters as needed so that the WHOLE pattern matches.<\/p>\n Step 1.\u00a0 \/home\/data\/books\/JavaForDummies.pdf\u2191<\/span><\/p>\n Step 2. \/home\/data\/books\/JavaForDummies.pd\u2191f<\/span><\/p>\n Step 3. \/home\/data\/books\/JavaForDummies.p\u2191df<\/span><\/p>\n …<\/p>\n Step 20. \/home\/data\/books\u2191<\/span><\/p>\n As long as (?:\/.+)+<\/span><\/em> can match anything, be it the shortest length, the regexp engine will stop processing and return the successful result. Indeed the greediness of the first part\u00a0\/(.+) <\/span><\/em> has priority over the greediness of the second one (?:\/.+)+<\/span><\/em>.<\/p>\n Now, back to our issue, we still want to extract the root folder from the file path. Each folder level in the path is delimited by the slash \/. The idea here would be to take the first group of text between slashes:<\/p>\n Patter: ^\/([^\/]+)\/.+$<\/span><\/em><\/p>\n This time the output is:<\/p>\n \u00a0Matches ? true That’s what we wanted. The trick here is the use of a negation in a character class:\u00a0[^\/]<\/span><\/em>. This means “anything except the a\/<\/em>“. Combined with the beginning \/ and the second \/, we can isolate the root folder from the remaining path: \/([^\/]+)\/<\/span><\/em><\/p>\n Alternatively we can use the reluctant version of our + quantifier:\u00a0 +?<\/p>\n Pattern:\u00a0 ^\/(.+?<\/span>)(?:\/.+)+$<\/span><\/em><\/p>\n The output:<\/p>\n \u00a0Matches ? true This time, instead of starting by consuming all the string, the reluctant +? will consume character by character until the whole pattern matches, thus giving us the smallest text that can match the string match.<\/p>\n <\/p>\n Recommended readings:<\/p>\n\n\nString text = "\/home\/data\/books\/JavaForDummies.pdf";\n\n \u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0Pattern pattern = Pattern.compile("^\/(.+)(?:\/.+)*$");\n \u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0Matcher matcher = pattern.matcher(text);\n \u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0if(matcher.matches())\n \u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0{\n \u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0System.out.println(" Root folder : " + matcher.group(1));\n \u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0}\n\n<\/pre>\n\n
\n
\n
\n
\nGroup 1 : home<\/p><\/blockquote>\n
\nGroup 1 : home<\/p><\/blockquote>\n