[Powered by Google Translate] [Seminario: Modello di corrispondenza con espressioni regolari] [John Mussman-Harvard University] [Questo è CS50.-CS50.TV] Va bene. Bene, benvenuti a tutti. Questo è CS50 2012. Il mio nome è John, e parlerò oggi sulle espressioni regolari. Le espressioni regolari è soprattutto uno strumento, ma anche a volte usati in codice attivamente per soddisfare essenzialmente modelli e stringhe. Quindi, ecco un web comic da xkcd. In questo fumetto vi è un giallo in cui l'assassino ha seguita qualcuno in vacanza, ei protagonisti devono cercare tra 200 megabyte di messaggi di posta elettronica alla ricerca di un indirizzo. E sono sul punto di rinunciare, quando qualcuno che conosce le espressioni regolari - presumibilmente un supereroe - piomba verso il basso e scrive un certo codice e risolve il mistero dell'omicidio. Quindi, presumibilmente, che sarà qualcosa che si ha il potere di fare dopo questo seminario. Stiamo solo andando a fornire una sintetica introduzione alla lingua e darà abbastanza mezzi per andare dopo più risorse sul proprio. 

Espressioni regolari così sembrano fondamentalmente come questo. Si tratta di una espressione regolare in Ruby. E non è molto diversa tra le varie lingue. Abbiamo solo su barre per iniziare e segnare l'espressione regolare in Ruby. E questa è una espressione regolare per cercare l'indirizzo email pattern. Così vediamo al primo bit cerca qualsiasi carattere alfanumerico. Questo perché gli indirizzi di posta elettronica spesso devono iniziare con un carattere alfabetico. E poi ogni carattere speciale seguita dal simbolo @. E poi la stessa cosa per il nome di dominio. E poi tra 2 e 4 caratteri per cercare il. Com,. Net, e così via. Quindi, questo è un altro esempio di espressione regolare. Espressioni regolari così sono protocolli per la ricerca di schemi in testo. Lo fanno i confronti, selezioni e sostituzioni. Quindi, un terzo esempio è trovare tutti i numeri di telefono che terminano in 54 in una directory. Quindi, prima di David strappa la directory CS50 potremmo cercare un modello in cui abbiamo parentesi poi 3 numeri poi finisce parentesi, Altre 3 cifre, un trattino, due numeri, e poi 54. E questo sarebbe essenzialmente come arriviamo con una espressione regolare per la ricerca di questo. 

Quindi ci sono - abbiamo fatto alcune cose in CS50 che sono un po 'come espressioni regolari, per cui - ad esempio - nel file dictionary.C per il controllo ortografico problema insieme potrebbe essere utilizzato fscanf di leggere in una parola dal dizionario. E si può vedere il 45s percentuale è alla ricerca di una stringa di 45 caratteri. Quindi è un po 'come una espressione regolare rudimentale. E si può avere 45 caratteri che misura la fattura in là e scegliere quelli su. E poi il secondo esempio nella più recente problema di programmazione web stabilito nel codice php distro per noi in realtà hanno una semplice espressione regolare. E questo è semplicemente cercando di verificare se la pagina web che viene passato corrisponde o login o il logout registrazione. PHP. E poi il ritorno vero o falso sulla base di tale corrispondenza dell'espressione regolare. 

Così, quando si usa l'espressione regolare? Perché sei qui oggi? Quindi non si vuole usare un'espressione regolare quando c'è qualcosa che fa ancora più facilmente il lavoro per voi. Quindi, XML e HTML sono in realtà piuttosto difficile di scrivere espressioni regolari per come vedremo tra poco. Quindi ci sono i parser dedicati per tali lingue. È inoltre necessario essere a posto con il compromessi e precisione di frequente. Se si sta cercando - e quindi abbiamo visto una espressione regolare per un indirizzo di posta elettronica, ma dici che volevi un indirizzo email specifico e gradualmente il espressione regolare potrebbe diventare più complesso come è diventato più preciso. In modo che sarebbe un compromesso. Dovete essere sicuri che si sta facendo bene con l'espressione regolare. Se sai esattamente quello che stai cercando potrebbe avere più senso a mettere in tempo e scrivere un parser più efficace. E infine c'è un problema storico con la regolarità di espressioni e linguaggi. Le espressioni regolari sono in realtà molto più potente di espressioni regolari per dire in senso formale. 

