[Powered by Google Translate] [Seminar: Pattern Matching mit regulären Ausdrücken] [John Mussman-Harvard University] [Dies ist CS50.-CS50.TV] Okay. Nun, jeder willkommen. Dies ist CS50 Jahr 2012. Mein Name ist John, und ich werde reden heute über reguläre Ausdrücke. Reguläre Ausdrücke ist in erster Linie ein Werkzeug, aber auch manchmal verwendet, im Code aktiv im Wesentlichen übereinstimmen Muster und Streichern. Also hier ist ein Web-Comic von xkcd. In diesem Comic gibt es ein Krimi, wo der Mörder hat gefolgt jemand im Urlaub, und die Protagonisten müssen Suche durch 200 Megabyte von E-Mails auf der Suche nach einer Adresse. Und sie sind schon aufgeben, wenn jemand, der reguläre Ausdrücke kennt - vermutlich ein Superheld - stürzt hin und schreibt einen Code und löst das Krimi. Also das wird vermutlich etwas, dass Sie ermächtigt wird, zu tun sein Nach diesem Seminar. Wir sind gerade dabei, eine kurze Einführung in die Sprache bieten und geben Ihnen genug nötige Kleingeld, um nach mehr Ressourcen auf eigene Faust. 

So reguläre Ausdrücke grundsätzlich aussehen wie diese. Dies ist ein regulärer Ausdruck in Ruby. Es ist nicht völlig anders über Sprachen. Wir haben nur auf Schrägstriche zu beginnen, und markieren Sie den regulären Ausdruck in Ruby. Und dies ist ein regulärer Ausdruck für die in E-Mail-Adresse Muster aussehen. So sehen wir auf den ersten Bit sieht für jedes alphanumerische Zeichen. Das ist, weil E-Mail-Adressen oft mit einem alphabetischen Zeichen beginnen. Und dann eines besonderen Charakter durch das @-Symbol gefolgt. Und dann das Gleiche für Domain-Namen. Und dann zwischen 2 und 4 Zeichen für die. Com schauen,. Net, und so weiter. Damit ist ein weiteres Beispiel des regulären Ausdrucks. So reguläre Ausdrücke sind Protokolle für die Suche nach Mustern in Text. Sie tun Vergleiche, Selektionen und Ersatz. Also ein drittes Beispiel findet alle Telefonnummern endet in 54 in einem Verzeichnis. Also, bevor David zerreißt der CS50 Verzeichnis konnten wir suchen ein Muster, wo wir stehen dann 3 Nummern dann am Ende Klammer 3 weitere Zahlen, einem Bindestrich, 2 Zahlen und dann 54. Und das wäre im Wesentlichen sein, wie wir kommen mit einem regulären Ausdruck für die Suche. 

So gibt es - wir haben einige Dinge in CS50 getan, die ein bisschen wie sind reguläre Ausdrücke, so - zum Beispiel - in der Datei dictionary.C für die Rechtschreibprüfung Problem Set können Sie fscanf verwendet haben in einem Wort aus dem Wörterbuch zu lesen. Und Sie können sehen, der Prozentsatz 45s ist für eine Reihe von 45 Zeichen suchen. Also es ist so etwas wie eine rudimentäre regulären Ausdrucks. Und Sie können keine 45 Zeichen, die den Gesetzesentwurf in dort und holen diejenigen up. Und dann das zweite Beispiel in der jüngsten Web-Programmierung Problem gesetzt in der Distribution Code für php wir eigentlich tun haben einen einfachen regulären Ausdruck. Und dieses ist einfach nur schauen, um zu überprüfen, ob die Webseite, die übergeben wird entspricht entweder-oder Abmeldung registrieren. PHP. Und dann wieder wahr oder falsch auf der Grundlage dieser reguläre Ausdrücke. 

Also, wenn Sie reguläre Ausdrücke verwenden? Warum sind Sie heute hier? Also Sie wollen nicht für reguläre Ausdrücke verwenden, wenn es etwas gibt, dass macht den Job für Sie noch einfacher. So XML und HTML sind eigentlich ziemlich tricky reguläre Ausdrücke für so werden wir in ein wenig sehen zu schreiben. So gibt es spezielle Parser für diese Sprachen. Sie müssen auch in Ordnung zu sein mit dem Handel offs und Genauigkeit häufig. Wenn Sie versuchen - so sahen wir einen regulären Ausdruck für eine E-Mail-Adresse, sondern sagen, Sie wollten eine bestimmte E-Mail-Adresse und die schrittweise regulären Ausdruck könnte komplexer geworden, wie es genauer geworden. Also das wäre ein Kompromiss sein. Sie müssen sicher sein, dass Sie in Ordnung machen mit dem regulären Ausdruck. Wenn Sie genau wissen, was du suchst, es könnte mehr Sinn machen bis in die Zeit und schreiben Sie eine effektivere Parser. Und schließlich gibt es ein historisches Problem mit der Regelmäßigkeit Ausdrücke und Sprachen. Reguläre Ausdrücke sind eigentlich viel stärker als reguläre Ausdrücke pro sagen in einem formalen Sinn. 

