Show HN: Expressões regulares transdutivas para edição de texto

 (github.com/c0stya)
1 pontos por GN⁺ 2025-02-09 | 1 comentários | Compartilhar no WhatsApp
  • TRRE é uma extensão da linguagem de expressões regulares que adiciona o operador : para expressar transformações de texto diretamente, e é oferecida com a ferramenta CLI experimental trre, semelhante ao grep -E
  • A forma básica é um par transdutivo como a:b, que transforma um padrão de entrada em um padrão de saída; exclusão é expressa como transformação com string vazia, como x:, e inserção como :x
  • Assim como nas expressões regulares comuns, é possível usar alternância, repetição e transformações de intervalo de caracteres, com exemplos como cat:dog, [a:A-z:Z] e cifra de César
  • A implementação interna constrói um Finite State Transducer (FST), que lida com pares de entrada-saída em vez do FSA de expressões regulares tradicionais, e também oferece determinização experimental on-the-fly
  • No momento não há binários pré-compilados, então é preciso compilar manualmente; entre os TODOs estão estabilização do DFT, suporte completo a Unicode, conclusão dos recursos de ERE e tratamento eficiente de intervalos

O problema que o TRRE tenta resolver

  • Expressões regulares comuns são úteis para encontrar padrões em texto, mas na edição de texto a lógica de processamento de grupos pode acabar funcionando como pós-processamento e ficar complexa
  • O TRRE expande a linguagem de expressões regulares para colocar correspondência de padrão e modificação de texto dentro da mesma expressão
  • A sintaxe central tem a forma pattern-to-match:pattern-to-generate, e o exemplo mais simples é a:b, que troca a por b
  • A ferramenta de linha de comando trre é uma implementação que demonstra esse conceito e funciona com uma proposta parecida com a do grep -E

Sintaxe básica de transformação

  • Substituição de string é escrita como cat:dog
    • echo 'cat' | ./trre 'cat:dog' imprime dog
    • Também é possível obter o mesmo resultado com transformação caractere por caractere, como (c:d)(a:o)(t:g)
  • Pode ser usado, como no sed, para trocar todas as correspondências dentro de uma string
    • Ao aplicar lamb:cat em Mary had a little lamb., o resultado é Mary had a little cat.
  • Exclusão é expressa deixando o lado direito vazio, na forma string_to_delete:
    • (x:)or remove x de xor e produz or
    • a: substitui todos os a pelo símbolo vazio no modo de varredura padrão, removendo-os
    • Dá para remover vários caracteres com a notação entre colchetes, como [aie]:
  • Inserção é expressa deixando o lado esquerdo vazio, na forma :string_to_insert
    • (:x)or insere x antes de or, formando xor
    • had a (:little )lamb insere little dentro do contexto

Transformação sobre expressões regulares

  • O TRRE suporta alternância com |, como uma expressão regular comum
    • (c:b)at|(d:h)og transforma cat dog em bat hog
  • Operadores de repetição também podem ser aplicados a transformações
    • (cat:dog)* transforma catcatcat em dogdogdog
    • No modo de varredura padrão, apenas cat:dog já é aplicado repetidamente e produz o mesmo resultado
  • Quando a repetição é usada no padrão da esquerda, várias entradas podem ser consumidas e convertidas em uma única saída
    • (cat)*:dog transforma catcatcat em dog
  • Usar * ou + no padrão da direita pode causar loop infinito
    • Expressões como :a* devem ser evitadas
    • Se for necessária repetição finita, é possível especificar a contagem, como em :(repeat-10-times){10}

Transformações por intervalo e geradores

  • Transformação de intervalo de caracteres é escrita como [a:A-z:Z]
    • Isso permite converter regular expressions em REGULAR EXPRESSIONS
  • Há um exemplo de cifra de César
    • [a:b-y:zz:a] transforma caesar cipher em dbftbs djqifs
    • [a:zb:a-z:y] faz o caminho inverso e restaura caesar cipher
  • Também é possível produzir várias saídas a partir de uma única entrada, como um generator
    • Por padrão, é usada a primeira correspondência possível
    • Com a opção -a, todas as saídas possíveis são geradas
  • Por exemplo, ao aplicar :(0|1){3} a uma entrada vazia, é possível gerar sequências binárias de 3 bits de 000 até 111
  • Com :(0|1){,3}? junto com -ma, é possível gerar saídas em forma de subconjuntos com comprimento de até 3

