Calculando a diferença e a interseção entre duas expressões regulares

 (phylactery.org)
2 pontos por GN⁺ 2023-09-12 | 1 comentários | Compartilhar no WhatsApp
  • Quando é preciso comparar expressões regulares como conjuntos de strings, o antimirov calcula em uma única tela a relação de inclusão e equivalência entre duas expressões α e β, além de interseção e diferença
  • A área de resultados mostra o complemento e as relações juntos, permitindo verificar operações como ~α, α < β, α = β, α & β, α ^ β, α - β
  • Ao inserir uma string separada s, é possível validar imediatamente se cada expressão regular faz correspondência, com s ∈ α e s ∈ β
  • A sintaxe oferece suporte a ., concatenação, alternativa |, repetição *·+·?·{n}·{m,n}, grupos de caracteres, grupos de caracteres negados, escape e escapes Unicode UTF-16
  • Não oferece suporte a recursos que alteram o comportamento, como âncoras, asserções de comprimento zero, retroreferências, extração de subgrupos, busca/correspondência parcial e ignorar maiúsculas e minúsculas

Comparação de regex e operações de conjunto

  • A área de entrada recebe duas expressões regulares α e β
  • A saída mostra juntos o complemento e as operações de relação/conjunto das duas expressões regulares
    • ~α, ~β: complemento de cada expressão regular
    • α < β, α = β, α > β: relação de inclusão e equivalência entre as duas expressões regulares
    • α & β: interseção
    • α ^ β: diferença simétrica
    • α - β: diferença de conjuntos
  • Ao inserir a string s, é possível verificar no formato s ∈ α, s ∈ β se ela pertence a cada expressão regular
  • Também são exibidos o tamanho de cada expressão regular e o número de estados do DFA
    • Na tela de exemplo, |α| = 1, |β| = 1
    • Na tela de exemplo, dfa(α) e dfa(β) têm 1 estado cada

Sintaxe de expressões regulares suportada

  • Os operadores básicos tratam caractere único, concatenação, alternativa e repetição
    • .: corresponde a qualquer caractere único
    • xy: concatenação que corresponde a x seguido de y
    • x|y: corresponde a x ou y
    • x*: repetição de 0 ou mais vezes
    • (xyz): agrupamento
    • (): regex vazia que corresponde à string vazia
  • Também há suporte a abreviações comuns de repetição
    • x+: repetição de 1 ou mais vezes, equivalente a xx*
    • x?: correspondência opcional, equivalente a (x|)
    • x{n}: concatena x n vezes
    • x{m,n}: concatena x de no mínimo m até no máximo n vezes
  • Conjuntos de caracteres e escapes podem usar as seguintes formas
    • [a-z0-9]: corresponde a um único caractere do grupo
    • [^a-z0-9]: corresponde a um único caractere que não está no grupo
    • \\c: escape do caractere especial c
    • \\u001a: corresponde ao caractere UTF-16 correspondente
    • Além disso, caracteres como a, b, c correspondem a si mesmos

Recursos não suportados

  • O antimirov é focado em tratar expressões regulares como alvo de operações de conjunto, por isso exclui os seguintes recursos
    • Âncoras ^, $
      • Ainda assim, ^ e $ precisam ser escapados
    • Asserções de comprimento zero, por exemplo (?=...), (?<=...)
    • Retrorreferências, por exemplo \\1, \\2
    • Extração de subgrupos
    • Busca ou correspondência parcial
    • Outros flags que alteram o comportamento, como ignorar maiúsculas e minúsculas
  • Mais informações estão em non/antimirov

Leituras relacionadas

