[Powered by Google Translate] [Seminar: uzorak podudaranje s regularnim izrazima] [John Mussman-Sveučilište Harvard] [Ovo je CS50.-CS50.TV] Ok. Pa, svatko dobrodošao. Ovo je CS50 2012. Moje ime je Ivan, a ja ću se govori danas o regularnim izrazima. Regularni izrazi je prvenstveno alat, ali također ponekad se koristi u kodu aktivno bitno kako bi se slagala uzorke i žice. Dakle, ovdje je web strip iz xkcd. U ovaj strip je ubojstvo otajstvo gdje je ubojica ima slijedio nekoga na odmor, a protagonisti moraju pretraživanje 200 megabajta poruke e-pošte u potrazi za adresom. I oni su o tome da se kada netko tko zna regularnih izraza - vjerojatno superjunak - swoops dolje i piše neki kod i rješava ubojstvu. Pa vjerojatno da će biti nešto što će biti ovlašten učiniti Nakon ovog seminara. Mi samo će dati sažeti uvod u jeziku i dati vam dovoljno novac za otići nakon više sredstava na svom. 

Dakle, regularni izrazi izgleda ovako osnovi. To je uobičajeni izraz u Ruby. To nije strašno razlikuju po jezicima. Imamo samo na crtama početi i označiti uobičajeni izraz u Ruby. A to je uobičajeni izraz tražiti u e-mail adresa uzorak. Dakle, vidimo na prvi malo izgleda za bilo koji alfanumerički. To je zato što e-mail adrese se često morati početi s abecednim karaktera. I onda neki poseban lik slijedi simbola @. A onda ista stvar za domene. A onda je između 2 i 4 znaka tražiti. Com,. Net, i tako dalje. Dakle, to je još jedan primjer regularnog izraza. Dakle, regularni izrazi su protokoli za pronalaženje obrazaca u tekstu. Oni su to usporedbe, izbore, i zamjene. Dakle Treći primjer je pronalaženje sve brojeve telefona koje završavaju s 54 u imeniku. Dakle, prije nego što David rips up CS50 direktorij smo mogli potražiti Uzorak u kojem imamo zagrade onda 3 broja onda kraj zagradu, Još 3 broja, crtica, 2 broja, a zatim 54. I to bi bilo bitno kako ćemo se s regularni izraz za pretraživanje da. 

Dakle, tu su - mi smo učinili neke stvari u CS50 da su malo kao što je regularni izrazi, tako da - primjerice - u dictionary.C datoteku za provjeru pravopisa set problema možda ste fscanf čitati u riječi iz rječnika. A možete vidjeti postotak 45s je u potrazi za niz od 45 znakova. Dakle, to je nešto kao rudimentaran regularnog izraza. I možete imati bilo 45 znakova da stane račun unutra i pokupiti one do. I onda drugi primjer u najnovijem web programiranja postavljena u distro kod za PHP zapravo imamo jednostavan regularni izraz. I ovaj je jednostavno u potrazi za provjeru je li web stranica koja se donosi u odgovara ni prijavite se ili se registrirajte odjaviti. PHP. A onda se vraćaju true ili false temelju tog regularnog izraza podudaranja. 

Dakle, kada ne koristite uobičajeni izraz? Zašto ste danas ovdje? Tako da ne želite koristiti regularni izraz kada postoji nešto što obavlja posao za vas, čak i lakše. Dakle, XML i HTML su zapravo prilično zahtjevno napisati regularne izraze za što ćemo vidjeti u malo. Dakle, postoje posvećena parsera za tim jezicima. Također morate biti u redu s trgovinskom off i točnost često. Ako pokušavate - kako smo vidjeli regularni izraz za e-mail adresu, ali kažu da ste htjeli određenu e-mail adresu i postupno regularni izraz mogao postati još složeniji jer je postao precizniji. Tako da će biti jedan trgovina off. Morate biti sigurni da ste dobro čine s regularni izraz. Ako znate točno ono što tražite to može učiniti više smisla staviti u vrijeme i napisati učinkovitiju parser. I na kraju tu je povijesno pitanje s pravilnosti izraza i jezika. Regularni izrazi su zapravo mnogo snažnije od Regularni izrazi po kažu u formalnom smislu. 

