[Powered by Google Translate] [Seminaari: Pattern Matching säännöllisiä lausekkeita] [John Mussman-Harvard University] [Tämä on CS50.-CS50.TV] Okei. No, tervetuloa kaikille. Tämä on CS50 2012. Nimeni on John, ja aion puhua tänään säännöllisiä lausekkeita. Säännölliset lausekkeet on ensisijaisesti väline, mutta myös joskus käytetään koodin aktiivisesti lähinnä vastaamaan malleja ja jousille. Joten tässä on web sarjakuva päässä xkcd. Tässä sarjakuva on murhamysteeri, jossa tappaja on jälkeen joku lomalla, ja päähenkilöt on etsiä 200 megatavua sähköposteja etsivät osoite. Ja he ovat aikeissa luopua, kun joku, joka tietää säännöllisiä lausekkeita - oletettavasti supersankari - swoops alas ja kirjoittaa koodia ja ratkaisee murha mysteeri. Niin todennäköisesti se, että on jotain, että sinulla on valtuudet tehdä tämän jälkeen seminaarin. Olemme juuri menossa antaa tiivis johdatus kielen ja antaa sinulle tarpeeksi keinot mennä sen jälkeen enemmän resursseja itse. 

Joten säännöllisiä lausekkeita näyttää pohjimmiltaan kuin tämä. Tämä on säännöllinen lauseke Ruby. Se ei ole kovin erilainen eri kielillä. Meillä on juuri viiltää alkaa ja merkitse säännöllisen lausekkeen Ruby. Ja tämä on säännöllinen lauseke etsiä sähköpostiosoitteesi kuvio. Joten näemme ensimmäisen bitin etsii aakkosnumeerisia merkkejä. Tämä johtuu sähköpostiosoitteet usein aloittaa kirjaimesta. Ja sitten kaikki erikoismerkin jälkeen @-merkkiä. Ja sitten sama asia verkkotunnus. Ja sitten välillä 2 ja 4 merkkiä etsiä. Com,. Net, ja niin edelleen. Niin, että on toinen esimerkki säännöllinen lauseke. Joten säännöllisiä lausekkeita ovat protokollia löytää hahmoissa tekstiä. He tekevät vertailuja, valintoja, ja vaihdot. Joten Kolmas esimerkki on löytää kaikki puhelinnumerot päättyy 54 hakemistoon. Joten ennen David repi CS50 hakemistoon voisimme etsiä kuvio, jossa meillä on suluissa sitten 3 numeroa sitten lopulta suluissa 3 enemmän numeroita, viiva, 2 numeroa, ja sitten 54. Ja se olisi lähinnä siitä, kuinka keksimme säännöllinen lauseke etsiä sitä. 

Joten on - olemme tehneet joitakin asioita CS50, jotka ovat vähän kuin säännöllisiä lausekkeita, niin - esimerkiksi - in dictionary.C tiedosto ja oikeinkirjoituksen tarkistus Harjoitus olet saattanut käyttää fscanf lukea sanan sanakirjasta. Ja voit nähdä prosenttiosuus 45s etsii merkkijono on 45 merkkiä. Joten se on hieman kuin alkeellinen säännöllinen lauseke. Ja voit olla mitä tahansa 45 merkkiä, jotka sopivat laskun siellä ja poimia ne ylös. Ja sitten toinen esimerkki viimeisimmän web ohjelmointi ongelma asetettu distro koodi php emme oikeastaan ​​on yksinkertainen säännöllinen lauseke. Ja tämä on vain yksinkertaisesti haluavat tarkistaa, jos Web-sivu, joka on läpäissyt vastaa joko kirjaudutaan sisään tai ulos Rekisteröidy. PHP. Ja palaavat sitten tosi tai epätosi perusteella, että säännöllisten lausekkeiden haku. 

