16

Both are supposed to the best of my knowledge to be the same but I actually see a difference, look at this minimal example from this question:

a<-c("/Cajon_Criolla_20141024","/Linon_20141115_20141130",
"/Cat/LIQUID",
"/c_puertas_20141206_20141107",
"/C_Puertas_3_20141017_20141018",
"/c_puertas_navidad_20141204_20141205")

sub("(.*?)_([0-9]{8})(.*)$","\\2",a)
[1] "20141024"    "20141130"    "/Cat/LIQUID" "20141107" "20141018"   
[6] "20141205"   

sub("(.*?)_([0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9])(.*)$","\\2",a)
[1] "20141024"    "20141115"    "/Cat/LIQUID" "20141206" "20141017"   
[6] "20141204" 

What am I missing? Or is this a bug?

5
  • In a semantic meaning, the two patterns are exactly the same, the only difference I know is that any regex engines are more performant with one of these two syntaxes for intrinsic reasons, but nothing of this explain the different results you obtain here. Commented Feb 25, 2015 at 22:02
  • 2
    Interestingly, if you change the parentheses to "(.*)?_([0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9]).*$" it works Commented Feb 25, 2015 at 22:32
  • 1
    @RichardScriven, but that changes the meaning of the regular expression, see: sub("(.*)?", "", "___x", perl=T) VS sub("(.*?)", "", "___x", perl=T). In this case, it doesn't matter though.
    – BrodieG
    Commented Feb 25, 2015 at 22:41
  • @BrodieG It does matter as I need the second result, not the second.
    – cmbarbu
    Commented Feb 25, 2015 at 22:50
  • @cmbarbu, agreed, I wasn't looking closely.
    – BrodieG
    Commented Feb 25, 2015 at 23:08

3 Answers 3

12

This is a bug in the TRE library related to greedy modifiers and capture groups. See:

7
  • The first quantifier used in the pattern is non-greedy and the greedy/ungreedy switcher modifier isn't used, not sure that it is the same bug. Commented Feb 25, 2015 at 22:45
  • @CasimiretHippolyte, certainly possible it is not the same bug, but there is a greedy modifier in a capture group (.*?) and as per Richard's experiment, changing that to (.*)? (i.e. taking the greedy modifier out of the capture group) fixes it, so it seems likely it is the same problem, or at a minimum very closely related.
    – BrodieG
    Commented Feb 25, 2015 at 22:48
  • .*? is a non-greedy quantifier. .* is a greedy quantifier. (?U) is the modifier that inverses these meanings. Commented Feb 25, 2015 at 22:50
  • @CasimiretHippolyte, when I say greedy modifier, I mean "modifier of greediness". I will strive to be more precise in the future ;)
    – BrodieG
    Commented Feb 25, 2015 at 22:50
  • (.*)? has a totally different behavior/meaning and is not pertinent here. Commented Feb 25, 2015 at 22:53
4

Setting perl=TRUE gives the same answer (as expected) for both expressions:

> sub("(.*?)_([0-9]{8})(.*)$","\\2",a,perl=TRUE)
[1] "20141024"    "20141115"    "/Cat/LIQUID" "20141206"    "20141017"    "20141204"   
> sub("(.*?)_([0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9])(.*)$","\\2",a,perl=TRUE)
[1] "20141024"    "20141115"    "/Cat/LIQUID" "20141206"    "20141017"    "20141204"
2
  • 4
    Interesting, but that doesn't explain the different results with the default regex mode. Commented Feb 25, 2015 at 22:04
  • So are you saying I should fill a bug report?
    – cmbarbu
    Commented Feb 25, 2015 at 22:04
2

Though I was initially convinced by BrodieG answer, it seems that [0-9] n times and [0-9]{n} are indeed different, at least for the "tre" regexp motor. According to http://www.regular-expressions.info the {} operator is greedy, [0-9] is not.

Hence the right regular expression in my case should be:

    sub("(.*?)_([0-9]{8}?)(.*)$","\\2",a)

Making all the difference:

    sub("(.*?)_([0-9]{8})(.*)$","\\2",a)
    [1] "20141024"    "20141130"    "/Cat/LIQUID" "20141107"    "20141018"   
    [6] "20141205"   
    sub("(.*?)_([0-9]{8}?)(.*)$","\\2",a)
    [1] "20141024"    "20141115"    "/Cat/LIQUID" "20141206"    "20141017"   
    [6] "20141204"

And even

    > sub("(.*)_([0-9]{8}?)(.*)$","\\2",a)
    [1] "20141024"    "20141115"    "/Cat/LIQUID" "20141206"    "20141017"   
    [6] "20141204"

Interpretation: 1) tre considers ? as "evaluate next atom the first time you can match this atom". This is always true for ".?" as everything matches, and it switches to _[0-9]{8}. When reaching the first group of 6 numbers, if {} is not greedy (no ?), as (.) matches also the first 8 numbers, the search continues to see if an other occurrence of "_[0-9]{8}" can be found on the line. If meeting the second set of 8 figures, it also memorizes it as a matching pattern, then it reaches the end of the line, the last matching pattern is kept and [0-9]{8} is matched to the second set of 8 numbers.

2) When {} operator is modified by ? The search stops the first time it sees 8 numbers, check if _(.*) can be matched to the rest. It can, so it returns the first set of 8 numbers.

Note that the perl regexp motor works differently,

1) ? after {} doesn't change a thing:

     sub("(.*)_([0-9]{8})","\\2",a,perl=TRUE)
     [1] "20141024"    "20141130"    "/Cat/LIQUID" "20141107"    "20141018"   
     [6] "20141205"   
     sub("(.*)_([0-9]{8}?)","\\2",a,perl=TRUE)
     [1] "20141024"    "20141130"    "/Cat/LIQUID" "20141107"    "20141018"   
     [6] "20141205"

2) the ? applied to .* makes it to stop at the first set of 8 figures:

     sub("(.*?)_([0-9]{8}).*","\\2",a,perl=TRUE)
     [1] "20141024"    "20141115"    "/Cat/LIQUID" "20141206"    "20141017"   
     [6] "20141204"   
     sub("(.*)_([0-9]{8}).*","\\2",a,perl=TRUE)
     [1] "20141024"    "20141130"    "/Cat/LIQUID" "20141107"    "20141018"   
     [6] "20141205" 

From these two observations, it seems that the two engines interpret differently the greediness in two different instances. I always found the greediness concept to be a bit vague ...

2
  • 3
    I'm pretty sure that the greediness of { is only meaningful when you are using wild card forms (e.g. {1,8}). What may be happening here is that the presence of two greed modifiers in capture groups offsets the bug in the TRE library.
    – BrodieG
    Commented Feb 25, 2015 at 23:34
  • Nevermind that greediness is meaningless for a fixed width pattern like {8} (though that is an issue here), the key problem is the greediness of the leftmost pattern. Regular expressions are matched left to right, so the greediness of the right pattern should not affect the greediness of the left since that is matched first. Yet that is happening. The reason why PERL and TRE are different is because there is a bug in the TRE library.
    – BrodieG
    Commented Mar 8, 2015 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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