Articoli Manifesto Tools Links Canali Libri Contatti ?
Linguaggi / Regular Expressions

Regular Expressions: confronti

Abstract
Le regular expressions sono disponibili in molti linguaggi, sotto forma di librerie esterne o direttamente tramite gli operatori o le funzioni standard. In questo documento si cercherà di evidenziare quali tratti accomunino o distinguano un'implementazione dall'altra nei cinque linguaggi scelti: Perl, PHP, Java, JavaScript e Python.
Data di stesura: 14/12/2002
Data di pubblicazione: 30/12/2002
Ultima modifica: 04/04/2006
di Marco Lamberto Discuti sul forum   Stampa

I protagonisti

Sono stati presi in considerazione cinque linguaggi estremamente diffusi che supportano le regexps: Perl, PHP, Java, JavaScript e Python.

Un benchmark banale

Iniziamo questo articolo con un confronto "per gioco", giusto per avere una qualche indicazione concreta, anche se approssimativa, da cui partire per fare alcune valutazioni.
In particolare sarà possibile soffermarsi sull'efficienza implementativa, non solo come velocità, ma anche come tipo e grado di integrazione con il linguaggio.

Il benchmark

Si è cercato di prendere una regexp banale ma non troppo, è presumibilmente ovvio che regexps più complesse abbiano un tempo di computazione maggiore ma non necessariamente proporzionale ad i valori presentati qui. 
\s([a-l]+)([m-z]+)\s
Questa regexp è in grado di individuare tutte le parole, precedute e seguite da spazi, divisibili in due pezzi rispettivamente composti da sole lettere nell'intervallo a-l ed m-z. Questi ultimi sono stati volutamente inseriti, tramite l'uso delle parentesi tonde, in due submatch per "stressare" l'engine obbligandolo a tenerne traccia.

I dati utilizzati per il benchmark sono un normalissimo brano in inglese.
L'operazione di match, riga per riga, è stata ripetuta per 10000 iterazioni. 

  1. When Scrooge awoke, it was so dark that, looking out of bed, he could scarcely 
  2. distinguish the transparent window from the opaque walls of his chamber. He was 
  3. endeavouring to pierce the darkness with his ferret eyes, when the chimes of a 
  4. neighbouring church struck the four quarters. So he listened for the hour. To 
  5. his great astonishment the heavy bell went on from six to seven, and from seven 
  6. to eight, and regularly up to twelve; then stopped. Twelve! It was past two 
  7. when he went to bed. The clock was wrong. An icicle must have got into the 
  8. works. Twelve. He touched the spring of his repeater, to correct this most 
  9. preposterous clock. Its rapid little pulse beat twelve: and stopped. Why, it 
  10. isn t possible, said Scrooge, that I can have slept through a whole day and 
  11. far into another night. It isn t possible that anything has happened to the 
  12. sun, and this is twelve at noon! The idea being an alarming one, he scrambled 
  13. out of bed, and groped his way to the window. He was obliged to rub the frost 
  14. off with the sleeve of his dressing-gown before he could see anything; and 
  15. could see very little then. All he could make out was that it was still very 
  16. foggy and extremely cold, and that there was no noise of people running to and 
  17. fro, and making a great stir, as there unquestionably would have been if night 
  18. had beaten off bright day, and taken possession of the world. This was a great 
  19. relief, because three days after sight of this First of Exchange pay to Mr. 
  20. Ebenezer Scrooge or his order, and so forth, would have become a mere United 
  21. States security if there were no days to count by. 
I sorgenti di tutti i tests sono disponibili alla fine del documento nelle risorse[1].

I risultati

Linguaggio Punteggio Iterazioni al secondo
Perl (5.6.0) 100 8474.58
Python (1.5.2) 42 3558.72
Java (1.4.1_01-b01) 37 3158.56
PHP (4.0.6) 33 2827.89
JavaScript (Mozilla 1.1) 22 1841.62
Come prevedibile da chiunque abbia un minimo di conoscenza dei linguaggi citati nel benchmark, Perl si conferma l'implementazione con migliori performances.

Modalità di implementazione

Prendiamo ora in considerazione come le regexps siano state inserite in ciascun linguaggio.
Le possibilità sono fondamentalmente due:
  • operatore
  • libreria

Operatore