Joten kun käytät säännöllinen lauseke? Miksi olet täällä tänään? Joten et halua käyttää säännöllisiä lausekkeita, kun siellä on jotain, joka tekee työtä sinulle vieläkin helpommin. Joten XML ja HTML ovat oikeastaan ​​aika hankala kirjoittaa säännöllisiä lausekkeita niin tulemme näkemään hieman. Joten on omistettu jäsentimiä niistä kielistä. Sinun on myös oltava kunnossa kompromisseista ja tarkkuus säännöllisesti. Jos yrität - niin näimme säännöllinen lauseke sähköpostiosoite, mutta sanovat halusi tiettyyn sähköpostiosoitteeseen ja vähitellen säännöllinen lauseke voi tulla monimutkaisempi kuin se tarkentui. Niin että olisi yksi kauppa pois. Sinun täytyy olla varma, että olet kunnossa päätöksentekoa säännöllinen lauseke. Jos tiedät tarkalleen mitä olet etsimässä sitä olla järkevää laittaa aikaa ja kirjoittaa tehokkaampaa jäsennin. Ja lopuksi on historiallinen ongelma säännöllisyys ilmaisujen ja kielet. Säännölliset lausekkeet ovat todella paljon tehokkaampia kuin säännöllisiä lausekkeita per sanoa muodollisesti. 

Joten en halua mennä liian pitkälle virallista teoriaa, mutta useimmilla kielillä, että koodia todellisuudessa eivät ole säännöllisiä. Ja siksi säännöllisiä lausekkeita joskus ei katsota kaikki turvallista. Joten periaatteessa on Chomskyn kielten, ja säännöllisiä lausekkeita on rakentaa käyttämällä liitto, ketjuttamista, ja Kleenen tähden toimintaa että näemme muutaman minuutin. Jos olet kiinnostunut teoriassa on aika paljon siellä tapahtuu konepellin alle. 

Joten lyhyt historia - vain yhteydessä täällä - säännöllinen sarjaa tuli vuonna 1950, ja sen jälkeen meillä oli yksinkertainen toimittajat, jotka sisällytetään säännöllisiä lausekkeita - vain etsivät jousille. Grep - joka on komentorivi työkalu - oli yksi ensimmäisistä hyvin suosittuja työkaluja, jotka sisällytetään säännöllisiä lausekkeita 1960. 80-luvulla, Perl on rakennettu - on ohjelmointikieli, joka sisältää säännöllisiä lausekkeita vähälle. Ja sitten viime aikoina meillä on ollut Perl-yhteensopiva säännöllisten lausekkeiden pöytäkirjojen periaatteessa muilla kielillä, jotka käyttävät paljon samaa syntaksia. Tietenkin tärkein tapahtuma oli vuonna 2008 jossa oli ensimmäinen National Regular Expressions Day, joka mielestäni on kesäkuu 1, jos haluat juhlia sitä. 

Jälleen vain hieman teoriaa täällä. Joten on olemassa pari eri tapoja rakentaa säännöllisiä lausekkeita. Yksi tapa on rakentaa lauseke aiot ajaa merkkijono tulkita - periaatteessa rakentaa pieni mini-ohjelma, joka analysoi paloja merkkijono ja nähdä, "Voi, tämä sopii säännöllinen lauseke vai ei?" Ja sitten ajaa sitä. Joten jos sinulla on hyvin pieni säännöllinen lauseke, tämä on luultavasti tehokkain tapa tehdä se. Ja sitten jos - toinen vaihtoehto on pitää jälleenrakentamista ilmaisun kuten mennä, ja että on simuloida mahdollisuus. Ja nämä Ensimmäisissä säännöllinen lauseke algoritmit suhteellisen yksinkertainen ja suhteellisen nopeasti, mutta ei ole paljon joustavuutta. Joten tehdä vielä joitakin asioita, että olemme menossa katsomaan Tänään olemme joutuneet tekemään monimutkaisempia säännöllinen lauseke toteutukset ovat potentiaalisesti paljon hitaampi, niin että on jotain mielessä Mukana on myös säännöllisiä lausekkeita kieltäminen hyökkäys erilaisia että hyödynnetään näitä uudempia toteutuksia säännöllisiä lausekkeita tulla hyvin monimutkainen. Ja paljon samassa mielessä kuin näimme puskurin ylivuoto hyökkäyksiä, sinulla on hyökkäyksiä, jotka toimivat tekemällä rekursiivinen silmukoita ylitys kapasiteetti muistia. Ja muuten Regexen on yksi virallisista taivutusmuodot säännöllisen lausekkeen vastaavasti härkien anglosaksisen. 

Okei, joten Python kirjasto monet teistä täällä henkilö on Macit, joten voit itse vetää tämän ylös näytön. Säännölliset lausekkeet on rakennettu Python. Ja niin Python on esiasennettu Mac ja myös verkossa tästä linkistä. Joten jos olet katsomassa voit keskeyttää ja varmista, että sinulla on Python niin soitamme täällä. On käsikirja verkossa, joten jos vain kirjoittaa Python tietokoneeseen huomaatte, että versio tulee esille terminaaliin. Olen siis jos linkki käsikirjan versio 2 Python sekä lunttilappua. On Version 3 Python, mutta Mac ei välttämättä mukana, että esiasennettu. Joten ei ole kovin erilainen. Okei, joten joitakin perusasioita käyttäen säännöllisiä lausekkeita Python. 

