3 ms·
Even Thompson didn't use the linear time algorithm that's named after him in Ed and Grep. The Python and Perl implementations were inspired by Henry Spencer's r
by AlotOfReading 2y ago
Even Thompson didn't use the linear time algorithm that's named after him in Ed and Grep. The Python and Perl implementations were inspired by Henry Spencer's regex, which was in turn reimplementing Thompson's backtracking implementations.
- grumpyprole 2y agoAre you sure it was Thompson who added backtracking to grep? Note also that the POSIX standard intentionally omits backtracking regex. It is a shame that others have not deprecated them.
- AlotOfReading 2y agoWe're talking about backtracking and not back references, right? The original implementations of Ed and Grep in Unix did backtracking, not back references.
- grumpyprole 2y agoOops I mean't back references, since that is the problem feature (that requires backtracking).