[Powered by Google Translate] [Seminarium: Mönstermatchning med reguljära uttryck] [John Mussman-Harvard University] [Detta är CS50.-CS50.TV] Okej. Tja, välkommen alla. Detta är CS50 2012. Mitt namn är John, och jag kommer att prata idag om reguljära uttryck. Reguljära uttryck är främst ett verktyg, men också ibland används i koden aktivt huvudsak matcha mönster och strängar. Så här är en web comic från xkcd. I denna serie finns en mordgåta där mördaren har följt någon på semester, och huvudpersonerna har att söka igenom 200 megabyte e-postmeddelanden som söker efter en adress. Och de är på väg att ge upp när någon som vet reguljära uttryck - förmodligen en superhjälte - sveper ner och skriver lite kod och löser mordgåta. Så förmodligen som kommer att vara något som du kommer att ha befogenhet att göra Efter detta seminarium. Vi kommer bara att ge en kortfattad introduktion till språket och ge dig tillräckligt med resurser för att gå efter mer resurser på egen hand. 

Så reguljära uttryck ser i princip ut så här. Detta är ett vanligt uttryck i Ruby. Det är inte så väldigt annorlunda på flera språk. Vi har bara på snedstreck för att börja och markera det reguljära uttrycket i Ruby. Och detta är ett reguljärt uttryck för att leta efter i e-postadress mönster. Så vi ser på den första biten ser för alla alfanumeriska tecken. Det beror på e-postadresser ofta måste börja med en bokstav. Och sedan någon speciell karaktär följt av tecknet @. Och sedan samma sak för domännamn. Och sedan mellan 2 och 4 tecken för att leta efter den. Com,. Net, och så vidare. Så det är ett annat exempel på reguljära uttryck. Så reguljära uttryck är protokoll för att hitta smattrar i text. De gör jämförelser, val, och utbyten. Så ett tredje exempel är att hitta alla telefonnummer som slutar på 54 i en katalog. Så innan David sliter upp CS50 katalogen vi kunde söka ett mönster där vi har parenteser därefter 3 siffror hamnar då parentes, Ytterligare 3 siffror, ett bindestreck, 2 siffror, och sedan 54. Och det skulle i stort sett hur vi kommit fram till ett reguljärt uttryck för att söka efter det. 

Så det finns - vi har gjort en del saker i CS50 som är lite som att reguljära uttryck, så - till exempel - i dictionary.C filen för stavningskontroll problemet set du kan ha använt fscanf att läsa in ett ord från ordlistan. Och du kan se den procentuella 45s är ute efter en sträng med 45 tecken. Så det är något som en rudimentär reguljärt uttryck. Och du kan ha några 45 tecken som passar räkningen i det och plocka upp dem. Och sedan det andra exemplet i den senaste webbprogrammering problem satt i distro kod för php vi gör faktiskt har en enkel reguljära uttryck. Och detta är bara helt enkelt ute efter att kontrollera om webbsidan som skickas i matchar antingen logga in eller logga registrera. PHP. Och sedan återvänder sant eller falskt baserat på det reguljära uttryck matchning. 

Så när använder du reguljära uttryck? Varför är du här idag? Så du vill inte använda reguljära uttryck när det är något som gör jobbet åt dig ännu enklare. Så XML och HTML är faktiskt ganska knepigt att skriva reguljära uttryck för när vi kommer att se i en liten bit. Så det finns särskilda tolkar för dessa språk. Du måste också vara okej med avvägningar och noggrannhet ofta. Om du försöker - så såg vi ett reguljärt uttryck för en e-postadress, men att säga att du ville ha en särskild e-postadress och gradvis reguljära uttryck kan bli mer komplicerad eftersom det blev mer exakt. Så det skulle vara en avvägning. Du måste vara säker på att du okej gör med det reguljära uttrycket. Om du vet exakt vad du letar efter det kanske vettigare att sätta i gång och skriva ett effektivare parser. Och slutligen finns det en historisk fråga med regelbundenhet av uttryck och språk. Reguljära uttryck är faktiskt mycket mer kraftfull än reguljära uttryck per säga i formell mening. 

Så jag vill inte gå för långt i den formella teorin, men de flesta språk som vi kod i själva verket inte är regelbunden. Och det är därför reguljära uttryck ibland inte betraktas allt som säker. Så i princip finns det ett Chomsky hierarki för språk, och reguljära uttryck är uppbyggda med hjälp av facket, sammanlänkning, och Kleene stjärnan operation som vi kommer att se i ett par minuter. Om du är intresserad av teorin finns det en hel del som händer där under huven. 

