3 ms·
It is for lesser mortals, too. I think everyone with half a CS degree should be able to pull it off. That said: it's an implementation which doesn't behave lik
by tgv 4y ago
It is for lesser mortals, too. I think everyone with half a CS degree should be able to pull it off.
That said: it's an implementation which doesn't behave like normal regexps (it's a left-shortest match first instead of the common left-longest) and it's a back-tracker. Because this implementation doesn't allow much choice, expensive examples will look contrived, but extending this implementation with character sets, groups and choices (i.e. a|b) will make its exponential nature felt very quickly.
- eesmith 4y agoThe book, two pages later, gives a left-longest implementation of matchstar. See https://archive.org/details/practiceofprogra0000kern/page/226/mode/2up?q=matchstar https://archive.org/details/practiceofprogra0000kern/page/22... . > extending this implementation The exercises at the end of the chapter ask the student to extension the implementation along these lines. Including support for utf8. > exponential nature Both the essay and the book highlight this issue. The latter comments that some commercial greps (at the time) also had exponential behavior. https://archive.org/details/practiceofprogra0000kern/page/226/mode/2up?q=exponential https://archive.org/details/practiceofprogra0000kern/page/22...