Hacker News Ressuscitou o Ensaio de Regex de Nikita Popov e Reabriu uma Divisão Crucial

O Hacker News ressuscitou um ensaio de Nikita Popov publicado há 14 anos, reabrindo um conflito que os atalhos da programação frequentemente escondem. O artigo argumenta que mecanismos modernos de regex conseguem reconhecer linguagens muito além das linguagens regulares formais. A reação no Hacker News se concentrou no preço desse alcance adicional.

Popov publicou o ensaio em 15 de junho de 2012, quando respondia com frequência a perguntas sobre PHP no Stack Overflow. Seu alvo era uma proibição conhecida: HTML não pode ser tratado com expressões regulares porque HTML não é regular.

Essa regra continua útil, mas Popov mostrou por que sua explicação teórica pode induzir ao erro. Um padrão PCRE não se limita ao objeto matemático chamado expressão regular. Recursão, retroreferências, asserções, condicionais e chamadas de subrotina dão a alguns mecanismos um alcance muito mais amplo.

O debate renovado, portanto, não é sobre Popov ter encontrado um padrão engenhoso. Ele diz respeito ao que desenvolvedores entendem por regex, quais garantias sobrevivem às escolhas de implementação e quando o reconhecimento se torna um substituto ruim para a análise sintática.

Por Que o Hacker News Ressuscitou um Argumento sobre Regex de 2012

O ensaio voltou porque sua distinção central continua sem solução no vocabulário cotidiano de software.

O ensaio de 2012 de Popov começa separando dois significados que desenvolvedores costumam combinar. Expressões regulares formais descrevem linguagens regulares. Mecanismos de regex de produção frequentemente implementam operadores adicionais que excedem essa classe formal.

Uma linguagem regular pode ser reconhecida com estado finito, o que significa que o reconhecedor não precisa de uma pilha sem limite vinculada à profundidade da entrada. Exemplos comuns incluem identificadores, formatos numéricos simples, padrões fixos de tokens e muitos filtros de busca.

PCRE, abreviação de Perl-Compatible Regular Expressions, adiciona construções que mudam esse cenário. Um subpadrão pode chamar a si mesmo, permitindo que o reconhecedor acompanhe estruturas aninhadas. Uma retroreferência pode exigir que um texto posterior seja igual ao texto capturado anteriormente.

Esses recursos tornam o termo “expressão regular” historicamente familiar, mas matematicamente impreciso. Desenvolvedores geralmente usam regex como um nome abrangente para linguagens de padrões. Especialistas em linguagens formais podem reservar o termo para expressões equivalentes a autômatos finitos.

A distinção conduziu a discussão de agosto. Um lado argumentou que o ensaio corre o risco de confundir expressões regulares verdadeiras com correspondência de padrões específica do PCRE. Outros responderam que Popov anunciou explicitamente essa distinção antes de examinar o sentido mais amplo usado por programadores.

Ambas as leituras identificam algo importante. O ensaio declara cuidadosamente seu escopo, mas seu título provocativo convida leitores a tratar mecanismos diferentes como uma única tecnologia. Um padrão PCRE que usa recursão diz pouco aos desenvolvedores sobre o que JavaScript, RE2, Rust, POSIX ou outra implementação aceita.

A discussão também foi além da teoria. Comentaristas levantaram questões de legibilidade, diferenças entre mecanismos, uso de memória, backtracking, exposição a negação de serviço e expressões geradas por IA. Essas preocupações explicam por que um ensaio de 2012 ainda parece atual.

Assistentes modernos de código podem produzir padrões densos sem garantir que quem dará manutenção entenda sua execução. Eles também podem sugerir sintaxe não suportada pelo mecanismo de destino. Um acesso maior à geração de regex não elimina a necessidade de escolher o reconhecedor certo.

O artigo original continua valioso porque desafia uma limitação excessivamente simplificada. A discussão renovada importa porque fornece a questão operacional que faltava: quanto custa essa expressividade adicional?

O Poder das Regex PCRE Vem de Recursos Fora das Linguagens Regulares

O resultado central do artigo pertence a mecanismos no estilo PCRE, e não a todo sistema que carrega o rótulo de regex.

Popov começa pela hierarquia de Chomsky, que agrupa linguagens formais conforme a gramática necessária para gerá-las. Linguagens regulares ficam dentro das linguagens livres de contexto, que ficam dentro das linguagens sensíveis ao contexto.

