Wenn Sie rote Kirschen essen, können Sie blaue Geister essen. Die Idee, dass Ableitungen verwendet werden können, um einen Algorithmus zum Abgleich regulärer Ausdrücke zu erstellen, ist fast genauso lächerlich. Lassen Sie mich erklären, wie dieser Algorithmus funktioniert und wie er sich auf Pac-Man bezieht.

1964 veröffentlichte Brzozowski den ersten Artikel über Ableitungen regulärer Ausdrücke . Dies ist bei weitem einer meiner Lieblingsalgorithmen. Unter Verwendung von Ableitungen regulärer Ausdrücke können wir einen Algorithmus implementieren, um den Abgleich regulärer Ausdrücke durchzuführen. Dieser Algorithmus ist sehr:

• einfach
• funktionell
• einfach erweiterbar mit eigenen Antrieben

In diesem Artikel zeige ich Ihnen, wie wir eine Zeichenfolge mit einem regulären Ausdruck abgleichen können, indem wir nur zwei reine Funktionen und einige Pac-Man-Analogien verwenden. Wenn Sie es vorziehen, können Sie sich das folgende Video ansehen, anstatt den Artikel zu lesen, da es dasselbe Material behandelt:

Zusammenfassung regulärer Ausdrücke

Lassen Sie uns zunächst einen kurzen Überblick über reguläre Ausdrücke geben, um sicherzustellen, dass wir uns auf derselben Seite befinden. Der Ausdruck a(a|b)*stimmt mit einer Zeichenfolge überein, die mit einem beginnt a, gefolgt von einer beliebigen Anzahl von a's und b's.

• Die Zeichenfolge abwird übereinstimmen a(a|b)*. Wir zeigen dies mit einem essbaren blauen Geist an.
• Die Zeichenfolge aabbbapasst auch, a(a|b)*da sie mit einem beginnt aund von mehreren a's und b's gefolgt wird.
• Als nächstes stimmt die Zeichenfolge acnicht überein a(a|b)*, da die Regex mit keinem übereinstimmt cund unsere Regex keine Übereinstimmung mit Teilzeichenfolgen durchführt. Wir werden dies mit einem roten Geist anzeigen, der den Pac-Man jagt.
• Schließlich stimmt die Zeichenfolge baauch nicht überein, a(a|b)*weil sie nicht mit einem beginnt a.

Überblick über den Algorithmus

Bevor wir uns mit den Details befassen, wollen wir uns einen Überblick darüber verschaffen, wie dieser Algorithmus funktioniert. Ich habe ein seltsames Pac-Man-Spiel entwickelt, bei dem Sie die Geister nur essen können, wenn Sie die Früchte in einer Reihenfolge essen, die dem Regex entspricht. Unser Pac-Man repräsentiert die Regex aba*. Es hat die folgende Reihe von Früchten zu essen: einen Apfel, dann eine Banane und dann einen Apfel: aba.

1. Als wir beginnen, verfolgt uns der Geist und der reguläre Ausdruck, den wir noch finden müssen, ist aba*.
2. Wir essen den ersten Apfel, und der reguläre Ausdruck, den wir jetzt abgleichen müssen, ist ba*. Der Geist jagt uns immer noch, da die Frucht, die wir bisher gegessen haben, der Apfel, nicht zur Regex passt.
3. Als nächstes essen wir die Banane. Die Regex, die wir dann noch abgleichen müssen, ist a*. Jetzt rennt der Geist davon, weil er technisch gesehen abschon passt aba*.
4. Wir können versuchen, den Geist zu essen oder einen anderen Apfel zu essen, in diesem Fall ist der reguläre Ausdruck, den wir noch finden müssen, immer noch a*. Der Geist rennt immer noch davon, da abaer auch mit dem regulären Ausdruck übereinstimmt aba*.

Hier ist eine weitere Funktion am Werk. Die Funktion prüft, ob der Geist den Pac-Man jagt oder ob der Pac-Man bereits die Regex gefunden hat und den Geist jagt. Diese Funktion wird Nullable-Funktion genannt; Es prüft, ob der übrig gebliebene Regex mit der leeren Zeichenfolge übereinstimmt. Das ist möglich, denn wenn der übrig gebliebene Regex mit dem leeren String übereinstimmt, muss die Frucht, die er gegessen hat, bereits ausgereicht haben, um den Regex zu befriedigen.

Derivative-Matching-Algorithmus

Das bedeutet, dass wir nur zwei Funktionen benötigen, um den Ableitungs-Matching-Algorithmus zu schreiben:

