Motor de Regex Simples em Rust

Expressões regulares são uma das ferramentas mais poderosas da computação. Neste projeto, vamos construir um motor de regex do zero — sem usar a crate regex — para entender como autômatos finitos não determinísticos (NFA) funcionam por trás dos bastidores. Ao final, você terá um motor funcional capaz de processar padrões com caracteres literais, wildcard ., repetições *, + e ?, além de classes de caracteres como [abc].

Construir um motor de regex é um exercício excelente para praticar enumerações, correspondência de padrões, recursão e manipulação de strings em Rust — tudo ao mesmo tempo.

O Que Vamos Construir

Um motor de expressões regulares com as seguintes funcionalidades:

Correspondência de caracteres literais
Wildcard . (corresponde a qualquer caractere)
Repetição * (zero ou mais ocorrências)
Repetição + (uma ou mais ocorrências)
Opcional ? (zero ou uma ocorrência)
Classes de caracteres [abc], [a-z]
Âncoras ^ (início) e $ (fim)
API simples para busca de padrões em texto

Estrutura do Projeto

regex-engine/
├── Cargo.toml
└── src/
    ├── main.rs
    ├── parser.rs
    ├── nfa.rs
    └── matcher.rs

Configurando o Projeto

cargo new regex-engine
cd regex-engine

O Cargo.toml é simples, pois não usaremos dependências externas:

[package]
name = "regex-engine"
version = "0.1.0"
edition = "2021"

Passo 1: O Parser de Padrões

O primeiro componente transforma a string do padrão regex em uma árvore sintática abstrata (AST). Cada nó da árvore representa um elemento do regex.

Crie o arquivo src/parser.rs:

/// Representa um nó da árvore sintática do regex
#[derive(Debug, Clone, PartialEq)]
pub enum RegexNo {
    /// Caractere literal
    Literal(char),
    /// Wildcard '.' - qualquer caractere
    Wildcard,
    /// Classe de caracteres [abc] ou [a-z]
    Classe(Vec<ClasseItem>),
    /// Zero ou mais repetições (*)
    Estrela(Box<RegexNo>),
    /// Uma ou mais repetições (+)
    Mais(Box<RegexNo>),
    /// Zero ou uma ocorrência (?)
    Opcional(Box<RegexNo>),
    /// Sequência de nós
    Sequencia(Vec<RegexNo>),
    /// Âncora de início ^
    Inicio,
    /// Âncora de fim $
    Fim,
}

/// Item dentro de uma classe de caracteres
#[derive(Debug, Clone, PartialEq)]
pub enum ClasseItem {
    /// Caractere único dentro da classe
    Unico(char),
    /// Faixa de caracteres (ex: a-z)
    Faixa(char, char),
}

/// Analisa um padrão regex e retorna a AST
pub fn analisar(padrao: &str) -> Result<RegexNo, String> {
    let mut analisador = Analisador::new(padrao);
    analisador.analisar_sequencia()
}

struct Analisador {
    caracteres: Vec<char>,
    posicao: usize,
}

impl Analisador {
    fn new(padrao: &str) -> Self {
        Self {
            caracteres: padrao.chars().collect(),
            posicao: 0,
        }
    }

    fn atual(&self) -> Option<char> {
        self.caracteres.get(self.posicao).copied()
    }

    fn avancar(&mut self) -> Option<char> {
        let c = self.atual();
        self.posicao += 1;
        c
    }

    fn analisar_sequencia(&mut self) -> Result<RegexNo, String> {
        let mut nos = Vec::new();

        while let Some(c) = self.atual() {
            let no = match c {
                '^' => {
                    self.avancar();
                    RegexNo::Inicio
                }
                '$' => {
                    self.avancar();
                    RegexNo::Fim
                }
                '.' => {
                    self.avancar();
                    self.aplicar_quantificador(RegexNo::Wildcard)
                }
                '[' => {
                    let classe = self.analisar_classe()?;
                    self.aplicar_quantificador(classe)
                }
                '\\' => {
                    self.avancar();
                    let escapado = self.avancar()
                        .ok_or("Escape incompleto no final do padrão")?;
                    self.aplicar_quantificador(RegexNo::Literal(escapado))
                }
                '*' | '+' | '?' => {
                    return Err(format!(
                        "Quantificador '{}' sem expressão precedente", c
                    ));
                }
                _ => {
                    self.avancar();
                    self.aplicar_quantificador(RegexNo::Literal(c))
                }
            };
            nos.push(no);
        }

        if nos.len() == 1 {
            Ok(nos.into_iter().next().unwrap())
        } else {
            Ok(RegexNo::Sequencia(nos))
        }
    }

