Series · October–November 2022

Making Regex From Scratch in Go

Finite state machine diagram

This series is a step-by-step guide to creating an (almost) fully fledged regex engine using Go. It explores the basics of finite state automata, incrementally creates a parser and compiler for turning strings into state machines, and walks through the setup of a visualizer for the FSM node graph. All of the development is structured as a TDD project and uses modern Go features such as fuzzing, generics, and profiling.

  1. 01 Intro
  2. 02 Getting into Some Code
  3. 03 Starting the Compiler
  4. 04 Testing, Fuzzing, and Fixing Things
  5. 05 Wildcards
  6. 06 Pretty Visualizations
  7. 07 Branches
  8. 08 Epsilons
  9. 09 Groups
  10. 10 Modifiers
  11. 11 Reducing an Epsilon-NFA to an NFA