Recursive Regexp Raptor (regexp4)

lang: en

regexp3 (C-lang, Go-lang) and regexp4 (C-lang, Go-lang)

raptor-book (borrador) : aqui

benchmarks ==> aqui

Caracteristicas

Manejo sencillo,
Sin verificacion de errores.
Solo expresiones regulares
El codigo mas compacto que alla precenciado nunca antes alguna libreria regexp humana.
Cero dependencias. Ni la libreria estandar de C esta precente C PURO.
Manejo no explicito de memoria dinamica. Ningun malloc, calloc, free, …
Conteo de coincidencias
Capturas
Reemplazo de capturas
Colocacion de capturas especificas dentro de un arreglo
Referencia dentro de la exprecion a capturas previas
Soporte UTF8

Introduccion

Recurseve Regexp Raptor es una libreria de busqueda, captura y reemplazo de expresiones regulares escrita en lenguaje C desce cero, intentando lograr lo siguiente:

Contar con la mayoria de caracteristicas presentes en cualquier otra libreria regexp.
Codigo elegante: sencillo, claro y dotado de gracia.
Evitar la peticion explicita de memoria dinamica.
Evitar el uso de ninguna libreria externa, incluida la libreria estandar.
Ser util como material de aprendizaje.

Existen dos desarrollos paralelos de esta libreria el primero (regexp3) se centra en la simplicidad y el codigo, el segundo aun en fase beta (el presente) intenta alcanzar la maxima velocidad posible implemetando una “tabla de instrucciones”. En ambos casos el algoritmo parte de cero, y solo se hace uso de C tal cual, enjoy!

Motivacion

C no dispone de una libreria estandar de expresiones regulares, si bien existen varias implementaciones, como pcre, la libreria regexp.h del proyecto GNU, regexp del sistema operativo Plan 9, y algunas otras mas, el autor de este trabajo (que igual y es un poco retard) encontro en todas codigo rebuscado y mistico repartido en varios ficheros, llenos de macros, guiones bajos y variables cripticas. Incapas de entender nada y tras un retiro a la isla de la meditacion onanista el autor se propuso hacer su propia libreria con casinos y colegialas japonesas.

Desarrollo y pruebas

Se ha utilizado GNU Emacs (el unico y verdadero sistema operativo), los compiladores gcc (6.3.1) y clang (LLVM) 3.8.1, konsole y fish, corriendo en Freidora 25.

existen dos pruebas para la libreria, la primera es una bateria de pruebas ascii en el fichero ascii_test.c.

para probar la vercion ascii de la libreria

gcc ascii_test.c regexp4_ascii.c

para la vercion UTF8

gcc ascii_test.c regexp4_utf8.c

la segunda bateria de pruebas es exclusiva de regexp4_utf8.c

gcc utf8_test.c regexp4_utf8.c

en cualquiera de los casos ejecute con

./a.out

Uso

Para incluir Recursive Regexp Raptor en su codigo necesita colocar los ficheros regexp4.h, charUtils.h y de pendiendo del caso de uso regexp4_ascii.c o regexp4_utf8.c dentro de la carpeta de su proyecto. Debe incluir el encabezado

#include "regexp4.h"

y por ultimo compilar bien con

gcc miProyecto.c regexp4_ascii.c

o con

gcc miProyecto.c regexp4_utf8.c

obviamente, compilar con optimizacion proporciona una disminucion drastica del tiempo de ejecucion, intente con -O3

funcion `regexp4()`

Esta es la unica funcion de busqueda, aqui su prototipo:

int regexp4( const char *txt, const char *re );

txt: apuntador a cadena sobre la que efectuar la busqueda, debe finalizar con el signo de terminacion ‘\0’.
re: apuntador a cadena que contiene la expresion regular de busqueda, debe finalizar con el signo de terminacion ‘\0’.

La funcion regresa el numero de coincidencias 0 (ninguna) o n coincidencias.

La sintaxis estandar para expresiones regulares utiliza el caracter ’\’, lamentablemente este signo entra en “conflicto” con la sintaxis de C, por esto e intentando mantener el codigo lo mas sencillo, se ha optado por una sintaxis alterna detallada a continuacion