Quindi io non voglio andare troppo lontano nella teoria formale, ma la maggior parte delle lingue che noi codice in realtà non sono regolari. E questo è il motivo per cui le espressioni regolari a volte non vengono considerati tutti che sicuro. Quindi, in pratica vi è una gerarchia di Chomsky per le lingue, e le espressioni regolari sono costruire con l'unione, concatenazione, e l'operazione di Kleene stella che vedremo in pochi minuti. Se siete interessati in teoria c'è un sacco succede là sotto il cofano. 

Quindi un po 'di storia - solo per il contesto qui - insiemi regolari si avvicinò nel 1950, e poi abbiamo avuto redattori semplici che incorporate le espressioni regolari - solo ricerca di stringhe. Grep - che è uno strumento a riga di comando - è stato uno dei primi strumenti molto popolari che incorporati espressioni regolari nel 1960. Negli anni '80, Perl è stato costruito - è un linguaggio di programmazione che incorpora espressioni regolari molto prominente. E poi, più recentemente abbiamo avuto Perl espressioni regolari compatibile protocolli fondamentalmente in altre lingue che utilizzano gran parte la stessa sintassi. Naturalmente l'evento più importante è stato nel 2008 dove c'era la prima Espressioni regolari Giornata Nazionale, che credo sia 1 giugno se si vuole festeggiare. 

Anche in questo caso, solo un po 'di più la teoria qui. Quindi ci sono un paio di modi diversi di costruire espressioni regolari. Un modo semplice è quello di costruire l'espressione che si sta per eseguire sulla stringa interpretare - fondamentalmente costruire un piccolo mini-programma che analizzerà i pezzi di una stringa e vedere: "Oh, questo non si adatta l'espressione regolare o no?" E quindi eseguire tale. Quindi, se si dispone di una piccola espressione regolare, questo è probabilmente il modo più efficiente per farlo. E poi se si - un'altra opzione è quella di mantenere la ricostruzione della espressione, come si va, e cioè la possibilità di simulazione. E questi primi tentativi di algoritmi di espressioni regolari erano relativamente semplice e relativamente veloce, ma non ha avuto un sacco di flessibilità. Quindi, per fare anche alcune delle cose che stiamo andando a guardare oggi abbiamo avuto a che fare più complessa espressione regolare implementazioni che sono potenzialmente molto più lento, così che è qualcosa da tenere a mente C'è anche una espressione regolare negazione della varietà attacco che sfruttare il potenziale di queste implementazioni più recenti di espressioni regolari per diventare molto complessa. E nello stesso senso che abbiamo visto in attacchi di buffer overflow, si dispone di attacchi che il lavoro da fare loop ricorsivo che superamento della capacità di memoria. E dal modo in Regexen è uno dei plurali ufficiali della espressione regolare per analogia al buoi in quello anglosassone. 

Ok, allora la Biblioteca Python molti di voi qui in persona hanno i Mac, così si può effettivamente tirare questo sul vostro schermo. Le espressioni regolari sono costruite in Python. E così Python è precaricato su Mac e anche disponibile on-line a questo link. Quindi, se si sta guardando è possibile mettere in pausa e di assicurarsi di avere Python come si gioca qui. C'è un manuale online, quindi se digiti Python nel vostro computer vedrete che la versione esce nel terminale. Così ho fornito un link al manuale per la versione 2 di Python, nonché un foglietto. Vi è una versione 3 di Python, ma il Mac non necessariamente venire con quella precaricata. Quindi, non è terribilmente diversa. Ok, quindi alcuni principi fondamentali di utilizzo di espressioni regolari in Python. 

