> If the POSIX standard is going to require backreferences, then it should also require a non-backtracking implementation for regular expressions without backreferences
At least in some regexp engines, this is possible. There is a concept of possessive (as opposed to reluctant, or as it's often called, "non-greedy") quantifiers. Given the string "abb", consider the following regexes:
/[ab]+b/ -- matches "abb"
/[ab]+?b/ -- matches "ab"
/[ab]++b/ -- DOES NOT MATCH!! (Because there is no back-tracking.)
At least in some regexp engines, this is possible. There is a concept of possessive (as opposed to reluctant, or as it's often called, "non-greedy") quantifiers. Given the string "abb", consider the following regexes:
/[ab]+b/ -- matches "abb"
/[ab]+?b/ -- matches "ab"
/[ab]++b/ -- DOES NOT MATCH!! (Because there is no back-tracking.)
More info: http://www.regular-expressions.info/possessive.html
One regexp engine which implements this (see section 4): https://raw.githubusercontent.com/k-takata/Onigmo/master/doc... -- this is the engine used by modern Ruby versions.