Dakle, ja ne želim ići predaleko u formalnom teorijom, ali većina jezici koji smo kod u zapravo nisu redoviti. I to je razlog zašto regularni izrazi ponekad ne smatraju svi da je siguran. Tako je u osnovi postoji hijerarhija Chomsky za jezike, i regularni izrazi su izgraditi korištenjem uniju, ulančavanje, i rad Kleene zvijezda koje ćemo vidjeti u nekoliko minuta. Ako ste zainteresirani u teoriji postoji dosta tamo događa ispod haube. 

Dakle kratku povijest - samo za kontekstu ovdje - redovni seta došao do u 1950, a zatim smo imali jednostavne urednika da uključene regularne izraze - samo u potrazi za gudače. Grep - što je alat naredbenog retka - bio je jedan od prvih Vrlo popularni alat koji ugrađeni regularnih izraza u 1960. U 80-tih, Perl sagrađena - je programski jezik koji uključuje uobičajene izraze vrlo istaknut. A onda je u novije vrijeme imali smo Perl kompatibilan regularni izraz Protokoli u osnovi na drugim jezicima koje koriste puno od iste sintakse. Naravno, najvažniji događaj bio je u 2008 tamo gdje je bio prvi Nacionalni dan regularne izraze, što vjerujem da je 1. lipnja, ako želite slaviti. 

Opet, samo malo više teorija ovdje. Dakle, postoji nekoliko različitih načina gradnje regularnih izraza. Jedan jednostavan način je da se izgradi izraz koji ćete pokrenuti na niz tumače - osnovi graditi malo mini-program koji će analizirati komada nizu i vidjeti, "Oh, to stane regularni izraz ili ne?" I onda pokrenuti to. Dakle, ako imate vrlo mali regularni izraz, to je vjerojatno Najučinkovitiji način da to učinite. A onda, ako vas - još jedna mogućnost je da bi rekonstruirati Izraz kao što ide, a to je mogućnost da simuliraju. A ovi rani pokušaji bili regularni izraz algoritama relativno jednostavan i relativno brzo, ali nije imala puno fleksibilnosti. Dakle, učiniti čak i neke od stvari koje ćemo gledati na Danas smo morali napraviti složeniji regularni izraz implementacije koji su potencijalno puno sporije, tako da je nešto imati na umu Tu je i redoviti izraze poricanje napada raznih da iskoriste potencijal za ovim novijim implementacijama Regularni izrazi postati vrlo složen. I na isti način kako smo vidjeli u buffer overflow napada, imate napade koji rade po izradi rekurzivne petlje da prekoračenje kapacitet memorije. I usput Regexen je jedan od službenih množine u regularnom izrazu Analogijom volova u anglosaksonskom. 

Ok, tako da Python knjižnica mnogi od vas ovdje osobno ima Macove, tako da zapravo možete povući ovaj gore na zaslonu. Regularni izrazi su ugrađeni u Pythonu. I tako Python je predinstaliran na Macovima i također dostupan online na ovom linku. Dakle, ako gledate možete pauzirati i provjerite imate li Python što ćemo igrati ovdje. Postoji upotrebu online, tako da ako samo upišite Python u računalo vidjet ćete da je verzija dolazi u terminalu. Tako sam pod uvjetom link na priručniku za Verziju 2. Python, kao i varati list. Postoji verzija 3 Python, ali vaš Mac ne nužno dolaze predinstalirane s tim. Dakle, nije strašno razlikuju. Ok, tako da neke osnove koristeći regularne izraze u Pythonu. 