    fn aplicar_quantificador(&mut self, no: RegexNo) -> RegexNo {
        match self.atual() {
            Some('*') => {
                self.avancar();
                RegexNo::Estrela(Box::new(no))
            }
            Some('+') => {
                self.avancar();
                RegexNo::Mais(Box::new(no))
            }
            Some('?') => {
                self.avancar();
                RegexNo::Opcional(Box::new(no))
            }
            _ => no,
        }
    }

    fn analisar_classe(&mut self) -> Result<RegexNo, String> {
        self.avancar(); // consome '['
        let mut itens = Vec::new();

        while let Some(c) = self.atual() {
            if c == ']' {
                self.avancar();
                return Ok(RegexNo::Classe(itens));
            }

            let caractere = self.avancar().unwrap();

            // Verifica se é uma faixa (ex: a-z)
            if self.atual() == Some('-') {
                self.avancar(); // consome '-'
                if let Some(fim) = self.avancar() {
                    if fim == ']' {
                        // O '-' era literal antes de ']'
                        itens.push(ClasseItem::Unico(caractere));
                        itens.push(ClasseItem::Unico('-'));
                        return Ok(RegexNo::Classe(itens));
                    }
                    itens.push(ClasseItem::Faixa(caractere, fim));
                } else {
                    return Err("Classe de caracteres não fechada".to_string());
                }
            } else {
                itens.push(ClasseItem::Unico(caractere));
            }
        }

        Err("Classe de caracteres não fechada (faltou ']')".to_string())
    }
}

#[cfg(test)]
mod testes {
    use super::*;

    #[test]
    fn testar_literal() {
        let resultado = analisar("abc").unwrap();
        assert_eq!(
            resultado,
            RegexNo::Sequencia(vec![
                RegexNo::Literal('a'),
                RegexNo::Literal('b'),
                RegexNo::Literal('c'),
            ])
        );
    }

    #[test]
    fn testar_wildcard_estrela() {
        let resultado = analisar("a.*b").unwrap();
        assert_eq!(
            resultado,
            RegexNo::Sequencia(vec![
                RegexNo::Literal('a'),
                RegexNo::Estrela(Box::new(RegexNo::Wildcard)),
                RegexNo::Literal('b'),
            ])
        );
    }

    #[test]
    fn testar_classe() {
        let resultado = analisar("[a-z]").unwrap();
        assert_eq!(
            resultado,
            RegexNo::Classe(vec![ClasseItem::Faixa('a', 'z')])
        );
    }
}

O parser usa análise descendente recursiva: ele percorre cada caractere do padrão e constrói os nós apropriados. Quantificadores (*, +, ?) são aplicados ao nó imediatamente anterior.

Passo 2: O Motor NFA

O NFA (Autômato Finito Não Determinístico) é o coração do nosso motor. Cada estado pode ter múltiplas transições, e exploramos todos os caminhos possíveis simultaneamente.

Crie o arquivo src/nfa.rs:

use crate::parser::{ClasseItem, RegexNo};

/// Verifica se um caractere pertence a uma classe
fn pertence_a_classe(c: char, itens: &[ClasseItem]) -> bool {
    itens.iter().any(|item| match item {
        ClasseItem::Unico(esperado) => c == *esperado,
        ClasseItem::Faixa(inicio, fim) => c >= *inicio && c <= *fim,
    })
}

