DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

Put the Longer Branch First Is a No-Op in grep and Changes 15.5% of Answers in JavaScript

#regex #programming #javascript #linux

A real POSIX ERE matcher: a hand-written parser, a Thompson automaton run as a parallel simulation for leftmost-longest, and a backtracker for leftmost-first, over one shared syntax tree — so the same pattern string can be read two ways, matched two ways, and the four answers put side by side.

Try any pattern: https://dev48.infy.uk/solve/day77-posix-ere-matcher.html

The most-repeated piece of regex advice

Everyone knows the first rule of alternation: branches are tried in order, so put the longer one first. /a|ab/ against ab matches a in JavaScript, Python and Perl. In grep, sed and awk it matches ab — and so does /ab|a/.

Over 12,000 swapped pairs:

branches reordered
POSIX answer changes 0 times
ECMAScript answer changes 1,860 times — 15.50%

The single most-repeated piece of regex advice is load-bearing in one family and a no-op in the other, with no error either way.

The finding is positional

a*? is three characters. To ECMAScript it is one lazy quantifier and the answer is the empty string. To POSIX it is two operators, (a*)?, and the answer is the whole run. Opposite extremes from an identical spelling, decided only by which binary you piped it through.

Inside a bracket expression POSIX has no escape character at all, so [\.] is a class of two members — backslash and dot. grep and sed agree; gawk, shipped by the same project, does not.

Of 40 frontier patterns, five real implementations return the same answer for only 19. Twenty split two ways, and ^* splits three:

^*    sed:  syntax error
      grep: matches
      gawk: no match
Enter fullscreen mode Exit fullscreen mode

The divergence is an identity, not chaos

Over 16,800 generated cases the two policies:

  • always agree on whether there is a match
  • always start at the same index
  • and the ECMAScript match is a prefix of the POSIX match — 16,800 out of 16,800

They differ only in how much, on 1,758 of them — 10.46%. That is a far more useful thing to know than "the engines differ": you can predict the direction every time.

Verifier 524,305 asserts, page self-check 18,971, 0 failures.

Top comments (0)