---
title: "Motor de Regex em Zig — Tutorial Passo a Passo"
url: "https://ziglang.com.br/projetos/motor-de-regex-em-zig-tutorial-passo-a-passo/"
markdown_url: "https://ziglang.com.br/projetos/motor-de-regex-em-zig-tutorial-passo-a-passo.MD"
description: "Construa um motor de expressões regulares simples em Zig baseado em NFA com suporte a concatenação, alternância, repetição e classes de caracteres."
date: "2026-02-21"
author: "Zig Brasil"
---

# Motor de Regex em Zig — Tutorial Passo a Passo

Construa um motor de expressões regulares simples em Zig baseado em NFA com suporte a concatenação, alternância, repetição e classes de caracteres.


# Motor de Regex em Zig — Tutorial Passo a Passo

Neste tutorial, vamos construir um **motor de expressões regulares** baseado em NFA (Autômato Finito Não-Determinístico) em Zig. Nosso motor vai compilar padrões regex em NFAs e executá-los para encontrar correspondências em texto.

## O Que Vamos Construir

Nosso motor de regex vai:

- Parsear padrões regex: literais, `.`, `*`, `+`, `?`, `|`, `()`, `[]`
- Compilar padrões em NFAs usando a construção de Thompson
- Simular o NFA para encontrar correspondências
- Suportar classes de caracteres (`[a-z]`, `[0-9]`)
- Fornecer API de match e search

## Por Que Este Projeto?

Expressões regulares são uma das ferramentas mais poderosas da computação. Entender como funcionam internamente — da teoria de autômatos à implementação — nos dá uma compreensão profunda de linguagens formais. O NFA é elegante e correto, ao contrário de implementações com backtracking que podem travar.

## Pré-requisitos

- Zig 0.13+ instalado ([guia de instalação](/tutoriais/instalacao/))
- Conhecimento de [estruturas de dados](/estruturas-dados/)
- Familiaridade com [allocators](/receitas/allocators/)

## Passo 1: Estrutura do Projeto

```bash
mkdir regex-engine
cd regex-engine
zig init
```

## Passo 2: Definindo o NFA

```zig
const std = @import("std");
const mem = std.mem;
const io = std.io;
const fmt = std.fmt;

const MAX_ESTADOS = 256;

/// Tipo de transição no NFA.
const Transicao = union(enum) {
    /// Transição ao consumir um caractere específico.
    literal: u8,
    /// Transição por qualquer caractere (.).
    qualquer: void,
    /// Transição epsilon (sem consumir entrada).
    epsilon: void,
    /// Classe de caracteres [a-z] etc.
    classe: struct {
        negada: bool,
        ranges: [16]struct { inicio: u8, fim: u8 },
        num_ranges: u8,
    },

    /// Verifica se o caractere corresponde a esta transição.
    pub fn corresponde(self: Transicao, c: u8) bool {
        switch (self) {
            .literal => |ch| return c == ch,
            .qualquer => return c != '\n',
            .epsilon => return false, // epsilon não consome entrada
            .classe => |cls| {
                var match = false;
                for (cls.ranges[0..cls.num_ranges]) |r| {
                    if (c >= r.inicio and c <= r.fim) {
                        match = true;
                        break;
                    }
                }
                return if (cls.negada) !match else match;
            },
        }
    }
};

/// Aresta do NFA: transição de um estado para outro.
const Aresta = struct {
    transicao: Transicao,
    destino: u16,
};

/// Estado do NFA com lista de transições de saída.
const EstadoNFA = struct {
    arestas: [4]Aresta, // no máximo 4 arestas por estado
    num_arestas: u8,
    aceita: bool,

    pub fn init() EstadoNFA {
        return .{
            .arestas = undefined,
            .num_arestas = 0,
            .aceita = false,
        };
    }

    pub fn adicionarAresta(self: *EstadoNFA, transicao: Transicao, destino: u16) void {
        if (self.num_arestas < 4) {
            self.arestas[self.num_arestas] = .{
                .transicao = transicao,
                .destino = destino,
            };
            self.num_arestas += 1;
        }
    }
};

/// Fragmento de NFA (usado durante construção).
const Fragmento = struct {
    inicio: u16,
    fim: u16,
};

/// NFA compilado a partir de um padrão regex.
const NFA = struct {
    estados: [MAX_ESTADOS]EstadoNFA,
    num_estados: u16,
    inicio: u16,

    const Self = @This();

    pub fn init() Self {
        var nfa = Self{
            .estados = undefined,
            .num_estados = 0,
            .inicio = 0,
        };
        for (&nfa.estados) |*e| {
            e.* = EstadoNFA.init();
        }
        return nfa;
    }

    fn novoEstado(self: *Self) u16 {
        const id = self.num_estados;
        self.num_estados += 1;
        return id;
    }
};
```

