[Powered by Google Translate] [Seminar: mønstergjenkjenning med Regular Expressions] [John Mussman-Harvard University] [Dette er CS50.-CS50.TV] Okay. Vel, velkommen alle. Dette er CS50 2012. Mitt navn er John, og jeg vil snakke i dag om regulære uttrykk. Regulære uttrykk er først og fremst et verktøy, men også noen ganger brukt i koden aktivt til hovedsak matche mønstre og strenger. Så her er en web tegneserien fra xkcd. I denne tegneserien er det en mordgåte der morderen har fulgt noen på ferie, og hovedpersonene må søke gjennom 200 megabyte av e-poster på jakt etter en adresse. Og de er i ferd med å gi opp da noen som vet regulære uttrykk - formodentlig en superhelt - swoops ned og skriver noen kode og løser mordgåte. Så formodentlig som vil være noe som du vil ha fullmakt til å gjøre etter dette seminaret. Vi er bare kommer til å gi en kortfattet innføring i språket og gi deg nok midlene til å gå etter mer ressurser på egen hånd. 

Så regulære uttrykk ser i utgangspunktet ut som dette. Dette er et vanlig uttrykk i Ruby. Det er ikke veldig forskjellig på tvers av språk. Vi har bare på flenger å begynne og markere det vanlige uttrykket i Ruby. Og dette er et vanlig uttrykk for å se etter i e-postadresse mønster. Så ser vi på den første biten ser for vilkårlig tall. Det er fordi e-postadresser ofte nødt til å starte med et alfabetisk tegn. Og så noen spesiell karakter etterfulgt av @-symbolet. Og deretter det samme for domenenavn. Og deretter mellom 2 og 4 tegn å se etter. Com,. Net, og så videre. Så det er et annet eksempel på regulært uttrykk. Så regulære uttrykk er protokoller for å finne patters i teksten. De gjør sammenligninger, valg, og utskiftninger. Så en tredje eksempel er å finne alle telefonnumrene som slutter på 54 i en katalog. Så før David rips opp CS50 katalogen kan vi søke etter et mønster hvor vi har parentes deretter tre tall så ender parentes, 3 flere numre, en dash, to tall, og deretter 54. Og det ville være vesentlig hvordan vi kommer opp med et regulært uttrykk for å søke etter det. 

Så det er - vi har gjort noen ting i CS50 som er litt som regulære uttrykk, så - for eksempel - i dictionary.C fil for stavekontroll oppgavesettet kan du ha brukt fscanf å lese inn et ord fra ordboken. Og du kan se den prosentvise 45s er på utkikk etter en streng med 45 tegn. Så det er noe som en rudimentær regulært uttrykk. Og du kan ha noen 45 tegn som passer regningen i det og plukke dem opp. Og deretter det andre eksemplet i den nyeste web-programmering problem satt i distro kode for php faktisk vi har et enkelt regulært uttrykk. Og dette er bare ute for å sjekke om nettside som er vedtatt i samsvarer enten med innlogging registrer deg. PHP. Og deretter returnere sann eller usann basert på at regulært uttrykk matching. 

Så da bruker du vanlig uttrykk? Hvorfor er du her i dag? Så du ikke ønsker å bruke vanlig uttrykk når det er noe som gjør jobben for deg enda lettere. Så XML og HTML er faktisk ganske vanskelig å skrive regulære uttrykk for som vi vil se i en liten bit. Så det er dedikert parsere for disse språkene. Du må også være i orden med handelen offs og nøyaktighet ofte. Hvis du prøver - så vi så et regulært uttrykk for en e-postadresse, men si at du ville ha en bestemt e-postadresse og gradvis regulært uttrykk kan bli mer komplisert som det ble mer presis. Så det ville være en avveining. Du må være sikker på at du er greit å gjøre med det vanlige uttrykket. Hvis du vet nøyaktig hva du leter etter kan det være mer fornuftig å sette i gang og skrive en mer effektiv parser. Og til slutt er det et historisk problem med regulariteten av uttrykk og språk. Regulære uttrykk er faktisk mye kraftigere enn regulære uttrykk pr sier i en formell forstand. 

Så jeg ønsker ikke å gå for langt inn i den formelle teorien, men de fleste språk som vi koden i faktisk ikke er vanlig. Og dette er grunnen til regulære uttrykk noen ganger ikke regnes alt som sikker. Så i utgangspunktet er det en Chomsky hierarki for språk, og regulære uttrykk er bygd opp ved hjelp av union, sammensetning, og Kleene stjerners operasjon som vi vil se i noen få minutter. Hvis du er interessert i teorien er det ganske mye som skjer der under panseret. 