Expressões regulares tradicionais ocupam o menor grupo. Concatenação, alternância, classes de caracteres e repetição podem descrever toda linguagem regular. Sozinhas, elas não conseguem lembrar uma profundidade de aninhamento ilimitada nem duplicar uma substring capturada arbitrária.

A recursão do PCRE altera a primeira limitação. Popov usa um grupo recursivo para reconhecer strings que contêm quantidades iguais de caracteres a seguidos por caracteres b. Essa linguagem é livre de contexto, mas não regular.

O mecanismo é compacto. Um padrão consome um a, invoca recursivamente o grupo ao redor e então consome um b. Cada chamada mais profunda adiciona um par correspondente em torno da correspondência aninhada.

A documentação atual do PCRE2 ainda descreve a sintaxe de padrões recursivos. Ela apresenta parênteses balanceados como exemplo direto. Um grupo corresponde a um parêntese de abertura, caracteres internos comuns ou outra invocação de grupo, e um parêntese de fechamento.

Essa é uma capacidade significativa. A correspondência tradicional baseada em estados finitos só pode suportar um limite de aninhamento predefinido. A correspondência recursiva pode acompanhar a profundidade de aninhamento da entrada, sujeita aos limites de recursos e ao comportamento do mecanismo.

Popov então mapeia regras de gramática livre de contexto em subpadrões PCRE nomeados. A construção (?(DEFINE)...) mantém definições sem consumir a entrada. Chamadas de subrotina nomeadas permitem que uma regra invoque outra.

Seu exemplo ampliado traduz partes da gramática de e-mail RFC 5322 para essa notação. O resultado se parece com uma gramática incorporada em um literal de regex, com espaçamento e comentários ativados pelo modo estendido.

Isso sustenta a afirmação marcante do ensaio: a recursão no estilo PCRE pode reconhecer linguagens livres de contexto depois que a recursão à esquerda incompatível é transformada. Isso não significa que toda regex curta possa processar toda linguagem livre de contexto.

Também não transforma o reconhecedor em um parser completo. O reconhecimento responde se uma entrada pertence a uma linguagem. A análise sintática cria uma saída estruturada que registra como a entrada se encaixa na gramática.

Essa diferença se torna decisiva para HTML. Um reconhecedor pode determinar se um fragmento bem-formado está em conformidade com uma gramática. Uma aplicação geralmente precisa de elementos, atributos, nós de texto, recuperação de erros, tratamento de entidades e navegação pelo documento.

HTML real acrescenta outra complicação. Navegadores processam documentos malformados por meio de comportamentos de recuperação especificados. Corresponder a uma linguagem idealizada e bem-formada não reproduz esse comportamento.

Popov reconhece ambas as limitações. Ele recomenda uma biblioteca DOM para processamento genérico de HTML e reserva regex para situações delimitadas. Portanto, a famosa afirmação é mais restrita do que muitas recontagens sugerem.

As retroreferências criam outro passo além das expressões regulares clássicas. Uma retroreferência corresponde exatamente ao texto capturado anteriormente por um grupo. O padrão ^(.+)\1$, por exemplo, reconhece uma string formada por duas metades idênticas.

Em geral, um autômato finito não consegue lembrar uma primeira metade arbitrária e compará-la com a segunda. O mecanismo precisa reter o conteúdo capturado e explorar possíveis pontos de divisão. Esse estado adicional altera tanto o alcance expressivo quanto o comportamento computacional.

Popov também combina recursão e asserções lookaround para reconhecer pelo menos algumas linguagens sensíveis ao contexto. Um lookaround verifica o texto ao redor sem consumi-lo nessa posição.

Ele evita afirmar que PCRE reconhece toda linguagem sensível ao contexto. Essa cautela importa. O ensaio distingue construções demonstradas de questões sem resposta, mesmo usando um título deliberadamente abrangente.

Regex Formal e Mecanismos de Backtracking Otimizam Promessas Diferentes

O conflito principal não é teoria contra prática; é execução previsível contra uma linguagem de padrões maior.

Um mecanismo limitado a construções de linguagens regulares pode executar padrões por meio de autômatos. Ele acompanha o conjunto de estados alcançáveis após cada caractere de entrada, em vez de se comprometer com um caminho e recuar após uma falha.

Um mecanismo de backtracking segue alternativas mais como uma busca em profundidade. Ele seleciona uma ramificação, continua e retorna a uma decisão anterior quando a correspondência posterior falha. Essa abordagem suporta capturas e comportamentos avançados com semântica intuitiva.

Ela também pode repetir trabalho. Quantificadores aninhados ambíguos podem criar muitas formas de dividir a mesma entrada. Um sufixo quase correspondente pode forçar o mecanismo a explorar essas combinações antes de informar a falha.