Also ich will nicht zu weit zu gehen in die formale Theorie, aber die meisten Sprachen, die wir in Code eigentlich nicht regelmäßig. Und das ist, warum reguläre Ausdrücke manchmal nicht berücksichtigt werden, dass alle sicher. Also im Grunde gibt es eine Chomsky-Hierarchie für Sprachen, und reguläre Ausdrücke werden mit Hilfe Vereinigung, Verkettung zu bauen, und die Kleene Sterne Betrieb, dass wir in ein paar Minuten zu sehen. Wenn Sie interessiert sind, in der Theorie gibt es eine ganze Menge, was dort unter der Haube. 

So eine kurze Geschichte - nur für den Rahmen hier - regelmäßige Sets kam in den 1950er Jahren, und dann hatten wir einfach, dass Redakteure eingebaut reguläre Ausdrücke - nur die Suche nach Zeichenfolgen. Grep - das ist ein Kommandozeilen-Tool - war einer der ersten sehr beliebte Tools, dass reguläre Ausdrücke in den 1960er Jahren aufgenommen. In den 80er Jahren wurde Perl gebaut - ist eine Programmiersprache, die enthält reguläre Ausdrücke sehr prominent. Und dann vor kurzem hatten wir Perl Compatible Regular Expression Protokolle grundsätzlich in anderen Sprachen, die viel von der gleichen Syntax verwenden. Natürlich ist das wichtigste Ereignis war im Jahr 2008 wo es die ersten nationalen Regular Expressions Tag, denen ich glaube, ist der 1. Juni, wenn Sie die feiern möchten. 

Wieder nur ein bisschen mehr Theorie hier. So gibt es ein paar verschiedene Möglichkeiten für den Bau von regulären Ausdrücken. Ein einfacher Weg ist, um den Ausdruck zu bauen, dass Sie zu gehen laufen auf die Saite zu interpretieren - im Grunde bauen eine kleine Mini-Programm, das wird Stücke von einem String zu analysieren und sehen, "Oh, passt das mit dem regulären Ausdruck oder nicht?" Und dann laufen die. Also, wenn Sie eine sehr kleine regulären Ausdruck haben, ist dies wahrscheinlich der effizienteste Weg, es zu tun. Und dann, wenn Sie - eine andere Möglichkeit ist es, die Rekonstruktion Ausdruck, wie Sie gehen, und das ist die Möglichkeit simulieren. Und diese frühen Versuche der regulären Ausdruck Algorithmen waren relativ einfach und relativ schnell, aber nicht über ein hohes Maß an Flexibilität. So zu tun, auch einige der Dinge, die wir gehen, um zu schauen heute haben wir zu komplexeren regulären Ausdruck zu tun Implementierungen, die möglicherweise sehr viel langsamer, so dass es etwas zu bedenken, Es gibt auch eine reguläre Ausdrücke Denial-of-Angriff Vielfalt dass das Potenzial für diese neueren Implementierungen reguläre Ausdrücke sehr komplex geworden. Und in der gleichen Sinne, dass wir in Pufferüberlauf-Attacken sahen, Sie haben Angriffe, dass die Arbeit, indem sie rekursive Schleifen, überrannt die Kapazität des Speichers. Und übrigens Regexen ist einer der offiziellen Plural von regulären Ausdrücken in Analogie zu Ochsen in der Anglo-Saxon. 

Okay, so dass der Python-Bibliothek viele von Ihnen hier in Person haben Macs, so können Sie tatsächlich ziehen Sie diese auf Ihrem Bildschirm. Reguläre Ausdrücke werden in Python gebaut. Und so Python auf Macs und auch online verfügbar unter diesem Link vorinstalliert. Also, wenn Sie sehen können Sie anhalten und sicherstellen, dass Sie Python wie wir spielen hier. Es ist ein Handbuch online, so, wenn Sie geben gerade Python in Ihren Computer Sie werden sehen, dass die Version up kommt im Terminal. Also habe ich einen Link bereitgestellt Handbuch zur Version 2 von Python sowie ein Spickzettel. Es gibt eine Version 3 von Python, aber Ihr Mac nicht unbedingt kommen mit, die vorinstalliert. Also nicht sehr unterschiedlich. Okay, so dass einige Grundlagen zur Verwendung von regulären Ausdrücken in Python. 

