[Powered by Google Translate] [Seminar: Pattern Matching med Regular Expressions] [John Mussman-Harvard University] [Dette er CS50.-CS50.TV] Okay. Nå, velkommen alle. Dette er CS50 2012. Mit navn er John og jeg vil tale i dag om regulære udtryk. Regulære udtryk er primært et værktøj, men også undertiden bruges i kode aktivt til væsentlige matche mønstre og strygere. Så her er en web-tegneserie fra xkcd. I denne tegneserie er der en mordgåde, hvor morderen har fulgt nogen på ferie, og hovedpersonerne er nødt til at søge gennem 200 megabyte af e-mails på udkig efter en adresse. Og de er ved at give op, når nogen, der kender regulære udtryk - formentlig en superhelt - swoops ned og skriver noget kode og løser mordgåde. Så formentlig, der vil være noget, som du vil blive bemyndiget til at gøre efter dette seminar. Vi er bare nødt til at give en kortfattet introduktion til sproget og give dig nok midlerne til at gå efter flere ressourcer på egen hånd. 

Så regulære udtryk se dybest set sådan ud. Dette er et regulært udtryk i Ruby. Det er ikke forfærdelig forskellig på tværs af sprog. Vi har netop på flænger at begynde og markere det regulære udtryk i Ruby. Og det er et regulært udtryk til at søge i e-mail-adresse mønster. Så vi ser på det første bit ser for enhver alfanumeriske tegn. Det er fordi e-mail adresser ofte nødt til at starte med et bogstav. Og så nogen særlig tegn efterfulgt af @-symbolet. Og så det samme for domænenavn. Og så mellem 2 og 4 tegn at lede efter den. Com,. Net, og så videre. Så det er endnu et eksempel på regulære udtryk. Så regulære udtryk er protokoller for at finde mønstre i tekst. De gør sammenligninger, markeringer og udskiftninger. Så et tredje eksempel er at finde alle de telefonnumre, der sluttede i 54 i en mappe. Så før David river op CS50 biblioteket, vi kunne søge et mønster, hvor vi har parenteser derefter 3 numre så ende parentes 3 flere tal, en bindestreg, 2 numre, og derefter 54. Og det ville være væsentligt, hvordan vi kommer op med et regulært udtryk for at søge efter det. 

Så der er - vi har gjort nogle ting i CS50, der er lidt ligesom regulære udtryk, så - for eksempel - i dictionary.C fil for stavekontrollen problemet sæt, du kan have brugt fscanf at læse i et ord fra ordbogen. Og du kan se den procentvise 45s er på udkig efter en streng på 45 tegn. Så det er lidt ligesom en rudimentær regulært udtryk. Og du kan have nogen 45 tegn, der passer regningen derinde og vælge dem op. Og så det andet eksempel i den seneste web programmering problem sat i distro koden til php vi faktisk har en simpel regulært udtryk. Og dette er simpelthen søger at kontrollere, om den webside, der er gået i matcher enten login eller logout registrere. PHP. Og derefter returnere sandt eller falsk baseret på, at regelmæssig udtryk matchning. 

Så når du bruger regulære udtryk? Hvorfor er du her i dag? Så du behøver ikke ønsker at bruge regulære udtryk, når der er noget, der gør arbejdet for dig endnu mere nemt. Så XML og HTML er faktisk temmelig tricky at skrive regulære udtryk, så vi vil se i en lille smule. Så der er dedikerede parsere for disse sprog. Du skal også være okay med den handel offs og nøjagtighed ofte. Hvis du forsøger - så vi oplevede et regulært udtryk for en e-mailadresse, men siger du ønskede en bestemt e-mail-adresse og efterhånden regulære udtryk kan blive mere kompliceret, da det blev mere præcis. Så det ville være en afvejning. Du er nødt til at være sikker på at du okay gør med det regulære udtryk. Hvis du ved præcis, hvad du leder efter det måske give mere mening at sætte i gang og skrive en mere effektiv parser. Og endelig er der et historisk problem med regelmæssighed af udtryk og sprog. Regulære udtryk er faktisk langt mere magtfulde end regulære udtryk per siger i en formel forstand. 

Så jeg ønsker ikke at gå for vidt i den formelle teori, men de fleste sprog, som vi kode i egentlig ikke er regelmæssige. Og dette er grunden til regulære udtryk undertiden betragtes ikke alt, sikker. Så dybest set er der en Chomsky hierarki for sprog, og regulære udtryk er bygget op ved hjælp af union, sammenkædning, og Kleene stjerne operation, som vi vil se i et par minutter. Hvis du er interesseret i teorien er der en hel masse i gang der under kølerhjelmen. 

