readme.org

October 17, 2017 · View on GitHub

#+TITLE: Recursive Regexp Raptor (regexp4) #+AUTHOR: nasciiboy #+LANGUAGE: en #+STARTUP: showall

lang: [[file:readme_es.org][es]]

regexp3 ([[https://github.com/nasciiboy/RecursiveRegexpRaptor][C-lang]], [[https://github.com/nasciiboy/regexp3][Go-lang]]) and regexp4 ([[https://github.com/nasciiboy/RecursiveRegexpRaptor-4][C-lang]], [[https://github.com/nasciiboy/regexp4][Go-lang]])

raptor-book (draft (spanish)) : [[https://github.com/nasciiboy/raptor-book/][here]]

benchmarks ==> [[https://nasciiboy.github.io/raptorVSworld/index.html][here]]

  • Characteristics

    • Easy to use.

    • No error checking.

    • only regexp

    • The most compact and clear code in a human regexp library.

    • Zero dependencies. Neither the standard C library is present PURE C.

    • No explicit dynamic memory management. No =malloc=, =calloc=, =free=, ...

    • Count matches

    • Catchs

    • Replacement catch

    • Placement of specific catches within an array

    • Backreferences

    • Support UTF8

  • Introduction

    Recurseve Regexp Raptor is a library search, capture and replacement Regular expressions written in C language from zero, trying to achieve what following:

    • Having most of the features present in any other regexp library.

    • Elegant Code: simple, clear and endowed with grace.

    • Avoid explicit request dynamic memory.

    • Avoid using any external libraries, including the standard library.

    • Be a useful learning material.

    There are two parallel developments of this library the first ([[https://github.com/nasciiboy/RecursiveRegexpRaptor][regexp3]]) focuses on simplicity and code, the second (this) still in beta seeks achieve the maximum speed possible implementing a "table of instructions." In both cases the algorithm is from scratch, and only use C, enjoy!

** Motivation

C does not have a standard library of regular expressions, although there are several implementations, such as pcre, the regexp.h library of the GNU project, regexp of the Plan 9 operating system, and some other more, the author of this work (which is a little bit retard) found in all code farfetched and mystical divided into several files full of macros, scripts low and cryptic variables. Unable to understand anything and after a retreat to the island of onanista meditacion the author intended to make your own library with casinos and Japanese schoolgirls.

** Development and Testing

Has been used GNU Emacs (the only true operating system), gcc (6.3.1) & clang compiler (LLVM) 3.8.1, konsole and fish, running in Freidora 25.

There are two tests for the library, the first ascii test battery is used in the file =ascii_test.c=.

to test the ascii library

#+BEGIN_SRC sh gcc ascii_test.c regexp4_ascii.c #+END_SRC

to the ut8 vercion

#+BEGIN_SRC sh gcc ascii_test.c regexp4_utf8.c #+END_SRC

the second battery of tests is exclusive of =regexp4_utf8.c=

#+BEGIN_SRC sh gcc utf8_test.c regexp4_utf8.c #+END_SRC

in either case run with

#+BEGIN_SRC sh ./a.out #+END_SRC

  • Use

    To include Recursive Regexp Raptor in their code, place the files =regexp4.h=, =charUtils.h= and =regexp4_ascii.c= or =regexp4_utf8.c= inside the folder of your draft. You must include the header

    #+BEGIN_SRC c #include "regexp4.h" #+END_SRC

    and finally compile well with

    #+BEGIN_SRC sh gcc myProyect.c regexp4_ascii.c #+END_SRC

    or

    #+BEGIN_SRC sh gcc myProyect.c regexp4_utf8.c #+END_SRC

    obviously compile with optimization provides a significant decline, runtime, try =-O3=

** The =regexp4()= function

This the only search function, its prototype is:

#+BEGIN_SRC c int regexp4( const char *txt, const char *re ); #+END_SRC

  • txt :: pointer to string on which to perform the search, must end with the sign of termination '\0'.

  • re :: pointer to string containing the regular expression search, You must end with the sign of termination '\0'.

The function returns the number of matches =0= (none) o =n= matches.

The standard syntax for regular expressions using the character '==', unfortunately this sign goes into "conflict" with the syntax of C, by this and trying to keep simple the code, has opted for a alternate syntax detailed below

** Syntax

** Captures

Catches are indexed according to the order of appearance in the expression for example:

#+BEGIN_EXAMPLE < < > | < < > > > = 1 ========================== = 2== = 2 ========= = 3 = #+END_EXAMPLE

If the exprecion matches more than one occasion in the search text index is increased according to their appearance that is:

#+BEGIN_EXAMPLE < < > | < > > < < > | < > > < < > | < > > = 1 ================== = 3 ================== = 5 ================== = 2== = 2== = 4== = 4== = 6== = 6== coincidencia uno coincidencia dos coincidencia tres #+END_EXAMPLE

=cpytCatch= function makes a copy of a catch into an array character, here its prototype:

#+BEGIN_SRC c char * cpyCatch( char * str, const int index ) #+END_SRC

  • str :: pointer capable of holding the largest capture.

  • index :: index of the grouping (=1= to =n=).

function returns a pointer to the capture terminated '\0'. an index incorrect return a pointer that begins in '\0'.

to get the number of catches in a search, using =totCatch=:

#+BEGIN_SRC c int totCatch(); #+END_SRC

returning a value of =0= a =n=.

Could use this and the previous function to print all catches with a function like this:

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

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

#+END_SRC

*** =gpsCatch()= y =lenCatch()=

functions =gpsCatch()= and =lenCatch()= perform the same work =cpyCatch=
with the variant not use an array, instead the first returns a pointer to
the initial position of capture within the text of search and the second
returns the length of the capture.

#+BEGIN_SRC c
  int          lenCatch( const int index );
  const char * gpsCatch( const int index );
#+END_SRC

the above example with these fuciones, would:

#+BEGIN_SRC c
  void printCatch(){
    int i = 0, max = totCatch();

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

*** Place catches in a string

#+BEGIN_SRC c
  char * putCatch( char * newStr, const char * putStr );
#+END_SRC

=putStr= argument contains the text with which to form the new chain as well
as indicators which you catch place. To indicate the insertion a coke
capture the '#' sign followed the capture index. for example =putStr=
argument could be

#+BEGIN_SRC c
  char *putStr = "catch 1 >>#1<< catch 2 >>#2<< catch 747 >>#747<<";
#+END_SRC

=newStr= is an character array large enough to contain the string +
catches. the function returns a pointer to the starting position of this
arrangement, which ends with the sign of completion '\0'.

to place the character '#' within the escape string '#' with '#'
further, ie:

#+BEGIN_EXAMPLE
  "## Comment" -> "# comment"
#+END_EXAMPLE

*** Replace a catch

Replacement operates on an array of characters in which is placed the text
search modifying a specified catch by a string text, the function in
charge of this work is =rplCatch=, its prototype is:

#+BEGIN_SRC c
  char * rplCatch( char * newStr, const char * rplStr, const int id );
#+END_SRC

- newStr :: character array dimension text is placed dende original on which
            is carried out and the replacement text of catches.

- rplStr :: replacement text capture.

- id     :: *Capture identifier* after the order of appearance within
            regular exprecion. Spend a wrong index, place a unaltered copy
            of the search string on the settlement = Newstr =.


in this case the use of the argument =id= unlike function =getCatch= does
not refer to a "catch" in specific, that is no matter how much of occasions
that has captured a exprecion, the identifier indicates the *position*
within the exprecion itself, ie:

#+BEGIN_EXAMPLE
     <   <   >  | <   <   >   >   >
  id = 1 ==========================
  id     = 2==    = 2 =========
  id                  = 3 =
  capturing position within the exprecion
#+END_EXAMPLE

The amendment affects so

#+BEGIN_EXAMPLE
  <   <   >  | <   >   >       <   <   >  | <   >   >      <   <   >  | <   >   >
  = 1 ==================       = 1 ==================      = 1 ==================
      = 2==    = 2==               = 2==    = 2==              = 2==    = 2==
  capture one                  "..." two                   "..." Three
#+END_EXAMPLE

** Metacharacters search

  • =:d= :: digit from 0 to 9.

  • =:D= :: any character other than a digit from 0 to 9.

  • =:a= :: any character is a letter (a-z, A-Z)

  • =:A= :: any character other than a letter

  • =:w= :: any alphanumeric character.

  • =:W= :: any non-alphanumeric character.

  • =:s= :: any blank space character.

  • =:S= :: any character other than a blank.

  • =:&= :: Non-ASCII character (in UTF8 version only).

  • =:|= :: Vertical bar

  • =:^= :: Caret

  • =:$= :: Dollar sign

  • =:(= :: Left parenthesis

  • =:)= :: Right parenthesis

  • =:<= :: Greater than

  • =:>= :: Less than

  • =:[= :: Left bracket

  • =:]= :: Right bracket

  • =:.= :: Point

  • =:?= :: Interrogacion

  • =:+= :: More

  • =:-= :: Less

  • =:*= :: Asterisk

  • =:{= :: Left key

  • =:}= :: Right key

  • =:#= :: Modifier

  • =::= :: Colons

additionally use the proper c syntax to place characters new line, tab, ..., etc. Similarly you can use the c syntax for "placing" characters in octal, hexadecimal or unicode.

** Examples of use

=ascii_test.c= file contains a wide variety of tests that are useful as examples of use, these include the next:

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

captures a date format string, separately day, stripper, month and year. The separator has to coincider the two occasions that appears

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

capture something like a web link

#+BEGIN_SRC c regexp4( "nasciiboy@gmail.com", "<[_A-Za-z0-9:-]+(:.[_A-Za-z0-9:-]+)>:@<[A-Za-z0-9]+>:.<[A-Za-z0-9]+><:.[A-Za-z0-9]{2}>" ); #+END_SRC

capture sections (user, site, domain) something like an email.

  • Hacking ** algorithm *** Flow Diagram

    #+BEGIN_EXAMPLE ┌────┐ │init│ └────┘ │◀───────────────────────────────────┐ ▼ │ ┌──────────────┐ │ │loop in string│ │ └──────────────┘ │ │ │ ▼ │ ┌─────────────┐ no ┌─────────────┐ │ <│end of string│>────▶<│search regexp│>──────┘ └─────────────┘ └─────────────┘ no match │ yes │ match ▼ ▼ ┌────────────────┐ ┌─────────────┐ │report: no match│ │report: match│ └────────────────┘ └─────────────┘ │ │ │◀────────────────────┘ ▼ ┌───┐ │end│ └───┘ #+END_EXAMPLE

    =search regexp= version one

    #+BEGIN_EXAMPLE ┌──────────────────────────────┐ ┏━━━━━━━━━━━━━┓ ▼ │ ┃search regexp┃ ┌───────────┐ │ ┗━━━━━━━━━━━━━┛ │get builder│ │ └───────────┘ │ │ │ ▼ │ ┌───────────────┐ no ┌────────────┐ │ <│we have builder│>────▶│finish: the │ │ └───────────────┘ │path matches│ │ │ yes └────────────┘ │ ┌────────┬─────┬──────────┼────────────┬──────────┐ │ ▼ ▼ ▼ ▼ ▼ ▼ │ ┌───────────┐┌───┐┌─────┐┌─────────────┐┌─────────┐┌────────┐ │ │alternation││set││point││metacharacter││character││grouping│ │ └───────────┘└───┘└─────┘└─────────────┘└─────────┘└────────┘ │ │ │ │ │ │ │ │ ▼ └─────┴──────────┼────────────┘ └──────┤ ┌────────────────┐ │ │ ┌────────│ save position │ ▼ │ │ └────────────────┘ ┌─────────────┐ no match │ │ ┌────────────────┐ <│match builder│>──────────┐ │ ▼◀───────│restore position│◀────┐ └─────────────┘ │ │ ┌──────────────┐└────────────────┘ │ │ match │ │ │loop in paths │ │ ▼ ▼ │ └──────────────┘ │ ┌─────────────────┐ ┌───────────────┐ │ │ │ │advance in string│ │finish, the │ │ ▼ │ └─────────────────┘ │path no matches│ │ ┌────────────┐ yes ┌─────────────┐ │ │ └───────────────┘ │ <│we have path│>───▶<│search regexp│>──┘ └──────────────────────────────┘ └────────────┘ └─────────────┘ no match │ no match │ ▼ ▼ ┌───────────────────────┐ ┌────────────┐ │finish, without matches│ │finish, the │ └───────────────────────┘ │path matches│ └────────────┘ #+END_EXAMPLE

    =search regexp= version two

    #+BEGIN_EXAMPLE ┌─────────────┐ │save position│ ┏━━━━━━━━━━━━━┓ └─────────────┘ ┃search regexp┃ ┌────────────▶│ ┗━━━━━━━━━━━━━┛ │ ▼ │ ┌──────────────┐ │ │loop in paths │ │ └──────────────┘ │ │ ┌────────────────────────────────┐ │ ▼ ▼ │ │ ┌────────────┐ yes ┌───────────┐ │ │ <│we have path│>────────▶│get builder│ │ │ └────────────┘ └───────────┘ │ │ │ no │ │ │ ▼ ▼ │ │ ┌───────────────────────┐ ┌───────────────┐ no ┌─────────────┐ │ │ │finish: without matches│ <│we have builder│>───▶│finish: the │ │ │ └───────────────────────┘ └───────────────┘ │path matches │ │ │ │ yes └─────────────┘ │ │ ┌─────┬──────────┼────────────┬─────────┐ │ │ ▼ ▼ ▼ ▼ ▼ │ ┌────────────────┐ ┌───┐┌─────┐┌─────────────┐┌─────────┐┌────────┐ │ │restore position│ │set││point││metacharacter││character││grouping│ │ └────────────────┘ └───┘└─────┘└─────────────┘└─────────┘└────────┘ │ ▲ │ │ │ │ │ │ │ └─────┴──────────┼────────────┘ │ │ │ ▼ ▼ │ ┌───────────────┐ no match ┌─────────────┐ ┌─────────────┐ │ │finish: the │◀────────┬──────────<│match builder│> ┌───<│search regexp│> │ │path no matches│ │ └─────────────┘ │ └─────────────┘ │ └───────────────┘ │ │ match │ │ │ └────────────────┈┈│┈┈────────┘ │ match │ ▼ │ │ ┌─────────────────┐ └─────────┤ │advance in string│ │ └─────────────────┘ │ │ │ └────────────────────────────────┘ #+END_EXAMPLE

  • License

    This project is not "open source" is free software, and according to this, use the GNU GPL Version 3. Any work that includes used or resulting code of this library, you must comply with the terms of this license.

  • Contact, contribution and other things

    [[mailto:nasciiboy@gmail.com]]