Joten tässä käytin hyvin yksinkertainen ilme, joten tein Python tuonti uudelleen ja sitten otti tulos re.search. Ja haku kestää 2 argumentteja. Ensimmäinen on säännöllinen lauseke, ja toinen on teksti tai merkkijono haluat analysoida. Ja sitten tulostaa result.group. Nämä ovat siis 2 perustoiminnot aiomme nähdä tänään oppimaan säännöllisiä lausekkeita. Joten Jakaessaan säännöllinen lauseke täällä h ja sitten \ w ja m niin \ w vain ottaa mitään kirjainmerkki siellä. Joten tässä etsimme "h" ja sitten toinen kirjainmerkki ja sitten m, joten tässä että sopisi kinkkua in, "Abraham Lincoln ja kinkkua voileipiä." Tämä on seurausta kyseisen ryhmän. Toinen asia, että voimme tehdä, on käyttää ennen jouset tekstiä Python. Joten kai aion mennä eteenpäin ja vedä, että täällä. Python tuonti uudelleen. Ja jos tekisin saman - sanokaamme teksti on, "Abraham," meidän suurentaa - sinne siis. Teksti on "Abraham syö kinkkua." Okei, ja sitten tulos = re.search. Ja sitten meidän ilmaisu voi olla h, ja niin aion tehdä piste m. Joten piste vie tahansa merkki, joka ei ole uuden linjan mukaan lukien lukumäärät, prosenttiosuus merkkejä, jotain sellaista. Ja sitten teksti - puomi - ja sitten result.group--joo. Niin, että on kuinka tehdä perus-toiminnallisuus täällä. Jos meillä olisi teksti rengas, joka - se hullu teksti - mukana sanoa paljon takaisin viiltää ja jousille sisällä ja asioita, jotka voisi näyttää tilanvaihdot, sitten luultavasti halua käyttää raaka tekstinsyöttöä varmistaa, että hyväksytään. Ja se vain näyttää, että. Joten jos etsimme kullekin niistä on meidän ei pitäisi löytyä mitään. Mutta se on miten sen toteuttaisi, juuri ennen merkkijono säännöllinen lauseke laitat r-kirjain. 

