tre
TRE 0.9.0
Este projeto está procurando mantenedores. Para iniciantes, existem algumas solicitações de tração aguardando a revisão.
Deixe -me saber em [email protected] se você deseja intensificar!
O TRE é uma biblioteca de correspondência REGEXP compatível com Posix leve, robusta e eficiente, com alguns recursos interessantes, como a correspondência aproximada (difusa).
O algoritmo correspondente usado no TRE usa o pior caso linear no comprimento do texto pesquisado e o pior caso quadrático no comprimento da expressão regular usada.
Em outras palavras, a complexidade do tempo do algoritmo é O (m^2n), onde m é o comprimento da expressão regular e n é o comprimento do texto. O espaço usado também é quadrático no comprimento do regex, mas não depende da sequência pesquisada. Esse comportamento quadrático ocorre apenas em casos patológicos que provavelmente são muito raros na prática.
Veja como trabalhar com este código.
Você precisará das seguintes ferramentas instaladas em seu sistema:
Primeiro, prepare a árvore. Mude para a raiz do diretório de origem e execute
./utils/autogen.sh
Isso regenerará várias coisas usando as ferramentas de pré -requisito, para que você acabe com uma árvore construtável.
Depois disso, você pode executar o script de configuração e construir o TRE como de costume:
./configure
make
make check
make install
Em uma árvore preparada, este comando cria um Tarball de código fonte:
./configure && make dist
Como alternativa, você pode correr
./utils/build-sources.sh
que constrói os pacotes de código -fonte e os coloca no subdiretório dist . Este script precisa de um comando zip de trabalho.
Tre não é apenas mais um Matcher Regexp. O TRE possui alguns recursos que não estão lá na maioria das implementações compatíveis com POSIX gratuitas. A maioria desses recursos também não está presente em implementações não livres, nesse caso.
A correspondência aproximada de padrões permite que as correspondências sejam aproximadas, ou seja, permite que as correspondências estejam próximas do padrão pesquisado sob alguma medida de proximidade. O TRE usa a medida de edição de edição (também conhecida como distância de Levenshtein), onde os caracteres podem ser inseridos, excluídos ou substituídos no texto pesquisado para obter uma correspondência exata.
Cada inserção, exclusão ou substituição adiciona a distância ou custo da partida. A TRE pode relatar as correspondências que têm um custo menor que algumas do valor limite. O TRE também pode ser usado para procurar correspondências com o menor custo.
O TRE inclui uma versão da ferramenta de linha de comando acordado (aproximação Grep) para que a correspondência aproximada do regexp no estilo de Grep. Diferentemente de outras implementações da AcordP (como a de Sun Wu e Udi Manber, da Universidade do Arizona), o TRE CONDP permite regexps completos de qualquer comprimento, qualquer número de erros e custos não uniformes de inserção, exclusão e substituição.
O POSIX define o comportamento das funções regexp com precisão. A TRE tenta estar em conformidade com essas especificações o mais estritamente possível. O TRE sempre retorna as correspondências corretas para subpadras, por exemplo. Muito poucas outras implementações fazem isso corretamente. De fato, as únicas outras implementações além da TRE que eu conheço (livre ou não) que acertam são RX de Tom Lord, Regex ++ de John Maddock, e o AT&T AST REGEX, de Glenn Fowler e Doug McIlroy.
O TRE padrão tenta se conformar é o IEEE STD 1003.1-2001, ou as especificações da base de grupo aberto Edição 6, comumente chamado de "Posix". As peças relevantes são as especificações básicas sobre expressões regulares (e a lógica) e a descrição da API regcomp() .
Para uma excelente pesquisa sobre os Matcores Posix Regexp, consulte as páginas do TestRegex de Glenn Fowler, da AT&T Labs Research.
Devido ao algoritmo correspondente usado no TRE, o tempo máximo consumido por qualquer chamada regexec() é sempre diretamente proporcional ao comprimento da sequência pesquisada. Há uma exceção: se as referências de volta forem usadas, a correspondência poderá levar tempo que cresce exponencialmente com o comprimento da string. Isso ocorre porque as referências de retorno correspondentes são um problema completo do NP e quase certamente requer tempo exponencial para corresponder no pior dos casos.
Uma chamada regexec() nunca aloca a memória da pilha. O TRE aloca toda a memória necessária durante uma chamada regcomp() e algum espaço de trabalho temporário do quadro da pilha durante a chamada regexec() . A quantidade de espaço temporário necessária é constante durante a correspondência e não depende da sequência pesquisada. Para regexps de tamanho razoável TRE precisa de menos de 50k de memória alocada dinamicamente durante a chamada regcomp() , menos de 20k para o buffer de padrão compilado e menos de dois quilobytes de espaço de trabalho temporário da estrutura da pilha durante uma chamada regexec() . Não há troca de tempo / memória. O TRE também é pequeno no tamanho do código; A ligação estaticamente com TRE aumenta o tamanho do executável menor que 30k (GCC-3.2, x86, GNU/Linux).
O TRE suporta conjuntos de caracteres multibyte. Isso possibilita o uso de regexps perfeitamente com, por exemplo, locais japoneses. O TRE também fornece uma ampla API de personagem.
O TRE fornece APIs que permitem caracteres zero binários tanto em regexps quanto em strings pesquisados. A API padrão não pode ser facilmente usada para, por exemplo, procurar palavras imprimíveis a partir de dados binários (embora seja possível com alguns hackers). A busca de padrões que contêm zeros binários incorporados não é possível com a API padrão.
Tre é completamente seguro. Todas as funções exportadas são reentrantes e um único objeto REGEXP compilado pode ser usado simultaneamente em vários contextos; por exemplo, em main() e um manipulador de sinal, ou em muitos threads de um aplicativo multithread.
O TRE é portátil em várias plataformas. Abaixo está uma tabela de plataformas e compiladores usados para desenvolver e testar o TRE:
| Plataforma | Compilador |
|---|---|
| FreeBSD 14.1 | Clang 18 |
| Ubuntu 22.04 | GCC 11 |
| MacOS 14.6 | Clang 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
O TRE deve compilar sem alterações nas plataformas mais modernas do tipo POSIX e ser facilmente portátil para qualquer plataforma com uma implementação C hospedada.
Dependendo da plataforma, pode ser necessário instalar o libutf8 para obter um amplo suporte ao conjunto de caracteres de caracteres e multibytes.
A TRE é liberada sob uma licença que é essencialmente a mesma da licença de estilo BSD "2 Cláusula" usada no NetBSD. Consulte a licença do arquivo para obter detalhes.
Atualmente, existem dois recursos, ambos relacionados a elementos de coleta, ausentes da conformidade com 100% do POSIX. Estes são:
Suporte a elementos de coleta (por exemplo [[.<X>.]] , Onde <X> é um elemento de coleta). Não é possível suportar elementos de coleta de vários caracteres, pois o POSIX não define uma maneira de determinar se uma sequência de caracteres é um elemento de coleta de vários caracteres ou não.
Suporte para classes de equivalência, por exemplo [[=<X>=]] , onde <X> é um elemento de coleta. Uma classe de equivalência corresponde a qualquer caractere que tenha o mesmo peso de agrupamento primário que <X> . Novamente, o POSIX não fornece mecanismo portátil para determinar o peso principal de agrupamento de um elemento de coleta.
Observe que outras implementações portáteis do REGEXP também não suportam elementos de coleta. A exceção única é Regex ++, que vem com seu próprio banco de dados para colar elementos para diferentes locais. O suporte a elementos e classes de equivalência não foi amplamente solicitado e não está muito alto na lista de tarefas no momento.
Estes são outros recursos que estou planejando implementar em breve agora:
Todas as extensões GNU ausentes ativadas no GNU regex, como [[:<:]] e [[:>:]] .
Um sinalizador REG_SHORTEST regexec() para retornar a partida mais curta em vez da partida mais longa.
Sintaxe compatível com Perl:
[:^class:] corresponde a qualquer coisa, menos os personagens da aula. Observe que [^[:class:]] já funciona, isso seria apenas uma abreviação de conveniência.
A correspondência apenas no início da string.
Z corresponde apenas ao final da string, ou antes da Newline no final.
z corresponde apenas ao final da string.
l minúsculo próximo char (pense vi).
u Uppercase Next Char (pense VI).
L minúscula até E (pense vi).
U uppercase até E (pense vi).
(?=pattern) A afirmações de aparência positiva de largura zero.
(?!pattern) afirmações negativas de largura zero.
(?<=pattern) ASSERÇÕES POSITIVAS POSITIVAS DE LAÇÃO zero-lar.
(?<!pattern) Afserções de aparência negativa de largura zero.
A documentação especialmente para as características fora do padrão do TRE, como a correspondência aproximada, é um trabalho em andamento (com "progresso" frouxamente definido ...) Se você deseja encontrar uma extensão para usar, lendo o cabeçalho de include/tre/tre.h Pode fornecer algumas dicas adicionais se você se sentir confortável com o código -fonte C.
