Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a Regex Engine in Fewer Than 40 Lines of Code

nickdrane.com

Post reply on HN
Print view View original

11–20 of 37 posts

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#11

Post by masklinn »

ridiculous_fish wrote: post #8

I've written a JS regexp parser and engine. It did not fit in 40 lines. The most obnoxious part is backreferences. The atom \3 is a backreference if the whole regexp contains at least 3 capture groups; otherwise it is an octal (!) escape for char code 3. But you don't know how many capture groups there are until you're done parsing. This is why JS regexp parsers sometimes must make two passes!

FWIW back references mean you're way outside of "regular languages" so e.g. DFA usually don't support them.

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#12

Post by jlg23 »

It have been a few years since I read the code, but it was so beautifully written that I cannot imagine it was screwed up in the meantime: Edi Weitz' CL-PPCRE[1] is a beautiful implementation in CL and highly recommended if one understands one aspect (CL or Perl compatible regular expressions) and wants to learn the other one. IIRC he even discovered some bugs in the original perl implementation while creating this library.

[1] https://github.com/edicl/cl-ppcre

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#14

Post by klibertp »

In the "Beautiful Code" book there is a chapter, I think from Rob Pike, which presents a bare-bones regex implementation in C. It doesn't implement alternatives or grouping if I remember correctly, but the implementation is breathtakingly beautiful and not any longer than this one.

I think it's the same implementation described here: http://www.cs.princeton.edu/courses/archive/spr09/cos333/bea... (not 100% sure as I lost my copy of Beautiful Code :()

EDIT: I see the author links to the article at the beginning of the post. Still, I missed this on my first reading, so I think posting the link here is still worthwhile. Especially because the translation to JS kind of misses the point - the beauty of the Rob's implementation comes from recursion and pointers and JS lacks the latter.

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#15

Post by perlgeek »

In 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 :-)

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#16

Post by 13throwaway37 »

klibertp wrote: post #14

In the "Beautiful Code" book there is a chapter, I think from Rob Pike, which presents a bare-bones regex implementation in C. It doesn't implement alternatives or grouping if I remember correctly, but the implementation is breathtakingly beautiful and not any longer than this one. I think it's the same implementation described here: http://www.cs.princeton.edu/courses/archive/spr09/cos333/bea... (not 100% sure as I…

Literally the first sentence in the posted article mentions this:

I stumbled upon an article the other day where Rob Pike implements a rudimentary regular expression engine in c. I converted his code to Javascript and added test specs so that someone can self-guide themselves through the creation of the regex engine. The specs and solution can be found in this GitHub repository.

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#17

Post by userbinator »

It'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)

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#18

Post by why-el »

klibertp wrote: post #14

In the "Beautiful Code" book there is a chapter, I think from Rob Pike, which presents a bare-bones regex implementation in C. It doesn't implement alternatives or grouping if I remember correctly, but the implementation is breathtakingly beautiful and not any longer than this one. I think it's the same implementation described here: http://www.cs.princeton.edu/courses/archive/spr09/cos333/bea... (not 100% sure as I…

If you liked that chapter, check out some recent ideas of his here: https://www.youtube.com/watch?v=HxaD_trXwRE.

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#19

Post by zaarn »

I would suggest that since it lacks grouping, like one other commenter pointed out, it's not a regular expression engine, it only implements a useful subset which is not a regular expression language.

For that you need to be able to build an equivalent to the regular language expression

    (x|y)*

Re: Building a Regex Engine in Fewer Than 40 Lines of Code

#20

Post by sebcat »

lifthrasiir wrote: post #9
lindig wrote: post #2

This does not implement grouping "()" or alternatives "|". Hence, looping is only required on individual characters. This is a considerable simplification over full regexp.

I really hated that Lua's "pattern" [1] is never a regular expression nor a regular language. So annoying that it will be better not to have it. [1] https://www.lua.org/manual/5.3/manual.html#6.4.1

In Lua, LPeg[1] is my goto for anything that can't be done/gets too complex with patterns.

[1] http://www.inf.puc-rio.br/~roberto/lpeg/

Post reply on HN