Dakle, ovdje sam koristio vrlo jednostavan izraz, pa mi je Python uvoz re , a zatim je rezultat re.search. I traži traje 2 argumente. Prvi je regularni izraz, a drugi je tekst string ili želite analizirati. A onda sam isprintati na result.group. Dakle, to su dvije osnovne funkcije ćemo vidjeti danas u učenju o regularnim izrazima. Dakle, samo što se razbije to uobičajeni izraz ovdje h, a zatim \ w a zatim m kako \ w jednostavno prihvati bilo slovo tamo. Dakle ovdje smo u potrazi za "h", a zatim još jedan abecedni znak a zatim m, pa evo da bi se slagala pršut u, "Abraham Lincoln i pršut sendviči." To je rezultat toj skupini. Još jedna stvar koju možemo učiniti je koristiti naše prije nizove teksta u Pythonu. Dakle, mislim da ću ići naprijed i povući da se ovdje. Python uvoz ponovno. I ako bih napraviti istu stvar - recimo tekst, "Abraham," neka nam uvećali - tamo idemo. Tekst je, "Abraham jede šunku." Ok, a zatim dovesti = re.search. I onda naš izraz može biti h, a onda ću napraviti dot metara. Dakle dot traje samo bilo znak koji nije nova linija, uključujući brojeve, postotnih znakovi, bilo što slično. I onda tekst - bum - i onda result.group--Da. Dakle, to je samo kako provesti osnovnu funkcionalnost ovdje. Ako smo imali taj tekst prsten - da je luda teksta - uključeno kažu puno kose crte i žice unutar i stvari koje bi mogle izgledati kao izlazni nizovi, onda vjerojatno želite koristiti sirovu unos teksta kako bi bili sigurni da je prihvaćen. I to samo izgleda kao da je. Dakle, ako smo bili u potrazi za svaku od njih tamo ne bismo trebali naći ništa. No, to je način na koji će to provesti, neposredno prije niz regularni izraz stavite slovo R. 

Ok, pa neka nas zadržati ide. U redu - pa pogledajmo nekoliko ponavljaju obrasce ovdje. Dakle, jedna stvar koju želite učiniti je ponavljati stvari kao da ste u potrazi kroz tekst. Tako da to slijedi bilo koji broj b - što učiniti ab *. A onda postoji niz drugih pravila previše. A možete gledati sve ove gore, samo ću pokrenuti kroz neke od Najčešće korišteni sebe. Tako ab + je zatim bilo N veći od 0 od b. ab? je zatim 0 ili 1. b. ab {N} je slijedi N iz B i tako dalje. Ako imate 2 brojeve u vitičastim zagradama ste navodeći niz koji se može eventualno odgovara. Tako ćemo pogledati još na par ponavljaju obrasce u minutu. Dakle, dvije stvari koje trebate imati na umu prilikom korištenja ove uzorak podudaranja alate ovdje. Tako kažu želimo gledati na hm za "Abraham Lincoln napravio sendviče sa šunkom." Tako sam promijenio Abrahama Lincolna ime Abrahamu. I sad smo u potrazi za ono što se vratio ovim funkciju pretraživanja, i to samo vraća pršut u ovom slučaju. I to ne zato da traži jednostavno prirodno vodi lijevu najviše red. I sve uobičajene izraze, osim ako nije drukčije će to učiniti. Ako smo željeli pronaći sve postoji funkcija za to - naći sve. Dakle, samo da bi mogao izgledati sve = re.findall ('h.m', tekst) a zatim all.group (). Svi proizvodi i pršut i šunku, u tom slučaju obje žice u svakom Abrahama šunke. Dakle, to je još jedna mogućnost. 

