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

• TRRE: Expressões regulares transdutivas

• Resumo

  • É uma extensão de expressões regulares para edição de texto e ferramentas de linha de comando semelhantes ao grep.
  • Como é um protótipo, não deve ser usado em ambientes reais.

• Introdução

  • Expressões regulares são ferramentas úteis para buscar padrões em texto.
  • Como isso parece pouco natural para edição de texto, esta extensão é proposta.
  • É chamada de expressão regular transdutiva ou trre.
  • Usa o símbolo : para definir transformações.
  • a:b é a forma mais simples, substituindo a por b.
  • Foi criada uma ferramenta de linha de comando chamada trre para demonstrar o conceito.

• Exemplos

  • Básico

    • Alterar cat para dog:

      $ echo 'cat' | trre 'c:da:ot:g'
      dog
      

    • Substitui todas as correspondências de uma string, como no sed:

      $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)'
      Mary had a little cat.
      

    • Remoção:

      $ echo 'xor' | trre '(x:)or'
      or
      

    • Inserção:

      $ echo 'or' | trre '(:x)or'
      xor
      

  • Expressões regulares por meio de transdução

    • Usando alternância:

      $ echo 'cat dog' | trre 'c:bat|d:hog'
      bat hog
      

    • Usando estrela para repetir a transformação:

      $ echo 'catcatcat' | trre '((cat):(dog))*'
      dogdogdog
      

  • Transformação por intervalo

    • Transformação de intervalo de caracteres:

      $ echo "regular expressions" | trre "[a:A-z:Z]"
      REGULAR EXPRESSIONS
      

  • Gerador

    • O trre pode gerar várias strings de saída para uma única entrada.
    • Sequência binária:

      $ echo '' | trre -ma ':(0|1){3}'
      000  001  010  011  100  101  110  111
      

• Especificação da linguagem

  • O trre é definido como um par casamento-de-padrão:geração-de-padrão.
  • casamento-de-padrão pode ser uma string ou uma expressão regular.
  • geração-de-padrão normalmente é uma string, mas também pode ser regex.

• Por que funciona

  • O trre constrói um autômato especial chamado transdutor finito de estados (FST).
  • Um FST processa pares de entrada e saída.

• Escolhas de projeto e questões em aberto

  • São necessárias várias decisões, como associatividade de :, precedência e épsilon implícito.

• Modos e ganância

  • O trre suporta dois modos:
    • Modo de varredura (padrão): aplica transformações em sequência.
    • Modo de correspondência: verifica a string inteira em relação à expressão.

• Determinização

  • O processo de converter um autômato não determinístico em um determinístico é importante.

• Desempenho

  • A versão NFT (não determinística) é um pouco mais lenta que o sed.
  • Em tarefas complexas, o trre_dft (versão determinística) pode ter desempenho melhor que o sed.

• TODO

  • Completar o conjunto de recursos ERE, suporte completo a Unicode, tratamento eficiente de intervalos etc.

• Referências

  • Inspirado em artigos de Russ Cox e em trabalhos de Cyril Allauzen e Mehryar Mohri.

[GN⁺]

Comentários do Hacker News

• Legal, espero ver a evolução deste projeto

  • A precedência dos operadores parece não ser natural
  • É estranho que cat:dog seja interpretado como ca(t:d)og em vez de (cat):(dog)

• Recomenda XFST (Xerox Finite-State Transducer)

  • É uma ferramenta usada em linguística computacional há mais de 20 anos
  • Já ouviu falar de casos de uso de FST em análise morfológica do finlandês

• Recomenda a Rosie Pattern Language como alternativa às expressões regulares padrão

  • Pode ser uma alternativa mais fácil de manter para quem tem dificuldade com a lógica de grupos
  • Links relacionados: GitLab, site oficial do Rosie

• Compartilha a experiência de ter escrito um artigo sobre transdutores de estados finitos em 1997

  • O tema era análise morfológica, e era um assunto subestimado
  • Pergunta se faz sentido definir na sintaxe que : tenha ligação mais forte do que ab

• Acha que isso não é suficiente para fazer substituição estrutural

  • Como a expressão regular define uma árvore sintática para a parte casada do texto, seria útil poder realizar transformações gerais dessa árvore

• Questiona a afirmação de que expressões regulares são pouco naturais para edição de texto

  • O objetivo do projeto depende dessa afirmação, mas não há exemplos
  • Não entende por que as pessoas têm dificuldade ao usar grupos
  • Faltam exemplos que expliquem por que a gramática deste projeto seria melhor que expressões regulares

• Elogia o código C por estar muito limpo

  • O link theory.pdf no README está quebrado e precisa ser corrigido

• Questiona o conselho de não usar * ou +

  • Isso tornaria a gramática mais complexa, mas talvez ainda fosse melhor do que não permitir isso

• Acha estranho o primeiro exemplo

  • O resultado de echo 'cat' | trre 'c:da:ot:g' parece esquisito
  • É difícil entender como a árvore sintática é construída
  • O método de busca/substituição da era MS-DOS parece mais intuitivo

• Questiona se os exemplos são realmente saídas do programa

  • Pode estar entendendo mal a gramática, mas os exemplos parecem incorretos
  • O resultado de echo 'cat dog' | trre 'c:bat|d:hog' parece estranho