Så en kort historik - bara för sammanhanget här - regelbundna uppsättningar kom upp på 1950-talet, och då hade vi enkla redaktörer som införlivas reguljära uttryck - att bara söka efter strängar. Grep - vilket är ett kommandoradsverktyg - var en av de första mycket populära verktyg som ingår reguljära uttryck på 1960-talet. Under 80-talet, var Perl byggd - är ett programmeringsspråk som inkorporerar reguljära uttryck väldigt framträdande. Och sedan mer nyligen har vi haft Perl kompatibla reguljära uttryck protokoll i princip på andra språk som använder mycket av samma syntax. Naturligtvis den viktigaste händelsen var 2008 där det var den första nationella Regular Expressions Dag, som jag tror är den 1 juni om du vill fira det. 

Återigen, bara lite mer teori här. Så det finns ett par olika sätt att konstruera reguljära uttryck. Ett enkelt sätt är att bygga ett uttryck som du ska köra på strängen tolkar - i princip bygga en liten mini-program som kommer att analysera delar av en sträng och se, "Åh, passar detta reguljära uttryck eller inte?" Och sedan köra det. Så om du har en mycket liten reguljära uttryck, är detta troligen det mest effektiva sättet att göra det. Och sedan om du - ett annat alternativ är att hålla rekonstruera uttryck som du går, och det är simulera möjligheten. Och dessa tidiga försök till reguljära uttryck algoritmer var relativt enkelt och relativt snabbt, men hade inte en stor flexibilitet. Så för att göra även några av de saker som vi kommer att titta på idag har vi haft att göra mer komplexa reguljära uttryck implementeringar som är potentiellt mycket långsammare, så det är något att ha i åtanke Det finns också en regelbunden uttryck förnekande av attack sort att utnyttja potentialen för dessa nyare implementeringar av reguljära uttryck för att bli mycket komplex. Och på samma sätt som vi såg i attacker buffertspill, du har attacker som verkar genom att göra rekursiva slingor som överskridande kapaciteten hos minnet. Och förresten Regexen är ett av de officiella pluralformer av reguljära uttryck analogt till oxar i den anglosaxiska. 

Okej, så det Python Library många av er här personligen har Mac, så du kan faktiskt dra upp detta på din skärm. Reguljära uttryck är inbyggda i Python. Och så Python är förinstallerad på Mac-datorer och även tillgängligt online på denna länk. Så om du tittar på kan du pausa och se till att du har Python som vi leka här. Det är en manuell på nätet, så om du bara skriver Python i din dator kommer du att se att den versionen kommer upp i terminalen. Så jag gav en länk till manualen för version 2 av Python samt en fusklapp. Det finns en version 3 av Python, men din Mac inte nödvändigtvis komma med det förinstallerade. Så inte så väldigt annorlunda. Okej, så några grunderna i att använda reguljära uttryck i Python. 

Så här har jag använt en mycket enkelt uttryck, så jag gjorde Python import re och tog sedan resultatet av re.search. Och sökandet tar 2 argument. Den första är det reguljära uttrycket, och den andra är texten eller sträng som du vill analysera. Och då jag skrev ut result.group. Så dessa är de två grundläggande funktioner vi kommer att se i dag att lära om reguljära uttryck. Så bara bryta ner detta reguljära uttryck här h och sedan \ w och sedan m så \ w accepterar bara någon bokstav i det. Så här är vi letar efter ett "h" och sedan en annan bokstav och därefter m, så här som skulle matcha skinka i, "Abraham Lincoln och skinka smörgåsar." Detta är resultatet av den gruppen. En annan sak som vi kan göra är att använda våra före textsträngar i Python. Så jag antar att jag kommer att gå vidare och dra upp det här. Python import re. Och om jag skulle göra samma sak - låt oss säga text är, "Abraham," låt oss zooma in - där vi går. Text är, "Abraham äter skinka." Okej, och sedan leda = re.search. Och så vårt uttryck kan vara h, och då kommer jag att göra dot m. Så dot tar bara alla tecken som inte är en ny linje med siffror, procentenheter tecken, något liknande. Och sedan text - boom - och sedan result.group--ja. Så det är bara hur man ska genomföra grundläggande funktionalitet här. Om vi ​​hade en text ring som - det galna text - inkluderat säga massor av back snedstreck och strängar inne och saker som skulle kunna se ut escape-sekvenser, då vi vill nog använda den råa textinmatning för att säkerställa att accepteras. Och som bara ser ut så. Så om vi letade efter vart och ett av dem där vi inte skulle hitta något. Men det är hur du skulle genomföra det, strax innan strängen av det reguljära uttrycket du sätter bokstaven r.. 

