Building a Regex Engine in Fewer Than 40 Lines of Code • Hacker News Board

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

#21

Post by wruza » Tue, Dec 05, 2017, 1:15 PM UTC

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

Lua is not a language to be used as is (and it isn’t in practice). Simple pattern matches are there for internal needs like constructing package paths, but one can luarocks install any regex implementation at will.

Bad side is that luarocks works fine on Windows only if no build step is involved, otherwise you’re doomed to mess with mingw/msys/msys2 environment that isn’t well-supported by third-parties; often not supported at all. It is not Lua’s fail, but it happens. New complicated build systems like CMake only make things worse since you cannot simply guess flags and gcc .c together anymore.

Edit: this is also true for all languages except maybe perl that includes full mingw system with it. Idk why some package managers do not prebuild windows packages on server-side. Windows actually does a lot to maintain binary compatibility.

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

#22

Post by erickj » Tue, Dec 05, 2017, 1:38 PM UTC

userbinator wrote: post #17

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 )

Here is the reference implementation for Russ Cox's work:

https://github.com/google/re2

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

#23

Post by jason-johnson » Tue, Dec 05, 2017, 1:40 PM UTC

Depending on how it’s being counted, I have a regex engine in around 30 lines [1] (the parser is longer). It handles branching, grouping, etc. and it’s run time is proportional to the length of the string being searched (I.e. no infinite loops on certain patterns, etc.).

[1] https://github.com/jason-johnson/frobo/blob/master/src/Text/...

The “match” function. And yes, this is ugly and needs to be cleaned up.

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

#24

Post by hyperpallium » Tue, Dec 05, 2017, 2:13 PM UTC

14 lines https://news.ycombinator.com/item?id=3202313

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

#25

Post by microtherion » Tue, Dec 05, 2017, 2:37 PM UTC

A 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

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

#26

Post by yellowflash » Tue, Dec 05, 2017, 3:13 PM UTC

Regular expressions are truly elegant. If the regex engine is built in a functional (compositional style), it is even more elegant. This particular Functional pearl is my favorite, http://sebfisch.github.io/haskell-regexp/regexp-play.pdf

And my implementation of the same in scala (40 lines if you ignore some niceties, and its terribly fast asymptotically) https://gist.github.com/yellowflash/826004277874cadabbc502e6...

For TLDR on the paper, It slowly builds an abstraction and implementation on regex engine which runs on O(mn) where m is length of the regex and n - length of the text. Then they generalize it to do grouping and even extend it to match context free grammar (using lazy evaluation mostly).

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

#27

Post by zoner14 » Tue, Dec 05, 2017, 3:19 PM UTC

Hi, I'm the original author of this article. I just want to say thank you for all the positive and constructive comments. I'm happy to answer questions that anyone has.

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

#28

Post by thesmallestcat » Tue, Dec 05, 2017, 3:25 PM UTC

perlgeek wrote: post #15

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

You can straight away drop any repetition of a zero-width assertion, no?

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

#29

Post by rlonstein » Tue, Dec 05, 2017, 3:35 PM UTC

microtherion wrote: post #25

A 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.

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

#30

Post by mar77i » Tue, Dec 05, 2017, 3:40 PM UTC

majewsky wrote: post #13

mar77i wrote: post #10

I'd almost admire how convenient it was that the language that was used ships regexes already.

To be fair, he doesn't use the builtin regex support in his 40 LOC.

TBH, that's exactly why I can't technically admire it. :)