Le Espressioni Regolari e gli Automi

:: Espressioni Regolari :: Linguaggi ed applicazioni

Università degli Studi di Salerno Corso di Automi, Linguaggi e Complessità

Maggio 2016

Autori: Giuseppe Luciano, Christian Ronca

Docente: Prof.ssa Margherita Napoli

Indice

• Introduzione

• Espressioni Regolari e Automi

• ER nei linguaggi di programmazione

• ER nei compilatori

Espressioni regolari, linguaggi ed applicazioni mag. ’16 2

Introduzione

Espressioni Regolari

Le espressioni regolare sono un modo semplice per capire se una stringa rispetta un certo formato: email, numeri di telefono, indirizzi IP, ecc.

Sono strettamente legate agli automi a stati finiti e possono rappresentare un’alternativa alla notazione degli automi a stati finiti per descrivere componenti software;

Con le ER si possono definire tutti e soli i linguaggi regolari.


Introduzione

Storia

• Verso la fine degli anni 60, Stephen Kleene formalizza i linguaggi regolari usando la nozione matematica «regular sets»;

• Nel 1962, fu creato SNOBOL che non utilizzava le espressioni regolari, ma un proprio modello di matching;

• Nel 1968, le espressioni regolari vengono usate all’interno di un editor di testo per fare pattern matching e come analizzatore lessicale in un compilatore;

• Successivamente vengono integrate nei programmi Unix (come grep) ed in altri sistemi; vengono standardizzate nello standard POSIX 2 nel 1992;

• Nel 1980 vengono introdotte in PERL e nel 1997 viene sviluppata PCRE da Philip Hazel, una libreria per espressioni per PERL utilizzata da numerosi programmi come ad esempio APACHE.


Introduzione


Espressioni regolari e automi

Le espressioni regolari (”Regular Expression”) garantiscono un metodo efficace e flessibile per l’elaborazione del testo.

Le espressioni regolari sono uno strumento indispensabile per i linguaggi di programmazione che gestiscono le stringhe, soprattutto per analizzarle.

Un linguaggio di programmazione per usare le R.E. ha bisogno di un Regular Expression Engine.



Engine

Un Engine è un motore che prende in input una stringa e un criterio di accettazione (o pattern) e restituisce uno tra:

• DFA • NFA Tradizionale • POSIX NFA

Tutte le engine provano a trovare il match leftmost più lungo, ma questo può cambiare a seconda del tipo di engine.



Costruzione di Engine: l'algoritmo di Thompson

Per costruire un engine ci sono diversi algoritmi.

Quello più famoso è l'algoritmo di Thompson, usato per trasformare un’espressione regolare in un automa equivalente non deterministico (NFA).



Esempi di Engine

Gli Engine DFA sono usati da MySql, Awk e operano in tempo lineare.

Il matching è detto ”text-direct”, man mano che i caratteri in input vengono letti, viene aggiornata una lista dei possibili match.



Esempi di Engine Gli Engine NFA Tradizionali sono usati dai linguaggi di programmazione

tradizionali. Caratteristiche:

• Esegue algoritmi più rigidi per la ricerca di testo con funzionalità di backtracking.

• Verifica tutte le possibili espansioni di un’espressione regolare in un determinato ordine e accetta la prima corrispondenza.

• Nei casi peggiori si può assistere a rallentamenti di carattere esponenziale. E’ conveniente ottimizzare la regexpr.

• Viene detto ”regex-direct”.



Esempi di Engine

POSIX NFA • È simile al modulo di gestione NFA tradizionali, con la sola eccezione

che continua il backtracking fino a maturare la certezza di aver trovato la corrispondenza più lunga

• Di conseguenza, un modulo di gestione POSIX NFA è più lento di un modulo di gestione NFA tradizionale

• Non è possibile favorire l’individuazione di una corrispondenza più breve rispetto a una più lunga modificando l’ordine di ricerca del backtracking.



Esempi di Engine

Engine ibridi DFA/NFA sono usati da GNU awk, GNU egrep and Tcl L’unica implementazione pienamente ibrida è quella sviluppata da

Henry Spencer (1) per Tcl. Egrep e awk usano due engine separati, scelti a seconda della presenza

di determinate caratteristiche nell'espressione regolare 1: https://garyhouston.github.io/regex/