Sintaxis

busqueda de texto en cualquier ubicacion:

regexp4( "Raptor Test", "Raptor" );

multiples opciones de busqueda “exp1|exp2”

regexp4( "Raptor Test", "Dinosaur|T Rex|Raptor|Triceratops" );

coincidencia con cualquier caracter ‘.’

regexp4( "Raptor Test", "R.ptor" );

coincidencia cero o una ves ‘?’

regexp4( "Raptor Test", "Ra?ptor" );

coincidencia una o mas veces ‘+’

regexp4( "Raaaptor Test", "Ra+ptor" );

coincidencia cero o mas veces ‘*’

regexp4( "Raaaptor Test", "Ra*ptor" );

rango de coincidencias “{n1,n2}”

regexp4( "Raaaptor Test", "Ra{0,100}ptor" );

numero de coincidencias especifico ‘{n1}’

regexp4( "Raptor Test", "Ra{1}ptor" );

numero minimo de coincidencias ‘{n1,}’

regexp4( "Raaaptor Test", "Ra{1,}ptor" );

Conjuntos.

Conjunto de caracteres “[abc]”

regexp4( "Raptor Test", "R[uoiea]ptor" );

Rango dentro de un conjunto de caracteres “[a-b]”

regexp4( "Raptor Test", "R[a-z]ptor" );

Metacaracter dentro de un conjunto de caracteres “[:meta]”
```
regexp4( "Raptor Test", "R[:w]ptor" );
        
```

inversion de conjunto de caracteres “[^abc]”

regexp4( "Raptor Test", "R[^uoie]ptor" );

caracteres con codificacion utf8

regexp4( "R△ptor Test", "R△ptor" );

tambien

regexp4( "R△ptor Test", "R[△]ptor" );

coincidencia con un caracter que sea una letra “:a”
```
regexp4( "RAptor Test", "R:aptor" );
    
```
coincidencia con un caracter que no sea una letra “:A”
```
regexp4( "R△ptor Test", "R:Aptor" );
    
```
coincidencia con un caracter que sea una numero “:d”
```
regexp4( "R4ptor Test", "R:dptor" );
    
```
coincidencia con un caracter que no sea un numero “:D”
```
regexp4( "Raptor Test", "R:Dptor" );
    
```
coincidencia con un caracter alfanumerico “:w”
```
regexp4( "Raptor Test", "R:wptor" );
    
```
coincidencia con un caracter no alfanumerico “:W”
```
regexp4( "R△ptor Test", "R:Wptor" );
    
```
coincidencia con un caracter que sea un espacio “:s”
```
regexp4( "R ptor Test", "R:sptor" );
    
```
coincidencia con un caracter que no sea un espacio “:S”
```
regexp4( "Raptor Test", "R:Sptor" );
    
```

coincidencia con un caracter utf8 “:&”

regexp4( "R△ptor Test", "R:&ptor" );

escape de caracteres con significado especial “:caracter”
los caracteres ‘|’, ‘(‘, ‘)’, ‘<’, ‘>’, ‘[‘, ‘]’, ‘?’, ‘+’, ‘*’, ‘{‘, ‘}’, ‘-‘, ‘#’ y ‘@’ indican como debe procesarse la exprecion regular, colocar alguno de estos caracteres tal cual, sin tener en cuenta una correcta sintaxis dentro de la exprecion, puede generar bucles infinitos al igual que errores por violacion de segmento.
```
regexp4( ":#()|<>", ":::#:(:):|:<:>" );
    
```
los caracteres especiales (exepto el metacarater :) pierden su significado detro de un conjunto
```
regexp4( "()<>[]|{}*#@?+", "[()<>:[:]|{}*?+#@]" );
    
```

agrupacion “(exp)”

regexp4( "Raptor Test", "(Raptor)" );

agrupacion con captura “<exp>”

regexp4( "Raptor Test", "<Raptor>" );