Così qui ho usato una espressione molto semplice, così ho fatto Python import re e poi ha preso il risultato di re.search. E la ricerca prende due argomenti. Il primo è l'espressione regolare, e il secondo è il testo o stringa che si desidera analizzare. E poi ho stampato il result.group. Quindi queste sono le due funzioni di base che andremo a vedere oggi a conoscere le espressioni regolari. Quindi, solo abbattendo questa espressione regolare qui h e poi \ w, quindi m così \ w accetta un qualsiasi carattere alfabetico in là. Così qui siamo alla ricerca di una "h" e poi un altro carattere alfabetico e poi m, ecco che sarebbe partita prosciutto In ", panini Abraham Lincoln e prosciutto." Questo è il risultato di tale gruppo. Un'altra cosa che possiamo fare è usare le nostre corde prima di testo in Python. Quindi credo che andrò avanti e tirare che fino qui. Python import re. E se dovessi fare la stessa cosa - diciamo così di testo è, "Abramo", fateci Zoom In - ci siamo. Il testo è: "Abramo mangia prosciutto". Va bene, e allora risultato = re.search. E poi la nostra espressione può essere h, e poi mi farà dot m. Quindi dot prende un qualsiasi carattere che non sia una nuova linea compresi i numeri, segni di percentuale, qualcosa di simile. E poi il testo - braccio - e poi result.group--si. Quindi questo è solo come implementare funzionalità di base qui. Se avessimo un anello testo - che il testo pazza - incluso dicono un sacco di barre rovesciate e stringhe all'interno e cose che potrebbero apparire come sequenze di escape, allora probabilmente vogliamo utilizzare il metodo di scrittura prima per assicurarsi che è accettato. E che sembra proprio così. Quindi, se stavamo cercando per ciascuno di essi in là non dovremmo trovare nulla. Ma è così che si dovrebbe attuarlo; poco prima della stringa di l'espressione regolare che ha messo la lettera r. 

Ok, quindi cerchiamo di andare avanti. Va bene - così vediamo un paio di schemi ripetitivi qui. Quindi una cosa che si vuole fare è ripetere le cose come si sta cercando attraverso il testo. Quindi, per fare un seguito da un numero qualsiasi di b - si fa ab *. E poi ci sono una serie di altre norme troppo. E si può guardare tutti questi up, mi limiterò a passare per alcuni dei quelli più comunemente utilizzati. Così ab + è seguito da un qualsiasi N maggiore di 0 di b. ab? è seguito da 0 o 1 di b. ab {N} è seguita da N di b, e poi così via. Se si dispone di due numeri in parentesi graffe si specifica un intervallo di che può essere eventualmente abbinato. Così vedremo più in un paio di schemi ripetitivi in ​​un minuto. Quindi due cose da tenere a mente quando si utilizzano questi strumenti di disegno di corrispondenza qui. Quindi diciamo che vogliamo guardare l'hm di "Abraham Lincoln fa panini al prosciutto." Così ho cambiato il nome di Abraham Lincoln ad Abramo. E ora siamo alla ricerca di ciò che viene restituito da questa funzione di ricerca, e restituisce solo prosciutto in questo caso. E lo fa perché cerca solo prende naturalmente la maggior parte della coda sinistra. E tutte le espressioni regolari se non diversamente specificato farà. Se volessimo trovare tutto quello che c'è una funzione per questo - trovare a tutti. In modo che può solo guardare come tutti = re.findall ('h.m', testo) e poi all.group (). Tutti produce sia prosciutto e prosciutto, in questo caso entrambe le stringhe in Abramo ogni prosciutto. Quindi questa è un'altra opzione. 