Så en kort historie - bare for den kontekst her - regelmæssige sæt kom op i 1950'erne, og derefter vi havde simple redaktører der indarbejdet regulære udtryk - blot at søge efter strenge. Grep - som er en kommandolinje værktøj - var en af ​​de første meget populære værktøjer, der er indarbejdet regulære udtryk i 1960'erne. I 80'erne blev Perl bygget - er et programmeringssprog, der inkorporerer regulære udtryk meget fremtrædende plads. Og så for nylig har vi haft Perl kompatibel regulært udtryk protokoller dybest set på andre sprog, der bruger meget af den samme syntaks. Selvfølgelig er den vigtigste begivenhed var i 2008 hvor der var den første nationale Regular Expressions Day, som jeg mener er 1 juni, hvis du ønsker at fejre det. 

Igen, bare en lille smule mere teori her. Så der er et par forskellige måder at konstruere regulære udtryk. En enkel måde er at bygge det udtryk, du kommer til at køre på strengen fortolke - grundlæggende bygger en lille mini-program, vil analysere stykker af en streng og se, "Åh, betyder det passer det regulære udtryk eller ej?" Og derefter køre det. Så hvis du har en meget lille regulært udtryk, det er nok den mest effektive måde at gøre det. Og så hvis du - en anden mulighed er at holde rekonstruere udtryk, som du går, og det er simulere mulighed. Og disse tidlige forsøg på regulære udtryk algoritmer var relativt simpel og forholdsvis hurtigt, men ikke har en masse fleksibilitet. Så for at gøre endnu nogle af de ting, som vi kommer til at se på i dag har vi haft at gøre mere kompleks regulært udtryk implementeringer, der er potentielt meget langsommere, så det er noget at huske på Der er også en regelmæssig udtryk fornægtelse af angreb sort der udnytter potentialet for disse nyere implementeringer af regulære udtryk til at blive meget kompliceret. Og på samme måde som vi så i buffer overflow angreb, du har angreb, der arbejder ved at gøre rekursive sløjfer, overskridelse kapaciteten af ​​hukommelsen. Og ved den måde Regexen er et af de officielle flertalsformer af regulære udtryk analogt på okser i den angelsaksiske. 

Okay, så Python Library mange af jer her i person have Macs, så du kan faktisk trække dette op på din skærm. Regulære udtryk er bygget ind Python. Og så Python er forudindlæst på Mac-computere og også tilgængelig online på dette link. Så hvis du ser du kan pause og sørg for at have Python da vi spiller her. Der er en manuel online, så hvis du bare skrive Python ind på din computer vil du se at den version kommer op i terminalen. Så jeg givet et link til manualen for version 2 af Python samt en bedrager ark. Der er en version 3 af Python, men din Mac ikke nødvendigvis kommer med den pågældende forudindlæste. Så ikke frygtelig anderledes. Okay, så nogle grundlæggende hjælp af regulære udtryk i Python. 

Så her jeg brugte en meget enkel udtryk, så jeg gjorde Python import re og derefter tog resultatet af re.search. Og søgningen tager 2 argumenter. Den første er det regulære udtryk, og den anden er den tekst eller streng, du vil analysere. Og så vil jeg udskrives ud result.group. Så disse er de 2 grundlæggende funktioner, vi kommer til at se i dag i at lære om regulære udtryk. Så bare nedbryde denne regulære udtryk her h og derefter \ w og derefter m så \ w bare accepterer enhver bogstav derinde. Så her er vi på udkig efter en "h", og derefter en anden bogstav og derefter m, så her, ville matche skinke i, "Abraham Lincoln og skinke sandwich." Dette er resultatet af denne gruppe. En anden ting, som vi kan gøre er at bruge vores før tekststrenge i Python. Så jeg tror jeg vil gå videre og trække det op her. Python import re. Og hvis jeg skulle gøre det samme - lad os sige tekst, "Abraham," lad os zoome ind - der går vi. Tekst er "Abraham spiser skinke." Okay, og derefter føre = re.search. Og så er vores udtryk kan være h, og så vil jeg gøre dot m.. Så dot bare tager ethvert tegn, der ikke er en ny linje, herunder tal, procentpoint skilte, noget lignende. Og så tekst - boom - og så result.group--ja. Så det er bare hvordan man gennemfører grundlæggende funktionalitet her. Hvis vi havde en tekst ring, der - den skøre tekst - inkluderet sige masser af back skråstreger og strygere inde og ting, der kunne ligne escape-sekvenser, så vi sandsynligvis vil bruge rå tekst input til at sikre, at der er accepteret. Og det bare ligner det. Så hvis vi ledte efter hver af dem derinde skulle vi ikke finde noget. Men det er hvordan du ville gennemfører den; lige før perlerække af det regulære udtryk du sætter bogstavet R. 