Esse risco não aparece apenas quando um padrão usa recursão ou retroreferências. Uma implementação com backtracking pode levar tempo excessivo em um padrão formalmente regular. Classe sintática e estratégia de execução estão relacionadas, mas não são idênticas.

Esse ponto corrigiu uma simplificação excessiva no debate online. Remover extensões não regulares não torna automaticamente toda implementação linear. O mecanismo também precisa usar um algoritmo que evite a exploração exponencial de caminhos.

O mecanismo de tempo linear do Google faz uma escolha deliberada. O RE2 garante tempo de correspondência assintoticamente linear no tamanho da entrada e opera dentro de um orçamento de memória configurável.

O RE2 exclui retroreferências e asserções lookaround porque seus projetistas não sabem como suportar essas construções preservando a mesma garantia. Ele também exclui chamadas recursivas de subrotina.

O resultado é menos expressivo que PCRE2, mas mais previsível para serviços que aceitam padrões não confiáveis ou processam texto não confiável. Essa diferença é uma decisão arquitetural, não prova de que um mecanismo substitui universalmente o outro.

O PCRE2 fornece controles que sistemas de produção podem usar, incluindo limites de correspondência, limites de profundidade, caminhos alternativos de execução e construção cuidadosa de padrões. Esses controles reduzem a exposição, mas exigem configuração e testes deliberados.

A escolha prática depende de quem controla o padrão e a entrada. Uma expressão controlada pelo desenvolvedor em registros delimitados cria um risco diferente de uma expressão fornecida pelo usuário que examina grandes cargas úteis em um serviço compartilhado.

A saída necessária também importa. Um comando de busca pode precisar apenas de uma correspondência booleana ou de algumas capturas. Um compilador, processador de documentos ou leitor de configuração precisa de resultados estruturados e locais úteis de falha.

É por isso que “regex consegue corresponder a isso” raramente encerra uma decisão de engenharia. A capacidade estabelece a possibilidade. Ela não estabelece manutenibilidade, limites de recursos, qualidade de diagnóstico ou compatibilidade.

A discordância no Hacker News fica mais clara sob esse enquadramento. Popov descreve o que mecanismos selecionados podem expressar. Críticos perguntam quais garantias as aplicações sacrificam quando dependem desse alcance.

Essas posições não são opostas. Elas tratam de camadas diferentes do mesmo sistema. O erro importante é levar uma afirmação de uma camada para outra sem qualificação.

A Questão do HTML Expõe o Limite Prático do Reconhecimento

Corresponder a uma linguagem não é o mesmo trabalho que construir uma representação confiável de um documento.

O alerta comum contra o processamento de HTML baseado em regex reúne vários argumentos. HTML é aninhado, documentos reais são malformados, linguagens incorporadas complicam os limites entre tokens, e aplicações geralmente precisam de saída estruturada.

Apenas o primeiro argumento diz respeito diretamente à expressividade das linguagens formais. A recursão do PCRE pode lidar com o aninhamento. Esse fato, por si só, não resolve os requisitos restantes.

Considere uma aplicação que extrai links. Uma expressão simples pode funcionar em marcação controlada gerada por um único template. Ela pode falhar quando > aparece dentro de um atributo entre aspas ou quando o texto de um script se parece com uma tag.

Comentários, referências de caracteres, namespaces, tags opcionais e regras de recuperação do navegador adicionam mais casos. Cada nova condição amplia o padrão, enquanto sua saída continua menos estruturada do que um DOM.

Isso não torna todo regex de HTML irresponsável. Uma expressão restrita pode ser apropriada quando o contrato de entrada é rigoroso e as consequências de uma falha são pequenas.

O escopo precisa ser explícito. “Encontrar um marcador conhecido em nosso fragmento gerado” é uma tarefa textual delimitada. “Interpretar páginas web arbitrárias como um navegador” é uma tarefa de processamento de documentos.

Um parser atribui a cada construção uma função nomeada. Ele pode associar localizações de origem, relatar um token inesperado, recuperar-se após um erro e expor uma árvore para transformações posteriores.

Um regex grande frequentemente comprime essas distinções em grupos e fluxo de controle. Subpadrões nomeados e formatação estendida ajudam, mas o mecanismo ainda retorna correspondências, e não uma árvore sintática nativa.

A lacuna de manutenção cresce quando os requisitos mudam. Suportar outra produção gramatical em um parser geralmente significa adicionar ou modificar uma regra. Em um regex fortemente acoplado, isso pode alterar o comportamento de retrocesso e de captura em outros pontos.