Grande. L'altra cosa da tenere a mente è che le espressioni regolari prendono il più grande intuitivamente. Vediamo questo esempio. Abbiamo fatto quello più a sinistra di ricerca qui, e poi ho tentato una ricerca più grande utilizzando l'operatore Kleene stella. Così per "Abraham Lincoln fa panini al prosciutto," e ho solo tornato m come risultato. La ragione di questo errore è che ho potuto prendere un qualsiasi numero di h 'perché non ho specificato tutto da seguire tra h e m. L'unico esempio che ci aveva m - gli unici esempi lì con m in esso e qualsiasi numero di h è erano solo la stringa m. Poi ho provato di nuovo, ho detto: "Va bene, cerchiamo di ottenere il più grande gruppo reale qui." E poi ho fatto h. * M, in modo che restituisce solo un numero qualsiasi di caratteri tra h e m. E se si è appena agli inizi e pensare: "Oh, va bene, bene questo sarà portami prosciutto, "ci vuole davvero tutto dalla h in Abraham Lincoln tutto il percorso fino alla fine del prosciutto. È avido, ma vede h - tutto questo altro testo - m, e questo è quello che ci vuole dentro Ciò è particolarmente eclatanti - questa è una caratteristica che possiamo anche specificare per non essere avidi usando altre funzioni. Ma questo è qualcosa che dobbiamo tenere a mente soprattutto quando guardando testo HTML, che è uno dei motivi che le espressioni regolari sono difficili per HTML. Perché se si dispone di un tag HTML aperto e poi un sacco di roba in mezzo e poi qualche altro tag HTML chiuso molto più tardi nel programma, avete appena mangiato un sacco di codice HTML possibilmente per errore. 

Tutti i giusti - i caratteri in modo più speciale, come molte altre lingue, fuggiamo utilizzando la barra. Quindi possiamo usare il punto per specificare qualsiasi carattere ad eccezione di una nuova linea. Possiamo usare la fuga w per specificare qualsiasi carattere alfabetico. E per analogia fuga d per ogni intero - carattere numerico. Siamo in grado di precisare - siamo in grado di utilizzare le parentesi per specificare le espressioni correlate. Quindi questo avrebbe accettato a, b, o c. E possiamo anche specificare o opzioni per a oppure b. Per esempio - se stavamo cercando molteplici possibilità tra parentesi si potrebbe utilizzare l'operatore o come in - così torniamo a questo esempio qui. E ora prendiamo - torniamo a questo esempio qui, e poi prendere ae - quindi questo dovrebbe restituire - Credo che questo sia ancora Abramo. Quindi questa - se facciamo tutti - grandi. Cerchiamo quindi di aggiornare il testo qui. "Abramo mangia prosciutto mentre orlatura sua -. Mentre orlatura" Grande. Tutti. Grande. Ora abbiamo il prosciutto, prosciutto, e orlo. Mentre orlatura - mentre canticchiando a lui - mentre canticchiando orlo lui. Grande. Stessa cosa. Ora tutto torna ancora solo prosciutto, prosciutto, e orlo senza sollevare il ronzio o il di lui. Grande - così che cosa se volessimo vedere i due che - in modo da poter anche fare lui o - ci torneremo a questo. Va bene - così - tutti i diritti - in posizioni è anche possibile utilizzare il cursore o il simbolo del dollaro per specificare che si sta cercando qualcosa all'inizio o alla fine di una stringa. Oppure l'inizio o la fine di una parola. Questo è un modo di utilizzare tale. 