Så en kort historie - bare for sammenhengen her - regelmessige sett kom opp i 1950, og da hadde vi enkle redaktører som innlemmet regulære uttrykk - bare å søke etter strenger. Grep - som er et kommandolinje verktøy - var en av de første svært populære verktøy som innlemmet regulære uttrykk i 1960. På 80-tallet, ble Perl bygget - er et programmeringsspråk som inkorporerer regulære uttrykk svært fremtredende. Og deretter mer nylig har vi hatt Perl kompatible regulære uttrykk protokoller i utgangspunktet på andre språk som bruker mye av den samme syntaksen. Selvfølgelig den viktigste hendelsen var i 2008 hvor det var den første nasjonale Regular Expressions Day, som jeg tror er juni 1 hvis du vil feire det. 

Igjen, bare litt mer teori her. Så det finnes et par forskjellige måter å konstruere regulære uttrykk. En enkel måte er å bygge uttrykket at du kommer til å kjøre på strengen tolke - i utgangspunktet bygge en liten mini-program som vil analysere deler av en streng og se, "Oh, passer dette det vanlige uttrykket eller ikke?" Og deretter kjøre det. Så hvis du har et veldig lite vanlig uttrykk, er dette sannsynligvis den mest effektive måten å gjøre det. Og så hvis du - et annet alternativ er å holde rekonstruere uttrykk som du går, og det er simulere mulighet. Og disse tidlige forsøk på regulære uttrykk algoritmer var relativt enkel og relativt rask, men hadde ikke mye fleksibilitet. Så for å gjøre enda noen av de tingene som vi kommer til å se på i dag har vi måtte gjøre mer komplekse regulære uttrykk implementeringer som er potensielt mye tregere, så det er noe å huske på Det er også en vanlig uttrykk fornektelse av angrep utvalg som utnytter potensialet for disse nyere implementeringer av regulære uttrykk til å bli svært komplisert. Og på samme måte som vi så i buffer overflow angrep, du har angrep som fungerer ved å gjøre rekursive løkker som overkjørt kapasiteten på minnet. Og forresten Regexen er en av de offisielle Flertall av regulære uttrykk ved analogi til okser i Anglo-Saxon. 

OK, så Python Library mange av dere her i person har Mac, slik at du faktisk kan trekke dette opp på skjermen. Regulære uttrykk er bygget inn i Python. Og så Python er forhåndsinstallert på Mac og også tilgjengelig på nettet på denne linken. Så hvis du ser at du kan pause og sørg for at du har Python som vi spiller rundt her. Det er en manuell nettet, så hvis du bare skriver Python inn i datamaskinen vil du se at den versjonen kommer opp i terminalen. Så jeg laget en link til manualen for versjon 2 av Python, samt en jukselapp. Det er en versjon 3 av Python, men Mac-maskinen ikke nødvendigvis komme med det forhåndsinstallert. Så ikke veldig annerledes. Ok, så noen grunnleggende bruk av regulære uttrykk i Python. 

Så her brukte jeg et veldig enkelt uttrykk, så jeg gjorde Python import re og deretter tok et resultat av re.search. Og søket tar to argumenter. Den første er det vanlige uttrykket, og den andre er teksten eller streng du vil analysere. Og da jeg skrevet ut result.group. Så disse er de to grunnleggende funksjonene vi kommer til å se i dag i å lære om regulære uttrykk. Så bare bryte ned dette regulære uttrykket her t og deretter \ w og m så \ w godtar bare noe alfabetisk tegn på det. Så her er vi på jakt etter en "h" og deretter en annen alfabetisk tegn og deretter m, så her som ville matche skinke i, "Abraham Lincoln og skinke smørbrød." Dette er resultatet av denne gruppen. En annen ting som vi kan gjøre er å bruke våre før tekststrenger i Python. Så jeg antar jeg vil gå foran og trekke det opp her. Python import re. Og hvis jeg skulle gjøre det samme - la oss si teksten er, "Abraham," la oss zoome inn - det vi går. Teksten er: "Abraham spiser skinke." Ok, og deretter resultere = re.search. Og da er vårt uttrykk kan være h, og da vil jeg gjøre dot m. Så dot tar bare noen tegn som ikke er en ny linje inkludert tall, prosentpoeng skilt, noe sånt. Og deretter tekst - bom - og deretter result.group--ja. Så det er bare hvordan man skal gjennomføre grunnleggende funksjonalitet her. Hvis vi hadde en tekst ring som - som gal tekst - inkludert si masse tilbake skråstreker og strenger inne og ting som kunne se ut som escape-sekvenser, da vi sannsynligvis vil bruke rå skriving å sørge for at blir akseptert. Og som bare ser slik ut. Så hvis vi var ute for hver av dem der vi ikke skal finne noe. Men det er hvordan du ville gjennomføre det, like før streng av det vanlige uttrykket du la brevet r. 