Espressioni regolari e automi: Esempio

Parola: oneselfsufficient

RegEx: /one(self)?(selfsufficient)?/

Con NFA normale si deve ottimizzare il pattern di match, per trovare il pattern leftmost più lungo.


Nfa

oneself

Posix Nfa

oneselfsufficient

ER nei linguaggi di programmazione

Come è fatta un’espressione regolare?

Le espressioni regolari sono costituite da un sottoinsieme di Metacaratteri, che sono caratteri speciali che rappresentano un insieme di altri caratteri o sequenze di caratteri. Es: Riconoscimento di un indirizzo e-mail:




Quantificatori: si inseriscono dopo il pattern e danno un’indicazione di quante volte ricercare una sequenza di caratteri: • + : una o più occorrenze;

• * : 0 o più occorrenze;

• ? : 0 o 1 sola occorrenza, es: A?

• {n}, {2,4} : n occorrenze;

NB: “?” può avere diversi significati a seconda di dove viene usato.




Ancore: identificano la posizione in cui cercare testo (^, $, \b). Es: • ^(il|la): stringhe che cominciano con «il» o «la»; • \d*$: stringhe che finiscono con numeri decimali; • \b (boundary) identifica il confine delle parole. Es: \bcat identifica 'cat'

all'inizio di ogni parola, mentre cat\b identifica 'cat' alla fine di ogni parola.




Classi: indicano un elenco di caratteri da ricercare e vengono racchiusi tra parentesi quadre. E’ possibile inserire anche degli intervalli di ricerca tramite il segno ‘-’ (es: [abc], [a-z], ecc);




Gruppi: vengono racchiusi tra parentesi tonde e vengono richiamati nel caso in cui avviene una sostituzione o per indicare una sottostringa. Nei gruppi è possibile usare anche l’operatore | (or). Es: c(o|a)sa.


mag. ’16 Espressioni regolari, linguaggi ed applicazioni 20


Come è fatta un’espressione regolare? Non-capturing subpattern - ?: Se facessimo il match della stringa "the red king“ con l'espressione regolare "the ((red|white) (king|queen))" le sottostringhe estratte sarebbero: "red king", "red" e "king". Se non vogliamo catturare un sub-pattern, si deve usare ?: davanti alle parentesi tonde, che vanno ad indicare il gruppo (in inglese subpattern). Infatti dalla stringa "the white queen" matchata con l'espressione "the ((?:red|white) (king|queen))" si prenderebbero solo le sottostringhe: "white queen" and "queen"



Asserzioni Look-around: elementi di controllo che vengono applicati alle ricerche. • (?=abc): positive lockahead. L’engine non si sposta avanti sul pattern. • (?<=abc): positive lookbehind. Es: “(?<=a)b” - seleziona una b preceduta da un a • (?!abc): negative lockahead. Es: “b(?!a)” - b non seguita da a • (?<!abc): negative lookbehind. Es: “(?<!a)b“ - a non precede b Altri esempi: http://www.regular-expressions.info/refadv.html



altri metacaratteri sono:

• Caratteri speciali: identificano caratteri come quelli di fine riga, tabulazioni o escape (\n, \r, \t, \*, \\, ecc..);

• Classi di carattere: specificano una serie di caratteri senza l’utilizzo dei gruppi.



Prestazioni: come ottimizzare un E.R.

A seconda dell’engine usato ci possono essere dei pattern che lavorano meglio o peggio;

Ci sono delle regole generiche che servono a migliorare le performance.




Genericamente si può dire che • le costruzioni più semplici sono più efficienti di altre:

• [aeiou] è più efficiente di (a|e|i|o|u)

• I pattern più lunghi di solito sono quelli più efficienti.




Più precisamente è consigliabile usare:

1. Le classi di caratteri. Specificare quale classi di caratteri usare (es: [a-z] o [0-9] ) invece di usare .*,

così da evitare il backtracking

2. I quantificatori Lazy dove richiesto: Es: “.* Lock_time” o “.*? Lock_time” ? Col primo pattern viene letta tutta la

frase e poi viene eseguito un backtrack (si va a ritroso) fino al primo “Lock_time”; col secondo viene letta la frase fino a “Lock_time”.




Il backtracking: lazy e greedy matching



Implementazione:

In quasi tutti i linguaggi di programmazione le espressioni regolari vengono prima compilate (viene generato l’automa corrispondente) e poi viene eseguito il match sulle stringhe.

Solo in Perl ci sono degli operatori di pattern binding: • =~ se uguale • ! ~ se diverso

che permettono di applicare le espressioni regolari senza compilarle prima.



Java



Python



Perl

#/user/bin/perl $string = 'The cat sat on the mat'; $string =~ s/cat/dog/; print "$string\n";

Questo codice stampa: The dog sat on the mat



PCRE - Perl Compatible Regular Expressions

La libreria PCRE è stata scritta in C da Philip Hazel ed implementa le funzionalità di pattern matching tramite espressioni regolari, usando la stessa sintassi e semantica di Perl 5. La sintassi di PCRE è molto più potente e flessibile dello standard POSIX e molte altre librerie di espressioni regolari (ad esempio: ereg). PCRE non viene usata solo da PERL, ma anche da Apache, PHP, KDE, Postfix, Analog, e Nmap.


http://httpd.apache.org/

http://www.php.net/

http://www.kde.org/

http://www.postfix.org/

http://www.analog.cx/

http://nmap.org/


Pattern Modifier

PCRE supporta i modificatori di criterio, ovvero, è possibile dare delle direttive alle espressioni regolari come: • i: non viene fatta nessuna distinzione tra caratteri maiuscoli e minuscoli; • m: la ricerca avviene su più linee, non si ferma alla prima occorrenza; • x: vengono ignorati gli spazi; • u: la stringa di ricerca viene considerata come utf-8; • g: ricerca globale; • …

Non tutti i linguaggi supportano questi valori di flag.



Feature di PCRE

• Supporto delle abbreviazioni: in PCRE è possibile individuare lettere o numeri

attraverso le seguenti abbreviazioni:

\d equivale a [0-9]

\D nega la precedente [^0-9]

\w equivale a [0-9A-Za-z]

\W nega la precedente [^0-9A-Za-z]

\s equivale a [ \t\n\r]

\S nega la precedente [^ \t\n\r]



Feature di PCRE

• Extended character classes: PCRE supporta le classi di caratteri a lettera

singola, ovvero tramite il carattere ‘\d’, è possibile identificare tutte le cifre da 0-9, con ‘\w’ tutte le parole dell’alfabeto a-z, ecc (es: in POSIX si usa [[:digit:]]);

• Lazy matching (a.k.a. “ungreedy”): Tramite l’uso del carattere ‘?’ è possibile

velocizzare il matching.



Feature di PCRE

• Unicode character properties: è possibile definire delle regole per la gestione

dei caratteri Unicode. Per esempio, con il carattere ‘\w’, è possibile riconoscere tutte le stringhe di caratteri letterali. Inserendo( *UCP) all’inizio del pattern, è possibile alterare la proprietà di ‘\w’ estendo il supporto anche ai caratteri accentati e speciali;

• Multiline matching: ^ e $ possono corrispondere all’inizio e la fine di una

stringa, oppure specificare l’inizio e la fine di una linea di caratteri presenti all’interno della stringa a seconda delle opzioni che sono state impostate.



Feature di PCRE

• Newline/linebreak options: è possibile specificare tramite PCRE tutti i caratteri

speciali che indicano l’inizio o l’interruzione e a capo di una stringa.

Per esempio: • (*LF) che corrisponde a \r;

• (*CR) che corrisponde a \n: fine stringa;

• (*ANYCRLF) che corrisponde a (?>\r\n|[\r\n]) oppure \R;

• (*ANY) che corrisponde a (?>\r\n|\n|\x0b|\f|\r|\x85) o \R ed include il supporto a UTF-8;



Feature di PCRE

• Atomic grouping : è un modo di prevenire il backtracking in un pattern. Ad

esempio, ‘a++’ prenderà tutte le ‘a’ all’interno di un insieme di stringhe senza mai fare backtracking. In pratica, la selezione avviene solo quando ci sono un certo numero di ‘a’ seguite da un altro carattere.



Feature di PCRE

• Recursive patterns: può

capitare che si è interessati a verificare che in una stringa, per lo stesso numero di parentesi aperte, ci sia lo stesso numero di parentesi chiuse.



Feature di PCRE

• Tricks: è possibile individuare tutte le stringhe che sono composte da 3 caratteri o che hanno una lunghezza multipla di 3;



