Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example:

Assume the following regular expression:

((a(b+))+(a|c))|a|c


Why is it that this accepts the strings:

a
c
abba
abbabbba
abbabbc


etc

But when I flip it around and use the regular expression

a|c|((a(b+))+(a|c))


I can now only ever get the following strings when I check it with a RegExp tester:

a
c


I know it is to do with the order of precedence but I don't understand why, please could somebody enlighten me?

• Both the patterns do match all the above strings. How did you test this? Did you try testing the string against the pattern, or did you try to find the matching substrings? Dec 11, 2013 at 4:43
• I think you should re-examine your premises/assumptions. You seem to have multiple assumptions that don't look accurate: Untitled has pointed out one (your assumption that the latter regexp doesn't accept the former strings); and you seem to be assuming that it has to do with order of precedence (which doesn't look right to me). I suggest you edit your question accordingly. I suspect you're not asking quite the right question just yet.
– D.W.
Dec 11, 2013 at 5:02
• Hi, I tested it using rubular.com
– user12006
Dec 11, 2013 at 5:29
• Any time you think you need to understand order of precedence to make something work, you should use brackets to make it absolutely clear. Everybody knows that $a\times b+c$ means $(a\times b)+c$ and everybody knows that $\neg A \vee B$ means $(\neg A)\vee B$ but for just about anything else, relying on order of precedence just invites mistakes and misunderstandings. Dec 11, 2013 at 11:08

Both the patterns match your given strings and are equivalent. The problem here is that your tester does not try to match the string against the pattern, but tries to find matching substrings, and it does that by trying each of the ORed patterns in order. Hence the second pattern stops when $a$ is matched, but the first one matches the whole string.

To see the difference Look at the below code, written in Java:

public static void main(String[] args) {
test("((a(b+))+(a|c))|a|c", "abbabbc");
test("a|c|((a(b+))+(a|c))", "abbabbc");
}

private static void test(String pattern, String str) {
System.out.println(str.matches(pattern));
Matcher matcher = Pattern.compile(pattern).matcher(str);
while(matcher.find())
System.out.println(str.substring(matcher.start(), matcher.end()));
}


The output is

true
abbabbc
true
a
a
c


which shows that both patterns do match $abbabbc$. They are only different in eyes of a matching-substrings-finder program.

• Awesome. I would so up vote this if I had the rep.
– user12006
Dec 11, 2013 at 6:01
• You can force most real-world regexp matchers to match an expression R against the whole input (line) by modifying it to ^(R)$ (creating a new capture group). Dec 11, 2013 at 8:00 You can't write 3 ORs. Example: A or B or C => it will compare A or B and ignore C ((a(b+))+(a|c))|a|c the last "|c" ignored. The proof, does it accept "abcc" ? likewise a|c|((a(b+))+(a|c)) the "|((a(b+))+(a|c))" ignored and only a|c left. Good Luck. • How does "$abcc\$" prove that one can not use 3 ORs? It is rejected, simply because it doesn't match neither of the three ORed expressions. Dec 11, 2013 at 4:29