/// Tenta corresponder a AST do regex contra o texto a partir da posição dada.
/// Retorna Some(posição_final) se houver correspondência, None caso contrário.
pub fn corresponder(no: &RegexNo, texto: &[char], pos: usize) -> Option<usize> {
    match no {
        RegexNo::Literal(esperado) => {
            if pos < texto.len() && texto[pos] == *esperado {
                Some(pos + 1)
            } else {
                None
            }
        }

        RegexNo::Wildcard => {
            if pos < texto.len() {
                Some(pos + 1)
            } else {
                None
            }
        }

        RegexNo::Classe(itens) => {
            if pos < texto.len() && pertence_a_classe(texto[pos], itens) {
                Some(pos + 1)
            } else {
                None
            }
        }

        RegexNo::Estrela(interno) => {
            // Tenta corresponder zero ou mais vezes (ganancioso)
            corresponder_estrela(interno, texto, pos)
        }

        RegexNo::Mais(interno) => {
            // Precisa corresponder pelo menos uma vez
            if let Some(proxima_pos) = corresponder(interno, texto, pos) {
                corresponder_estrela_a_partir(interno, texto, proxima_pos, proxima_pos)
            } else {
                None
            }
        }

        RegexNo::Opcional(interno) => {
            // Tenta corresponder uma vez; se falhar, aceita zero
            Some(corresponder(interno, texto, pos).unwrap_or(pos))
        }

        RegexNo::Sequencia(nos) => {
            corresponder_sequencia(nos, texto, pos, 0)
        }

        RegexNo::Inicio => {
            if pos == 0 {
                Some(pos)
            } else {
                None
            }
        }

        RegexNo::Fim => {
            if pos == texto.len() {
                Some(pos)
            } else {
                None
            }
        }
    }
}

/// Corresponde zero ou mais repetições (ganancioso com backtracking)
fn corresponder_estrela(no: &RegexNo, texto: &[char], pos: usize) -> Option<usize> {
    corresponder_estrela_a_partir(no, texto, pos, pos)
}

fn corresponder_estrela_a_partir(
    no: &RegexNo,
    texto: &[char],
    pos: usize,
    melhor: usize,
) -> Option<usize> {
    // Tenta avançar mais uma vez
    if let Some(proxima_pos) = corresponder(no, texto, pos) {
        if proxima_pos > pos {
            // Avançou — tenta corresponder mais
            return corresponder_estrela_a_partir(no, texto, proxima_pos, proxima_pos);
        }
    }
    Some(melhor)
}

/// Corresponde uma sequência de nós em ordem
fn corresponder_sequencia(
    nos: &[RegexNo],
    texto: &[char],
    pos: usize,
    indice: usize,
) -> Option<usize> {
    if indice >= nos.len() {
        return Some(pos);
    }

    let no_atual = &nos[indice];

    // Tratamento especial para Estrela/Mais seguido de mais nós
    // (backtracking necessário)
    match no_atual {
        RegexNo::Estrela(interno) => {
            // Coleta todas as posições possíveis (ganancioso: tenta mais longo primeiro)
            let mut posicoes = vec![pos]; // zero ocorrências
            let mut atual = pos;
            while let Some(prox) = corresponder(interno, texto, atual) {
                if prox == atual {
                    break;
                }
                posicoes.push(prox);
                atual = prox;
            }
            // Tenta do mais longo para o mais curto (ganancioso)
            for &p in posicoes.iter().rev() {
                if let Some(resultado) = corresponder_sequencia(nos, texto, p, indice + 1) {
                    return Some(resultado);
                }
            }
            None
        }
        RegexNo::Mais(interno) => {
            let mut posicoes = Vec::new();
            let mut atual = pos;
            while let Some(prox) = corresponder(interno, texto, atual) {
                if prox == atual {
                    break;
                }
                posicoes.push(prox);
                atual = prox;
            }
            // Precisa de pelo menos uma correspondência
            for &p in posicoes.iter().rev() {
                if let Some(resultado) = corresponder_sequencia(nos, texto, p, indice + 1) {
                    return Some(resultado);
                }
            }
            None
        }
        RegexNo::Opcional(interno) => {
            // Tenta com e sem a correspondência
            if let Some(prox) = corresponder(interno, texto, pos) {
                if let Some(resultado) = corresponder_sequencia(nos, texto, prox, indice + 1) {
                    return Some(resultado);
                }
            }
            corresponder_sequencia(nos, texto, pos, indice + 1)
        }
        _ => {
            if let Some(proxima_pos) = corresponder(no_atual, texto, pos) {
                corresponder_sequencia(nos, texto, proxima_pos, indice + 1)
            } else {
                None
            }
        }
    }
}