Especificação da linguagem e precedência de operadores

  • De forma informal, o TRRE é definido como pares pattern-to-match:pattern-to-generate
  • O pattern-to-match à esquerda pode ser uma string ou uma expressão regular
  • O pattern-to-generate à direita normalmente é uma string, mas também pode ser uma expressão regular
  • O operador : atualmente é tratado como não associativo, e a forma TRRE:TRRE não é permitida pela gramática
    • Essa forma teria um significado natural como composição das relações definidas pelo TRRE, mas ainda foi deixada de fora porque a complexidade pode crescer bastante
  • A precedência de operadores, da mais alta para a mais baixa, é a seguinte
    • caractere de escape \
    • notação entre colchetes []
    • agrupamento ()
    • repetição * + ? {m,n}
    • concatenação
    • Transdução :
    • alternância |

Modos e ganância

  • O trre oferece dois modos
    • Scan Mode: modo padrão, aplica transformações em sequência
    • Match Mode: usa a flag -m e verifica se a string inteira corresponde à expressão
  • A opção -a gera todas as saídas possíveis
  • O modificador ? torna os operadores *, +, {,} non-greedy
    • <(.:)*> gera <> a partir de <cat><dog>
    • <(.:)*?> gera <><> a partir da mesma entrada
  • Também há exemplos de alteração de conteúdo dentro de tags ou parênteses
    • <(.*?:cat)> transforma <dog> <mouse> em <cat> <cat>

Implementação baseada em FST e determinização

  • O TRRE constrói internamente um Finite State Transducer (FST)
  • Um FST é semelhante ao Finite State Automaton (FSA) usado em expressões regulares comuns, mas lida com pares de entrada-saída em vez de strings simples
  • As diferenças centrais do TRRE são as seguintes
    • define uma relação binária entre duas linguagens regulares
    • usa FST em vez de FSA para inferência
    • oferece determinização experimental on-the-fly por desempenho
  • Em mecanismos de regex tradicionais, a determinização converte um autômato não determinístico em um autômato determinístico para permitir inferência em tempo linear em relação ao tamanho da string de entrada
  • No TRRE, uma abordagem semelhante também é possível, mas nem todo transdutor não determinístico NFT pode ser convertido em um transdutor determinístico DFT
    • Se houver dois ciclos “bad” com o mesmo rótulo de entrada, a geração de estados pode entrar em loop infinito
    • Existem formas de detectar esse tipo de loop, mas elas têm custo alto

Desempenho e estado da instalação

  • A versão não determinística básica apresenta um exemplo em que fica um pouco atrás do sed em substituição simples
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • Em tarefas mais complexas, há um exemplo em que a versão determinística trre_dft supera o sed
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • Ainda não há binários pré-compilados disponíveis
  • A instalação é feita clonando o repositório e depois executando make && sh test.sh para compilar e testar
  • Os TODOs atuais incluem
    • uma versão DFT estável
    • suporte completo a Unicode
    • conclusão dos recursos de ERE
      • negação ^ dentro de []
      • classes de caracteres
      • símbolos âncora $^
    • tratamento eficiente de intervalos

Abordagens usadas como referência

Leituras relacionadas

