[Powered by Google Translate] [Seminar: Het matchen met Regular Expressions] [John Mussman-Harvard University] [Dit is CS50.-CS50.TV] Oke. Nou, welkom iedereen. Dit is CS50 2012. Mijn naam is John, en ik zal praten vandaag over reguliere expressies. Reguliere expressies is voornamelijk een hulpmiddel, maar soms ook gebruikt in code actief te wezen overeenkomen patronen en strijkers. Dus hier is een web comic van xkcd. In deze strip is er een moord mysterie waar de moordenaar heeft volgde iemand op vakantie, en de protagonisten moeten zoeken in 200 megabyte aan e-mails op zoek naar een adres. En ze over te geven als iemand die reguliere expressies weet - vermoedelijk een superheld - swoops naar beneden en schrijft wat code en lost het moordmysterie. Dus vermoedelijk dat zal iets zijn dat je wordt gemachtigd zijn om te doen Na dit seminar. We gaan gewoon een beknopte inleiding te geven in de taal en geven u voldoende middelen om te gaan na meer middelen op uw eigen. 

Dus reguliere expressies lijken in principe net als dit. Dit is een reguliere expressie in Ruby. Het is niet erg verschillend over talen. We moeten gewoon op slashes te beginnen en markeer de reguliere expressie in Ruby. En dit is een reguliere expressie te zoeken in e-mailadres patroon. Zo zien we in de eerste bit ziet er voor een alfanumeriek teken. Dat komt omdat e-mailadressen moeten vaak beginnen met een letterteken. En dan geen speciale teken, gevolgd door het @-symbool. En dan hetzelfde voor domeinnaam. En dan tussen de 2 en 4 karakters om te zoeken naar het. Com,. Net, en ga zo maar door. Dus dat is een ander voorbeeld van de reguliere expressie. Dus reguliere expressies zijn protocollen voor het ontdekken van patronen in de tekst. Ze doen vergelijkingen, selecties, en vervangingen. Dus een derde voorbeeld is het vinden van alle telefoonnummers eindigend in 54 in een directory. Dus voordat David scheurt de CS50 directory we konden zoeken een patroon waar we haakjes dan 3 nummers eindigen dan haakjes, 3 meer nummers, een streepje, 2 cijfers, en daarna 54. En dat zou in wezen zijn hoe we komen met een reguliere expressie om te zoeken naar dat. 

Dus er zijn - we hebben een aantal dingen gedaan in CS50 die zijn een beetje zoals reguliere expressies, dus - bijvoorbeeld - in het dictionary.C bestand voor de spellingcontrole probleem set u heeft gebruikt fscanf te lezen in een woord uit het woordenboek. En je kunt zien is het percentage 45s is op zoek naar een string van 45 tekens. Dus het is een beetje zoals een rudimentaire reguliere expressie. En u kunt elk 45 tekens dat het wetsvoorstel past in daar hebben en pak deze op. En dan het tweede voorbeeld in de meest recente web programmeren probleem in de distro code voor php we eigenlijk wel een eenvoudige reguliere expressie. En deze is gewoon op zoek om te controleren of de webpagina die wordt doorgegeven in overeenkomt ofwel inloggen of uitloggen registreren. PHP. En vervolgens terug te keren waar of onwaar zijn gebaseerd op die reguliere expressies voor zoeken. 

Dus als je reguliere expressie gebruiken? Waarom ben je hier vandaag? Dus je wilt niet reguliere expressie gebruiken wanneer er iets dat doet het werk voor u nog makkelijker. Dus XML en HTML zijn eigenlijk behoorlijk lastig schrijven van reguliere expressies voor zoals we zullen zien in een klein beetje. Dus er zijn speciale parsers voor die talen. Je moet ook goed met de trade offs en nauwkeurigheid te vaak. Als je probeert - zo zagen we een reguliere expressie voor een e-mailadres, maar zeggen dat je wilde een specifiek e-mailadres en geleidelijk aan de reguliere expressie wellicht complexer geworden als het werd nauwkeuriger. Zodat men de handel af zou zijn. Je moet er zeker van zijn dat u in orde maken met de reguliere expressie. Als je precies weet wat je zoekt is het misschien zinvoller te zetten in de tijd en schrijf een meer effectieve parser. En ten slotte is er een historisch probleem met de regelmaat van uitdrukkingen en talen. Reguliere expressies zijn eigenlijk veel krachtiger dan reguliere expressies per zeggen in formele zin. 