Por isso, os testes precisam cobrir mais do que exemplos válidos representativos. As equipes precisam de entradas inválidas, casos quase correspondentes, entradas grandes, entradas aninhadas, casos Unicode e strings adversariais projetadas para acionar caminhos dispendiosos.

É também aqui que a documentação se torna operacional, e não decorativa. Uma expressão complexa deve indicar seu mecanismo, flags, contrato de entrada aceito, capturas esperadas, limites de tamanho e o motivo para não usar um parser.

Equipes que preservam decisões técnicas podem manter essas restrições ao lado de registros de implementação pesquisáveis. Uma base de conhecimento de engenharia compartilhada ajuda futuros mantenedores a recuperar a intenção por trás de código de correspondência conciso.

A decisão central não é regex versus parser como identidades rivais. É se a tarefa exige reconhecimento, extração, transformação, recuperação ou interpretação completa.

Regex continua excelente para tokenização, validação sob regras delimitadas, busca, filtragem de logs e pequenas extrações. Um parser se torna preferível quando a estrutura gramatical é o dado de trabalho da aplicação.

A própria conclusão de Popov segue esse limite. Ele rejeita a proibição teórica absoluta, mantendo a recomendação prática de usar uma biblioteca DOM para o processamento genérico de HTML.

Essa nuance frequentemente desaparece online. “Regex não consegue analisar HTML” persiste porque evita falhas comuns. “Alguns mecanismos de regex conseguem reconhecer estruturas livres de contexto” continua verdadeiro porque essa capacidade subjacente existe.

Uma regra madura de engenharia pode sustentar ambas as afirmações. Não confunda um padrão útil com um teorema, nem uma construção teórica com um design de produção.

O Que o Argumento Sobre Regex Ainda Subestima

Expressividade adicional cria obrigações de segurança e manutenção que uma suíte de testes bem-sucedida pode não revelar.

A negação de serviço por expressões regulares, ou ReDoS, ocorre quando um mecanismo de correspondência passa tempo excessivo explorando alternativas para uma entrada elaborada. Um atacante pode consumir capacidade de processamento sem enviar um grande volume de tráfego.

As orientações sobre ReDoS descrevem mecanismos que atingem tempos de execução extremos quando padrões ambíguos encontram strings adversariais. O perigo frequentemente surge próximo a uma correspondência malsucedida.

Um validador pode processar uma entrada comum rapidamente porque a primeira ramificação tem sucesso. Um atacante pode fornecer um prefixo longo que se encaixa em muitos caminhos, seguido por um caractere que invalida todos eles.

O mecanismo então precisa revisitar escolhas anteriores. Repetições aninhadas, alternativas sobrepostas e componentes opcionais podem multiplicar o espaço de busca. Um padrão conciso pode ocultar esse comportamento durante a revisão de código.

Referências retroativas acrescentam outra dimensão de complexidade. Pesquisas sobre seus limites expressivos as tratam como uma extensão substancial, compatível com muitos mecanismos convencionais. Seu comportamento não pode ser reduzido à correspondência comum de estados finitos.

O ensaio de Popov observa que a correspondência com referências retroativas introduz casos NP-completos. Isso é uma afirmação sobre o problema geral, não uma previsão de que cada padrão será lento.

Muitas expressões com capturas e referências retroativas terminam rapidamente em entradas comuns. Resultados de complexidade alertam que nenhuma solução geral eficiente abrange todos os casos, a menos que premissas importantes da teoria da complexidade mudem.

A recursão introduz preocupações separadas quanto a recursos. Um padrão que acompanha uma entrada profundamente aninhada consome profundidade gerenciada pelo mecanismo ou um estado equivalente. As implementações aplicam limites e diferem na forma como a recursão interage com o retrocesso.

A versão do mecanismo também importa. O PCRE2 mudou a semântica de recursão ao longo do tempo para se alinhar mais de perto ao Perl em determinadas situações. Um padrão testado em uma versão pode se comportar de forma diferente após uma migração.

Portanto, a portabilidade é limitada até mesmo entre mecanismos descritos como compatíveis com Perl. O suporte de sintaxe, as regras Unicode, os valores de captura, a ordem de correspondência e a semântica de recursão podem variar.

Regex gerado por IA aumenta os riscos porque a geração reduz a fricção que antes limitava a complexidade. Um desenvolvedor pode pedir uma única expressão para uma gramática e receber algo sintaticamente convincente em segundos.