Izvrsno. Druga stvar koju treba imati na umu je da regularni izrazi se najveći intuitivno. Neka nam pogled na ovom primjeru. Napravili smo tu lijevu najviše potragu ovdje, a onda sam pokušao veći pretragu pomoću Kleene zvijezda operatera. Tako je za "Abraham Lincoln napravio sendviče sa šunkom," a ja sam samo dobio natrag m kao rezultat. Razlog za to je pogreška bila što sam mogao uzeti bilo koji broj h je zato što nisam ništa specificirati da ide u između H, M. Jedini primjer koji je imao tu m - jedini primjeri tamo s m u njemu i bilo koji broj H bili samo string m. Tada sam ga ponovno pokušao, rekao sam: "Dobro, neka nam se stvarni najveću skupinu ovdje." A onda sam h. * M, tako da je samo bilo koji vraća broj znakova između H, M. A ako ste tek počinje out i razmišljanja, "Oh, ok, ali to će daj mi pršut, "to je zapravo sve što se iz sata u Abraham Lincoln pa sve do kraja šunke. To je pohlepna, ona vidi h - sve je to drugi tekst - m, i to je ono što je potrebno rezervirati To je posebno nečuven - to je značajka možemo također navesti za to ne biti pohlepan pomoću druge funkcije. No, to je nešto što moramo imati na umu posebno kada se gleda na HTML tekst, što je jedan od razloga da Regularni izrazi su teško za HTML. Jer ako imate otvorenu HTML oznake i onda puno stvari u sredini a onda neka druga HTML zatvorena oznaku mnogo kasnije u programu, ste upravo pojeli puno HTML koda eventualno greškom. 

Sva prava - tako da više posebnih znakova, kao i mnogim drugim jezicima, možemo pobjeći pomoću crtu. Dakle, možemo koristiti točku navesti bilo koji znak osim za novu liniju. Možemo koristiti w bijeg navesti bilo slovo. A po analogiji bijega d za svaki cijeli broj - brojčana znakova. Možemo navesti - možemo koristiti zagrade navesti srodne izraze. Dakle, to će prihvatiti a, b, ili c. I mi također može odrediti ili opcije za bilo A ili B. Na primjer - ako smo u potrazi za više mogućnosti u zagradama smo mogli koristiti ili operatera kao u - pa neka nam se vratiti na ovaj primjer ovdje. I sada uzmimo - vratimo se na ovaj primjer ovdje, a zatim potrajati AE - pa to bi se trebali vratiti - Mislim da je to još uvijek Abraham. Dakle, to - ako smo učiniti sve - super. Pa neka nam ažurirati tekst ovdje. "Abraham jede šunku, a njegov rubljenja -. Dok Hemming" Izvrsno. Sve. Izvrsno. Sada smo dobili pršut, šunka, i skuta. Dok Hemming - zuji dok mu - dok je pjevušio s njim kašljucati. Izvrsno. Ista stvar. Sada sve se vraća još uvijek samo šunka, šunka, i rub bez dizanja na Hum ili na njega. Sjajno - Pa što ako smo htjeli gledati na bilo koji - kako bismo mogli napraviti njega ili - mi ćemo se vratiti na to. Ok - tako da - sve u redu - na mjestima također možete koristiti znak za umetanje ili znak dolara navesti da ste u potrazi za nečim na početku ili na kraju niza. Ili početak ili kraj riječi. To je jedan način da se to koristiti. 

