Expressão regular

Imagem: SIAPL - Sistema de Apoio ao Processo Legislativo da Câmara Municipal de João Pessoa · BY-SA · Openverse

Uma expressão regular (ou, um padrão) descreve um conjunto de cadeias de caracteres, de forma concisa, sem precisar listar todos os elementos do conjunto. Por exemplo, um conjunto contendo as cadeias "Handel", "Händel" e "Haendel" pode ser descrito pelo padrão H(ä|ae?)ndel. A maioria dos formalismos provê pelo menos três operações para construir expressões regulares.

A origem das expressões regulares está na teoria dos autômatos e na teoria das linguagens formais, e ambas fazem parte da teoria da computação. Esses campos estudam modelos de computação (autômatas) e formas de descrição e classificação de linguagens formais. Na década de 1950, o matemático Stephen Cole Kleene descreveu tais modelos usando sua notação matemática chamada de "conjuntos regulares", formando a álgebra de Kleene. A linguagem SNOBOL foi uma implementação pioneira de casamento de padrões, mas não era idêntica às expressões regulares. Ken Thompson construiu a notação de Kleene no editor de texto QED como uma forma de casamento de padrões em arquivos de texto. Posteriormente, ele adicionou essa funcionalidade no editor de texto Unix ed, que resultou no uso de expressões regulares na popular ferramenta de busca grep. Desde então, diversas variações da adaptação original de Thompson foram usadas em Unix e derivados, incluindo expr, AWK, Emacs, vi e lex.

Expressões regulares podem ser expressas através da teoria de linguagens formais. Elas consistem de constantes e operadores que denotam conjuntos de cadeias de caracteres e operações sobre esses conjuntos, respectivamente. Dado um alfabeto finito Σ, as seguintes constantes são definidas: As constantes e os operadores acima formam a álgebra de Kleene. Para evitar parênteses, é assumido que o fecho de Kleene possui a maior prioridade, depois a concatenação e por fim a alternância. Se não houver ambiguidades, os parênteses podem ser omitidos. Por exemplo, (ab)c pode ser escrito como abc, e a|(b(c*)) pode ser escrito como a|bc*. A definição formal de expressões regulares é concisa e evita a utilização dos quantificadores redundantes ? e +, que podem ser expressados respectivamente por (a|ε) e aa*. Por vezes o operador de complemento ~ é adicionado; ~R denota o conjunto das cadeias de caracteres de Σ* que não estão em R. Esse operador é redundante, e pode ser expressado usando outros operadores, apesar da computação para tal representação ser complexa.

Diversas funcionalidades encontradas em bibliotecas atuais de expressões regulares provem um poder de expressão que excede as linguagens regulares. Por exemplo, a habilidade de agrupar subexpressões com parênteses e chamar novamente o valor casado na mesma expressão significa que o padrão pode casar cadeias de palavras repetidas como "papa" ou "WikiWiki", os chamados quadrados na teoria de linguagens formais. O padrão para essas cadeias é (.*)\1. Entretanto, a linguagem de quadrados não é regular, nem livre de contexto. Casamento de padrões com um número indeterminado de referências anteriores, como suportado em ferramentas atuais, é NP-difícil. Entretanto, as ferramentas que fornecem tais construções ainda usam o termo expressões regulares para os padrões, o que leva a uma nomenclatura que difere da teoria das linguagens formais. Por essa razão, algumas pessoas usam o termo regex ou simplesmente padrão para descrever esse conceito mais abrangente.

Existem pelo menos dois algoritmos fundamentalmente diferentes entre si que decidem se e como uma expressão regular casa uma cadeia de caracteres. O mais antigo e mais rápido faz uso dum princípio da teoria de linguagens formais que permite a todas as máquinas de estado finito não determinísticas serem transformadas em máquinas de estado finito determinísticas. Geralmente chamado de DFA, o algoritmo realiza ou simula tal transformação e então executa a máquina determinística resultante na cadeia de caracteres, um símbolo de cada vez. Esse último processo tem complexidade linear relativa ao tamanho da cadeia de caracteres. Mais precisamente, uma cadeia de caracteres de tamanho n pode ser testada numa expressão regular de tamanho m no tempo O( n + 2 m {\displaystyle n+2^{m}} ) ou O( n m {\displaystyle nm} ), dependendo dos detalhes de implementação. Esse algoritmo é rápido, mas pode ser usado somente para casamentos e não para a nova chamada de grupos de captura, quantificação preguiçosa e diversas outras funcionalidades encontradas nas bibliotecas modernas de expressões regulares. Também é possível executar a máquina não determinística diretamente, construindo cada estado da máquina determinística quando necessário e então descartando-o no próximo passo. Isso evita a quantidade exponencial de memória necessária para a construção completa da máquina determinística, ainda que garantindo a busca em tempo linear.

Originalmente, as expressões regulares eram usadas com caracteres ASCII, mas várias implementações atuais suportam Unicode. Na maioria dos casos não há diferença entre conjuntos de caracteres, mas algumas questões são relevantes ao suportar Unicode. Uma delas é a codificação suportada, já que algumas implementações esperam UTF-8, enquanto outras podem esperar UTF-16 ou UTF-32. Outra questão é estender as funcionalidades disponíveis para ASCII no Unicode. Por exemplo, em implementações ASCII, conjuntos de caracteres na forma [x-y] são válidos para quaisquer x e y no intervalo [0x00,0x7F] desde que o código de x seja menor que o código de y. A escolha natural seria permitir o mesmo em Unicode no intervalo de códigos [0,0x10FFFF], o que não é possível pois algumas implementações não permitem que conjuntos de caracteres ultrapassem os blocos de código disponíveis. Do ponto de vista dos detalhes técnicos do Unicode, também surgem questões. Como a normalização, pois, em Unicode, mais de um código pode representar o mesmo caractere. Por exemplo, o caractere "é" pode ser representado por U+0065 (letra latina "e" minúsculo) combinado com U+0301 (diacrítico "acento agudo"), mas também pode ser representado como U+00E9 (letra latina "e" com diacrítico "acento agudo"). Também há os códigos de controle Unicode, as marcas de ordem de byte e as marcas de direção de texto, que devem ser tratados separadamente.

Expressões regulares são usadas por diversos editores de texto, utilitários e linguagens de programação para procurar e manipular texto baseado em padrões. Por exemplo, Perl e Tcl possuem suporte a expressões regulares nativamente. Diversos utilitários de distribuições Unix incluem o editor de texto ed, que popularizou o conceito de expressão regular, e o filtro grep. Outro uso é a validação de formatos de texto (validação de protocolos ou formatos digitais). Por exemplo, ao receber a entrada dum campo de formulário duma aplicação que supõe receber um endereço de email, pode-se usar uma expressão regular para garantir que o que foi recebido de fato é um endereço de email. Mais um uso é a implementação interna dum sistema de realce de sintaxe, como encontrado em ambientes de desenvolvimento integrado. Expressões regulares podem ser usadas para encontrar palavras reservadas, literais e outros tokens específicos, e para alterar a formatação do texto de acordo com o casamento feito.