O padrão gerado pode visar ao dialeto errado. Ele pode passar nos exemplos do prompt, mas deixar de tratar entradas malformadas, consumir recursos excessivos ou retornar capturas com semântica inesperada.

Revisores devem tratar regex gerado como código gerado. Eles precisam identificar o mecanismo, entender cada construção não trivial, executar testes adversariais e impor limites de entrada e execução.

A legibilidade não é uma preocupação estética neste caso. Um fluxo de controle ilegível impede mantenedores de identificar alternativas sobrepostas ou perceber quando uma pequena alteração cria retrocesso catastrófico.

O modo estendido fornece espaços em branco e comentários nos mecanismos que o suportam. Grupos nomeados reduzem a dependência de índices numéricos que mudam. Padrões menores e compostos podem esclarecer responsabilidades.

Essas práticas ajudam, mas a composição deve respeitar a sintaxe do mecanismo. Algumas linguagens hospedeiras interpolam strings antes que o compilador de regex as processe, produzindo outra camada de escape e possível injeção.

Fragmentos não confiáveis nunca devem ser inseridos em um padrão sem o escape adequado ao mecanismo. Usuários não confiáveis não devem receber acesso irrestrito a um mecanismo com retrocesso dentro de um serviço compartilhado.

A conclusão cética é mais restrita do que “nunca use regex avançado”. Ela afirma que cada construção avançada consome parte do orçamento de previsibilidade de um sistema.

Os desenvolvedores devem conseguir nomear o que recebem em troca. A recursão pode proporcionar reconhecimento conciso para uma estrutura aninhada limitada. Uma referência retroativa pode impor uma restrição de igualdade que, de outro modo, exigiria código procedural.

Se o benefício for apenas evitar um pequeno parser, a escolha se torna mais difícil de justificar. Parsers geralmente oferecem erros melhores, evolução mais clara e uma saída que o código subsequente pode usar diretamente.

Três Sinais Determinarão se a Lição Vai Permanecer

O resultado duradouro depende da seleção de mecanismos, da revisão de código gerado e de as equipes testarem o comportamento em falhas, em vez de apenas exemplos.

O primeiro sinal é uma seleção de mecanismos mais ampla e explícita. Os desenvolvedores devem deixar de tratar regex como uma linguagem portátil única e documentar se um padrão visa PCRE2, RE2, JavaScript, Java, .NET, Rust ou outra implementação.

Se bibliotecas e plataformas tornarem visíveis as garantias de execução, o debate no Hacker News se tornará mais fácil de resolver. Os desenvolvedores poderão discutir um mecanismo definido, em vez de debater um rótulo sobrecarregado.

O segundo sinal é como assistentes de programação lidam com pedidos de regex. Sistemas úteis devem perguntar pelo dialeto de destino, limites de entrada, pressupostos sobre dados confiáveis e capturas necessárias antes de gerar expressões complexas.

Eles também devem explicar construções não suportadas e propor um parser quando a saída solicitada for estruturada. Se os assistentes continuarem produzindo padrões densos sem essas verificações, falhas de manutenção e segurança aumentarão.

O terceiro sinal é a adoção rotineira de testes adversariais. As equipes devem medir correspondências bem-sucedidas, falhas tardias, entradas longas e repetidas, aninhamento profundo, limites Unicode e entradas moldadas para maximizar a ambiguidade.

Um padrão que passa em dez exemplos amigáveis estabeleceu correção apenas para esses exemplos. Ele não estabeleceu comportamento aceitável no pior caso nem compatibilidade com os limites de produção.

Esses sinais reforçam a lição mais ampla de Popov, ao mesmo tempo em que restringem sua aplicação. Mecanismos modernos de padrões podem superar os limites formais sugeridos por seu nome. Esse fato merece ser compreendido, não usado como um endosso universal de design.

O ensaio reavivado também oferece uma correção útil para ambos os lados. A teoria formal importa porque explica quais garantias estão disponíveis. Os detalhes de implementação importam porque os mecanismos implantados não preservam todos essas garantias.

Para desenvolvedores que acompanham o debate no Hacker News, a próxima ação é concreta. Identifique o mecanismo por trás do seu padrão de produção mais complexo, documente seu contrato de entrada e teste seu caso de falha mais lento. Em seguida, pergunte se a aplicação precisa de reconhecimento ou de uma análise estruturada.

Se o padrão continuar claro, delimitado e mensurável, mantenha-o. Se sua correção depender de comportamento de dialeto não documentado ou de retrocesso frágil, substitua a gramática oculta por um parser explícito.