## Passo 3: Compilador de Regex para NFA

Usamos a construção de Thompson, que converte cada operação regex em um fragmento de NFA e os combina.

```zig
/// Compila um padrão regex em um NFA.
fn compilarRegex(padrao: []const u8) !NFA {
    var nfa = NFA.init();
    var pilha: [64]Fragmento = undefined;
    var topo: usize = 0;

    var i: usize = 0;
    while (i < padrao.len) {
        const c = padrao[i];

        switch (c) {
            '.' => {
                // Qualquer caractere
                const inicio = nfa.novoEstado();
                const fim = nfa.novoEstado();
                nfa.estados[inicio].adicionarAresta(.qualquer, fim);
                pilha[topo] = .{ .inicio = inicio, .fim = fim };
                topo += 1;
            },
            '*' => {
                // Zero ou mais: pega o fragmento anterior
                if (topo == 0) return error.PadraoInvalido;
                topo -= 1;
                const frag = pilha[topo];

                const inicio = nfa.novoEstado();
                const fim = nfa.novoEstado();

                nfa.estados[inicio].adicionarAresta(.epsilon, frag.inicio);
                nfa.estados[inicio].adicionarAresta(.epsilon, fim);
                nfa.estados[frag.fim].adicionarAresta(.epsilon, frag.inicio);
                nfa.estados[frag.fim].adicionarAresta(.epsilon, fim);

                pilha[topo] = .{ .inicio = inicio, .fim = fim };
                topo += 1;
            },
            '+' => {
                // Um ou mais
                if (topo == 0) return error.PadraoInvalido;
                topo -= 1;
                const frag = pilha[topo];

                const fim = nfa.novoEstado();
                nfa.estados[frag.fim].adicionarAresta(.epsilon, frag.inicio);
                nfa.estados[frag.fim].adicionarAresta(.epsilon, fim);

                pilha[topo] = .{ .inicio = frag.inicio, .fim = fim };
                topo += 1;
            },
            '?' => {
                // Zero ou um
                if (topo == 0) return error.PadraoInvalido;
                topo -= 1;
                const frag = pilha[topo];

                const inicio = nfa.novoEstado();
                const fim = nfa.novoEstado();

                nfa.estados[inicio].adicionarAresta(.epsilon, frag.inicio);
                nfa.estados[inicio].adicionarAresta(.epsilon, fim);
                nfa.estados[frag.fim].adicionarAresta(.epsilon, fim);

                pilha[topo] = .{ .inicio = inicio, .fim = fim };
                topo += 1;
            },
            '|' => {
                // Alternância: combina os dois fragmentos no topo
                if (topo < 1) return error.PadraoInvalido;

                // Compilar o resto até encontrar ) ou fim
                i += 1;
                continue;
            },
            '[' => {
                // Classe de caracteres
                var classe: Transicao = .{ .classe = .{
                    .negada = false,
                    .ranges = undefined,
                    .num_ranges = 0,
                } };

                i += 1;
                if (i < padrao.len and padrao[i] == '^') {
                    classe.classe.negada = true;
                    i += 1;
                }

                while (i < padrao.len and padrao[i] != ']') {
                    const char_inicio = padrao[i];
                    i += 1;
                    if (i + 1 < padrao.len and padrao[i] == '-') {
                        i += 1;
                        const char_fim = padrao[i];
                        i += 1;
                        if (classe.classe.num_ranges < 16) {
                            classe.classe.ranges[classe.classe.num_ranges] = .{
                                .inicio = char_inicio,
                                .fim = char_fim,
                            };
                            classe.classe.num_ranges += 1;
                        }
                    } else {
                        if (classe.classe.num_ranges < 16) {
                            classe.classe.ranges[classe.classe.num_ranges] = .{
                                .inicio = char_inicio,
                                .fim = char_inicio,
                            };
                            classe.classe.num_ranges += 1;
                        }
                    }
                }

                const inicio = nfa.novoEstado();
                const fim = nfa.novoEstado();
                nfa.estados[inicio].adicionarAresta(classe, fim);
                pilha[topo] = .{ .inicio = inicio, .fim = fim };
                topo += 1;
            },
            '\\' => {
                // Escape
                i += 1;
                if (i < padrao.len) {
                    const inicio = nfa.novoEstado();
                    const fim = nfa.novoEstado();
                    nfa.estados[inicio].adicionarAresta(.{ .literal = padrao[i] }, fim);
                    pilha[topo] = .{ .inicio = inicio, .fim = fim };
                    topo += 1;
                }
            },
            else => {
                // Caractere literal
                const inicio = nfa.novoEstado();
                const fim = nfa.novoEstado();
                nfa.estados[inicio].adicionarAresta(.{ .literal = c }, fim);
                pilha[topo] = .{ .inicio = inicio, .fim = fim };
                topo += 1;
            },
        }

        // Auto-concatenação: se há 2+ fragmentos consecutivos, concatenar
        while (topo >= 2) {
            // Verificar se o próximo caractere é um quantificador
            if (i + 1 < padrao.len) {
                const proximo = padrao[i + 1];
                if (proximo == '*' or proximo == '+' or proximo == '?') break;
            }

            topo -= 1;
            const frag2 = pilha[topo];
            topo -= 1;
            const frag1 = pilha[topo];

            nfa.estados[frag1.fim].adicionarAresta(.epsilon, frag2.inicio);

            pilha[topo] = .{ .inicio = frag1.inicio, .fim = frag2.fim };
            topo += 1;
            break;
        }

        i += 1;
    }

    // Concatenar fragmentos restantes
    while (topo >= 2) {
        topo -= 1;
        const frag2 = pilha[topo];
        topo -= 1;
        const frag1 = pilha[topo];
        nfa.estados[frag1.fim].adicionarAresta(.epsilon, frag2.inicio);
        pilha[topo] = .{ .inicio = frag1.inicio, .fim = frag2.fim };
        topo += 1;
    }

    if (topo == 1) {
        nfa.inicio = pilha[0].inicio;
        nfa.estados[pilha[0].fim].aceita = true;
    }

    return nfa;
}
```