A função corresponder_sequencia é onde a mágica do backtracking acontece. Quando encontramos um * ou +, tentamos a correspondência mais longa primeiro (ganancioso) e voltamos atrás se as próximas partes do padrão não corresponderem.

Passo 3: A API de Alto Nível

Agora vamos criar o módulo matcher.rs com uma API amigável para o usuário.

Crie o arquivo src/matcher.rs:

use crate::nfa;
use crate::parser::{self, RegexNo};

/// Resultado de uma busca de regex
#[derive(Debug, Clone)]
pub struct Correspondencia {
    pub inicio: usize,
    pub fim: usize,
    pub texto: String,
}

/// Motor de regex compilado
pub struct Regex {
    ast: RegexNo,
    padrao_original: String,
}

impl Regex {
    /// Compila um padrão regex
    pub fn compilar(padrao: &str) -> Result<Self, String> {
        let ast = parser::analisar(padrao)?;
        Ok(Self {
            ast,
            padrao_original: padrao.to_string(),
        })
    }

    /// Verifica se o padrão corresponde em algum lugar do texto
    pub fn buscar(&self, texto: &str) -> Option<Correspondencia> {
        let caracteres: Vec<char> = texto.chars().collect();

        // Verifica se tem âncora de início
        let ancorado_inicio = tem_ancora_inicio(&self.ast);
        let ancorado_fim = tem_ancora_fim(&self.ast);

        if ancorado_inicio {
            // Só tenta a partir da posição 0
            if let Some(fim) = nfa::corresponder(&self.ast, &caracteres, 0) {
                if !ancorado_fim || fim == caracteres.len() {
                    return Some(Correspondencia {
                        inicio: 0,
                        fim,
                        texto: caracteres[..fim].iter().collect(),
                    });
                }
            }
            return None;
        }

        // Tenta corresponder a partir de cada posição
        for inicio in 0..=caracteres.len() {
            if let Some(fim) = nfa::corresponder(&self.ast, &caracteres, inicio) {
                if !ancorado_fim || fim == caracteres.len() {
                    return Some(Correspondencia {
                        inicio,
                        fim,
                        texto: caracteres[inicio..fim].iter().collect(),
                    });
                }
            }
        }
        None
    }

    /// Encontra todas as correspondências no texto
    pub fn buscar_todas(&self, texto: &str) -> Vec<Correspondencia> {
        let caracteres: Vec<char> = texto.chars().collect();
        let mut resultados = Vec::new();
        let mut pos = 0;

        while pos <= caracteres.len() {
            if let Some(fim) = nfa::corresponder(&self.ast, &caracteres, pos) {
                if fim > pos {
                    resultados.push(Correspondencia {
                        inicio: pos,
                        fim,
                        texto: caracteres[pos..fim].iter().collect(),
                    });
                    pos = fim;
                } else {
                    pos += 1;
                }
            } else {
                pos += 1;
            }
        }
        resultados
    }

    /// Verifica se o padrão corresponde ao texto inteiro
    pub fn corresponde_tudo(&self, texto: &str) -> bool {
        let caracteres: Vec<char> = texto.chars().collect();
        if let Some(fim) = nfa::corresponder(&self.ast, &caracteres, 0) {
            fim == caracteres.len()
        } else {
            false
        }
    }

    /// Retorna o padrão original
    pub fn padrao(&self) -> &str {
        &self.padrao_original
    }
}

fn tem_ancora_inicio(no: &RegexNo) -> bool {
    match no {
        RegexNo::Inicio => true,
        RegexNo::Sequencia(nos) => nos.first().map_or(false, |n| matches!(n, RegexNo::Inicio)),
        _ => false,
    }
}

fn tem_ancora_fim(no: &RegexNo) -> bool {
    match no {
        RegexNo::Fim => true,
        RegexNo::Sequencia(nos) => nos.last().map_or(false, |n| matches!(n, RegexNo::Fim)),
        _ => false,
    }
}

impl std::fmt::Display for Correspondencia {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "'{}' (posição {}..{})",
            self.texto, self.inicio, self.fim
        )
    }
}

Passo 4: Juntando Tudo no main.rs

