How Do Regular Expressions Really Work?

In this video we're going to build a basic regular expression engine from scratch, in order to illustrate the underlying mechanisms that make them tick. First with a naive attempt, and then implementing the nuanced "backtracking" feature.

00:00 - Intro

00:53 - Constraints
02:40 - Parsing
10:45 - Writing the regex engine
17:00 - Testing the engine
18:40 - Fundamental flaw
20:20 - Implementing backtracking

=[ 🔗 Links 🔗 ]=

[wlockuz]

Wow this is mind blowing! I have read a lot of theory about Regex but I have never seen a practical example so well done! You earned a sub!

[fabiodan]

Thanks for spreading the good word on parsers and virtual machines. It's important work, what you're doing here, and more people should do it.

Liked and subscribed!

[huizhang]

Holy shit, I spent 2 weeks learning the principles of compilers. I learned tons of terminology, regular expressions, NFA, DFA, and how to convert one into another. But when it came to writing a regular expression engine, I still didn't know where to start. But this video taught me in just 20 minutes!!! A big thank you to you.👍

[kylefong]

YOU'RE ABSOLUTELY SICK!!! I geek out about stuff like this, this is so cool. Thank you for taking the time to share your knowledge!

[ben.faerber]

Wow, I'm so happy to have found a channel like this about my favorite language! I'm writing an APL clone in Javascript and will have to use your videos for research!

[poof]

Very interesting, even if I don't have seen it at the best moment. End of day on my couch, I was starting to fall asleep at the end of the video 😅

[AmanGupta_Dev]

After watching your videos, I am pretty much confident that all those curious questions / doubts I had, will be solved ! once and for all !

[ShaunakDe]

Thanks for doing this. It was very instructive to watch.

[yapdog]

Wildcard (.) matches everything but newline (\n). At least in most engines. Great video, very timely for me 😁👍

[dentjoener]

For repetition (including all of the variants) I usually use a generic repeat pattern with min and max, and for unbounded versions I set max to some incredibly high value. (MAX_SAFE_INTEGER or something).

This allows me to do the following tranformations: ? -> repeat(0, 1), * -> repeat(0, MAX), + -> repeat(1, MAX), ... etc

[BryanChance]

I learned about regex when I was trying to learn Perl. Oh yes, the syntax is absolutely mind boggling to me at the time. (I'm talking about Perl's syntax) Just kidding but it's close. LOL After about 8 months, it finally clicked; the regex syntax made sense. Anyhow, Perl and regex are perfect together. I think learning Perl and regular expression broke my brain. LOL Then I found out about sed, awk, and all the other text utilities commands like cut, sort, uniq, tr, etc..
I couldn't imagine the complexity of writing a regex engine. But I 'll find out watching video!. Thank you for sharing your work.

[gimmemoreborisbrejcha]

I believe implementing such an engine can be easier with usage of some nfa implementation, and being able to combine them. I actually implemented one that contains very advanced features of modern engines, like captures and such.

[ratchetfreak]

a better way than backtracking is to instead have an array of current states and go character per character. Then when a choice is to be made on a state you duplicate that state and simulate both choices. This lets you avoid the most common pitfall of regex implementations

If a state fails to match the character you drop it from the state array. The regex matches when you get to the end of the string with a state that is at the end of the regex.

[anonymoussloth]

Can u tell me where i can learn to create a more complicated one? I have studied finite automata and compiler design so I am not new to regex and dfa, but I want to learn how to implement onw from scratch

[mluevanos]

Thanks for bringing the advanced JavaScript topics to YT.

[JSRFFD]

This was a very good video, thank you! I wonder if backtracking could be handled more elegantly with recursion. I also wonder if backtracking or recursion would be better suited to handle something like a|b

[MrLiquitorleaveit]

I´m feeling like I´m a bazillion hours away from producing code like this. Watched the whole video though, kind of fascinating how it all adds up in the end.

[eugenegordo]

Thanks for the video! Tell me please which font you using in the editor?

[panjak]

Regex is much easier once you learn DFA and NFA and regular grammars.
Then it's just syntactic sugar, and can be implemented as such.

[calvinlucian]

Nope. Still can't work with regex. 😪 Great tutorial tho ❤