Skip to content
Back to the catalog
Project regex-engineLanguagesAdvancedBeta

A regular expression engine

From the expression to the automaton. Backtracking, groups and character classes without your language's regex.

Start this challengeBrowse other projects

Build it in your language

TypeScriptPythonRust

The tester treats your program as a black box: any language works. These are just the most convenient ones for this project.

Guide language

EnglishEspañol

The stage guides read in this language. Only languages this project is fully translated into show up here; the interface language does not change.

What this project is about

Regular expressions look like an esoteric language until you build the engine that runs them. Then they become what they are: a small tree and a machine that walks it.

You'll parse the expression, turn it into an automaton and run it against text. You'll implement groups, quantifiers and character classes, and see first-hand why certain expressions take forever.

Roadmap

8 stages across 4 phases. Every stage comes with its guide and its tests: you move on when they pass.

  1. Phase 12 stages

    Basic matching

    Literals, the dot, anchors, and a first minimal recursive engine.

    1. 01Literals and dot
    2. 02Anchors and search
  2. Phase 23 stages

    The full syntax

    A parser for quantifiers, alternation, character classes and groups.

    1. 01Quantifiers
    2. 02Alternation
    3. 03Classes and groups
  3. Phase 32 stages

    Backtracking with captures

    Captured groups, lazy quantifiers and substitution.

    1. 01Captures
    2. 02Lazy quantifiers and replacement
  4. Phase 41 stage

    Without blowing up

    NFA simulation and a performance comparison against the backtracking engine.

    1. 01NFA simulation

Before you start

Your own regex engine: a parser for the syntax (concatenation, alternation, quantifiers, classes, anchors, groups), automaton construction, backtracking execution with group capture, and a second NFA-simulation implementation that doesn't blow up on pathological input.

Related challenges

  • json-parser
    Beta

    A JSON parser

    Your first contact with lexers and grammars. Tokenize, build the tree and fail with useful errors.

    Beginner7 stages~6 hLanguages
    tokenizerparsingrecursión

    TypeScript · Python · Go · Java

  • lisp-interpreter
    Beta

    A Lisp interpreter

    Tokenizer, parser, evaluator and closures. Discover how a language runs your code, step by step.

    Advanced11 stages~16 hLanguages
    parsingastclosures+1

    Python · JavaScript · TypeScript

  • mini-compiler
    Beta

    A mini compiler to bytecode

    From source code to runnable bytecode. Lexing, AST, semantic analysis, code generation and a VM that runs it.

    Expert16 stages~30 hLanguages
    lexerastbytecode+1

    Rust · C++ · TypeScript