News for hackers. Stuff that matters.
Re:A Regular Expression Matcher (2007) by posharma on Thursday August 25, 2022 @02:20AM (#32590240)
Only Rob could pull this feat. Not for the lesser mortals :-)
Re:A Regular Expression Matcher (2007) by tgv on Thursday August 25, 2022 @03:29AM (#32590712)
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.

Re:A Regular Expression Matcher (2007) by eesmith on Thursday August 25, 2022 @08:53AM (#32593061)
The book, two pages later, gives a left-longest implementation of matchstar. See 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/22...

Re:A Regular Expression Matcher (2007) by abecedarius on Friday August 26, 2022 @10:52AM (#32608289)
It's a natural approach to anyone familiar with the pattern matchers explained in old Lisp books. This is not just hindsight because when I first read this chapter in Beautiful Code I stopped after the problem statement and wrote something similar before reading the rest.

(I didn't choose exactly the same grep sublanguage to implement -- it was something like supporting the most basic escaping instead of ^ and $.)