## Passo 4: Simulação do NFA

```zig
/// Simula o NFA sobre uma string de entrada.
/// Usa a técnica de "conjunto de estados" (Thompson's algorithm):
/// mantém todos os estados possíveis simultaneamente.
fn simularNFA(nfa: *const NFA, entrada: []const u8) bool {
    var estados_atuais: [MAX_ESTADOS]bool = [_]bool{false} ** MAX_ESTADOS;
    var estados_proximos: [MAX_ESTADOS]bool = [_]bool{false} ** MAX_ESTADOS;

    // Estado inicial + epsilon closure
    estados_atuais[nfa.inicio] = true;
    epsilonClosure(nfa, &estados_atuais);

    // Processar cada caractere da entrada
    for (entrada) |c| {
        @memset(&estados_proximos, false);

        // Para cada estado ativo, seguir transições que correspondem a c
        for (0..nfa.num_estados) |i| {
            if (!estados_atuais[i]) continue;

            const estado = &nfa.estados[i];
            for (estado.arestas[0..estado.num_arestas]) |aresta| {
                if (aresta.transicao.corresponde(c)) {
                    estados_proximos[aresta.destino] = true;
                }
            }
        }

        // Epsilon closure dos novos estados
        epsilonClosure(nfa, &estados_proximos);

        @memcpy(&estados_atuais, &estados_proximos);
    }

    // Verificar se algum estado atual é de aceitação
    for (0..nfa.num_estados) |i| {
        if (estados_atuais[i] and nfa.estados[i].aceita) return true;
    }

    return false;
}

/// Expande um conjunto de estados seguindo todas as transições epsilon.
fn epsilonClosure(nfa: *const NFA, estados: *[MAX_ESTADOS]bool) void {
    var mudou = true;
    while (mudou) {
        mudou = false;
        for (0..nfa.num_estados) |i| {
            if (!estados[i]) continue;

            const estado = &nfa.estados[i];
            for (estado.arestas[0..estado.num_arestas]) |aresta| {
                if (aresta.transicao == .epsilon and !estados[aresta.destino]) {
                    estados[aresta.destino] = true;
                    mudou = true;
                }
            }
        }
    }
}

/// Busca uma correspondência em qualquer posição do texto.
fn search(nfa: *const NFA, texto: []const u8) ?struct { inicio: usize, fim: usize } {
    for (0..texto.len) |inicio| {
        for (inicio + 1..texto.len + 1) |fim| {
            if (simularNFA(nfa, texto[inicio..fim])) {
                return .{ .inicio = inicio, .fim = fim };
            }
        }
    }
    return null;
}
```