Okay, så lad os holde i gang. Okay - så lad os se på et par gentagne mønstre her. Så én ting, du ønsker at gøre, er at gentage tingene som du søger gennem tekst. Så for at gøre en efterfulgt af et vilkårligt antal b - du gør ab *. Og så er der en række andre regler også. Og du kan se alle disse op, jeg vil bare køre gennem nogle af de mest almindeligt anvendte dem. Så ab + er en efterfulgt af en N større end 0, hvor b. AB? er en efterfulgt af 0 eller 1 i b.. ab {N} er en efterfulgt af N af b, og derefter så videre. Hvis du har 2 numre i de krøllede parenteser du angiver et interval der kan være eventuelt matches. Så vi vil se mere på et par gentagne mønstre i et minut. Så 2 ting at huske på, når du bruger disse mønstertilpasning redskaber her. Så siger vi ønsker at se på hm af "Abraham Lincoln gør skinkesandwiches." Så jeg skiftede Abraham Lincolns navn til Abraham. Og nu er vi på udkig efter, hvad der er tilbage af denne søgefunktion, og det kun returnerer skinke i dette tilfælde. Og det gør det, fordi søgningen bare naturligt tager længst til venstre køen. Og alle regulære udtryk, medmindre du angiver andet, vil gøre det. Hvis vi ønskede at finde alle der er en funktion til det - finde alle. Så bare kunne ligne alle = re.findall ('h.m', text) og derefter all.group (). Alle producerer både skinke og skinke, i dette tilfælde begge strenge i Abraham hver skinke. Så det er en anden mulighed. 

Great. Den anden ting at huske på er, at regulære udtryk tager den største intuitivt. Lad os se på dette eksempel. Vi gjorde det længst til venstre søgning her, og så forsøgte jeg en større søgning bruger Kleene stjerne operatør. Så for "Abraham Lincoln gør skinkesandwiches", og jeg fik kun tilbage m som resultat. Årsagen til denne fejl var, at jeg kunne have taget en række h er fordi jeg ikke angav noget at gå i mellem h og m. Det eneste eksempel der, havde m - de eneste eksempler der med m i det og et antal timer s var bare strengen m.. Så jeg prøvede det igen, sagde jeg: "Okay, lad os få den faktiske største gruppe her." Og så gjorde jeg h. * M, så der bare returnerer vilkårligt antal tegn mellem h og m. Og hvis du lige er startet ud og tænker, "Åh, vil okay, godt denne få mig skinke, "det faktisk tager alt fra h i Abraham Lincoln hele vejen op til slutningen af ​​skinke. Det er grådige, det ser h - alt dette andet tekst - m, og det er, hvad det tager i. Dette er et særligt grove - dette er en funktion, som vi kan også angiver for det ikke være grådig hjælp af andre funktioner. Men det er noget, vi er nødt til at huske på, især når man ser på HTML-teksten, der er en grund til, at regulære udtryk er svære for HTML. Fordi hvis du har en HTML åbent tag, og derefter masser af ting i midten og derefter nogle andre HTML lukket tag langt senere i programmet, du lige har spist en masse af din HTML-kode eventuelt ved en fejltagelse. 

Okay - så mere specialtegn, ligesom mange andre sprog, vi undslippe bruger skråstreg. Så vi kan bruge dot til at angive alle tegn bortset fra en ny linje. Vi kan bruge flugt w for at angive eventuelle bogstav. Og analogt escape d for enhver heltal - numerisk karakter. Vi kan angive - vi kan bruge parenteser til at angive relaterede udtryk. Så det ville acceptere a, b, eller c.. Og vi kan også angive eller muligheder for enten a eller b. For eksempel - hvis vi var på udkig efter flere muligheder i parentes vi kunne bruge eller operatøren i - så lad os gå tilbage til dette eksempel her. Og lad os nu tage - lad os gå tilbage til dette eksempel her, og derefter tage ae - så det skal returnere - Jeg tror det er stadig Abraham. Så dette - hvis vi gør alt - store. Så lad os ajourføre teksten her. "Abraham spiser skinke, mens Hemming hans -. Mens Hemming" Great. All. Great. Nu får vi skinke, skinke, og forneden. Mens Hemming - mens nynne for ham - mens nynne til søm ham. Great. Samme ting. Nu er alt tilbage stadig bare skinke, skinke og hem uden at løfte på brummen eller ham. Great - så hvad nu hvis vi ønskede at se på, enten at - så vi kunne også gøre ham eller - vi vil vende tilbage til. Okay - så - okay - i stillinger, du kan også bruge karet eller dollartegn at angive, at du er på udkig efter noget i starten eller slutningen af ​​en streng. Eller i starten eller slutningen af ​​et ord. Det er en måde at bruge det. 