Fra i linguaggi presi in esame è solamente Perl ad avere una così stretta integrazione delle regexps. Queste sono disponibili come operatori del linguaggio.
Normali =~
!~
Quote-Like /PATTERN/
m/PATTERN/
qr/STRING/
s/PATTERN/REPLACEMENT/
Essendo integrate a tutti gli effetti fra gli operatori del linguaggio Il codice delle regexp è manipolato direttamente dal runtime di Perl (l'interprete), questo teoricamente garantisce una maggiore velocità di esecuzione.
Un risultato evidente dell'avere le regexps disponibili come operatore nativo è una estrema immediatezza nell'uso, non servono dichiarazioni e chiamate di metodi.

Tutto questo non vuol dire però che un sorgente Perl che usi o abusi delle regexps sia più comprensibile di altri sorgenti in altri linguaggi. Come sempre il risultato finale dipende anche dal programmatore e dalla sua esperienza.

Libreria

Escluso Perl, tutti gli altri linguaggi presentano un'implementazione basata su una libreria che può essere stata scritta nel linguaggio stesso (ad es. Java) o tramite l'incapsulamento (wrapping) di una libreria esterna (ad es. PHP usa la libpcre e la libregex per implementare rispettivamente le regexps Perl e Posix).

Il giallo del "doppio escaping"

Il problema maggiore che in certi linguaggi un'implementazione così fatta comporta la necessità di ricorrere al "doppio escaping". L'escaping consiste nel preporre ad un carattere il simbolo di backslash "\", la sequenza così ottenuta assume un significato particolare quand'è usata nelle stringhe (ad es. "\t" corrisponde al carattere di tabulazione).

Le sequenze di escaping sono interpretate dal parser o, nel caso di Java, dal compilatore.
Il problema è che le regexps possiedono una ricca serie di sequenze di escaping che non necessariamente hanno lo stesso significato nel contesto di una normale stringa (usata solitamente per passare la regexp alle funzioni in grado di interpretarla).
Ammettendo che "\s" passi il parsing, questa verrebbe molto probabilmente trasformata nel carattere "s" o comunque in un carattere singolo. Successivamente, passato come argomento al motore delle regexp, non verrebbe più interpretato come "\s" ma come qualche cosa di potenzialmente diverso.
In questi casi l'uso di una sequenza di escape in una regexp obbliga l'inserimento di un doppio backslash "\\" per far sì che questo venga trasformato durante la fase di parsing in un singolo "\" e mantenga il significato della regexp. 

  1. Pattern p = Pattern.compile("\\s([a-l]+)([m-z]+)\\s?i"); 
L'uso del doppio escape è obbligatorio nel caso di Java, dove non è stata operata una modifica sostanziale del runtime per riconoscere la presenza di regexps in base al contesto.

In Python è usato il "trucco" di preporre una "r" alla definizione della stringa contenente la regexp, ciò abilita l'uso delle sequenze di escape delle regexp invece di quelle "classiche".
È da sottolineare che questo "trucco" permette di usare le sequenze di escaping estese anche in contesti diversi da una regexp. Questa cosa potrebbe distrarre il programmatore meno smaliziato creando qualche equivoco.
Quest'ultimo, nel leggere un sorgente, potrebbe credere che in una riga, per qualche motivo, sia stata usata una regexp anche se nessun RegexObject è direttamente coinvolto.

Ovviamente se non si usa il modificatore "r", è necessario il "doppio escaping" anche in Python. 

  1. p = re.compile(r"\s([a-l]+)([m-z]+)\s"); 
  2. p = re.compile("\\s([a-l]+)([m-z]+)\\s"); 

Modo d'uso: integrazione sintattico/semantica con il linguaggio

Un risultato immediato della scelta implementativa si riflette nelle modalità d'uso delle regexps all'interno di un sorgente.

Compilazione dei patterns

Le regexps sono interpretate, devono quindi passare una fase di validazione e trasformazione iniziale altresì detta compilazione.
Ovviamente la compilazione è un'operazione che prende un certo tempo in base alla complessità del pattern. L'uso in un loop di una regexp che debba essere ricompilata ad ogni iterazione impatterà sicuramente sulle performances in maniera direttamente proporzionale al numero di iterazioni del ciclo.
Anche in questo caso le scelte implementative permettono l'individuazione di due categorie:
Compilazione preventiva Perl (tramite l'opzione "o"), Java, JavaScript, Python
Ricompilazione ad ogni richiesta Perl, PHP

I commenti

La leggibilità di una regexp tende a calare in maniera vertiginosa man mano che questa diventa più lunga. Perl e Java permettono di inserire dei commenti all'interno dei patterns tramite l'uso del modificatore "x".
Nello specifico di Java è possibile usare "?x" o la costante Pattern.COMMENTS.

Esempio pratico dell'uso dei commenti

Supponiamo di avere un file di configurazione per un sistema di controllo degli accessi (ACL) che permetta determinate operazioni in maniera selettiva basandosi su chi opera, da dove opera, che operazione venga richiesta e su che oggetto, così fatto: 
ALL: ANY: HELO(ALL)
ALL: ANY: BLBK(ALL)
ALL: ANY: STAT(ALL)
ALL: 192.168.1: STAT(ALL)
ALL: 192.168.1.1: STAT(ALL)
ALL: tac: STAT(ALL)
ALL: tac.silab.dsi.unimi.it,192.168.1: STAT(ALL)
USER(ml568366): hal: HELO(GROUP(student))
USER(ml568366): hal: HELO(SELF)
Dove per ciascuno dei campi siano definite le seguenti regole di sintassi:
Campo Possibili valori ammessi
chi
  • La parola chiave ALL.
  • La funzione USER o GROUP con argomento una lista di utenti o gruppi.
da dove
  • Una lista di indirizzi simbolici o numerici in dotted notation. In quest'ultimo caso è possibile applicare la regola ad una intera classe ip omettendo gli ultimi numeri (es. 127.0 per 127.0.x.x).
comando
  • Il nome di un comando composto da 4 lettere maiuscole.
applicato a
  • La parola chiave ALL.
  • La funzione USER o GROUP con argomento una lista di utenti o gruppi.
Una regexp adatta al match potrebbe essere la seguente: 
  1. / 
  2.   ^\s* 
  3.   (?:                                          # chi opera 
  4.     (ALL)| 
  5.     (GROUP|USER) 
  6.       \( 
  7.         (ALL|(?:\s*\w+\s*,)*(?:\s*\w+\s*)) 
  8.       \) 
  9.   ) 
  10.   \s*:\s*                                      # : 
  11.   (?:                                          # da dove opera 
  12.     (ALL)| 
  13.     ([0-9A-Z]{4})                              # comando 
  14.       \( 
  15.         (?:                                    # applicato a ... 
  16.           (ALL|SELF)| 
  17.           (GROUP|USER) 
  18.             \( 
  19.               (ALL|(?:\s*\w+\s*,)*(?:\s*\w+\s*)) 
  20.             \) 
  21.         ) 
  22.       \) 
  23.   ) 
  24.   \s*$ 
  25. /x; 

Effettiva praticità d'uso

Solamente in Perl e JavaScript è possibile dichiarare una regexp senza l'uso esplicito di funzioni o oggetti.
Questo fattore può migliorare la leggibilità e la compattezza del codice.
Tralasciando infatti dichiarazioni e inizializzazioni si permette l'uso immediato del pattern, senza troppi "fronzoli". 
  1. if ($linea =~ /\s([a-l]+)([m-z]+)\s/i) { 
  2.   ... 
  3. } 
  1. if (/\s([a-l]+)([m-z]+)\s/i.test(linea)) { 
  2.   ... 
  3. } 

Conclusioni

Avere a disposizione uno strumento come le regexp integrato nel linguaggio è sicuramente un punto a nostro vantaggio. Usarle con criterio, consci dei limiti dovuti all'implementazione sottostante, permette sicuramente di migliorare la qualità di un progetto.

In questo primo confronto ho cercato di evidenziare i differenti livelli di integrazione delle regexps in alcuni linguaggi che le supportano. È possibile un ulteriore analisi, questa volta interna alle classi di regexps, POSIX e Perl compliant, che verranno trattate in un prossimo articolo.

Informazioni sull'autore

Marco Lamberto, laureato in Informatica presso la Statale di Milano, con diversi anni di esperienza sistemistica, di sicurezza e sviluppo prevalentemente in ambienti UNIX (Linux in primis) con linguaggi come C, Java, Perl, PHP, XML, HTML, ...

È possibile consultare l'elenco degli articoli scritti da Marco Lamberto.

Altri articoli sul tema Linguaggi / Regular Expressions.

Risorse

  1. I sorgenti del benchmark.
    http://www.siforge.org/articles/2002/12/regex-cfr/benchmark.zip (9Kb)
  2. Precedente articolo introduttivo sulle Regular Expressions.
    http://www.siforge.org/articles/2002/09/22-regex.html
Discuti sul forum   Stampa

Cosa ne pensi di questo articolo?

Discussioni

Questo articolo o l'argomento ti ha interessato? Parliamone.