## Passo 5: Interface CLI

```zig
pub fn main() !void {
    const stdout = io.getStdOut().writer();
    const stdin = io.getStdIn().reader();

    try stdout.print(
        \\
        \\  ==========================================
        \\     REGEX ENGINE - NFA - Zig
        \\  ==========================================
        \\  Suporte: . * + ? [] [^]  \\ (escape)
        \\  Comandos:
        \\    match <padrao> <texto>  - Match completo
        \\    search <padrao> <texto> - Busca em substring
        \\    sair
        \\  ==========================================
        \\
        \\
    , .{});

    var buf: [1024]u8 = undefined;

    while (true) {
        try stdout.print("regex> ", .{});
        const linha = stdin.readUntilDelimiter(&buf, '\n') catch |err| {
            if (err == error.EndOfStream) break;
            return err;
        };
        const trimmed = mem.trim(u8, linha, " \t\r\n");
        if (trimmed.len == 0) continue;
        if (mem.eql(u8, trimmed, "sair")) break;

        var it = mem.splitScalar(u8, trimmed, ' ');
        const cmd = it.next() orelse continue;
        const padrao = it.next() orelse {
            try stdout.print("  Uso: match|search <padrao> <texto>\n", .{});
            continue;
        };
        const texto = it.rest();

        if (texto.len == 0) {
            try stdout.print("  Texto nao fornecido\n", .{});
            continue;
        }

        const nfa = compilarRegex(padrao) catch {
            try stdout.print("  Erro: padrao invalido\n", .{});
            continue;
        };

        if (mem.eql(u8, cmd, "match")) {
            const resultado = simularNFA(&nfa, texto);
            try stdout.print("  Match: {}\n", .{resultado});
        } else if (mem.eql(u8, cmd, "search")) {
            if (search(&nfa, texto)) |r| {
                try stdout.print("  Encontrado: \"{s}\" (posicao {d}-{d})\n", .{
                    texto[r.inicio..r.fim], r.inicio, r.fim,
                });
            } else {
                try stdout.print("  Nao encontrado\n", .{});
            }
        } else {
            try stdout.print("  Comando desconhecido: {s}\n", .{cmd});
        }
    }
}
```

## Testes

```zig
test "literal match" {
    const nfa = try compilarRegex("abc");
    try std.testing.expect(simularNFA(&nfa, "abc"));
    try std.testing.expect(!simularNFA(&nfa, "ab"));
    try std.testing.expect(!simularNFA(&nfa, "abcd"));
}

test "dot match" {
    const nfa = try compilarRegex("a.c");
    try std.testing.expect(simularNFA(&nfa, "abc"));
    try std.testing.expect(simularNFA(&nfa, "axc"));
    try std.testing.expect(!simularNFA(&nfa, "ac"));
}

test "star match" {
    const nfa = try compilarRegex("ab*c");
    try std.testing.expect(simularNFA(&nfa, "ac"));
    try std.testing.expect(simularNFA(&nfa, "abc"));
    try std.testing.expect(simularNFA(&nfa, "abbc"));
}

test "plus match" {
    const nfa = try compilarRegex("ab+c");
    try std.testing.expect(!simularNFA(&nfa, "ac"));
    try std.testing.expect(simularNFA(&nfa, "abc"));
    try std.testing.expect(simularNFA(&nfa, "abbc"));
}

test "classe de caracteres" {
    const nfa = try compilarRegex("[a-z]");
    try std.testing.expect(simularNFA(&nfa, "a"));
    try std.testing.expect(simularNFA(&nfa, "z"));
    try std.testing.expect(!simularNFA(&nfa, "A"));
}
```

## Compilando e Executando

```bash
zig build run

# regex> match abc abc
#   Match: true
# regex> match a.c axc
#   Match: true
# regex> search [0-9]+ abc123def
#   Encontrado: "123" (posicao 3-6)
```

## Conceitos Aprendidos

- **NFA** (Autômato Finito Não-Determinístico)
- **Construção de Thompson** para compilar regex
- **Epsilon closure** para transições sem consumo
- **Simulação paralela** de múltiplos estados
- **Union types** para representar tipos de transição

## Próximos Passos

- Explore [estruturas de dados](/estruturas-dados/) para grafos
- Veja o [Compilador de Expressões](/projetos/compilador-expressoes/) para parsing
- Construa o [LSP Server](/projetos/lsp-server-basico/) que usa regex
- Consulte [algoritmos](/algoritmos/) para mais teoria