Motor de Regex em Zig — Tutorial Passo a Passo

9 min de leitura
zig regex nfa automato avançado tutorial

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

Passo 1: Estrutura do Projeto

mkdir regex-engine
cd regex-engine
zig init

Passo 2: Definindo o NFA

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.

/// 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

/// 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

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

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

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 Mais

🚀 Primeiros Passos 🔧 Build System 📋 Receitas Prontas 💼 Vagas e Carreira ❓ FAQ (50 Perguntas) 🔄 Migrar de Outra Linguagem

Artigos relacionados

Continue aprendendo Zig

Explore mais tutoriais e artigos em português para dominar a linguagem Zig.

📚 Ver Todos os Tutoriais 💬 Junte-se à Comunidade