1 comentários

 
GN⁺ 2023-09-12
Opiniões no Hacker News

  • Criei uma demonstração web parecida que mostra o processo de uma regex virando parser → NFA → DFA → DFA mínimo, e que também gera saída do DFA mínimo para LLVM IR/Javascript/WebAssembly
    http://compiler.org/reason-re-nfa/src/index.html

    • Dito isso, ir de um NFA para um DFA explícito nem sempre é uma boa escolha
      Como referência, a derivada de Brzozowski, que pode ser usada como uma abordagem alternativa para correspondência de regex, também pode ser interessante: https://en.wikipedia.org/wiki/Brzozowski_derivative

  • Esta biblioteca pode ser usada para criar uma hierarquia de classes de strings e, com isso, aproveitar strings tipadas de forma mais ativa
    Por exemplo, e-mails e URLs têm gramáticas especiais, e o espaço de valores deles é um subconjunto de todas as strings não vazias; strings não vazias são um subconjunto de todas as strings
    Se o sistema de tipos souber que uma string de e-mail é um subtipo de string não vazia, pode considerar válido passar um endereço de e-mail para uma função que exige uma string não vazia
    Esta biblioteca pode ser usada para verificar a definição e a hierarquia desses tipos de string, e a implementação da hierarquia varia conforme a linguagem, com subclassing, limites de traits etc.

    • Em linguagens com tipos de união marcados, essa abordagem é usada com frequência. Em pseudocódigo no estilo Haskell, seria mais ou menos assim
      O construtor Address não é exportado, apenas o tipo; a validação é feita em fromString :: Text -> Maybe Address, retornando Nothing se o endereço for inválido
      Não misture a validade nos dados; sinalize-a por um caminho separado e, quando precisar produzir saída, extraia de volta o valor encapsulado com toText :: Address -> Text
    • É melhor não usar regex para validar endereços de e-mail
      https://news.ycombinator.com/item?id=31092912
    • Há poucas coisas tão peculiares quanto investigar, numa manhã de fim de verão, o que é ou não permitido como endereço de e-mail à esquerda do @
      A heurística simples de considerar errada qualquer regex que tente expressar um “endereço de e-mail válido” é bastante segura, mas acaba com toda a diversão
    • Fiquei curioso sobre o que significa “espaço de valores”

  • Regex é um bom exemplo de uma teoria matemática bem elegante e complexa empacotada em uma interface valiosa
    Sinto algo parecido com álgebra linear

    • Sempre me surpreende como tanta matemática pode se transformar em álgebra linear quando se tem um corpo adequado
      Até transformações de Möbius no plano complexo, w=(az+b)/(cz+d), podem ser convertidas em álgebra linear
    • Normalmente, nesses casos, isso significa que a representação está ficando mais próxima da verdade
      Boas interfaces têm valor intrínseco, mas muita gente focada em resultados não reconhece bem isso
    • Se minha memória não falha, acho que a conexão com álgebra linear aparecia no livro do Conway https://store.doverpublications.com/0486485838.html. Só dei uma olhada por alto

  • Esta página incrível calcula relações binárias entre pares de regex e mostra o DFA como grafo
    É uma demonstração realmente impressionante de operações bem não triviais realizadas sobre regex

    • É muito legal, mas, a rigor, não surpreende que ela não dê suporte a recursos que fazem com que elas deixem de ser regex
      Ainda assim, achei que as âncoras ^ e $ não seriam problema

  • Colei “regex filter numbers divisible by 3” e a página travou completamente: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    Fiquei curioso se existe uma expressão mais curta

    • Esta página web trava em regexes que criam DFAs com muitos estados
      Por exemplo, coisas como (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog
    • De qualquer forma, a descrição da página diz que âncoras não são suportadas

  • Eu queria ver a interseção entre URLs e endereços de e-mail sintaticamente válidos, mas só inserir a regex de URL abaixo já faz a página demorar demais para processar
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Fonte: https://stackoverflow.com/a/3809435/623763

    • Expressões como (...){1,256} são muito pesadas, e o código em Scala JS acaba estourando o tempo ou matando o navegador
      Se trocar isso por (...)+, funciona pelo menos no meu ambiente. Expressões pequenas como (...){1,6} provavelmente não têm problema

  • Fiquei surpreso com o fato de que as regexes geradas por união e interseção não são particularmente concisas, mas logo entendi
    Por exemplo, a interseção de "y.+" e ".+z" pode ser escrita como a expressão muito simples "y.*z", e a página também confirma a equivalência. Mas a ferramenta produz yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz*
    Deve haver uma razão para esse resultado, mas é bem possível que gerar a regex mínima por algum critério como número de caracteres seja muito mais difícil

    • Um dos motivos deve ser que ".+z" fica maior e mais bagunçada depois de ser convertida para um autômato determinístico

  • Já usei esse conceito no passado para escrever a lógica de validação da configuração “IP RegEx filter”
    O objetivo era permitir que o usuário configurasse filtros de IP por meio de expressões regulares. O pessoal de marketing não entendia CIDR e, por causa do Google Analytics, conhecia expressões regulares
    Como definir uma expressão regular válida? A interseção com a expressão regular de “todos os endereços IPv4” não podia ser vazia e, ao mesmo tempo, também não podia ser igual à expressão regular de “todos os endereços IPv4”
    Isso evitou muitas reclamações de que o filtro não fazia nada, mas não impediu a entrada de filtros incorretos em si

    • Será que não havia uma solução mais simples? Em vez de tentar validar a expressão regular do filtro, bastaria mostrar endereços IP de exemplo ou deixar o usuário inserir um conjunto de endereços e então mostrar quais endereços dão match e quais não dão
      Isso também ajuda a lidar com o problema de filtros incorretos

  • Para ficar mais prático no mobile, seria bom desativar a sugestão automática no campo de entrada de expressões regulares
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • Testei a página com 2 expressões regulares para números divisíveis por 3 parecidas, e ela travou mesmo removendo o ^ e o $ das extremidades
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    Tudo era parseado até imediatamente antes do último *, mas, no momento em que eu acrescentava o *, a página inteira travava
    Sem o *, ele gerava um validador válido que parseava trechos numéricos cuja soma dos dígitos é divisível por 3