Also hier bin ein sehr einfacher Ausdruck verwendet, also tat ich Python import re und nahm dann das Ergebnis re.search. Und die Suche dauert 2 Argumente. Die erste ist der reguläre Ausdruck, und der zweite ist der Text, oder Zeichenfolge, die Sie analysieren möchten. Und dann habe ich ausgedruckt die result.group. Das sind also die 2 Grundfunktionen wir heute sehen, sind in das Lernen über reguläre Ausdrücke. Also einfach brechen dieser reguläre Ausdruck hier h und dann \ w und dann so m \ w nur akzeptiert alle alphabetischen Zeichen drin. So, hier sind wir für ein "h" suchen und dann noch alphabetischen Zeichen und dann m, so hier das würde passen Schinken in "Abraham Lincoln und Schinken-Sandwiches." Dies ist das Ergebnis dieser Gruppe. Eine andere Sache, die wir tun können, ist unsere vor Text-Strings in Python. Also ich denke, ich werde weitermachen und ziehen, dass hier oben. Python import re. Und wenn ich das Gleiche tun - sagen wir Text ist, "Abraham," lassen Sie uns es zu vergrößern - es geht los. Text ist "Abraham Schinken isst." Okay, und dann führen = re.search. Und dann ist unser Ausdruck kann h sein, und dann werde ich dot m zu tun. So dot dauert nur jedes Zeichen, das nicht ist eine neue Linie einschließlich Zahlen, Prozent-Zeichen, so etwas. Und dann Text - boom - und dann result.group--ja. Also das ist nur, wie man grundlegende Funktionalität hier umzusetzen. So verrückt text - - Wenn wir einen Text Ring, hatte inbegriffen sagen viele Backslashes und Streicher innen und Dinge, die wie Escape-Sequenzen aussehen könnte, dann werden wir wahrscheinlich wollen die rohe Texteingabe verwenden, um sicherzustellen, dass akzeptiert wird. Und das sieht einfach so. Also, wenn wir für jeden von ihnen in dort suchten wir sollten nichts finden. Aber das ist, wie Sie es umsetzen; kurz vor der Zeichenfolge der reguläre Ausdruck Sie legte den Brief r. 

Okay, also lasst uns weitermachen. Alles klar - so lassen Sie uns ein paar sich wiederholende Muster hier. So eine Sache, die Sie tun möchten, ist Dinge wiederholen wie Sie durch Textsuche. So zu tun, eine beliebige Anzahl von b gefolgt - Sie ab *. Und dann gibt es noch eine Reihe anderer Regeln zu. Und Sie können sehen alle diese auf, ich werde nur durch einige der laufen am häufigsten diejenigen verwendet. So ab + ist ein von einem N größer als 0 von b gefolgt. ab? ist, gefolgt von 0 oder 1 b. ab {N} ist ein von N aus b gefolgt, und dann so weiter. Wenn Sie 2 Zahlen in den geschweiften Klammern haben Sie das Festlegen einer Reihe das kann möglicherweise abgestimmt. So werden wir mehr auf ein paar sich wiederholende Muster in einer Minute zu suchen. Also 2 Dinge im Auge zu behalten, wenn Sie diese Pattern-Matching-Tools hier. Sagen Sie so wollen wir am hm von aussehen, "Abraham Lincoln macht Schinken-Sandwiches." Also änderte ich Abraham Lincoln den Namen Abraham. Und jetzt sind wir für das, was von dieser Suchfunktion zurückgegeben suchen, und es gibt nur Schinken in diesem Fall. Und sie tut das, weil Suche nur natürlich ist der am weitesten links Warteschlange. Und alle reguläre Ausdrücke, sofern Sie nichts anderes angeben wird das tun. Wenn wir alle finden wollten gibt es eine Funktion dafür - finden Sie alle. Also das könnte wie alle re.findall = ('h.m', Text) suchen und dann all.group (). All produziert sowohl Schinken und Schinken, in diesem Fall sowohl der Saiten in Abraham jeder Schinken. Damit ist eine weitere Option. 