Dus ik wil niet te ver te gaan in de formele theorie, maar de meeste talen die code in feite zijn we niet regelmatig. En dit is waarom reguliere expressies soms niet worden beschouwd dat alles veilig is. Dus eigenlijk is er een Chomsky hiërarchie voor talen, en reguliere expressies worden opgebouwd met behulp unie, aaneenschakeling, en de Kleene ster operatie die we zullen zien in een paar minuten. Als u geïnteresseerd bent in theorie is er heel veel gebeurt er onder de motorkap. 

Dus een korte geschiedenis - alleen voor de context hier - reguliere sets kwam in de jaren 1950, en toen moesten we eenvoudige editors die opgenomen reguliere expressies - alleen het zoeken naar strings. Grep - dat is een command-line tool - was een van de eerste zeer populaire tools die opgenomen reguliere expressies in de jaren 1960. In de jaren '80, werd Perl gebouwd - is een programmeertaal die bevat reguliere expressies erg prominent. En dan meer recent hebben we Perl compatible reguliere expressie had protocollen principe in andere talen die veel van dezelfde syntax. Natuurlijk is de belangrijkste gebeurtenis was in 2008 waar was de eerste Nationale Regular Expressions Dag, waarvan ik denk dat is 1 juni als u wilt vieren dat. 

Nogmaals, net een beetje meer theorie hier. Dus er zijn een paar verschillende manieren om het maken van reguliere expressies. Een eenvoudige manier is om de expressie te bouwen die je gaat draaien op de snaar te interpreteren - in principe de bouw van een kleine mini-programma dat analyseert stukjes van een string en zie, "Oh, doet dit aan de reguliere expressie of niet? ' En dan lopen die. Dus als u een zeer kleine reguliere expressie, dit is waarschijnlijk de meest efficiënte manier om het te doen. En dan als je - een andere optie is om te blijven reconstructie van de expressie als je gaat, en dat is het simuleren mogelijkheid. En deze vroege pogingen tot reguliere algoritmes expressie waren relatief eenvoudig en relatief snel, maar had niet veel flexibiliteit. Dus om zelfs sommige van de dingen die we gaan kijken naar vandaag hebben we moesten meer complexe reguliere expressie doen implementaties die potentieel veel langzamer, dus dat is iets om in gedachten te houden Er is ook een reguliere expressies ontkenning van aanval variëteit dat het potentieel voor deze nieuwere implementaties van exploiteren reguliere expressies tot zeer complex geworden. En in vrijwel dezelfde zin dat we in buffer overflow-aanvallen zag, je moet aanvallen die werken door het maken van recursieve lussen die een overschrijding van de capaciteit van het geheugen. En trouwens Regexen is een van de officiële meervouden van reguliere expressie naar analogie van ossen in de Angelsaksische. 

Oke, dus de Python Library velen van u hier in persoon hebben Macs, dus je kunt eigenlijk trekt dit op uw scherm. Reguliere expressies zijn ingebouwd in Python. En zo Python is voorgeladen op Macs en ook online beschikbaar op deze link. Dus als je je in de gaten kunt pauzeren en zorg ervoor dat je Python als we spelen hier rond. Er is een handleiding online, dus als je typt gewoon Python in uw computer je zult zien dat de versie komt in de terminal. Dus heb ik een link naar de handleiding voor versie 2 van Python, evenals een spiekbriefje. Er is een versie 3 van Python, maar uw Mac niet noodzakelijkerwijs komen met die voorgeladen. Dus niet erg verschillend. Oke, dus een aantal basisprincipes van het gebruik van reguliere expressies in Python. 