backreferences “@id”
las referencias necesitan que previamente se halla capturado una exprecion mediante “<exp>”, luego se coloca el numero de aparicion de la captura precidido por ‘@’
```
regexp4( "ae_ea", "<a><e>_@2@1" )
    
```
modificadores de comportamiento
Existen dos tipos de modificadores. El primero afecta de forma global el comportamiento de la exprecion, el segundo afecta secciones en especifico. En ambos caso los la sintaxis es la misma, el signo ‘#’, seguido por los modificadores,

los modificadores de alcance global se coloca al inicio, de toda la exprecion y son los siguientes
- busqueda solo al inicio ‘#^exp’
```
regexp4( "Raptor Test", "#^Raptor" );
        
```
- busqueda solo al final ‘#$exp’
```
regexp4( "Raptor Test", "#$Test" );
        
```
- busqueda al inicio y final “#^$exp”
```
regexp4( "Raptor Test", "#^$Raptor Test" );
        
```
- detener con la primer coincidencia “#?exp”
```
regexp4( "Raptor Test", "#?Raptor Test" );
        
```
- buscar por la cadena caracter a caracter “#~”
  de forma predeterminada cuando una exprecion coincide con una region del texto de busqueda, la busqueda prosigue a partir del final de dicha coincidencia, para ignorar este comportamiento, haciendo que la busqueda siempre sea caracter a caracter se utiliza este modificador
```
regexp4( "aaaaa", "#~a*" );
        
```
  en este ejemplo, sin el modificador el resultado seria una coincidencia, sin embargo con este modificador la busqueda continua inmediatamente despues del siguente caracter regresando cinco coincidencias.
- ignorar entre minusculas y mayusculas “#*exp”
```
regexp4( "Raptor Test", "#*RaPtOr TeSt" );
        
```

todos los modificadores anteriores son compatibles entre si es decir podria buscar

regexp4( "Raptor Test", "#^$*?~RaPtOr TeSt" );

sin embargo los modificadores ‘~’ y ‘?’ pierden sentido debido a la presencia de ‘^’ y/o ‘$’.

una exprecion del tipo:

regexp4( "Raptor Test", "#$RaPtOr|#$TeSt" );

es erronea, el modificador despues del ‘|’ se aplicaria la seccion entre ‘|’ y ‘#’, es decir cero, con un retorno de erroneo

los modificadores locales se colocan despues del indicador de repeticion (de existir) y afectan la misma region que afectan los indicadores de repeticion, es decir caracteres, conjuntos o agrupaciones.

ignorar entre minusculas y mayusculas “exp#*”

regexp4( "Raptor Test", "(RaPtOr)#* TeS#*t" );

no ignorar entre minusculas y mayusculas “exp#/”

regexp4( "RaPtOr TeSt", "#*(RaPtOr)#/ TES#/T" );

Capturas

Las capturas se indexan segun el orden de aparicion dentro de la expresion por ejemplo:

<   <   >  | <   <   >   >   >
= 1 ==========================
    = 2==    = 2 =========
                 = 3 =

Si la exprecion coincide mas de una ocacion dentro del texto de busqueda el indice, se incrementa segun su aparicion es decir:

<   <   >  | <   >   >   <   <   >  | <   >   >   <   <   >  | <   >   >
= 1 ==================   = 3 ==================   = 5 ==================
    = 2==    = 2==           = 4==    = 4==           = 6==    = 6==
coincidencia uno         coincidencia dos         coincidencia tres

la funcion cpytCatch hace una copia de una la captura dentro de un arreglo de caracteres, aqui su prototipo:

char * cpyCatch( char * str, const int index )

str: puntero lo suficientemete grande para contener la captura.
index: indice de la agrupacion (de 1 a n).

la funcion regeresa un apuntador a la captura terminada en ‘\0’. Un indice incorrecto regresara un apuntador que inicia en ‘\0’.

para optener el numero capturadas dentro de una busqueda, utlice totCatch:

int totCatch();

que regresa un valor de 0 a n.

Podria utilzar esta y la anterior funcion para imprimir las capturadas con una funcion como esta:

void printCatch(){
  char str[128];
  int i = 0, max = totCatch();

  while( ++i <= max )
    printf( "[%d] >%s<\n", i, cpyCatch( str, i ) );
}