Ok, så la oss holde det gående. Greit - så la oss se på et par repetitive mønstre her. Så en ting som du ønsker å gjøre er å gjenta ting som du søker gjennom tekst. Så for å gjøre en etterfulgt av en rekke b - du gjør ab *. Og så er det en rekke andre regler også. Og du kan se alle disse opp, jeg vil bare kjøre gjennom noen av de mest brukte seg. Så ab + er et etterfulgt av en hvilken som helst n er større enn 0 av B. ab? er et etterfulgt av 0 eller 1 av f.. ab N {} er et etterfulgt av N for B, og deretter så videre. Hvis du har to tallene i klammeparentes du spesifisere et område som kan være muligens matchet. Så vil vi se mer på et par repeterende mønstre i et minutt. Så to ting å huske på når du bruker disse mønstergjenkjenning verktøy her. Så si at vi ønsker å se på hm av, "Abraham Lincoln gjør skinke smørbrød." Så jeg endret Abraham Lincolns navn til Abraham. Og nå er vi på jakt etter hva som er returnert av denne søkefunksjonen, og den returnerer bare skinke i dette tilfellet. Og det gjør at fordi søk bare naturlig tar venstre mest køen. Og alle regulære uttrykk med mindre du angir noe annet vil gjøre det. Hvis vi ønsket å finne alt det er en funksjon for det - finne alle. Slik at vi kunne bare se ut som alle = re.findall ('h.m', text) og deretter all.group (). Alle produserer både skinke og skinke, i dette tilfellet både av strengene i Abraham hver skinke. Så det er et annet alternativ. 

Flott. Den andre ting å huske på er at regulære uttrykk ta den største intuitivt. La oss se på dette eksempelet. Vi gjorde det venstre mest søket her, og da jeg forsøkte et større søk bruker Kleene stjerners operatør. Så for, "Abraham Lincoln gjør skinke smørbrød", og jeg bare kom tilbake m som resultat. Grunnen til at feilen var at jeg kunne ha tatt en rekke h er fordi jeg ikke har angitt noe å gå i mellom h og m. Den eneste eksempel der som hadde m - de eneste eksemplene der med m i det og en rekke h-tallet var bare strengen m. Da jeg prøvde det igjen, jeg sa: "Ok, la oss få den faktiske største gruppen her." Og så gjorde jeg h.. * M, slik at bare returnerer et vilkårlig antall bokstaver mellom h og m. Og hvis du bare starte opp og tenker: "Å, vil okay, vel dette få meg skinke, "det tar faktisk alt fra t på Abraham Lincoln helt opp til slutten av skinke. Det er grådig, det ser h - alt dette andre tekst - m, og det er det som trengs i. Dette er en spesielt skjerpende - dette er en funksjon vi kan også angir for det ikke være grådig bruker andre funksjoner. Men dette er noe vi må huske på spesielt når man ser på HTML-teksten, som er en grunn til at regulære uttrykk er vanskelig for HTML. Fordi hvis du har en HTML åpen tag og så mange ting i midten og deretter noen andre HTML stengt tag mye senere i programmet, du nettopp har spist opp mye av HTML-koden muligens ved en feiltakelse. 

All right - så flere spesialtegn, som mange andre språk, vi slippe å bruke slash. Så vi kan bruke dot å spesifisere hvilket som helst tegn unntatt for en ny linje. Vi kan bruke flukten w for å angi en alfabetisk tegn. Og ved analogi flukt d for alle heltall - numerisk karakter. Vi kan spesifisere - vi kan bruke parentes for å angi beslektede uttrykk. Så dette ville godta a, b eller c. Og vi kan også angi eller alternativer for enten a eller b. For eksempel - hvis vi leter etter flere muligheter i parentes kan vi bruke eller operatør som i - så la oss gå tilbake til dette eksempelet her. Og nå la oss ta - la oss gå tilbake til dette eksempelet her, og deretter ta ae - så dette bør gå tilbake - Jeg antar dette er fremdeles Abraham. Så dette - hvis vi gjør alt - flott. Så la oss oppdatere teksten her. "Abraham spiser skinke mens hemming hans -. Mens hemming" Flott. Alle. Flott. Nå får vi skinke, skinke, og hem. Mens hemming - mens nynner til ham - mens nynner til hem ham. Flott. Samme. Nå er alt returnerer fortsatt bare skinke, skinke, og hem uten å plukke opp på nynne eller ham. Stor - så hva om vi ønsket å se på enten det - så vi kan også gjøre ham eller - vi vil komme tilbake til det. Ok - så - greit - i stillinger kan du også bruke cirkumflekstegnet eller dollartegn å spesifisere at du er ute etter noe i starten eller slutten på en streng. Eller starten eller slutten av et ord. Det er en måte å bruke som. 