Dus hier heb ik een heel eenvoudige uitdrukking, dus ik deed Python import re en nam toen het resultaat van re.search. En de zoektocht duurt 2 argumenten. De eerste is de reguliere expressie, en de tweede is de tekst of tekenreeks die u wilt analyseren. En vervolgens afgedrukt ik uit de result.group. Dus dit zijn de 2 basisfuncties gaan we vandaag te zien in het leren over reguliere expressies. Dus gewoon afbreken van deze reguliere expressie hier h en vervolgens \ w en vervolgens op m zo \ w accepteert zomaar een letter uit het alfabet in. Dus hier zijn we op zoek naar een "h" en dan nog een letter uit het alfabet en dan m, dus even dat zou overeenkomen met ham in, "Abraham Lincoln en ham broodjes." Dit is het gevolg van die groep. Een ander ding dat we kunnen doen is gebruik maken van ons vóór snaren van tekst in Python. Dus ik denk dat ik zal doorgaan en trek die omhoog hier. Python import re. En als ik hetzelfde doen - laten we zeggen tekst is, "Abraham," laat ons in te zoomen - daar gaan we. De tekst is: "Abraham eet ham." Oke, en dan resulteren = re.search. En dan is onze expressie kan worden h, en dan zal ik de dot m doen. Dus dot duurt slechts een teken dat geen een nieuwe lijn, waaronder nummers, percentage tekenen, iets dergelijks. En dan tekst - boom - en vervolgens result.group--ja. Dus dat is gewoon hoe je hier implementeren basisfunctionaliteit. Als we een tekst ring die - dat gekke tekst - Inclusief zeggen veel backslashes en strijkers binnen en dingen die er zou kunnen uitzien escape sequences, dan zijn we waarschijnlijk willen de ruwe tekstinvoer gebruiken om ervoor te zorgen dat wordt geaccepteerd. En dat ziet er gewoon zo. Dus als we zochten elk van hen daar moeten we niets vinden. Maar dat is hoe je het zou voeren; net voor de string van de reguliere expressie die u de letter r gezet. 

Oke, dus laten we blijven gaan. Oke - dus laten we eens kijken naar een paar herhalende patronen hier. Dus een ding dat je wilt doen is herhalen dingen als u op zoek bent via tekst. Dus om te doen een gevolgd door een willekeurig aantal b - je doet ab *. En dan zijn er nog een reeks andere regels ook. En u kunt al deze omhoog te kijken, ik zal gewoon lopen door een aantal van de meest gebruikte degenen. Dus ab + is een, gevolgd door een N groter dan 0 of b. ab? is gevolgd door 0 of 1 b. ab {N} is een gevolgd door N van b, en dan zo verder. Als je 2 nummers in de accolades u een bereik dat kan eventueel aangepast. Dus zullen we meer kijken naar een paar herhalende patronen in een minuut. Dus 2 dingen in gedachten te houden bij het gebruik van deze pattern matching gereedschappen hier. Dus zeggen dat we willen kijken naar de hm van, "Abraham Lincoln maakt ham sandwiches." Dus ik veranderde de naam van Abraham Lincoln aan Abraham. En nu zijn we op zoek naar wat wordt geretourneerd door deze zoekfunctie, en dat het alleen resultaten ham in dit geval. En het doet dat omdat search gewoon van nature neemt de meest linkse wachtrij. En alle reguliere expressies, tenzij u anders opgeeft zal dat doen. Als we wilden allemaal vinden is er een functie voor die - allemaal vinden. Dus dat kon gewoon uitzien als alle = re.findall ('h.m', tekst) en dan all.group (). Alle produceert zowel ham en ham, in dit geval zowel van de snaren in Abraham elke ham. Dat is precies een optie. 

