3 ms·

Well, technically ... if your dialect supports capturing groups, there's technically a non-commutativity anyway. Assuming input is "ab", /(a)b|a(b)/ produce

by o11c 1y ago

Well, technically ... if your dialect supports capturing groups, there's technically a non-commutativity anyway. Assuming input is "ab", /(a)b|a(b)/ produces \1=a, \2=<missing> /a(b)|(a)b/ produces \2=<missing>, \1=b Probably the easiest way to test this yourself is with GNU sed.

cvoss 1y ago
What you say is not only technically untrue, it's just plain untrue. It's a choice of the language designer whether capturing groups break commutativity. Sed makes one choice. I'd guess that GP would call this broken garbage too, and I'd agree. Regular expressions have all these nice theoretical properties like closure under all the boolean operations and linear-time matching, but these nice properties get trashed by features that don't mesh or aren't fully thought through. In this case (thinking about capturing groups and commutativity), one property of regular expressions is that for each one there is a machine that can do the linear-time matching -- a DFA. Even if the regular expression contains not-mutually-exclusive alternations, when it gets compiled to a DFA, the matching procedure is deterministic by construction. I can imagine a way to integrate capturing start and end actions into the transition edges of the DFA. The right thing to do is to perform capturing on all the matching alternands, not just the first. You lose the ability to number the capturing groups left to right, but instead you should lay them out in a tree that follows the concatenation/alternation structure of the expression.
- burntsushi 1y ago
  I find your certainty here quite odd. You claim to know what the "right thing" is, but there is no implementation of it and it gives up an incredibly useful feature of capturing that general purpose regex engines all utilize.
- deleted 1y ago
  [deleted]
HelloNurse 1y ago
This is a broken regexp, with deliberate ambiguity: nondeterministically choosing the groups according to one of several matching alternatives is an implementation-defined ambiguity "resolution" that should not happen. Just write /(a)b/ or /a(b)/ or /ab/ or /(ab)/ or /(a)(b)/ which mean five slightly different things.
- deleted 1y ago
  [deleted]
- o11c 1y ago
  It's called a minimal example. You can easily get nontrivial real-world versions, such as "All vowels or all uppercase" or "Three letters, at least two of which are A's". It is not reasonable to expect the user to manually disambiguate every regex.

by o11c 1y ago

cvoss 1y ago

What you say is not only technically untrue, it's just plain untrue. It's a choice of the language designer whether capturing groups break commutativity. Sed makes one choice. I'd guess that GP would call this broken garbage too, and I'd agree. Regular expressions have all these nice theoretical properties like closure under all the boolean operations and linear-time matching, but these nice properties get trashed by features that don't mesh or aren't fully thought through. In this case (thinking about capturing groups and commutativity), one property of regular expressions is that for each one there is a machine that can do the linear-time matching -- a DFA. Even if the regular expression contains not-mutually-exclusive alternations, when it gets compiled to a DFA, the matching procedure is deterministic by construction. I can imagine a way to integrate capturing start and end actions into the transition edges of the DFA. The right thing to do is to perform capturing on all the matching alternands, not just the first. You lose the ability to number the capturing groups left to right, but instead you should lay them out in a tree that follows the concatenation/alternation structure of the expression.

burntsushi 1y ago
I find your certainty here quite odd. You claim to know what the "right thing" is, but there is no implementation of it and it gives up an incredibly useful feature of capturing that general purpose regex engines all utilize.
deleted 1y ago
[deleted]

HelloNurse 1y ago

This is a broken regexp, with deliberate ambiguity: nondeterministically choosing the groups according to one of several matching alternatives is an implementation-defined ambiguity "resolution" that should not happen. Just write /(a)b/ or /a(b)/ or /ab/ or /(ab)/ or /(a)(b)/ which mean five slightly different things.

deleted 1y ago
[deleted]
o11c 1y ago
It's called a minimal example. You can easily get nontrivial real-world versions, such as "All vowels or all uppercase" or "Three letters, at least two of which are A's". It is not reasonable to expect the user to manually disambiguate every regex.