Okej, så låt oss fortsätta. Okej - så låt oss titta på ett par repetitiva mönster här. Så en sak som du vill göra är att upprepa saker när du söker igenom text. Så för att göra en följt av valfritt antal B - du gör ab *. Och sedan finns det en rad andra regler också. Och du kan se alla dessa upp, jag ska bara gå igenom en del av den mest använda sådana. Så ab + är en följd av något N större än 0 i b.. ab? är en följd av 0 eller 1 av b.. ab {N} är en följd av N av b, och sedan så vidare. Om du har 2 nummer i klammerparenteser du anger ett intervall som kan vara eventuellt matchas. Så vi kommer att titta mer på ett par återkommande mönster i en minut. Så 2 saker att tänka på när du använder dessa mönstermatchning verktyg här. Så säger vi vill titta på hm av, "Abraham Lincoln gör skinka smörgåsar." Så jag bytte Abraham Lincoln namn till Abraham. Och nu söker vi för vad som returneras av denna sökfunktion, och den återvänder bara skinka i det här fallet. Och det gör det eftersom sökningen bara naturligt tar den vänstra mest kö. Och alla reguljära uttryck om du inte anger annat kommer att göra det. Om vi ​​ville hitta allt finns det en funktion för att - hitta alla. Så att bara kunde se ut som alla = re.findall ('h.m ", text) och sedan all.group (). Alla producerar både skinka och skinka, i detta fall de båda strängarna i Abraham varje skinka. Så det är ett annat alternativ. 

Jättebra. Den andra saken att tänka på är att reguljära uttryck tar den största intuitivt. Låt oss titta på detta exempel. Vi gjorde det vänstra mest söka här, och då jag försökte en större sökning använder Kleene stjärnan operatören. Så för, "Abraham Lincoln gör skinka smörgåsar," och jag bara fick tillbaka m som följd. Anledningen till det misstaget var att jag kunde ha tagit ett antal h är eftersom jag inte angav något att gå in mellan h och m.. Det enda exemplet där som hade m - de enda exemplen där med m i det och valfritt antal h s var bara strängen m. Sedan försökte jag det igen, jag sa, "Okej, låt oss få den faktiska största gruppen här." Och då gjorde jag h.. * M, så att bara returnerar antal tecken mellan h och m.. Och om du just har börjat och tänka, "Åh, kommer okej, väl detta få mig skinka, "det tar faktiskt allt från h på Abraham Lincoln ända fram till slutet av skinka. Det är giriga, det ser h - allt detta andra text - m, och det är vad det tar i. Detta är en särskilt egregious - detta är en funktion som vi kan också anger för det inte vara girig använda andra funktioner. Men detta är något vi måste tänka på speciellt när man tittar på HTML-text, vilket är en anledning till att reguljära uttryck är svårt för HTML. För om du har en HTML öppen tagg och sedan massor av grejer i mitten och lite annat HTML stängt taggen långt senare i programmet, du har precis ätit upp en hel del av HTML-koden möjligen av misstag. 

Alla rätt - så mer specialtecken, liksom många andra språk, vi fly med snedstreck. Så vi kan använda prick för att ange alla tecken med undantag för en ny linje. Vi kan använda escape w för att ange någon bokstav. Och analogt fly d för något heltal - numeriska tecken. Vi kan ange - vi kan använda parenteser för att specificera besläktade uttryck. Så detta skulle acceptera a, b eller c. Och vi kan också ange eller alternativ för antingen a eller b. Till exempel - om vi söker flera möjligheter inom parentes vi kunde använda den eller operatören som i - så låt oss gå tillbaka till exemplet här. Och låt oss nu ta - låt oss gå tillbaka till exemplet här, och sedan ta ae - så här ska återvända - jag antar att detta är fortfarande Abraham. Så detta - om vi gör allt - bra. Så låt oss uppdatera texten här. "Abraham äter skinka medan fålla hans -. Medan fållning" Jättebra. Alla. Jättebra. Nu får vi skinka, skinka, och nertill. Medan fålla - samtidigt nynna för honom - samtidigt nynna till fåll honom. Jättebra. Samma sak. Nu är allt återvänder fortfarande bara skinka, skinka, och nertill utan att plocka upp på brum eller honom. Stor - så tänk om vi ville titta på någon som - så vi kunde också göra honom eller - vi kommer att återkomma till detta. Okej - så - okej - i positioner du kan också använda cirkumflex eller dollartecken att ange att du letar efter något i början eller slutet av en sträng. Eller i början eller slutet av ett ord. Det är ett sätt att använda detta. 

Okej - så låt oss leka med en något större textblock. Låt oss säga att denna raden här - detta uttalande här. Kraften av reguljära uttryck är att de kan specificera mönster inte bara fasta tecken. Låt oss göra - låt oss kalla detta block. Då kommer vi att läsa allt detta i. Och sedan ha en - låt oss göra alla =, så vad är några saker som vi kunde söka in här lönsamt? Vi kunde se för uttrycket örat. Inte mycket intressant. Vad sägs om det? Vi får se vad som händer. Jag gav det ett problem. Så valfritt antal saker innan du och alla. Så det borde återvända allt från början till alla åter kanske ett par gånger. Och så här har vi makt reguljära uttryck är att de kan specificera mönster inte bara tecken här är. Så hela vägen fram till den slutliga re, började den med vänster mest och var giriga. Låt oss se - vad kan vi leta efter. Jag antar att en sak om du var intresserad av att leta efter de pronomen hon och han, du kan kontrollera för s är lika med 0 eller 1 och uttrycket han, och som förmodligen inte kommer att återvända - åh, jag antar att det återvände han för att det vi ser på makt, den dagen är här. Låt oss försöka specificera att detta måste komma i början av någonting. Låt oss se om det sjunker. Så vi kan göra fett, och det vi inte får något eftersom hon och han förekommer inte i denna fras. Jättebra. Okej - så tillbaka till katten här. Så komplexa mönster skadar hjärnan. Så det är därför vi använder reguljära uttryck för att undvika dessa problem. 

Så här är några andra användbara lägen du kan leka med. Vi tittade på sökning idag, men du kan också använda match, split, findall och grupper. Så andra coola saker du kan göra med reguljära uttryck Förutom att bara leta efter mönster tar ett mönster och hålla alla matcher - dess variabler - och sedan använda dem i din kod senare. Det kan vara ganska bra. Andra saker kan räkna. Så vi kan räkna antalet förekomster av ett mönster för reguljära uttryck, och det är vad vi kan använda grupper för. Och andra lägen samt är också möjliga. Så jag vill bara prata lite mer om andra sätt du kan använda reguljära uttryck. 

Så en mer avancerad applikation är fuzzy matchning. Så om du letar efter en text för uttrycket, Julius Caesar, och du ser antingen Gaius Julius Caesar eller namnet Julius Caesar i andra språk, då kanske du också vill ge lite tyngd till dessa värden. Och om det är nära nog - om den korsar en viss tröskel - då du vill att kunna ta emot Julius Caesar. Så det finns ett par olika implementationer för att i några andra språk. Här är några andra verktyg, Regex PAL - en behändig liten app nätet till kontrollera om dina reguljära uttryck består korrekt. Det finns också fristående verktyg som du kan köra från skrivbordet som Ultra Pico, och liksom bara kokböcker. Så om du gör ett projekt som involverar massor av reguljära uttryck Detta är förmodligen den plats att gå utanför idag. Och sedan bara för att ge dig en känsla av hur vanligt det är det finns grep i Unix, har Perl inbyggd, och C finns det PCRE för C. Och sedan alla dessa andra språk har också reguljära uttryck paket som arbetar med väsentligen samma syntax som vi fick en smak av idag. PHP, Java, Ruby, och så vidare. 

Google Code Search är faktiskt värt att nämna, det är en av de relativt få program där ute som gör allmänheten att få tillgång till sin databas med reguljära uttryck. Så om du tittar på Google Code Search hittar koden Om du letar efter ett exempel på hur en funktion kan användas, Du kan använda ett reguljärt uttryck för att finna denna funktion används i alla möjliga olika ärenden. Du kan leta efter fwrite, och sedan kan du leta efter flagga skriva eller läsa om du ville ha ett exempel på fwrite som används i det fallet. Så samma sak där, och här är några referenser. Detta kommer att vara tillgängliga på nätet också, så gå framåt om du vill titta på Python, grep, Perl - du vill bara få lite inspiration eller om du vill titta mer på teorin här är några bra hoppning av platser. Tack så mycket. [CS50.TV]