Skip to content
Back to the catalog
Project regex-engineLanguagesAdvancedBeta

Un motor de expresiones regulares

De la expresión al autómata. Backtracking, grupos y clases de caracteres sin usar la regex de tu lenguaje.

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

Las expresiones regulares parecen un lenguaje esotérico hasta que construyes el motor que las ejecuta. Entonces se convierten en lo que son: un árbol pequeño y una máquina que lo recorre.

Parsearás la expresión, la convertirás en un autómata y la ejecutarás contra un texto. Implementarás grupos, cuantificadores y clases de caracteres, y verás en primera persona por qué ciertas expresiones tardan una eternidad.

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

    Coincidencias básicas

    Literales, el punto, anclas y el primer motor recursivo mínimo.

    1. 01Literales y punto
    2. 02Anclas y búsqueda
  2. Phase 23 stages

    La sintaxis completa

    Parser de cuantificadores, alternancia, clases de caracteres y grupos.

    1. 01Cuantificadores
    2. 02Alternancia
    3. 03Clases y grupos
  3. Phase 32 stages

    Backtracking con capturas

    Grupos capturados, cuantificadores perezosos y sustitución.

    1. 01Capturas
    2. 02Cuantificadores perezosos y reemplazo
  4. Phase 41 stage

    Sin explotar

    Simulación de NFA y comparación de rendimiento con el motor por backtracking.

    1. 01Simulación de NFA

Before you start

Un motor de regex propio: parser de la sintaxis (concatenación, alternancia, cuantificadores, clases, anclas, grupos), construcción del autómata, ejecución por backtracking con captura de grupos, y una segunda implementación basada en simulación de NFA que no explota con entradas patológicas.

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