Great. Die andere Sache im Auge zu behalten ist, dass reguläre Ausdrücke die größte nehmen intuitiv. Lassen Sie uns an diesem Beispiel zu sehen. Wir haben das am weitesten links Suche hier, und dann habe ich versucht, eine größere Suche Verwendung des Kleene Stern-Operator. Also für "Abraham Lincoln macht Schinken-Sandwiches," und ich bekam nur zurück m als Ergebnis. Der Grund für diesen Fehler war, dass ich eine beliebige Anzahl von genommen haben h ist, weil ich nicht alles geben, um in zwischen h und m gehen. Das einzige Beispiel, dass es m hatte - die einzigen Beispiele gibt es mit m in und eine beliebige Anzahl von h die waren einfach die Zeichenfolge m. Dann versuchte ich es wieder, ich sagte: "Okay, lassen Sie uns die tatsächliche größte Gruppe hier." Und dann habe ich h. * M, so dass nur gibt eine beliebige Anzahl von Zeichen zwischen h und m. Und wenn Sie gerade erst anfangen und denken: "Oh, okay, auch dies wird mich Schinken, "es tatsächlich dauert alles aus dem h in Abraham Lincoln den ganzen Weg bis zum Ende des Schinkens. Es ist gierig, es sieht h - all diese anderen Text - m, und das ist, was es nimmt in. Dies ist eine besonders krasse - dies ist ein Feature, das wir können auch geben für sein nicht gierig mit anderen Funktionen. Aber das ist etwas, das wir im Auge behalten vor allem wenn man HTML-Text, ist das ein Grund, dass reguläre Ausdrücke sind für HTML schwierig. Denn wenn Sie ein HTML-Tag geöffnet und dann viele Sachen in der Mitte und dann einige andere HTML-Tag geschlossen viel später in das Programm, Sie haben gerade einen großen Teil Ihrer HTML-Code möglicherweise versehentlich gegessen. 

Alle Recht - so mehr Sonderzeichen, wie viele andere Sprachen, wir entfliehen mit dem Schrägstrich. So können wir den Punkt, um jedes Zeichen außer für eine neue Zeile zu spezifizieren. Wir können die Flucht w jede alphabetischen Zeichen angeben. Und analog Flucht d für integer - numerische Zeichen. Wir können angeben - wir können Klammern verwenden, um verwandte Ausdrücke angeben. So würde dies akzeptieren, b oder c. Und wir können auch angeben, oder Optionen für entweder a oder b. Zum Beispiel - wenn wir für mehrere Möglichkeiten suchen in Klammern wir die oder Betreiber wie in verwenden - so lassen Sie uns zurück zu diesem Beispiel hier. Und nun lassen Sie uns - lassen Sie uns zurück zu diesem Beispiel hier, und dann ae nehmen - so sollte dies zurück - ich denke, das ist noch Abraham. Also das - wenn wir alle tun - großartig. Also lassen Sie uns den Text hier aktualisieren. "Abraham Schinken isst, während seine Säumen -. Während Säumen" Great. All. Great. Jetzt bekommen wir Schinken, Schinken und Saum. Während Säumen - während summte ihm - während summt zu säumen ihn. Great. Dasselbe. Nun kehrt gerade noch Schinken, Schinken und Saum ohne Kommissionierung bis auf das Brummen oder ihn. Toll - so was ist, wenn wir entweder sehen wollte, dass - so konnten wir auch tun ihn oder - wir kommen darauf zurück. Ok - so - alles in Ordnung - in Positionen, die Sie können auch den Cursor oder das Dollarzeichen um anzugeben, dass Sie etwas am Anfang oder Ende einer Zeichenkette suchen. Oder der Anfang oder das Ende eines Wortes. Das ist eine Möglichkeit, dass zu verwenden. 

