[Powered by Google Translate] [Seminar: model de potrivire cu expresii regulate]
[John Mussman-Universitatea Harvard]
[Acest lucru este CS50.-CS50.TV]
Bine. Ei bine, bun venit toată lumea. Acest lucru este CS50 2012.
Numele meu este John, și voi vorbi astazi despre expresii regulate.
Expresii regulate este în primul rând un instrument, dar, de asemenea, folosit uneori
în cod în mod activ pentru a se potrivi în esență, modele și siruri de caractere.
Deci, aici e un comic web de la xkcd.
In acest comic este un mister crima în care criminalul a
a urmat cineva în vacanță, iar protagoniștii trebuie să
căuta prin 200 de megabytes de e-mailuri în căutarea pentru o adresă.
Și ei sunt pe cale să renunțe la cineva care știe expresii regulate -
probabil un super-erou - coboară în jos și scrie unele cod
și rezolvă misterul crimei.
Deci, probabil că va fi ceva care va fi împuternicită să facă
După acest seminar.
Noi sunt doar de gând să ofere o introducere concisă a limbii
și vă va oferi suficient de mijloacele necesare pentru a merge după mai multe resurse pe cont propriu.
>> Expresii atât de regulate arata practic ca aceasta.
Aceasta este o expresie regulată în Ruby.
Acesta nu este teribil de diferite în limbi.
Avem doar pe slash-uri pentru a începe și marca expresie regulată în Ruby.
Și aceasta este o expresie regulată pentru a căuta în e-mail model adresa.
Deci ne vedem la primul bit cauta orice caracter alfanumeric.
Asta se datorează faptului că adresele de e-mail au de multe ori să înceapă cu un caracter alfabetic.
Și atunci orice caracter special, urmat de simbolul @.
Și apoi același lucru pentru nume de domeniu.
Și apoi între 2 și 4 caractere să caute. Com,. Net, și așa mai departe.
Astfel că este un alt exemplu de expresie regulata.
Expresii atât de regulate sunt protocoale pentru a găsi tipare în text.
Ei fac comparații, selecții, și înlocuiri.
Deci, un al treilea exemplu este de a găsi toate numerele de telefon care se termină în 54 într-un director.
Deci, înainte de David rupe până directorul CS50 am putea căuta
un model de care avem paranteze apoi 3 numere apoi termina paranteze,
3 mai multe numere, de o liniuță, 2 numere, și apoi 54.
Și că ar fi în esență modul în care vom veni cu o expresie regulată pentru a căuta pentru asta.
>> Deci, există - noi am făcut unele lucruri în CS50, care sunt un pic ca
expresii regulate, astfel încât - de exemplu - în fișierul dictionary.C
pentru Spell Check set de probleme ați fi putut folosi fscanf
pentru a citi într-un cuvânt din dicționar.
Și puteți vedea 45 de ani procentul este în căutarea pentru un șir de 45 de caractere.
Deci, este oarecum ca o expresie regulată rudimentar.
Și tu poți avea orice 45 de caractere care se potrivesc proiectul de lege acolo
și alege cele sus.
Și apoi al doilea exemplu în cea mai recentă problemă de programare web
stabilit în codul de distribuție pentru php noi de fapt nu au o expresie regulată simplu.
Și acesta este doar pur și simplu în căutarea de a verifica dacă pagina de web, care este trecut în
potrivește fie autentificarea sau dezautentificarea înregistrați. PHP.
Și apoi se întoarce adevărat sau fals bazat pe care potrivire expresie regulată.
>> Deci, atunci când folosiți expresie regulată?
De ce ești aici azi?
Deci, nu doriți să utilizați expresii regulate atunci când există ceva care
are loc de muncă pentru tine, chiar mai ușor.
Deci, XML și HTML sunt de fapt destul de complicat
a scrie expresii regulate pentru ca vom vedea într-un pic.
Deci, există interpretoare dedicate pentru aceste limbi.
De asemenea, aveți nevoie pentru a fi în regulă cu compromisuri și precizie frecvent.
Dacă se încearcă - așa că am văzut o expresie regulată pentru o adresă de e-mail,
dar spun ai vrut o adresă de e-mail specifice și, treptat,
expresie regulată ar putea deveni mult mai complex, deoarece a devenit mult mai precis.
Așa că ar fi un compromis.
Trebuie să fiți sigur că vă sunt bine face cu expresia regulată.
Dacă știți exact ceea ce cauți pentru că s-ar putea face mai mult sens
pentru a pune în timp și a scrie un parser mai eficient.
Și, în sfârșit există o problemă istorică cu regularitate
de expresii și limbi.
Expresiile regulate sunt de fapt mult mai puternic decât
expresii regulate pe spune într-un sens formal.
>> Deci, eu nu vreau să merg prea departe în teorie formală,
dar cele mai multe limbi pe care le codul de fapt, nu sunt regulate.
Și acesta este motivul pentru expresii regulate, uneori, nu sunt considerate tot ca sigur.
Deci, practic nu există o ierarhie Chomsky de limbi,
și expresii regulate sunt construite cu ajutorul Uniunii, concatenare,
și funcționarea Kleene stele, pe care le vom vedea în câteva minute.
Dacă sunteți interesat în teorie, există destul de multe pe acolo sub capota.
>> Deci, un scurt istoric - doar pentru contextul aici - seturi regulate de venit
în anii 1950, iar apoi am avut editori simple care
încorporate expresii regulate - doar în căutarea pentru siruri de caractere.
Grep - care este un instrument de linie de comandă - a fost una din primele
instrumente foarte popular, care încorporate expresii regulate în anii 1960.
În anii '80, Perl a fost construit - este un limbaj de programare care
încorporează expresii regulate foarte proeminent.
Și apoi, mai recent, am avut Perl expresii regulate compatibil
protocoale de fapt în alte limbi care utilizează o mare parte din aceeași sintaxă.
Desigur, cel mai important eveniment a fost, în 2008,
unde a fost primul national reglementar Ziua expresii,
care cred că este 01 iunie, dacă doriți să sărbătorim.
>> Din nou, doar un pic mai mult teorie aici.
Deci, există câteva moduri diferite de a construi expresii regulate.
Un mod simplu este de a construi expresia pe care aveți de gând să
rula pe șirul de interpretare - de fapt construi un mini-program de mic, care
va analiza bucăți de sfoară și vezi, "Oh, se potrivește acest lucru expresia regulată sau nu?"
Și apoi executați ca.
Deci, dacă aveți un foarte mic expresie regulată, acest lucru este, probabil,
cel mai eficient mod de a face acest lucru.
Și apoi, dacă - O altă opțiune este de a păstra reconstituirea
expresie ca te duci, și că este posibilitatea de simula.
Și aceste încercări timpurii de algoritmi de expresie regulata au fost
relativ simplă și relativ rapidă, dar nu au o mulțime de flexibilitate.
Deci, pentru a face chiar și o parte din lucrurile pe care le vom uita la
astăzi am avut de a face expresii regulate mai complexe
implementari care sunt potențial mult mai lent, astfel că este ceva să aibă în vedere
Există, de asemenea, un expresii negare regulat de soi atac
care a exploata potențialul acestor implementari noi de
expresii regulate a devenit foarte complex.
Și în același sens pe care am văzut-o în atacuri buffer overflow,
aveți atacuri că munca de a face buclele recursive care
depășire a capacității de memorie.
Și de modul în care Regexen este una dintre cele mai plural oficiale de expresie regulată
prin analogie cu boi în cel anglo-saxon.
>> Ok, deci Biblioteca Python mulți dintre voi aici, în persoană au Mac-uri,
astfel încât să puteți trage de fapt asta pe ecran.
Expresiile regulate sunt construite în Python.
Și astfel Python este preîncărcat pe Mac-uri și, de asemenea, disponibil online la acest link.
Deci, dacă vă uitați puteți să întrerupeți și asigurați-vă că aveți Python
ca vom juca aici.
Există un manual on-line, așa că, dacă tastați doar Python în computer
veți vedea că versiunea vine în terminal.
Așa că am oferit un link la manualul pentru versiunea 2 a Python, precum și o foaie de ieftin.
Există o versiune 3 de Python, dar Mac-ul nu neapărat
vin cu care preîncărcat.
Deci, nu foarte diferit.
Ok, deci unele elementele de bază ale folosind expresii regulate în Python.
>> Deci, aici am folosit o expresie foarte simplu, așa că am făcut Python re import
și apoi a luat rezultatul re.search.
Și de căutare are 2 argumente.
Primul este expresie regulată, iar al doilea este textul
sau șir doriți să le analizați.
Și apoi am imprimat result.group.
Deci, acestea sunt cele două funcții de bază, pe care le vom vedea astăzi
în procesul de învățare despre expresii regulate.
Deci, doar de rupere jos această expresie regulată aici
h și apoi \ w și apoi m astfel \ w accepta orice fel de caracter alfabetic acolo.
Deci, aici suntem în căutarea pentru un "h" și apoi un alt caracter alfabetic
și apoi m, asa ca aici care să se potrivească Ham
în, "Abraham Lincoln și șuncă sandwich-uri."
Acesta este rezultatul acestui grup.
Un alt lucru pe care îl putem face este folosi șiruri noastre înaintea textului în Python.
Deci cred ca voi merge mai departe și trage asta aici.
Python re import.
Și dacă ar fi să fac același lucru - să zicem Textul este,
"Avraam," să ne mări - acolo mergem.
Textul este, "Avraam mănâncă șuncă."
Bine, și apoi conduce = re.search.
Și apoi expresia noastră poate fi h, iar apoi voi face dot m.
Deci, punct nevoie doar de orice caracter care nu este o linie nouă, inclusiv numere,
semne procentuale, ceva de genul asta.
Și apoi Text - boom-ul - și apoi result.group--da.
Astfel că este doar modul de a implementa funcționalitatea de bază aici.
Dacă am avut un inel de text care - ca textul nebun - inclus spune o mulțime de bare înapoi
și siruri de caractere în interiorul și lucruri care ar putea arata ca secvențe escape,
atunci probabil că doriți să utilizați de introducere a textului prime pentru a vă asigura că este acceptat.
Și asta doar arata asa.
Deci, dacă am fost în căutarea pentru fiecare dintre ei acolo nu ar trebui să găsim nimic.
Dar care este modul în care v-ar pune în aplicare, chiar înainte de șir de
expresie regulată vă pune litera R.
>> Ok, deci hai să ne continuăm.
Bine - deci să ne uităm la câteva modele repetitive aici.
Deci, un lucru pe care doriți să faceți este să repete lucruri
cum sunteți în căutarea prin text.
Deci, pentru a face un urmat de orice numar de b - faci ab *.
Și apoi există o serie de alte norme prea.
Si poti sa te uiti de toate astea, voi alerga doar prin unele dintre cele
cel mai frecvent utilizate cele.
Deci ab + este o urmată de orice N mai mare decât 0 din b.
AB? este o urmată de 0 sau 1 de b.
ab {N} este o urmată de N al b, și apoi așa mai departe.
Dacă aveți două numere în acolade sunteți specificarea unei game
care pot fi, eventual, potrivite.
Deci, ne vom uita mai mult la o modele repetitive cuplu într-un minut.
Deci, 2 lucruri de a păstra în minte atunci când se utilizează aceste instrumente model de potrivire aici.
Deci, spune că vrea să se uite la HM a, "Abraham Lincoln face sandwich-uri sunca."
Așa că am schimbat numele lui Abraham Lincoln la Avraam.
Și acum suntem în căutarea pentru ceea ce se întoarce de această funcție de căutare,
și returnează doar sunca în acest caz.
Și face asta, deoarece căutarea doar ia în mod natural cea mai mare coadă stânga.
Și toate expresiile regulate dacă nu specificați altfel va face asta.
Dacă ne-am dorit pentru a afla tot ce este o funcție pentru care - găsi tot.
Astfel că ar putea arata la fel ca toate = re.findall ('h.m ", text)
și apoi all.group ().
Toate produce atât sunca si sunca, în acest caz atât de siruri de caractere în Avraam fiecare Ham.
Astfel că este o altă opțiune.
>> Mare. Un alt lucru de a păstra în minte este că expresii regulate ia cea mai mare intuitiv.
Să ne uităm la acest exemplu.
Am făcut-o mai caută la stânga aici, și apoi am încercat o căutare mai mare
folosind operatorul Kleene stele.
Deci, pentru, "Abraham Lincoln face sandwich-uri sunca," și eu doar am întors
m ca rezultat.
Motivul pentru această greșeală a fost că am putut avea orice număr de
h din cauză că nu a specificat nimic pentru a merge în între h și m.
Singurul exemplu acolo care a avut m - singurele exemple acolo cu m în ea
precum și orice număr de lui h au fost doar șirul m.
Apoi am încercat din nou, i-am spus, "Bine, haideți să ne cel mai mare grup real aici."
Și apoi am făcut h.. * M, astfel încât doar întoarce orice număr de caractere între h și m.
Și dacă sunteți doar la început și de gândire, "Oh, da, ei bine acest lucru va
mă șuncă, "este nevoie de fapt, totul, de la h în Abraham Lincoln
tot drumul până la sfârșitul lui Ham.
Acesta este lacom, se vede h - tot acest alt text - m,
și că este ceea ce este nevoie de inch
Aceasta este o deosebit de extraordinar - aceasta este o caracteristică putem, de asemenea,
specificați pentru că nu fi lacom cu alte funcții.
Dar acest lucru este ceva ce trebuie să țină cont mai ales
atunci când se uită la text HTML, care este unul dintre motivele pentru care
expresii regulate sunt dificil pentru HTML.
Pentru că, dacă aveți o etichetă deschisă HTML și apoi o mulțime de lucruri în mijloc
și apoi un alt HTML închis tag-ul mult mai târziu în program,
tocmai ați mâncat o mulțime de cod HTML, eventual, din greșeală.
>> Bine - caractere speciale atât mai mult, la fel ca multe alte limbi,
vom scăpa folosind slash.
Deci, putem folosi punctul de a specifica orice caracter, cu excepția pentru o nouă linie.
Putem folosi evadare w pentru a specifica orice caracter alfabetic.
Și de evacuare d analogie pentru orice întreg - caractere numerice.
Putem specifica - putem folosi paranteze pentru a specifica expresii legate.
Deci, aceasta ar accepta o, b, c sau.
Și, de asemenea, putem specifica sau opțiuni, fie pentru a sau b.
De exemplu - dacă am fost în căutarea pentru mai multe posibilități de
în paranteze putem folosi operatorul sau in -
astfel încât să ne întoarcem la acest exemplu aici.
Și acum să ne ia - să ne întoarcem la acest exemplu aici, și apoi
ia AE - astfel încât aceasta ar trebui să se întoarcă - Cred că acest lucru este încă Avraam.
Deci, acest lucru -, dacă vom face tot - mare.
Așa că haideți să actualizeze textul aici.
"Avraam mănâncă șuncă în timp ce hemming lui -. În timp ce Hemming" Mare.
Toate. Mare. Acum avem sunca, sunca, și tiv.
În timp ce Hemming - în timp ce fredona la el - în timp ce fredona la tiv-l. Mare.
Același lucru.
Acum, totul se întoarce încă doar sunca, sunca, și tiv fără a ridica pe hum sau el.
Mare - Și ce dacă am vrut să se uite la nici că - așa am putea face, de asemenea,
el sau - vom reveni la asta.
Ok - deci - în regulă - în pozițiile puteți utiliza, de asemenea, caret sau semnul dolarului
pentru a specifica faptul că sunteți în căutarea pentru ceva la începutul sau la sfârșitul unui șir.
Sau la începutul sau la sfârșitul unui cuvânt.
Care este o modalitate de a folosi.
>> Ok - deci să ne jucăm cu un bloc puțin mai mare de text.
Să spunem că acest rând aici - această declarație aici.
Puterea de expresie regulată este faptul că acestea pot specifica modelelor
nu doar caractere fix.
Să facem - să ne numim acest bloc.
Apoi, vom citi toate că inch
Și apoi au o - să facem tot =; Deci, ce sunt unele lucruri pe care le-ar putea căuta aici profitabil?
Am putea uita pentru ureche expresie.
Nu este foarte interesant. Ce zici de asta? Vom vedea ce se întâmplă.
I-am dat o problemă.
Deci, orice număr de lucruri înainte de a re și toate.
Așa că ar trebui să se întoarcă totul de la început până la toate re, probabil, de câteva ori.
Și apoi aici, avem puterea de expresii regulate este că ei
pot specifica modele nu doar personaje de aici sunt.
Deci, tot drumul până la re finală, a început cu cea mai din stânga și a fost lacom.
Să vedem - ce altceva am putea cauta.
Cred că un singur lucru dacă ai fi interesat în căutarea pentru pronumele ea și el,
ai putea verifica e fiind egală cu 0 sau 1
și expresia el, și că nu este, probabil, va reveni -
Oh, cred că sa întors pentru că nu ne uitam la putere, în acea zi, aici sunt.
Să încercăm precizând că acest lucru trebuie să vină de la începutul a ceva.
Să vedem dacă scade.
Deci, putem face grăsime, și acolo nu vom primi nimic pentru ea și el
nu apar în această frază.
Mare. Ok - deci înapoi la pisica aici.
Modele atât de complex este doare creierul.
Deci, de aceea vom folosi expresii regulate pentru a evita aceste probleme.
>> Deci, aici sunt alte câteva moduri de utile pe care le puteți juca în jurul cu.
Ne-am uitat la căutare azi, dar se poate folosi, de asemenea meci, Split, findall, și grupuri.
Deci, alte lucruri interesante pe care le puteți face cu expresii regulate în afară de doar
în căutarea de modele este de a lua un model și deține toate meciurile -
variabilele sale - iar mai apoi folosind cele din codul mai târziu.
Care poate fi destul de util. Alte lucruri ar putea fi de numărare.
Deci, putem contoriza numărul de instanțe ale unui model de expresie regulată,
și că este ceea ce putem folosi pentru grupuri.
Și alte moduri, precum și sunt, de asemenea, posibile.
Deci, eu doar vreau să vorbesc un pic mai mult despre alte moduri de a folosi expresii regulate.
>> Deci, o cerere mai avansat este in potrivire neclare.
Deci, dacă sunteți în căutarea pentru un text de exprimare, Iulius Cezar,
și veți vedea fie Gaius Iulius Cezar sau numele de Iulius Cezar în alte limbi,
atunci ați putea dori, de asemenea, să atribuie unele greutate la aceste valori.
Și dacă aceasta este destul de aproape - în cazul în care se trece de un anumit prag - atunci vrei
să fie în măsură să accepte Julius Caesar.
Deci, există câteva implementări diferite, pentru că în câteva alte limbi.
Iată câteva alte instrumente, Regex Pal - o aplicatie la îndemână mic on-line la
verificați dacă expresii regulate sunt compuse corect.
Există, de asemenea, instrumente independente pe care le puteți rula de pe desktop
cum ar fi Ultra Pico, și precum și cărți de bucate doar.
Deci, dacă faci un proiect care implică o tona de expresii regulate
aceasta este, probabil, locul pentru a merge în afara domeniului de aplicare al azi.
Și apoi doar pentru a vă oferi un sentiment de modul în comun este
există grep în Unix, Perl a construit-in, iar C este PCRE pentru C.
Și apoi toate aceste limbi au, de asemenea, pachete regulate de expresie
care operează cu esență, aceeași sintaxă am primit un gust de azi.
PHP, Java, Ruby, și așa mai departe.
>> Google Code Search este de fapt demn de menționat, este unul din
relativ puține aplicații acolo care permite publicului să acceseze
baza sa de date folosind expresii regulate.
Deci, dacă te uiți pe Google Code Search puteți găsi codul de
dacă sunteți în căutarea pentru un exemplu de cum ar putea fi utilizată o funcție,
se poate utiliza o expresie regulată pentru a găsi că funcția de a fi folosite în tot felul de cazuri diferite.
Ai putea uita pentru fwrite, și apoi te puteai uita pentru steagul de scriere sau citire
dacă ai vrut un exemplu de fwrite fi utilizate în acest caz.
Deci, același lucru acolo, și aici sunt câteva referințe.
Acesta va fi disponibil on-line, precum și, deci merge înainte, dacă
vrei să te uiți la Python, grep, Perl - vrei doar pentru a obține unele inspirație
sau, dacă vrei să te uiți mai mult la teoria aici sunt câteva sărituri în afara terenului locuri.
Mulțumesc mult.
[CS50.TV]