Ok - så la oss leke seg med en litt større blokk med tekst. La oss si at denne raden her - denne uttalelsen her. Kraften i regulært uttrykk er at de kan angi mønstre ikke bare fikset tegn. La oss gjøre - la oss kalle denne blokken. Da vil vi lese alt dette i. Og deretter har en - la oss gjøre alt =, så hva er noen ting vi kunne søke her lønnsomt? Vi kunne se for uttrykket øret. Ikke veldig interessant. Hva om det? Vi får se hva som skjer. Jeg ga det et problem. Så en rekke ting før re og alt. Så det skal returnere alt fra starten til alle re kanskje et par ganger. Og så her har vi kraften av regulære uttrykk er at de kan spesifisere mønstre ikke bare tegn her er. Så hele veien opp til den endelige re, det startet med venstre mest og var grådig. La oss se - hva annet kan vi se etter. Jeg antar en ting hvis du var interessert i jakt etter pronomen hun og han, du kan se etter er å være lik 0 eller 1 og uttrykket han, og det er sannsynligvis ikke kommer til å returnere - oh, jeg antar det vendte han tilbake fordi det vi ser på kraften, den dagen er her. La oss forsøke å spesifisere at dette må komme i starten av noe. La oss se om det faller av. Så vi kan gjøre fett, og det vi ikke får noe fordi hun og han ikke forekommer i denne setningen. Flott. Ok - så tilbake til katten her. Så komplekse mønstre er skade hjernen. Så det er derfor vi bruker regulære uttrykk for å unngå disse problemene. 

Så her er noen andre nyttige moduser du kan spille rundt med. Vi så på søk i dag, men du kan også bruke kampen, split, findall og grupper. Så andre kule ting du kan gjøre med regulære uttrykk dessuten bare på jakt etter mønstre tar et mønster og holder alle kampene - variablene - og deretter bruke dem i koden senere. Som kan være ganske nyttig. Andre ting kan være å telle. Så vi kan telle antall forekomster av et regulært uttrykk mønster, og det er det vi kan bruke grupper for. Og andre moduser samt er også mulig. Så jeg vil bare snakke litt mer om andre måter du kan bruke vanlige uttrykk. 

Så en mer avansert program er i fuzzy matching. Så hvis du er ute etter en tekst for uttrykket, Julius Cæsar, og du ser enten Gaius Julius Caesar eller navnet Julius Caesar i andre språk, kan dere også vil tildele en viss vekt på disse verdiene. Og hvis det er nært nok - hvis det krysser en viss terskel - så du vil å være i stand til å akseptere Julius Cæsar. Så det er et par ulike implementeringer for at i noen andre språk også. Her er noen andre verktøy, Regex Pal - en hendig liten app på nettet for å kontrollere om regulære uttrykk er sammensatt riktig. Det finnes også frittstående verktøy som du kan kjøre fra skrivebordet som Ultra Pico, og så vel som bare kokebøker. Så hvis du gjør et prosjekt som involverer massevis av regulære uttrykk dette er trolig stedet å gå utenfor i dag. Og så bare for å gi deg en følelse av hvor vanlig det er det er grep i Unix, har Perl innebygd, og C er det PCRE for C. Og så alle disse andre språk har også regulære uttrykk pakker som opererer med i hovedsak de samme syntaks vi fikk en smak av i dag. PHP, Java, Ruby, og så videre. 

Google Code Search er faktisk verdt å nevne, det er en av de relativt få programmer der ute som gjør det mulig for publikum å få tilgang sin database ved hjelp av regulære uttrykk. Så hvis du ser på Google Code Search kan du finne koden hvis du er ute etter en forekomst av hvordan en funksjon kan benyttes, du kan bruke et vanlig uttrykk for å finne den funksjonen blir brukt i alle slags forskjellige saker. Du kan se etter fwrite, og så kan du se etter flagget skrive eller lese Hvis du ønsker et eksempel på fwrite blir brukt i dette tilfellet. Så det samme der, og her er noen referanser. Dette vil være tilgjengelig på nettet også, så det går fremover hvis Ønsker du å se på Python, grep, Perl - du bare ønsker å få litt inspirasjon eller hvis du ønsker å se mer på teorien her er noen god hopping av steder. Tusen takk. [CS50.TV]