Agora vamos criar o ponto de entrada que permite ao usuário testar o motor interativamente.

Crie o arquivo src/main.rs:

mod matcher;
mod nfa;
mod parser;

use std::io::{self, BufRead, Write};

fn main() {
    println!("=== Motor de Regex Simples em Rust ===");
    println!("Comandos:");
    println!("  padrao <regex>   - Define o padrão regex");
    println!("  buscar <texto>   - Busca o padrão no texto");
    println!("  todas <texto>    - Encontra todas as correspondências");
    println!("  testar <texto>   - Testa se o texto inteiro corresponde");
    println!("  sair             - Encerra o programa");
    println!();

    let stdin = io::stdin();
    let mut regex_atual: Option<matcher::Regex> = None;

    loop {
        print!("> ");
        io::stdout().flush().unwrap();

        let mut linha = String::new();
        if stdin.lock().read_line(&mut linha).unwrap() == 0 {
            break;
        }
        let linha = linha.trim();

        if linha.is_empty() {
            continue;
        }

        let (comando, argumento) = match linha.split_once(' ') {
            Some((cmd, arg)) => (cmd, arg),
            None => (linha, ""),
        };

        match comando {
            "padrao" => {
                match matcher::Regex::compilar(argumento) {
                    Ok(r) => {
                        println!("Padrão compilado: {}", r.padrao());
                        regex_atual = Some(r);
                    }
                    Err(e) => println!("Erro ao compilar: {}", e),
                }
            }
            "buscar" => {
                if let Some(ref regex) = regex_atual {
                    match regex.buscar(argumento) {
                        Some(m) => println!("Encontrado: {}", m),
                        None => println!("Sem correspondência."),
                    }
                } else {
                    println!("Defina um padrão primeiro com 'padrao <regex>'");
                }
            }
            "todas" => {
                if let Some(ref regex) = regex_atual {
                    let resultados = regex.buscar_todas(argumento);
                    if resultados.is_empty() {
                        println!("Nenhuma correspondência encontrada.");
                    } else {
                        for (i, m) in resultados.iter().enumerate() {
                            println!("  [{}] {}", i + 1, m);
                        }
                    }
                } else {
                    println!("Defina um padrão primeiro com 'padrao <regex>'");
                }
            }
            "testar" => {
                if let Some(ref regex) = regex_atual {
                    let resultado = regex.corresponde_tudo(argumento);
                    println!(
                        "Correspondência total: {}",
                        if resultado { "SIM" } else { "NÃO" }
                    );
                } else {
                    println!("Defina um padrão primeiro com 'padrao <regex>'");
                }
            }
            "sair" => {
                println!("Até logo!");
                break;
            }
            _ => println!("Comando desconhecido: {}", comando),
        }
    }
}

Como Executar

# Compilar e executar
cargo run

# Exemplo de uso interativo:
> padrao [a-z]+@[a-z]+\.[a-z]+
Padrão compilado: [a-z]+@[a-z]+\.[a-z]+

> buscar meu email eh joao@exemplo.com blabla
Encontrado: 'joao@exemplo.com' (posição 16..32)

> padrao a.*b
Padrão compilado: a.*b

> testar aXYZb
Correspondência total: SIM

> todas abcadefb
  [1] 'abcadefb' (posição 0..8)

# Executar os testes
cargo test

Desafios para Expandir

Grupos de captura: Implemente (abc) para capturar sub-expressões e permitir referências retroativas como \1.
Alternação: Adicione suporte ao operador | para permitir expressões como gato|cachorro.
Quantificadores preguiçosos: Implemente *? e +? para correspondência não gananciosa (lazy matching).
Negação em classes: Suporte [^abc] para corresponder qualquer caractere exceto os listados.
Compilação para NFA explícito: Em vez de recursão, construa uma estrutura de dados NFA com estados e transições, permitindo visualização em formato DOT/Graphviz.

Veja Também

Trabalhando com Strings — manipulação de strings em Rust
Vec: Vetores Dinâmicos — a estrutura fundamental usada no motor
Iteradores em Rust — processamento funcional de sequências
Option e Valores Opcionais — tratamento seguro de valores ausentes
Como Usar Regex em Rust — usando a crate regex para produção