Ok - so lassen Sie uns spielen, um mit einem etwas größeren Textblock. Lassen Sie uns sagen, diese Zeile hier - diese Aussage hier. Die Macht des regulären Ausdrucks ist, dass sie Muster angeben nicht nur Zeichen fixiert. Lassen Sie uns - nennen wir diesen Block. Dann lesen wir alle, dass in. Und dann haben ein - lassen Sie uns alle =; so was sind einige Dinge, die wir in hier gewinnbringend? Wir konnten für die Expression Ohr schauen. Nicht sehr interessant. Wie wäre es damit? Wir werden sehen, was passiert. Ich gab es ein Problem. So beliebige Anzahl von Dingen vor der Wiederverwendung und alle. Also das sollte zurückkehren alles von Anfang an bis zu allen re vielleicht ein paar Mal. Und dann haben wir hier die Leistung von regulären Ausdrücken ist, dass sie können Muster geben nicht nur Zeichen hier sind. Also den ganzen Weg bis zum Finale wieder, begann es mit dem am weitesten links und war gierig. Lassen Sie uns sehen - was sonst könnten wir suchen. Ich denke, eine Sache, wenn Sie Interesse an der Suche nach den Pronomen waren sie und er, Sie könnte für s gleich 0 oder 1 überprüfen und der Ausdruck, den er, und das wird wahrscheinlich nicht zurückkehren - oh, ich denke, es kehrte er, weil wir dort an der Macht, an diesem Tag auf der Suche sind, sind hier. Lassen Sie uns versuchen, dass diese Angabe am Anfang von etwas kommen muss. Lassen Sie uns sehen, ob das wieder aus. So können wir tun, Fett, und da haben wir nicht bekommen nichts, weil sie und er nicht in dieser Phrase auftreten. Great. Ok - so zurück auf die Katze hier. So komplexe Muster zu verletzen das Gehirn. Also das ist, warum wir reguläre Ausdrücke, um diese Probleme zu vermeiden verwenden. 

Also hier sind einige andere nützliche Modi spielen, um mit. Wir schauten Suche heute, aber Sie können auch Spiel, Split, findall und Gruppen. So andere coole Dinge, die Sie mit regulären Ausdrücken neben nur tun können Suche nach Mustern nimmt ein Muster und hält alle Spiele - seine Variablen - und dann mit denen in Ihrem Code später auf. Das kann sehr hilfreich sein. Andere Dinge werden könnten zählen. So können wir die Anzahl der Instanzen eines Muster eines regulären Ausdrucks, und das ist, was können wir für Gruppen verwenden. Und anderen Modi sind möglich. Also ich will nur ein bisschen mehr reden über andere Möglichkeiten, wie Sie reguläre Ausdrücke verwenden können. 

So eine erweiterte Anwendung ist in Fuzzy Matching. Also, wenn Sie für einen Text für den Ausdruck, Julius Caesar suchen, und Sie sehen entweder Gaius Julius Caesar oder den Namen Julius Caesar in anderen Sprachen, dann könnten Sie auch wollen, um etwas Gewicht zu diesen Werten zuordnen. Und wenn es in der Nähe genug - wenn es eine bestimmte Schwelle überschreitet - dann wollen in der Lage sein, um Julius Caesar zu akzeptieren. So gibt es ein paar verschiedene Implementierungen für die in einigen anderen Sprachen. Hier sind einige andere Tools, Regex Pal - ein handliches, kleines App online überprüfen, ob Ihre reguläre Ausdrücke richtig zusammengesetzt sind. Es gibt auch Standalone-Tools, die Sie von Ihrem Desktop ausgeführt werden können wie Ultra-Pico, und so gut wie nur Kochbücher. Also, wenn Sie ein Projekt zu machen, dass eine Tonne von regulären Ausdrücken beinhaltet Dies ist wahrscheinlich der Ort, um außerhalb des Anwendungsbereichs von heute gehen. Und dann nur, um Ihnen ein Gefühl dafür, wie es üblich gibt es in Unix grep, hat Perl eingebaut, und C gibt es PCRE für C. Und dann all diese anderen Sprachen auch reguläre Ausdrücke Pakete das arbeiten mit im Wesentlichen der gleichen Syntax bekamen wir einen Vorgeschmack von heute. PHP, Java, Ruby, und so weiter. 

Google Code Search ist eigentlich erwähnenswert, es ist eines der relativ wenige Anwendungen gibt, die die Öffentlichkeit zugreifen können seine Datenbank mit regulären Ausdrücken. Also, wenn Sie auf Google Code Search suchen finden Sie Code wenn Sie für eine Instanz, wie eine Funktion verwendet werden könnte suchen, Sie können einen regulären Ausdruck, um diese Funktion ist in allen möglichen verschiedenen Fällen verwendet zu finden. Sie könnten für fwrite suchen, und dann könnte man für die Flagge von Schreib sehen oder lesen wenn man wollte ein Beispiel für fwrite in diesem Fall verwendet werden. Also die gleiche Sache gibt, und hier sind einige Referenzen. Dies wird auch online verfügbar sein, so gehen nach vorne, wenn Sie wollen an Python, grep, Perl aussehen - Sie wollen einfach nur etwas Inspiration zu bekommen oder wenn Sie mehr über die Theorie hier schauen wollen, sind einige gute jumping off Plätze. Vielen Dank. [CS50.TV]