`gpsCatch()` y `lenCatch()`

las funciones gpsCatch() y lenCatch() realizan la misma labor que cpyCatch con la variante de no utilizar un arreglo, en su lugar la primera regresa un puntero a la posicion inicial de la captura dentro del texto de busqueda y la segunda regresa la longitud de dicha captura.

int          lenCatch( const int index );
const char * gpsCatch( const int index );

el ejemplo anterior con estas fuciones, seria:

void printCatch(){
  int i = 0, max = totCatch();

  while( ++i <= max )
    printf( "[%d] >%.*s<\n", i, lenCatch( i ), gpsCatch( i ) );
}

Colocar capturas dentro de una cadena

char * putCatch( char * newStr, const char * putStr );

el argumento putStr contiene el texto con el cual formar la nueva cadena asi como indicadores de cuales capturas colocar. Para indicar la insercion de una captura coque el signo ‘#’ seguido del indice de captura. por ejemplo el argumento putStr podria ser

char *putStr = "captura 1 >>#1<< captura 2 >>#2<< captura 747 >>#747<<";

newStr es un arreglo de caracteres lo suficientemente grande como para contener la cadena + las capturas. la funcion regresa un apuntador a la posicion inicial de este arreglo, que finaliza con el signo de terminacion ‘\0’.

para colocar el caracter ‘#’ dentro de la cadena escape ‘#’ con un ‘#’ adicional, es decir:

"## comentario"  -> "# comentario"

Reemplazar una captura

El reemplazo opera sobre un arreglo de caracteres en el cual se coloca el texto de busqueda modificando una captura especifica por una cadena de texto, la funcion encargada de esta labor es rplCatch, su prototipo es:

char * rplCatch( char * newStr, const char * rplStr, const int id );

newStr: arreglo de caracteres de dimension dende se colocara el texto original sobre el que se efectua y el texto de reemplazo de las capturas.
rplStr: texto de reemplazo para captura.
id: identificador de captura segun el orden de aparicion dentro de la exprecion regular. Pasar un indice incorrecto, coloca una copia sin modificacion de la cadena de busqueda sobre el arreglo newStr.

en este caso el uso del argumento id a diferencia de la funcion getCatch no se refiere a una “captura” en especifico, es decir no importa la cantidad de ocaciones que se ha capturado una exprecion, el identificador indica la posicion dentro de la exprecion en si, es decir:

   <   <   >  | <   <   >   >   >
id = 1 ==========================
id     = 2==    = 2 =========
id                  = 3 =
posicion de la captura dentro de la exprecion

la modificacion afecta de este modo

<   <   >  | <   >   >       <   <   >  | <   >   >      <   <   >  | <   >   >
= 1 ==================       = 1 ==================      = 1 ==================
    = 2==    = 2==               = 2==    = 2==              = 2==    = 2==
captura uno                  "..." dos                   "..." tres

Metacaracteres de busqueda

:d: dígito del 0 al 9.
:D: cualquier carácter que no sea un dígito del 0 al 9.
:a: cualquier caracter que sea una letra (a-z,A-Z)
:A: cualquier caracter que no sea una letra
:w: cualquier carácter alfanumérico.
:W: cualquier carácter no alfanumérico.
:s: cualquier caracter de espacio en blanco.
:S: cualquier carácter que no sea un espacio en blanco.
:&: caracter no ascii (solo en version UTF8).
:|: barra vertical
:^: acento circunflejo
:$: signo dolar
:(: parentesis izquierdo
:): parentesis derecho
:<: mayor que
:>: menor que
:[: corchete izquierdo
:]: corchete derecho
:.: punto
:?: interrogacion
:+: mas
:-: menos
:*: asterisco
:{: llave izquierda
:}: llave derecha
:#: modificador
::: dos puntos

adicionalmente utilice la sintaxis propia de c para colocar caracteres como nueva linea, tabulador, campana,…, etc. De igual forma puede utilizar la sintaxis c para “colocar” caracteres en notacion octal, hexadecimal o unicode.

algunos ejemplos de uso

El fichero ascii_test.c contiene una amplia variedad de pruebas que son utiles como ejemplos de uso, entre estos se encuentran los siguentes:

regexp4( "07-07-1777", "<0?[1-9]|[12][0-9]|3[01]><[/:-\\]><0?[1-9]|1[012]>@2<[12][0-9]{3}>" );

captura una cadena con formato de fecha, de forma separada dia, separador, mes y año. El separador tiene que coincider las dos ocaciones que aparece

regexp4( "https://en.wikipedia.org/wiki/Regular_expression", "(https?|ftp):://<[^:s/:<:>]+></[^:s:.:<:>,/]+>*<.>*" );

capturar algo parecido a un enlace web

regexp4( "<mail>nasciiboy@gmail.com</mail>", "<[_A-Za-z0-9:-]+(:.[_A-Za-z0-9:-]+)*>:@<[A-Za-z0-9]+>:.<[A-Za-z0-9]+><:.[A-Za-z0-9]{2}>*" );

capturar por secciones (usuario,sitio,dominio) algo parecido a un correo.

Hacking

algoritmo

Diagrama de flujo

Esta diagrama es una aproximacion del funcionimento del motor, los nombres no se corresponden con los nombres del codigo, para una explicacion completa revisar el libro

    ┌──────┐
    │inicio│
    └──────┘
        │◀───────────────────────────────────┐
        ▼                                    │
┌────────────────┐                           │
│bucle por cadena│                           │
└────────────────┘                           │
        │                                    │
        ▼                                    │
 ┌─────────────┐  no   ┌─────────────┐       │
<│fin de cadena│>────▶<│buscar regexp│>──────┘
 └─────────────┘       └─────────────┘  no coincide
        │ si                  │ coincide
        ▼                     ▼
┌────────────────┐    ┌────────────────┐
│informar: no    │    │informar:       │
│hay coincidencia│    │hay coincidencia│
└────────────────┘    └────────────────┘
        │                     │
        │◀────────────────────┘
        ▼
      ┌───┐
      │fin│
      └───┘

En esta version de @c(buscar regexp) todos los constructores se optienen por una sola funcion:

                                                            ┌───────────────────────────────┐
┏━━━━━━━━━━━━━┓                                             ▼                               │
┃buscar regexp┃                                   ┌───────────────────┐                     │
┗━━━━━━━━━━━━━┛                                   │Optener constructor│                     │
                                                  └───────────────────┘                     │
                                                            │                               │
                                                            ▼                               │
                                                    ┌───────────────┐  no  ┌─────────────┐  │
                                                   <│hay constructor│>────▶│terminar: la │  │
                                                    └───────────────┘      │ruta coincide│  │
                                                            │ si           └─────────────┘  │
                              ┌──────────┬────────┬─────────┼───────────┬──────────┐        │
                              ▼          ▼        ▼         ▼           ▼          ▼        │
                        ┌───────────┐┌────────┐┌─────┐┌────────────┐┌────────┐┌──────────┐  │
                        │alternacion││conjunto││punto││metacaracter││caracter││agrupacion│  │
                        └───────────┘└────────┘└─────┘└────────────┘└────────┘└──────────┘  │
                              │          │        │         │           │          │        │
                              ▼          └────────┴─────────┼───────────┘          └────────┤
                       ┌──────────────────┐                 │                               │
            ┌──────────│ guardar posicion │                 ▼               no              │
            │          └──────────────────┘       ┌──────────────────┐   coincide           │
            │          ┌──────────────────┐      <│buscar constructor│>─────────┐           │
            ▼◀─────────│restaurar posicion│◀──┐   └──────────────────┘          │           │
     ┌───────────────┐ └──────────────────┘   │             │ coincide          │           │
     │recorrer rutas │                        │             ▼                   ▼           │
     └───────────────┘                        │    ┌──────────────────┐ ┌────────────────┐  │
            │                                 │    │avanzar por cadena│ │terminar, ruta  │  │
            ▼                                 │    └──────────────────┘ │sin coincidencia│  │
        ┌────────┐   si     ┌─────────────┐   │             │           └────────────────┘  │
       <│hay ruta│>───────▶<│buscar regexp│>──┘             └───────────────────────────────┘
        └────────┘          └─────────────┘ no coincide
            │ no           coincide │
            ▼                       ▼