Geweldig. Het andere ding om in gedachten te houden is dat reguliere expressies nemen het grootste intuïtief. Laten we eens kijken naar dit voorbeeld. Wij deden dat meest linkse zoeken hier, en toen probeerde ik een grotere zoekopdracht met behulp van de Kleene ster operator. Dus voor, "Abraham Lincoln maakt broodjes ham," en ik alleen terug m als gevolg. De reden voor die fout was dat ik een aantal van had kunnen nemen h is omdat ik niet iets te gaan tussen h en m te geven. Het enige voorbeeld dat er m had - de enige voorbeelden daar met m erin en een willekeurig aantal uur waren alleen de snaarmhoge. Daarna probeerde ik het opnieuw, ik zei: 'Oke, laten we hier de werkelijke grootste groep. " En toen deed ik h. * M, zodat die net terugkeert willekeurig aantal tekens tussen h en m. En als je net begint en denken, "Oh, oke, ook dit zal Begrijp me ham, "het duurt eigenlijk alles van de h in Abraham Lincoln helemaal tot aan het einde van de ham. Het is hebzuchtig, het ziet h - al deze andere tekst - m, en dat is wat er nodig is in Dit is een bijzonder ongehoorde - dit is een functie die we kunnen ook op te geven voor het niet hebzuchtig te zijn met andere functies. Maar dit is iets wat we moeten vooral in gedachten te houden als we kijken naar HTML tekst, dat is een reden dat reguliere expressies zijn moeilijk voor HTML. Want als je een HTML-tag geopend en vervolgens veel dingen in het midden en dan sommige andere HTML gesloten tag veel later in het programma, je net gegeten een hoop van uw HTML-code eventueel per ongeluk. 

Oke - dus meer speciale tekens, net als veel andere talen, We ontsnappen met behulp van de slash. Dus we kunnen de stip gebruiken om elk karakter te geven met uitzondering van een nieuwe lijn. We kunnen gebruik maken van de escape w om elke letter uit het alfabet geven. En naar analogie ontsnapping d voor elk geheel getal - numeriek karakter. We kunnen specificeren - kunnen we haakjes gebruiken om soortgelijke uitdrukkingen geven. Het zou dus a, b of c te accepteren. En we kunnen ook opties voor zowel a of b te specificeren of. Bijvoorbeeld - als we waren op zoek naar meerdere mogelijkheden tussen haakjes kunnen we het of operator te gebruiken als in - dus laten we teruggaan naar dit voorbeeld hier. En nu laten we - laten we teruggaan naar dit voorbeeld hier, en vervolgens neem ae - dus dit zou terugkeren - ik denk dat dit nog steeds Abraham. Dus dit - als we allemaal - geweldig. Dus laten we de tekst hier te werken. "Abraham eet ham terwijl zomen zijn -. Terwijl omzomen" Geweldig. Alle. Geweldig. Nu krijgen we ham, ham, en zoom. Terwijl zomen - terwijl neuriën hem - terwijl neuriën tot zoom hem. Geweldig. Hetzelfde. Nu alles keert nog net ham, ham, en zoom zonder het oppakken van de brom-of het hem. Geweldig - dus wat als we wilden om te kijken naar een van beide dat - dus we konden ook doen hem of - we zullen terugkomen naar dat. Oke - dus - oke - op de posities kunt u ook het dakje of het dollarteken gebruiken om aan te geven dat u op zoek bent naar iets aan het begin of het einde van een string. Of het begin of het einde van een woord. Dat is een manier om dat te gebruiken. 

Oke - dus laten we spelen met een iets grotere blok tekst. Laten we hier zeggen deze rij - deze verklaring hier. De kracht van reguliere expressies is dat ze patronen kunt opgeven niet alleen gefixeerd karakters. Laten wij - laten wij noemen dit blok. Dan zullen we dat allemaal in te lezen En dan een - laat ons allen =; dus wat zijn sommige dingen die we zouden kunnen zoeken in hier winstgevend? We konden kijken naar de expressie oor. Niet erg interessant. Hoe zit dat? We zullen zien wat er gebeurt. Ik gaf het een probleem. Dus een aantal dingen alvorens opnieuw en alles. Dus dat moet alles van het begin tot alle re misschien een paar keer terug. En dan hebben we hier de kracht van reguliere expressies is dat ze kunnen patronen specificeren niet alleen personages hier zijn. Dus de hele weg tot aan de uiteindelijke re, het begon met de meest linkse en was hebberig. Laat ons zien - wat anders zou zoeken we naar. Ik denk dat een ding als je geïnteresseerd bent in het zoeken naar de voornaamwoorden waren zij en hij, je zou kunnen controleren s gelijk is aan 0 of 1 en de uitdrukking hij, en dat is waarschijnlijk niet van plan om terug te keren - oh, ik denk dat hij terug, want er zijn we op zoek naar de kracht, die dag, hier zijn. Laten we proberen te specificeren dat dit moet komen aan het begin van iets. Laten we zien of dat druppels uit. Dus kunnen we vet doen, en daar hebben we niets krijgen, omdat zij en hij niet voorkomen in deze zin. Geweldig. Oke - dus terug naar de kat hier. Dus complexe patronen wordt het kwetsen van de hersenen. Dus dat is waarom we gebruik van reguliere expressies om deze problemen te voorkomen. 