Okei, joten meidän pitää käynnissä. Okei - niin Katsokaamme pari toistuvia kuvioita täällä. Niin yksi asia, jonka haluat tehdä, on toistaa asioita kun etsivät tekstin läpi. Joten tehdä seuraa niin monta b - teet ab *. Ja sitten on joukko muita sääntöjä liikaa. Ja voit katsoa kaikki nämä ylös, minä vain ajaa läpi joitakin yleisimmin käytetty niistä. Joten ab + on seuraa mitään N suurempi kuin 0 b. ab? on sen jälkeen 0 tai 1 b. ab {N} on sen jälkeen N b, jälkeen ja niin edelleen. Jos sinulla on 2 numeroa aaltosulkeiden olet määritellään alue joka voi olla mahdollisesti sovitettu. Joten me tarkastelemme enemmän pari toistuvia kuvioita minuutin. Joten 2 asioita pitää mielessä, kun käytät näitä kaavoja työkaluja täällä. Joten sanoa haluamme tarkastella HM, "Abraham Lincoln tekee kinkkua voileipiä." Joten vaihdoin Abraham Lincolnin nimen Abraham. Ja nyt etsimme mitä palautetaan tämän hakutoiminto, ja se palauttaa vain kinkkua tässä tapauksessa. Ja se, että koska haku vain luonnollisesti vie eniten vasemmalla jono. Ja kaikki säännöllisiä lausekkeita ellet muuta tekee sen. Jos halusimme löytää kaikki on toiminto, joka - löytää kaikki. Niin, että voisi vain näyttää kaikki = re.findall (h.m ", teksti) ja sitten all.group (). Kaikki tuottaa sekä kinkkua ja kinkkua, tässä tapauksessa molemmat jousille Abraham kunkin kinkkua. Niin, että on toinen vaihtoehto. 

Suuri. Toinen asia pitää mielessä on, että säännöllisiä lausekkeita ottaa suurin intuitiivisesti. Katsokaamme tätä esimerkkiä. Teimme että eniten vasemmalla täältä, ja sitten yritin suurempi haku käyttäen Kleenen tähden operaattori. Joten, "Abraham Lincoln tekee kinkkua voileipiä," ja minä vain sai takaisin m seurauksena. Syynä tähän virhe oli, että olisin voinut ottaa minkä tahansa määrän h on koska en määritä mitään mennä välillä h ja m. Ainoa esimerkki on, että oli m - vain esimerkkejä siellä m sen ja rajoittamattoman määrän h: n oli vain merkkijono m. Sitten yritin uudestaan, sanoin, "Okei, jatkakaamme todellinen suurin ryhmä täällä." Ja sitten tein h.. * M, joten palaa aivan mitä tahansa merkkejä välillä h ja m. Ja jos olet lähtemässä pois ja ajatella, "Oh, okei, hyvin tämä saada minut kinkkua, "se todella vie kaiken h Abraham Lincoln kaikki tavalla jopa loppuun kinkkua. Se on ahne, se näkee h - kaikki tämä muu teksti - m, ja että on mitä se tekee sisään Tämä on erityisen törkeä - tämä on ominaisuus voimme myös täsmennettävä se ei ole ahne käyttää muita toimintoja. Mutta tämä on jotain meidän on pidettävä mielessä erityisesti kun tarkastellaan HTML tekstiä, mikä on yksi syy, että säännöllisiä lausekkeita ovat vaikeita HTML. Koska jos sinulla on HTML avoin koodi ja sitten paljon tavaraa keskellä ja sitten jotkut muut HTML suljettu tag paljon myöhemmin ohjelmassa, olet juuri syönyt paljon html-koodiin mahdollisesti vahingossa. 

Okei - niin enemmän erikoismerkkejä, kuten monet muut kielet, me voimme päästä pakoon käyttäen slash. Joten voimme käyttää piste määrittää minkä tahansa merkin paitsi uuden linjan. Voimme käyttää paeta w mahdolliset kirjainmerkki. Ja vastaavasti paeta d tahansa kokonaisluku - numeerinen luonnetta. Voimme määritellä - voimme käyttää suluissa määrittää liittyviä ilmaisuja. Joten tämä hyväksyisi, b tai c. Ja voimme myös määrittää tai vaihtoehtoja joko a tai b. Esimerkiksi - jos etsimme useita mahdollisuuksia Suluissa voisimme käyttää tai operaattori kuten - joten palatkaamme tähän esimerkki tästä. Ja nyt ottakaamme - palatkaamme tähän esimerkki tästä, ja sitten ottaa ae - niin tämän pitäisi palata - Kai tämä on vielä Abraham. Joten tämä - jos teemme kaiken - suuri. Olkaamme siis päivittää tekstiä täällä. "Abraham syö kinkkua kun Hemming hänen - kun Hemming." Suuri. Kaikki. Suuri. Nyt saamme kinkkua, kinkkua, ja helmassa. Vaikka hemming - vaikka hyräillä hänelle - vaikka hyräillä helmaan häntä. Suuri. Sama juttu. Nyt kaikki palaa edelleen vain kinkkua, kinkkua, ja helmassa ilman poimien humina tai häntä. Suuri - niin mitä jos halusimme katsoa, ​​että joko - jotta voisimme myös tehdä häntä tai - palaamme siihen. Okei - niin - kaikki hyvin - tehtävissä voit käyttää myös järjestelmäkohdistimen tai dollarin merkki täsmentää, että etsit jotain alussa tai lopussa merkkijono. Tai alussa tai lopussa sanan. Tämä on yksi tapa käyttää sitä. 

Okei - niin olkaamme leikkiä hieman suurempi tekstialue. Sanokaamme tämä rivi täällä - tämä lausuma täällä. Voima säännöllinen lauseke on, että ne voidaan määrittää malleja ei vain kiinteä merkkiä. Tehkäämme - kutsukaamme tämän lohkon. Silloin saamme lukea kaikki, että sisään Ja sitten on - tehkäämme kaikki =, niin mitkä ovat asioita, että voisimme etsiä täällä kannattavasti? Voisimme etsiä ilmaisua korvaan. Ei kovin mielenkiintoinen. Miten olisi? Saa nähdä mitä tapahtuu. Annoin sen ongelma. Joten mikä tahansa joukko asioita ennen uudelleen ja kaikki. Niin, että pitäisi palata kaiken alusta asti kaikki uudelleen ehkä pari kertaa. Ja sitten täällä on voima säännöllisiä lausekkeita on, että ne voidaan määrittää malleja ei vain merkkejä tästä ovat. Joten kaikki tavalla jopa lopulliseen uudelleen, se alkoi vasemmalta eniten ja oli ahne. Katsokaamme - mitä muuta voisimme etsiä. Oletan, yksi asia, jos olisit kiinnostunut etsivät pronominit hän ja hän, voisit tarkistaa s on 0 tai 1. ja ilmaisun hän, ja se on todennäköisesti aio palata - oh, kai se palasi hän koska etsimme voima, joka päivä, täällä. Pyrkikäämme täsmensi, että tämän on tultava alussa jotain. Katsokaamme, jos putoaa. Joten voimme tehdä rasvaa, ja siellä emme saa mitään, koska hän ja hän eivät esiinny tämän lauseen. Suuri. Okei - niin takaisin kissa täällä. Niin monimutkaisia ​​kuvioita vahingoittaa aivoja. Joten siksi käytämme säännöllisiä lausekkeita välttää näitä kysymyksiä. 

Joten tässä on joitakin muita hyödyllisiä tiloja voit leikkiä. Me katsoimme haku tänään, mutta voit käyttää myös ottelu, split, findall, ja ryhmät. Joten muita hienoja asioita voit tehdä säännöllisiä lausekkeita lisäksi vain etsivät malleja on ryhtynyt kuvio ja pitämällä kaikki ottelut - muuttujat - ja sitten käyttää niitä oman koodin myöhemmin. Se voi olla varsin hyödyllistä. Muut asiat saattavat laskea. Joten voimme luottaa määrän kopioita mainittu merkkijono, ja sitähän voimme käyttää ryhmiä. Ja muut tilat sekä ovat myös mahdollisia. Joten haluan vain puhua vähän enemmän muita tapoja voit käyttää säännöllisiä lausekkeita. 

Joten yksi edistyksellinen sovellus on sumeaa hakua. Joten jos etsit tekstin ilmaisua, Julius Caesar, ja näet joko Gaius Julius Caesar tai nimi Julius Caesar muilla kielillä, niin ehkä myös haluat määrittää painoa näitä arvoja. Ja jos se on tarpeeksi lähellä - jos se ylittää tietyn kynnyksen - niin haluat pystyä hyväksymään Julius Caesar. Joten on olemassa pari eri toteutuksia, että muutamia muita kieliä kuin hyvin. Tässä muutamia muita työkaluja, Regex Pal - kätevä sovellus verkossa tarkistaa, onko säännöllisiä lausekkeita koostuvat oikein. On myös erillistyökalut, että voit alkaa työpöydällesi kuten Ultra Pico, ja sekä juuri keittokirjoja. Joten jos olet tekemässä projekti, johon ton säännöllisiä lausekkeita tämä on luultavasti paikka mennä ulkopuolella tänään. Ja sitten vain antaa sinulle käsityksen siitä, miten yhteistä se on on grep Unix-, Perl on sisäänrakennettu, ja C on PCRE for C. Ja sitten kaikki nämä muut kielet on myös säännöllinen lauseke paketit jotka toimivat periaatteessa samaa syntaksia saimme maistaa tänään. PHP, Java, Ruby, ja niin edelleen. 

Google Code Search on todella syytä mainita, se on yksi suhteellisen vähän hakemuksia siellä, että kansalaiset voivat käyttää sen tietokantaan käyttäen säännöllisiä lausekkeita. Joten jos näytät Google Code Search löydät koodin jos etsit esimerkiksi siitä, kuinka toiminto voidaan käyttää, voit käyttää säännöllinen lauseke löytää, että toimintoa käytetään kaikenlaisia ​​erilaisia ​​tapauksia. Voisit etsiä fwrite, ja sitten voit etsiä lipun kirjoittaa tai lukea jos halusi esimerkki fwrite käytetään tällöin. Joten sama asia siellä, ja tässä on joitakin viittauksia. Tämä on saatavilla verkossa samoin, niin menee eteenpäin, jos haluat tarkastella Python, grep, Perl - haluat vain saada inspiraatiota tai jos haluat näyttää enemmän teorian tässä on muutamia hyviä hyppäämällä paikkoja. Paljon kiitoksia. [CS50.TV]