1. die Ableitungsfunktion
2. die Nullable-Funktion

Einer in Golang für die imperativen Programmierer:

und ein weiteres in Haskell für funktionale Programmierer:

Diese beiden Funktionen sind gleichwertig und nur in unterschiedlichen Programmierstilen geschrieben. Im Haskell-Code foldlerledigt das in anderen Sprachen auch fold left oder Reduce genannt die Arbeit der for-Schleife für Sie. Außerdem brauchen wir in Haskell keine Kommas, um Parameter an Funktionen zu übergeben; Da die Funktionsanwendung die häufigste Operation in einer funktionalen Programmiersprache ist, verwenden wir Leerzeichen, um Parameter abzugrenzen.

Lassen Sie uns nun näher darauf eingehen, wie die Nullable- und Ableitungsfunktionen implementiert werden.

Pac-Man Origin Story Exkurs

Aber bevor wir das tun, weiß ich nicht, ob Sie sich jemals über die Ursprungsgeschichte von Pac-Man gewundert haben. Ich behaupte, es gab kein Atommüllfass, in das Pac-Man gefallen ist, was dazu führte, dass Pac-Man die Macht erlangte, Geister zu essen. Die Logik ist viel einfacher.

Pac-Man ist eine Frucht! Wenn Pac-Man andere Früchte isst, ist Pac-Man ein Kannibale. Wenn Sie also jemals von einem Geist verfolgt werden, müssen Sie etwas Menschenfleisch essen, und der Geist sollte zumindest vorübergehend vor Ihnen davonlaufen. Nun, ich habe das selbst nicht ausprobiert, aber die Logik scheint vernünftig zu sein.

Dies erklärt, warum Zombies immer Menschen jagen. Wie David Attenborough einmal sagte:

„Die Zombies, die uns verfolgen, werden selbst von Geistern verfolgt, die wir nicht sehen können. Nachdem die Zombies etwas von unserem menschlichen Fleisch gegessen haben, werden Sie sehen, wie sie das seltsame Verhalten zeigen, in die Luft zu kauen, das ist der Zombie, der den Geist frisst, der ihn zuvor gejagt hat.“

Grundlegende Operatoren

Die Implementierung der nullbaren und abgeleiteten Funktionen erfordert, dass wir zuerst die grundlegenden Operatoren definieren, die in unseren regulären Ausdrücken verfügbar sind.

Wir können uns einen regulären Ausdruck so vorstellen, dass er eine Menge von Strings beschreibt.

• Das bedeutet, dass die leere Menge einen Operator darstellt, der mit keinen Zeichenfolgen übereinstimmt.
• Die leere Zeichenfolge stellt einen Singleton-Satz einer einzelnen Zeichenfolge dar, die nur mit der leeren Zeichenfolge übereinstimmt.
• Das Zeichen stellt auch einen Singleton-Satz dar, der nur mit dem einzelnen Zeichen übereinstimmt a.
• Wir können diese regulären Basisausdrücke dann mit Operatoren kombinieren wie: or, concatenationund Kleene star, wobei rund sdie beiden regulären Ausdrucksausdrücke darstellt, die wir kombinieren.

Nullable-Funktion

Wir können mit der Nullable-Funktion beginnen. Schauen wir uns einige Beispiele an und finden heraus, welcher dieser regulären Ausdrücke mit der leeren Zeichenfolge übereinstimmt, um einen Einblick in die Implementierung dieser Funktion zu erhalten.

• a*stimmt mit der leeren Zeichenfolge überein, da null oder mehr null enthält.
• (a*|b)stimmt mit der leeren Zeichenkette überein, da die linke Seite von or mit der leeren Zeichenkette übereinstimmt.
• abstimmt nicht mit dem leeren String überein, da es nur mit dem String übereinstimmtab
• ab*stimmt auch nicht mit der leeren Zeichenfolge überein, da ab*eine Zeichenfolge erforderlich ist, die mit an beginnta
• (a|b)stimmt nicht mit der leeren Zeichenkette überein, da weder die linke noch die rechte Seite der ormit der leeren Zeichenkette übereinstimmt.

Hier ist die Implementierung der Nullable-Funktion. Die linke Seite stellt Werte dar, die an die Funktion übergeben werden, und die rechte Seite stellt die Implementierung der Funktion in diesem Fall dar. Die roten Geister repräsentieren falsch und die blauen Geister repräsentieren wahr:

• Die leere Menge stimmt nicht mit der leeren Zeichenfolge überein, da sie mit keiner Zeichenfolge übereinstimmt.
• Die leere Zeichenfolge stimmt mit der leeren Zeichenfolge überein, weil sie nur mit der leeren Zeichenfolge übereinstimmt.
• Das Zeichen astimmt nicht mit der leeren Zeichenfolge überein, da es nur mit dem Zeichen übereinstimmt a.
• Wenn wir ein logisches orhaben, müssen wir beide Seiten prüfen. Wenn eine der beiden mit der leeren Zeichenfolge übereinstimmt, stimmt die logische ormit der leeren Zeichenfolge überein.
• Damit die concatenationbeiden regulären Ausdrücke mit der leeren Zeichenfolge übereinstimmen, müssen beide mit der leeren Zeichenfolge übereinstimmen.
• Und schließlich, wenn wir zero or morevon etwas haben, dann enthält das Null, was bedeutet, dass es immer mit dem leeren String übereinstimmt.

1. Unser Top-Operator ist das orDas heißt, wir müssen die Nullbarkeit der linken und rechten Seite prüfen: bund a*.
2. Wir prüfen und sehen, dass das Zeichen bauf der linken Seite nicht nullable ist: false.
3. Dann überprüfen wir und sehen, dass das a*auf der rechten Seite nullable ist: true.
4. Jetzt sind wir zurück falseund truewir können orsie bekommen true.

Nullfähige Übungen

Versuchen Sie, die Implementierung durchzugehen, und überprüfen Sie, ob die folgenden regulären Ausdrücke nullable sind. Sie können darauf klicken, um Ihre Antwort zu überprüfen:

1. a
2. a*(b*|∅)
3. εa
4. ∅*
5. (∅|b)*(abc|ε)

Bevor wir uns mit der Implementierung der Funktion befassen, schauen wir uns Beispiele für eine Ableitung an. Hier nehmen wir die Ableitung einiger regulärer Ausdrücke, alle in Bezug auf das Zeichen a:

• Der reguläre Ausdruck, der noch gefunden werden muss, nachdem ein Apfel a*gegessen wurde, ist immer noch .aa*
• Die Ableitung von ab*in Bezug auf aist b*, da wir das Präfix bereits angepasst haben a.
• Die Ableitung von (a|b)bin Bezug auf aist b.
• Die Ableitung von b|(a*b)in Bezug auf aist a*b. Das linke bpasste nicht, also konnten wir es wegwerfen und das wurde von den 's auf der rechten Seite averbraucht .zero or more a
• Als nächstes haben wir ab*, dieser ist etwas knifflig. Nachdem es den Apfel gegessen hat, ist der reguläre Ausdruck, der noch gefunden werden muss, b(ab)*. Da wir nur den gematcht haben a, erwarten wir mindestens einen weiteren b.

• Die Ableitung der leeren Menge ist immer die leere Menge. Es gibt keine Möglichkeit zur Wiederherstellung, da die leere Menge mit nichts übereinstimmt.
• Die Ableitung der leeren Zeichenfolge bezüglich eines beliebigen Zeichens ist die leere Menge. Es wurde nicht erwartet, zu einem Charakter zu passen. Es wird nur mit der leeren Zeichenfolge abgeglichen.
• Die Ableitung eines einzelnen Zeichens von einem ähnlichen Zeichen (in diesem Fall das apple) ist die leere Zeichenfolge, da nach der Übereinstimmung mit sich selbst nur noch die leere Zeichenfolge übrig bleibt.
• Die Ableitung eines Zeichens in Bezug auf ein anderes Zeichen, das nicht gleich ist, in diesem Fall das bAnana, ist die leere Menge, da wir das spezifische Zeichen nicht zugeordnet haben.
• Die Ableitung eines orAusdrucks ist die order Ableitungen. Es schiebt das Problem einfach auf seine Kinder.
• Die Ableitung des concatAusdrucks muss prüfen, ob sie den ersten Ausdruck überspringen kann. Der erste Ausdruck kann nur übersprungen werden, wenn der erste Ausdruck mit der leeren Zeichenfolge übereinstimmt und nullfähig ist. Also überprüfen wir das als erstes. Denken wir an den Fall, in dem der erste Ausdruck nicht übersprungen werden kann, wenn der Ausdruck rnicht nullable ist. Dann ist die Ableitung die Ableitung des ersten Ausdrucks concatenatedmit dem zweiten Ausdruck s. Wenn wir die erste Regex überspringen können, müssen wir eine Alternative in Betracht ziehen, die nur die Ableitung des zweiten Ausdrucks ist. Wir können dann ordie beiden Alternativen überspringen rund nicht überspringen rund das als Ergebnis zurückgeben.
• Schließlich haben wir den starOperator. Es stimmt null oder mehrmals mit einem Ausdruck überein. Da uns ein Zeichen übergeben wird, ist dies nicht der Nullfall. Also müssen wir den one or moreFall betrachten. Das heißt, wir müssen die Ableitung des Ausdrucks innerhalb des starund concatenatees wieder mit dem zero or moreAusdruck bilden.