Dus hier zijn enkele andere handige functies heeft die u kunt spelen met. We keken naar zoeken vandaag, maar je kunt ook gebruik maken van wedstrijd, split, findall, en groepen. Zodat andere leuke dingen die je kunt doen met reguliere expressies dan alleen op zoek naar patronen is het nemen van een patroon en houdt alle wedstrijden - zijn variabelen - en vervolgens met behulp van deze in uw code later. Dat kan heel nuttig zijn. Andere dingen kunnen worden tellen. Dus we kunnen het aantal exemplaren van een reguliere expressie patroon te tellen, en dat is wat we groepen kunnen gebruiken voor. En andere modes, maar zijn ook mogelijk. Dus ik wil gewoon een beetje meer praten over andere manieren waarop u kunt gebruik maken van reguliere expressies. 

Dus een meer geavanceerde toepassing is in fuzzy matching. Dus als u op zoek bent naar een tekst voor de expressie, Julius Caesar, en je ziet ofwel Gaius Julius Caesar of de naam van Julius Caesar in andere talen, dan kun je misschien ook wat gewicht toe te kennen aan die waarden. En als het dichtbij genoeg - als het kruist een bepaalde drempel - dan wil je kunnen Julius Caesar accepteren. Dus er zijn een paar verschillende implementaties voor dat in een paar andere talen ook. Hier zijn een aantal andere instrumenten, Regex Pal - een handige kleine app online aan controleren of uw reguliere expressies correct zijn samengesteld. Er zijn ook standalone tools die u kunt uitvoeren vanaf uw bureaublad zoals Ultra Pico, en zo goed als alleen maar kookboeken. Dus als je bent bezig met een project dat een ton van reguliere expressies impliceert Dit is waarschijnlijk de plaats buiten het bereik van om te gaan. En dan alleen maar om u een idee van hoe vaak het is geven er grep in Unix, Perl heeft ingebouwd, en C is er PCRE voor C. En dan al die andere talen hebben ook reguliere expressie pakketten die werken met in essentie dezelfde syntax kregen we een voorproefje van vandaag. PHP, Java, Ruby, enzovoort. 

Google Code Search is eigenlijk het vermelden waard, het is een van de relatief weinig applicaties die er zijn dat het publiek in staat om toegang te krijgen de database met behulp van reguliere expressies. Dus als je kijkt op Google Code Search kunt u code te vinden als u op zoek bent naar een voorbeeld van hoe een functie zou kunnen worden gebruikt, kunt u een reguliere expressie gebruiken om die functie wordt gebruikt in allerlei verschillende zaken vinden. Je zou kunnen kijken voor fwrite, en dan kon je kijken naar de vlag van schrijf-of lees Als u een voorbeeld van fwrite worden gebruikt in dat geval wilden. Dus het zelfde ding daar, en hier zijn enkele referenties. Dit zal online beschikbaar zijn zo goed, dus gaan vooruit als je wilt kijken naar Python, grep, Perl - wil je gewoon wat inspiratie op te doen of als u wilt meer hier kijken naar de theorie zijn een aantal goede jumping off plaatsen. Heel hartelijk bedankt. [CS50.TV]