1 comentários

 
GN⁺ 2025-02-09
Opiniões no Hacker News

  • É interessante ver para onde este projeto vai. Dito isso, a precedência dos operadores parece pouco natural, e outras pessoas nesta thread parecem ter sentido algo parecido
    cat:dog naturalmente leva a esperar algo equivalente a (cat):(dog), não ca(t:d)og

    • É uma ideia interessante em vários aspectos
      Também fiquei confuso com o fato de cat:dog ser interpretado como ca(t:d)og, e não como (cat):(dog), mas isso fez sentido quando lembrei que todo mundo usa regex de um jeito um pouco errado. Regex “originalmente” deve ser vista não como um matcher, mas como um gerador de strings, então cat|dog pode ser entendido formalmente como se expandindo para um conjunto como {catog,cadog}
      Para matching, basta fazer correspondência de substring desse conjunto de strings contra um texto maior. O problema é que a maioria dos motores de regex reais não funciona assim e faz várias coisas estranhas para corresponder às expectativas ou por eficiência
      Se você testar várias ferramentas de regex, aparecem variações como (cat)|(dog) ou (cat)|(dog)|(ca[td]og). Então, de um ponto de vista mais formal, acho correto que cat:dog produza ca(t:d)og, e não (cat):(dog). Mas, por décadas, abusamos de regex como ferramenta de matching ajustada às expectativas do usuário, então agora todo mundo coloca parênteses em volta da expressão que quer substituir
      Esta proposta é interessante e bem projetada, mas dá a impressão de tentar devolver regex ao seu modelo de gerador original. O problema está mais nas ferramentas do que na sintaxe
      Trabalhei com algo próximo a essa área no passado; se você nunca pensou em regex como gerador de conjuntos de strings, pode brincar aqui: https://onlinestringtools.com/generate-string-from-regex
      Dito isso, o comportamento dessas ferramentas de geração também é muito específico. As ferramentas que eu usava tinham várias formas de limitar o gerador especificando restrições para closures etc.
    • Obrigado pelo feedback; a precedência é algo em que também estou pensando, então posso mudar
      Se eu a empurrar para depois da concatenação, isso pode criar outro problema. Por exemplo, com : não associativo, talvez cat:dog:mouse devesse ser ilegal, e não tenho certeza de como lidar com isso
      Na versão atual, insiro epsilon, ou seja, a string vazia. Por exemplo, para remover pulando uma letra de cada vez, tecnicamente dá para executar ..:, que é .(.:eps)
      O resultado de echo 'abcde' | ./trre '..:' é 'ace'
      Na verdade, a associação de : também poderia ter o significado de composição de relações regulares, mas achei complexo demais por enquanto
    • Transformações de intervalo são parecidas. Em vez de [a:A-z:Z], [a-z:A-Z] é melhor, e eu sugeriria algo como [a-y:b-z;z:a] em vez de [a:b-y:zz:a]

  • Se você tem interesse em transdutores de estado finito e ferramentas relacionadas, vale olhar o XFST (Xerox Finite-State Transducer). Ele é usado há mais de 20 anos em aplicações de linguística computacional
    Um pesquisador finlandês da PARC veio a uma aula na UT e mostrou como tratar morfologia do finlandês com FSTs; mesmo olhando de fora, parecia algo bem impressionante

    • Eu também ia mencionar isso. Link do artigo de Kaplan: https://aclanthology.org/J94-3001.pdf
      Ele descreve o trabalho feito na PARC
    • http://hfst.github.io/ é a versão open source moderna do XFST. Abrange foma e OpenFst, e provavelmente consegue fazer quase tudo que o trre faz, e mais
    • Também vale se interessar pelo Pynini. É um wrapper em Python para o OpenFst, com muitos recursos extras de usabilidade
      OpenFst é uma biblioteca realmente excelente para transdutores. Os tutoriais de casos de uso do Pynini feitos em forma de tarefas por Johns Hopkins e outros também são bons
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • Se você está procurando uma alternativa a regex padrão e, em especial, acha difícil a lógica de grupos ou quer expressões mais manuteníveis, a Rosie Pattern Language pode ser adequada
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • Legal. Por volta de 1997 escrevi minha tese de Diplom em ciência da computação sobre transdutores de estado finito, e foi muito menos trivial do que eu esperava
    A tarefa era implementar composição e DFA sempre que possível, inclusive com transdutores compostos. Era uma “álgebra de transdutores de estado finito”, e o caso de uso era morfologia. O tema era muito subestimado, então tive de encerrar mais ou menos no meio. Portanto, meus respeitos
    Sobre a sintaxe, fico me perguntando se você realmente quer que : se ligue com mais força do que a concatenação ab

    • Usei OpenFST em bioinformática no começo dos anos 2000. Era divertido de brincar, mas acabou não sendo útil para o trabalho que eu fazia
      É bom ver que o projeto continua depois de 20 anos: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • É uma escolha muito ousada atrelar, na prática, a graduação a “conseguir lidar com regex com força suficiente”
    • Sim. Transdutores são um tema bem antigo. Por algum motivo, não ficaram tão fortemente ligados a linguagens específicas quanto regex
      Ainda não tenho certeza se : deve se ligar com mais força do que a concatenação. Depois de ver cerca de 100 exemplos, achei mais natural o jeito atual, ou seja, : com precedência menor que ., mas no código isso é literalmente mudar um único número. Por isso postei aqui: preciso de feedback real

  • No momento em que se tenta fazer algum tipo de substituição estrutural, essa abordagem não parece suficiente. Por exemplo, às vezes dá vontade de fazer algo como s/"([^"]*)"/'$1'/
    Além disso, seria ainda mais útil se, dentro de [^"], o que corresponder a ['] pudesse ser trocado por \'
    De forma mais geral, como uma regex efetivamente define uma árvore de análise para o resultado da correspondência, seria útil poder executar transformações mais gerais nessa árvore

    • Se eu entendi corretamente, a seguinte expressão ttre faz o que você quer:
      ":'(':(\\')|[^"'])*":'
    • Se entendi direito, você quer alterar o conteúdo dentro do bloco "..." e trocar as aspas por aspas simples '
      Isso é possível com esta expressão:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      O resultado é '-' '-'
      Ou seja, com a expressão ".+?:-", o texto dentro de "" é substituído pelo símbolo - e, ao mesmo tempo, as aspas ao redor também são trocadas. O ponto de interrogação significa modo não guloso

  • Parece que o projeto inteiro depende da afirmação de que “regex é uma ótima ferramenta para encontrar padrões em texto, mas sempre pareceu pouco natural para edição de texto”, mas não há nenhum exemplo
    Não entendo por que regex seria pouco natural para edição. Também não sei o que “edição” significa aqui, nem por que as pessoas teriam dificuldade com grupos
    Há muitos exemplos da sintaxe deste projeto, mas não vejo por que ela é melhor que regex comum. Acho que eu entenderia o projeto se houvesse alguns exemplos do tipo “a versão com regex básica é esta, a minha versão é esta, e por isso fica mais fácil”

    • Vejo regex como algo que normalmente tem uma natureza de escrever uma vez e não mexer mais. Criar protótipos que tentem ir além disso é uma boa forma de explorar um futuro melhor nessa área
    • É uma observação válida. O exemplo mais claro é quando é preciso substituir apenas dentro de um contexto
      Por exemplo, para trocar por Y apenas o y que está entre x e z, em Python seria mais ou menos assim:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      Eu gostaria de substituir isso pelo padrão xy:Yz:
      result = re.trre('xy:Yz', text)
      Se x e z forem padrões mais complexos, ou regexes por si só, essa abordagem pode ser mais conveniente
    • Acho correto dizer que regex, sozinha, não oferece funcionalidade de edição. Existem grupos, mas, para combiná-los, é preciso usar outra linguagem, como sed
    • A questão é substituição. Com a sintaxe do autor, expressar substituições — literalmente digitá-las — fica mais fácil
      Bom projeto

  • O código em C é realmente agradável de ler. Muito bom, ainda estou lendo
    Só um comentário rápido: o link para theory.pdf no README está quebrado. O PDF está no diretório docs/, então basta incluir docs/ na URL

    • Obrigado pelo feedback e por apontar o erro de digitação. Corrigi. Na verdade, minhas habilidades em C estão bem enferrujadas, então fico um pouco inseguro

  • Diz que é melhor evitar usar * ou + no lado direito porque pode causar loop infinito, mas não daria para simplesmente proibir?
    Entendo que isso tornaria a especificação da sintaxe mais difícil, mas não vejo um bom motivo para manter

    • É uma observação válida e concordo. Por enquanto, acho melhor desativar
      O motivo original era que eu queria implementar uma operação interessante chamada composição de transdutores. Dá para fazer operações simples em strings e compor trre como filtros, mas ainda não terminei isso. Então, sim, é uma observação válida

  • É uma exploração interessante, mas faltam exemplos de por que isso é realmente melhor. Claro, talvez eu esteja acostumado com regex há tempo demais
    Por exemplo, não vejo por que (cat):(dog) em trre é melhor que s/cat/dog, nem o que (x:)or tem de melhor que s/xor/or. Quase todos os exemplos têm, na minha cabeça, uma correspondência relativamente simples em regex
    Se houver uma vantagem central, imagino que esteja na lógica de grupos, então seria bom concentrar os exemplos nisso. Parece melhor explicar por que esta é uma escolha superior antes mesmo de explicar a sintaxe básica
    O exemplo da cifra de César parece pedir muito um recurso de “aplicar isso no sentido inverso”. É uma solicitação comum em muitas substituições de texto e, nesse exemplo, fica especialmente claro. A cabeça de programador imediatamente grita: “por que preciso expressar a mesma lógica duas vezes?”
    Ainda não sei se é útil, mas explorar alternativas ao status quo consolidado é ótimo. Normalmente, tentativas assim têm grande chance de não dar certo, mas a exploração em si é boa de ver

  • A especificação parece bem insuficiente. Já o primeiro exemplo é estranho:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    Não sei o que está acontecendo aqui. A gramática está assim:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    Qual é a árvore de parsing aqui? Por que c não vira da? Ou por que c não é removido e da não vira ot?
    A ideia de ter uma semântica de busca/substituição mais intuitiva do que operadores de agrupamento é boa. Na época do MS-DOS dava para fazer algo como ren .log .txt, e funcionava; pelo modo de pensar moderno do bash isso não faz sentido nenhum, mas, olhando, a intenção era muito clara

    • Isto é uma questão de precedência de operadores e tokenização. Nesta linguagem, os tokens são caracteres únicos, e há um operador invisível entre os caracteres
      Se chamarmos explicitamente esse operador de ~, o exemplo fica assim:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      Com parênteses desnecessários, fica assim:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • A gramática está pouco especificada. A gramática completa é mais complexa. Acho que a versão atual deveria ser removida da documentação; no momento, ela de fato causa confusão
      O motivo de c não virar da é inteiramente a precedência. Olhando esta discussão, acho que escolhi uma precedência ruim, e isso está causando confusão
      A tabela de precedência atual é a seguinte:
      | 1 | caractere de escape | \ |
      | 2 | expressão entre colchetes | [] |
      | 3 | agrupamento | () |
      | 4 | repetição ERE de caractere único | * + ? {m,n} |
      | 5 | transformação | : |
      | 6 | concatenação | . (implícita) |
      | 8 | alternância | | |
      Portanto : se liga com mais força que ., ou seja, que a concatenação implícita
    • Sim, a especificação é insuficiente. O exemplo de exclusão mostra que uma string vazia também pode ser uma REGEX. Então, na prática, dá para considerar que há tantas regexes de string vazia quanto se quiser em qualquer posição, o que torna o parsing infinitamente múltiplo
      Em vez disso, se exigirmos que a regex não possa ser vazia, o exemplo de exclusão quebra, mas a ambiguidade passa para a concatenação. Ou seja, fica ambíguo se é (((c:d)(a:o))(t:g)) ou ((c:d)((a:o)(d:g))). Se assumirmos associatividade, essa diferença provavelmente não importa
    • Pela sensação do comportamento, parece ser c:d, a: ou seja, nada, e ot:g
      Mas, relendo, é definitivamente confuso, e teoricamente a crítica faz sentido. Depois de ler o repositório, eu também passei a acreditar que c deveria virar da, mas não tenho certeza