Ableitungsbeispiel 1

Nehmen wir die Ableitung von (ab)*in Bezug auf a.

(ab)*ist ein zero or moreAusdruck, also schauen wir uns die zero or moreRegel an. Wir sehen, dass dies erfordert, die Ableitung des Ausdrucks innerhalb von zu nehmen star.

Dies ist die concatenationvon aund b. Also prüfen wir, ob die linke Seite nullable ist und das Zeichen anicht nullable ist. Das bedeutet, dass wir es nicht überspringen können. Wir müssen die Ableitung von anach bilden a. Aber das ist die leere Zeichenkette, also wenn wir concatenatedie leere Zeichenkette mit der rechten Seite haben, was war b, bekommen wir b.

Nun, wir kehren zurück zu zero or more, denken Sie daran, dass wir die Ableitung von abin Bezug auf genommen aund a zurückbekommen haben b. Jetzt können wir das (ab)*wieder mit verketten und erhalten b(ab)*.

Ableitungsbeispiel 2

Nehmen wir die Ableitung von (a*ba)in Bezug auf b.

• a*wird mit verkettet ba, also schauen wir uns die Verkettungsregel an.
• Wir prüfen, ob die linke Seite a*nullable ist, was auch der Fall ist. Das bedeutet, dass wir es überspringen können, was auch bedeutet, dass wir eine orvon zwei Ableitungen bilden müssen.
• Die linke Seite passt nicht zusammen, da a*does not match b.
• Zum Glück haben wir eine Alternative, die ba. Die Ableitung von bain Bezug auf bist und a.

Ich habe hier einige Details übersprungen. Betrachten Sie es als Übung, meine Arbeit zu überprüfen, indem Sie selbst durch die Funktion gehen.

Ableitungsübungen

Versuchen Sie, die Implementierung durchzugehen, und überprüfen Sie, was die Ableitungen der folgenden regulären Ausdrücke in Bezug auf b. Sie können darauf klicken, um Ihre Antwort zu überprüfen:

1. b
2. bbc)
3. a*(b|c)
4. bεb
5. ∅*b

Ich hoffe, Sie verstehen jetzt, warum das Essen von roten Kirschen Ihnen die Möglichkeit gibt, blaue Geister zu essen, und wie Sie einen Matcher für reguläre Ausdrücke mit dem abgeleiteten Algorithmus implementieren.

Wir haben hier den grundlegenden Arbeitsalgorithmus behandelt, aber es gibt viele Möglichkeiten, diesen Algorithmus mit sehr kleinen Änderungen noch besser zu machen. Wir haben in diesem Beitrag Vereinfachungsregeln geschummelt und beschönigt, indem wir sie verwendet haben, ohne sie zu erklären, was besonders deutlich wird, wenn Sie die Übungen durchgehen. Wir haben auch nicht besprochen, wie Sie die Memoisierung verwenden können, um einen effizienten Automaten faul zu bauen.

Wir können den Algorithmus auch leicht erweitern, um neue Operatoren wie , notund interleavesogar kontextfreie Grammatiken zu unterstützen. Ich werde einige dieser Themen im nächsten Artikel besprechen .

In der Zwischenzeit würde ich gerne Ihre Implementierung dieses Algorithmus in einer Programmiersprache sehen, mit der Sie sich am wohlsten fühlen. Bitte senden Sie mir einen Link in den Kommentaren.

Danke schön

• Brink van der Merwe dafür, dass er sich die Zeit genommen hat, mir diesen Algorithmus zu erklären.

• Brzozowski, Janusz A. „Ableitungen regulärer Ausdrücke.“ Zeitschrift der ACM (JACM) 11.4 (1964): 481–494.
• Owens, Scott, John Reppy und Aaron Turon. „Derivate mit regulären Ausdrücken erneut untersucht.“ Zeitschrift für funktionale Programmierung 19.2 (2009): 173–190.