Domini applicativi

grep (general regular expression print) è un comando dei sistemi Unix e Unix-like, e più in generale dei sistemi POSIX e GNU, che ricerca in uno o più file di testo le linee che corrispondono ad uno o più modelli specificati con espressioni regolari o stringhe letterali, e produce un elenco delle linee (o anche dei soli nomi di file) per cui è stata trovata corrispondenza.



Domini applicativi http://www.regexpal.com/ E’ un servizio web che offre la possibilità di testare e debuggare la correttezza delle espressioni regolari. Ci sono numerosi servizi che offrono la stessa cosa come: • http://regexr.com/ • https://regex101.com/ • Altri…


http://www.regexpal.com/

http://regexr.com/

https://regex101.com/

ER nei compilatori

Le espressioni regolari ricoprono un ruolo cruciale nella progettazione di un compilatore!

Presupposto: Un compilatore è diviso in diverse componenti • Lexer: scansiona l’input in cerca di lessemi;

• Parser: analizza la struttura sintattica del sorgente;

• Semant: analizza la struttura semantica del sorgente;

• Generatore di codice: dato l’albero semantico genera il codice eseguibile.


Token Lexer

Syntax Tree Parser

Syntax Tree Seman

Codice intermedio Code

Generator

ER nei compilatori

Il componente che ci interessa è il Lexer:

• Prende il codice sorgente come un flusso di caratteri, lo scansiona alla ricerca di lessemi

• Per ogni lessema restituisce un token al parser, cioè una coppia <Nome, Valore>

Il Lexer opera come un DFA!


ER nei compilatori

Come si progetta un Lexer? Ci sono due modi:

1. Pensare a un DFA per leggere i token e implementarlo;

2. Scrivere Espressioni Regolari per riconoscere i token ed usare un lexer-generator per convertirli in un DFA.

Meglio il secondo caso: è più facile!


ER nei compilatori

Come si definiscono le espressioni regolari

Le Definizioni regolari sono una sequenza del tipo: • d1 -> r1

• d2 -> r2

dove di è un nuovo simbolo non appartenente all’alfabeto Γ e ri è un’espressione regolare sull’alfabeto: Γ U {d1, d2, …di-1}

• Così si evita la ricorsione!


ER nei compilatori

Un lexer generator

JFLEX: • JFLEX è un analizzatore lessicale che prende come input un insieme di

espressioni regolari e delle azioni da effettuare, per generare un programma che legge un testo in input, che fa un match del testo tramite le espressioni regolari e che esegue un’azione sul testo riconosciuto.

• I lexer Flex sono basati su automi deterministici finiti (DFA). Sono molto veloci e non fanno molto backtracking.


ER nei compilatori

JFLEX: Come si definisce una definizione regolare

RegExp ::= RegExp '|' RegExp

| RegExp RegExp

| '(' RegExp ')' | ('!'|'~') RegExp

| RegExp ('*'|'+'|'?')

| RegExp "{" Number ["," Number] "}"

| CharClass | PredefinedClass | MacroUsage

| '"' StringCharacter+ '"' | Character


ER nei compilatori

JFLEX: Le regole e le azioni LineTerminator = \r|\n|\r\n

WhiteSpace = {LineTerminator} | [ \t\f]

Identifier = [:jletter:] [:jletterdigit:]*

DecIntegerLiteral = 0 | [1-9][0-9]*

<YYINITIAL> "abstract" { return symbol(sym.ABSTRACT); }

<YYINITIAL> "boolean" { return symbol(sym.BOOLEAN); }

<YYINITIAL> "break" { return symbol(sym.BREAK); }

.


STATO EXPR AZIONE

FINE! Grazie per l’attenzione!


Fonti

• http://www.rexegg.com: un sito davvero completo sull’Espressioni Regolari

• PCRE: http://php.net/manual/it/book.pcre.php

• Blog di Loggly: https://www.loggly.com/blog/regexes-the-bad-better-best/

• Motori di ricerca

• Wikipedia


http://www.rexegg.com/

http://www.rexegg.com/

http://php.net/manual/it/book.pcre.php

https://www.loggly.com/blog/regexes-the-bad-better-best/









Le Espressioni Regolari e gli Automi

Technology

Transcript of Le Espressioni Regolari e gli Automi