Okay - så lad os lege med en lidt større blok af tekst. Lad os sige denne række her - dette udsagn her. Den effekt af regulære udtryk er, at de kan angive mønstre ikke bare fast tegn. Lad os gøre - lad os kalde denne blok. Så vil vi læse alt dette i. Og derefter har en - lad os gøre alle =, og så hvad er nogle ting, vi kunne søge ind her rentabelt? Vi kunne kigge efter udtrykket øre. Ikke meget interessant. Hvad med det? Vi vil se, hvad der sker. Jeg gav det et problem. Så en række ting, før man igen og alle. Så det skal returnere alt fra begyndelsen op til alle re måske et par gange. Og så har vi her magt regulære udtryk er, at de kan angive mønstre ikke bare tegn her er. Så hele vejen op til den endelige re, det startede med den venstre mest og var grådige. Lad os se, - hvad andet kunne vi kigge efter. Jeg gætter én ting, hvis du var interesseret i at lede efter de pronominer hun og han, kan du kontrollere, om s er lig med 0 eller 1 og udtrykket han, og det er sandsynligvis ikke kommer til at vende tilbage - åh, jeg tror det returnerede han, fordi der vi ser på magten, den dag, der er her. Lad os prøve det præciseres, at dette har til at komme i starten af ​​noget. Lad os se, om det falder ud. Så vi kan gøre fedt, og der får vi ikke noget, fordi hun og han forekommer ikke i denne sætning. Great. Okay - så tilbage til katten her. Så komplekse mønstre er såre hjernen. Så det er derfor, vi bruger regulære udtryk til at undgå disse problemer. 

Så her er nogle andre nyttige funktioner, du kan lege med. Vi kiggede på søgning i dag, men du kan også bruge match, split, findall og grupper. Så andre seje ting, du kan gøre med regulære udtryk udover bare udkig efter mønstre tager et mønster og holde alle kampene - dens variabler - og så bruge dem i din kode senere. Det kan være ganske nyttigt. Andre ting kunne være at tælle. Så vi kan tælle antallet af forekomster af et regulært udtryk mønster, og det er, hvad vi kan bruge grupper til. Og andre transportformer samt er også mulige. Så jeg vil bare tale lidt mere om andre måder, du kan bruge regulære udtryk. 

Så en mere avanceret anvendelse er i fuzzy matching. Så hvis du er på udkig efter en tekst til udtrykket, Julius Cæsar, og du kan se enten Gaius Julius Cæsar eller navnet Julius Cæsar i andre sprog, så skal du måske også ønsker at tildele en vis vægt på disse værdier. Og hvis det er tæt nok - hvis den krydser en vis tærskel - så du ønsker at være i stand til at acceptere Julius Cæsar. Så der er et par forskellige implementeringer for at i et par andre sprog så godt. Her er nogle andre værktøjer, Regex Pal - en handy lille app online for at kontrollere, om dine regulære udtryk er sammensat korrekt. Der er også enkeltstående værktøjer, som du kan køre fra skrivebordet Ligesom Ultra Pico, og så godt som bare kogebøger. Så hvis du laver et projekt, der involverer et væld af regulære udtryk dette er sandsynligvis stedet at gå uden for i dag. Og så bare for at give dig en fornemmelse af, hvor almindeligt det er Der er grep i Unix, Perl har indbygget, og C er der PCRE for C. Og så alle disse andre sprog har også regulære udtryk pakker der opererer med væsentligt samme syntaks, vi fik en smag af i dag. PHP, Java, Ruby, og så videre. 

Google Code Search er faktisk værd at nævne, det er et af de relativt få programmer derude, der giver offentligheden adgang sin database ved hjælp af regulære udtryk. Så hvis man ser på Google Code Search kan du finde koden Hvis du er på udkig efter en instans af, hvordan en funktion kan anvendes, kan du bruge et regulært udtryk til at finde denne funktion bliver brugt i alle mulige forskellige sager. Du kan kigge efter fwrite, og så kunne du kigge efter flag skrive eller læse hvis du ønsker et eksempel på fwrite bliver brugt i denne sag. Så den samme ting der, og her er nogle referencer. Dette vil være tilgængelige online så godt, så går fremad, hvis du ønsker at se på Python, grep, Perl - du blot ønsker at få lidt inspiration eller hvis du ønsker at se mere på teorien her er nogle god hoppe fra steder. Mange tak. [CS50.TV]