Ok - pa neka nam se poigrati s nešto većim blok teksta. Recimo ovaj redak ovdje - ovu izjavu ovdje. Snaga regularnog izraza je da oni mogu odrediti obrasce ne samo fiksne znakove. Učinimo - nazovimo ovaj blok. Onda ćemo čitati sve to u. I onda su - da nas čine sve =, tako što su neke stvari koje smo mogli tražiti ovdje profitabilno? Mogli bismo tražiti izraz uho. Nije vrlo zanimljiva. Kako o tome? Vidjet ćemo što će se dogoditi. Dao sam ga problem. Dakle, bilo koji broj stvari prije ponovnog i sve. Tako da bi trebao vratiti sve, od početka do svih istraživanja možda par puta. I onda ovdje imamo moć regularnih izraza je da oni Možete odrediti obrasce ne samo likovi su ovdje. Dakle, sve do konačnog ponovnog, počeo je s lijeve strane, a najviše je pohlepni. Neka nam vidjeti - što još možemo tražiti. Valjda jednu stvar, ako ste bili zainteresirani u potrazi za zamjenice ona i on, možete provjeriti i biti jednak 0 ili 1 , a izraz je, a to vjerojatno neće vratiti - Oh, mislim da se vratio jer mi se gleda na snagu, taj dan, ovdje su. Pokušajmo navodeći da mora doći na početku nečega. Neka nam vidjeti ako to padne off. Dakle, što možemo učiniti masnoća, a ne dobivamo ništa, jer je i on se ne javljaju u tom izrazu. Izvrsno. Ok - pa natrag na mačka ovdje. Dakle kompliciraniji način je ranjavanje mozak. Dakle, to je razlog zašto mi koristimo uobičajene izraze kako bi izbjegli ove probleme. 

Dakle, ovdje su neke druge korisne načina možete poigrati s. Mi smo gledali na traženju i danas, ali također može koristiti meča, Split, findall, i grupe. Dakle druge cool stvari koje možete učiniti s regularnim izrazima osim samo u potrazi za uzorke uzima uzorak i drži sve utakmice - njegove varijable - a zatim pomoću onih u kodu kasnije. To može biti vrlo korisno. Ostale stvari koje se mogu brojati. Dakle, možemo računati broj instanci regularni izraz uzorak, a to je ono što možemo koristiti grupe za. I drugi načini, kao dobro su moguće. Dakle, ja samo želim govoriti malo više o drugim načinima na koje možete koristiti regularne izraze. 

Dakle, još jedan napredni program je fuzzy podudaranja. Dakle, ako ste u potrazi za tekst za izražavanje, Julije Cezar, a vidiš ni Gaj Julije Cezar ili ime Julije Cezar u drugim jezicima, onda možda želite dodijeliti neku težinu tim vrijednostima. A ako je dovoljno blizu - ako se prijeđe određeni prag - onda želite biti u mogućnosti prihvatiti Julija Cezara. Dakle, postoji nekoliko različitih implementacija za to u nekoliko drugih jezika, kao dobro. Ovdje su neke druge alate, Regex Pal - zgodan mali app za on-line provjeriti da li su vaše uobičajene izraze sastoji ispravno. Tu su i samostalne alate koje možete pokrenuti na računalu kao što su Ultra Pico, i kao i samo kuharica. Dakle, ako se radi projekt koji uključuje tonu regularnim izrazima ovo je vjerojatno mjesto za izlazak izvan dosega danas. I onda samo dati vam osjećaj kako je zajednička postoji u Unix grep, Perl ima izgrađen-in, a C je pcre za C. A onda svi ti drugi jezici imaju redovite izraz pakete koji rade s gotovo isti sintaksu smo dobili okus danas. PHP, Java, Ruby, i tako dalje. 

Google Code Search je zapravo vrijedno spomena, to je jedan od relativno mali broj aplikacija vani koji omogućuje javnosti za pristup Njegova baza podataka pomoću regularnih izraza. Dakle, ako pogledate na Google Code Search možete pronaći kod Ako ste u potrazi za primjer kako se funkcija može se koristiti, možete koristiti uobičajeni izraz pronaći tu funkciju koja se koristi u svim vrstama različitih slučajeva. Ti bi mogao tražiti fwrite, a onda ste mogli tražiti zastavom pisati ili čitati ako ste htjeli primjer fwrite se koristi u tom slučaju. Dakle, ista stvar postoji, a ovdje su neke reference. To će biti dostupan online, kao i, tako da ide prema naprijed, ako želite gledati na Python, Perl, grep - samo želite da biste dobili neke inspiracije ili ako želite pogledati više na teoriji ovdje su neke dobre jumping off mjesta. Puno hvala. [CS50.TV]