┌─────────────────────────┐ ┌─────────────┐
│terminar sin coincidencia│ │terminar, la │
└─────────────────────────┘ │ruta coincide│
                            └─────────────┘

buscar regexp: diseño actual

              ┌──────────────────┐
              │ guardar posicion │                                 ┏━━━━━━━━━━━━━┓
              └──────────────────┘                                 ┃buscar regexp┃
         ┌────────────▶│                                           ┗━━━━━━━━━━━━━┛
         │             ▼
         │      ┌───────────────┐
         │      │recorrer rutas │
         │      └───────────────┘
         │             │                         ┌─────────────────────────────────┐
         │             ▼                         ▼                                 │
         │         ┌────────┐   si     ┌───────────────────┐                       │
         │        <│hay ruta│>────────▶│obtener constructor│                       │
         │         └────────┘          └───────────────────┘                       │
         │             │ no                      │                                 │
         │             ▼                         ▼                                 │
         │ ┌─────────────────────────┐   ┌───────────────┐  no  ┌─────────────┐    │
         │ │terminar sin coincidencia│  <│hay constructor│>────▶│terminar: la │    │
         │ └─────────────────────────┘   └───────────────┘      │ruta coincide│    │
         │                                       │ si           └─────────────┘    │
         │                    ┌────────┬─────────┼───────────┬──────────┐          │
         │                    ▼        ▼         ▼           ▼          ▼          │
┌──────────────────┐      ┌────────┐┌─────┐┌────────────┐┌────────┐┌──────────┐    │
│restaurar posicion│      │conjunto││punto││metacaracter││caracter││agrupacion│    │
└──────────────────┘      └────────┘└─────┘└────────────┘└────────┘└──────────┘    │
         ▲                    │        │         │           │          │          │
         │                    └────────┴─────────┼───────────┘          │          │
         │                                       ▼                      ▼          │
 ┌────────────────┐    no coincide     ┌──────────────────┐      ┌─────────────┐   │
 │terminar: ruta  │◀────────┬─────────<│buscar constructor│>  ┌─<│buscar regexp│>  │
 │sin coincidencia│         │          └──────────────────┘   │  └─────────────┘   │
 └────────────────┘         │                    │ coincide   │         │          │
                            └──────────────────┈┈│┈┈──────────┘         │ coincide │
                                                 ▼                      │          │
                                        ┌──────────────────┐            └──────────┤
                                        │avanzar por cadena│                       │
                                        └──────────────────┘                       │
                                                 │                                 │
                                                 └─────────────────────────────────┘

Licencia

Este proyecto no es de codigo “abierto”, es software libre, y acorde a ello se utiliza la licencia GNU GPL Version 3. Cualquier obra que incluya o derive codigo de esta libreria, debera cumplir con los terminos de esta licencia.

Contacto, contribucion y otras cosas

mailto:nasciiboy@gmail.com

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

readme_es.org

readme_es.org

Recursive Regexp Raptor (regexp4)

Caracteristicas

Introduccion

Motivacion

Desarrollo y pruebas

Uso

funcion `regexp4()`

Sintaxis

Capturas

`gpsCatch()` y `lenCatch()`

Colocar capturas dentro de una cadena

Reemplazar una captura

Metacaracteres de busqueda

algunos ejemplos de uso

Hacking

algoritmo

Diagrama de flujo

Licencia

Contacto, contribucion y otras cosas

Files

readme_es.org

Latest commit

History

readme_es.org

File metadata and controls

Recursive Regexp Raptor (regexp4)

Caracteristicas

Introduccion

Motivacion

Desarrollo y pruebas

Uso

funcion regexp4()

Sintaxis

Capturas

gpsCatch() y lenCatch()

Colocar capturas dentro de una cadena

Reemplazar una captura

Metacaracteres de busqueda

algunos ejemplos de uso

Hacking

algoritmo

Diagrama de flujo

Licencia

Contacto, contribucion y otras cosas

funcion `regexp4()`

`gpsCatch()` y `lenCatch()`