[deleted]
Building a Regex Engine in Fewer Than 40 Lines of Code
31–37 of 37 posts
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#32In my experience, it's the edge cases that are a pain when implementing a regex engine. Think about weird regexes like "^*", "$?" (or any quantified zero-width match), anchors that appear in the middle of regexes, nested quantifiers (don't make much sense, but you need to generate good error messages). Once you add captures and maybe even backreferences, you get a whole new world of weird :-)
You can straight away drop any repetition of a zero-width assertion, no?
You can, but you need to drop the entire zero-width assertion if the repetition allows zero occurrences.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#33Code golf link to a similar challenge https://codegolf.stackexchange.com/questions/125708/regular-...
That does indeed implement grouping and alternative
It's nicely coded but leaves out an important part of that algorithm: the regex derivatives never get simplified for comparison, so equal states appear different, so the set of states blows up as you march along the string. If you're OK with an inefficient matcher like that, then a backtracking algorithm probably gives you even simpler code.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#34It's small, but unfortunately due to how ? is implemented with recursive backtracking (look at how matchQuestion() tries both alternatives), has an exponential worst-case runtime. Fortunately, the algorithm to do it in linear time is pretty simple too: https://swtch.com/~rsc/regexp/regexp1.html (previously discussed at https://news.ycombinator.com/item?id=466845 )
I actually don't think this is the case (I definitely might be wrong). Although the matchQuestion function has the pattern that typically resembles a function of exponential runtime (where a function invokes itself recursively multiple times), there is a slight difference in our scenario. If you look at matchQuestion's invocations of match, you'll notice that on both sides of the OR, the pattern is stripped of two characters (the "_?"). This means that the recursive invocation of match will never invoke matchQuestion a second time, unless there is a second '?', in which case it's entirely appropriate.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#35"Building a Regex Engine in Fewer than 40 Libraries of Code" .. there you go, fixed that for you.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#36A bit longer than 40 lines, but back in the day, I was a big fan of the simplicity and clarity of Henry Spencer's regex code: https://github.com/garyhouston/regexp.old
> Henry Spencer's regex code: https://github.com/garyhouston/regexp.old Glad to see that come up in this thread. It was the first clearly explained regex engine for me in _Software Solutions in C_ (Schumacher D., Academic Press, 1994). I still have a copy and the original disk (and disk image). If anyone is interested I could scan that chapter tonight.
I looked all over for a copy. I'd love a scan. Is the disk 3.5 or 5.25?
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#37It's small, but unfortunately due to how ? is implemented with recursive backtracking (look at how matchQuestion() tries both alternatives), has an exponential worst-case runtime. Fortunately, the algorithm to do it in linear time is pretty simple too: https://swtch.com/~rsc/regexp/regexp1.html (previously discussed at https://news.ycombinator.com/item?id=466845 )
I actually don't think this is the case (I definitely might be wrong). Although the matchQuestion function has the pattern that typically resembles a function of exponential runtime (where a function invokes itself recursively multiple times), there is a slight difference in our scenario. If you look at matchQuestion's invocations of match, you'll notice that on both sides of the OR, the pattern is stripped of two ch…
unless there is a second '?', in which case it's entirely appropriate.
That's precisely where the exponential behaviour comes from; consider e.g. matching the pattern "a?a?a?aaa" against "aaa". It will try matching "a?" against the first "a", which succeeds, leading to a recursive call to match "a?a?aaa" with "aa". That eventually fails, so it tries matching "a?a?aaa" against "aaa"; and inside those two branches, it also splits into two depending on whether to match the "a?", etc. The result is, for each "a?" and "a" added, the total amount of work involved in matching doubles, so it is exponential.