Va bene - quindi cerchiamo di giocare con un po 'più grande blocco di testo. Diciamo questa riga qui - questa affermazione qui. Il potere di espressione regolare è che possono specificare i modelli di non solo i caratteri fissi. Facciamo - chiamiamo questo blocco. Poi ci sarà leggere tutto questo dentro E poi hanno un - facciamo tutti =, così che cosa sono alcune cose che potremmo cercare qui dentro con profitto? Potremmo cercare l'orecchio espressione. Non molto interessante. Che ne dici? Staremo a vedere cosa succede. Ho dato un problema. Quindi, qualsiasi numero di cose prima di re e di tutti. Così che dovrebbe tornare tutto dall'inizio fino a tutto ri forse un paio di volte. E poi qui abbiamo il potere di espressioni regolari è che essi può specificare i modelli non solo personaggi qui sono. Quindi, tutta la strada fino alla ri finale, è iniziato con la più a sinistra ed è stato avido. Vediamo - che altro possiamo cercare. Credo che una cosa se foste interessati a cercare i pronomi lei e lui, si potrebbe verificare la presenza di s è uguale a 0 o 1 e l'espressione lui, e che probabilmente non sta per tornare - Oh, credo che egli ritornò perché ci stiamo guardando il potere, quel giorno, ecco. Cerchiamo precisando che questo deve avvenire a inizio di qualcosa. Vediamo se questo cade. Così possiamo fare il grasso, e non ci non ottenere nulla, perché lei e lui non si verificano in questa frase. Grande. Va bene - in modo nuovo al gatto qui. Modelli così complesso sta danneggiando il cervello. Quindi è per questo che usiamo le espressioni regolari per evitare questi problemi. 

Così qui sono alcune altre modalità utili si può giocare con. Abbiamo guardato ricerca di oggi, ma è possibile utilizzare anche incontro, dividere, findall, e gruppi. Così le altre cose interessanti che si possono fare con le espressioni regolari, non solo di ricerca di modelli sta prendendo un modello e tenendo tutte le partite - le sue variabili - e quindi utilizzando quelli nel codice successivamente. Che può essere molto utile. Altre cose che potrebbero essere di conteggio. Così siamo in grado di contare il numero di istanze di un modello di espressione regolare, e questo è ciò che siamo in grado di utilizzare i gruppi per. E altri modi così sono anche possibili. Quindi, voglio solo parlare un po 'di più su altri modi è possibile utilizzare le espressioni regolari. 

Così una applicazione più avanzata è in corrispondenza fuzzy. Quindi, se siete alla ricerca di un testo per l'espressione, Giulio Cesare, e si vede sia Caio Giulio Cesare o il nome di Giulio Cesare in altre lingue, allora si potrebbe anche voler assegnare un certo peso a quei valori. E se è abbastanza vicino - se attraversa una certa soglia - poi si desidera per essere in grado di accettare Giulio Cesare. Quindi ci sono un paio di diverse implementazioni per che in alcune altre lingue. Qui ci sono alcuni altri strumenti, Regex Pal - un po 'di applicazione pratica on-line per controllare se le espressioni regolari sono composti correttamente. Ci sono anche strumenti indipendenti che è possibile eseguire dal desktop come Pico Ultra, e così come pochi libri di cucina. Quindi, se si sta facendo un progetto che coinvolge un sacco di espressioni regolari questo è probabilmente il posto dove andare fuori dell'ambito di oggi. E poi solo per darvi un'idea di come comune è c'è grep in Unix, Perl ha built-in, e C c'è PCRE per C. E poi tutte le altre lingue hanno anche pacchetti di espressioni regolari che operano con sostanzialmente la stessa sintassi che abbiamo ottenuto un assaggio di oggi. PHP, Java, Ruby, e così via. 

Google Code Search è davvero degno di nota, è uno dei relativamente poche applicazioni là fuori che consente al pubblico di accedere suo database utilizzando le espressioni regolari. Quindi, se si guarda su Google Code Search è possibile trovare il codice se siete alla ricerca di un esempio di come potrebbe essere utilizzata una funzione, si può usare una espressione regolare per trovare quella funzione viene utilizzata in tutti i tipi di diversi casi. Si potrebbe cercare fwrite, e allora si potrebbe cercare la bandiera di scrivere o leggere se si voleva un esempio di fwrite essere usati in tale caso. Quindi la stessa cosa qui, e qui ci sono alcuni riferimenti. Questo sarà disponibile anche online, in modo da andare avanti se si vuole guardare a Python, grep, Perl - si vuole solo per ottenere un po 'di ispirazione o se si vuole guardare più alla teoria ecco alcune buone rendessero posti. Grazie mille. [CS50.TV]