Schreiben eines Parsers für reguläre Ausdrücke

Selbst nach Jahren des Programmierens schäme ich mich zu sagen, dass ich reguläre Ausdrücke nie wirklich vollständig verstanden habe. Wenn ein Problem einen regulären Ausdruck erfordert, kann ich normalerweise (nach einigem Verweisen auf die Syntax) eine geeignete finden, aber es ist eine Technik, die ich immer häufiger verwende.

Um mich selbst zu unterrichten und reguläre Ausdrücke richtig zu verstehen , habe ich beschlossen, das zu tun, was ich immer tue, wenn ich versuche, etwas zu lernen. Versuchen Sie also, etwas Ehrgeiziges zu schreiben, das ich wahrscheinlich aufgeben werde, sobald ich das Gefühl habe, genug gelernt zu haben.

Zu diesem Zweck möchte ich einen Parser für reguläre Ausdrücke in Python schreiben. In diesem Fall bedeutet "genug lernen", dass ich einen Parser implementieren möchte, der die erweiterte Regex-Syntax von Perl vollständig verstehen kann. Es muss jedoch nicht der effizienteste Parser sein oder sogar unbedingt in der realen Welt verwendet werden. Es muss lediglich korrekt mit einem Muster in einer Zeichenfolge übereinstimmen oder nicht übereinstimmen.

Die Frage ist, wo fange ich an? Ich weiß fast nichts darüber, wie Regexes analysiert und interpretiert werden, abgesehen von der Tatsache, dass es sich in irgendeiner Weise um einen Automaten mit endlichem Zustand handelt. Vorschläge zur Lösung dieses eher entmutigenden Problems sind sehr willkommen.

EDIT: Ich sollte klarstellen, dass ich, während ich den Regex-Parser in Python implementieren werde, nicht übermäßig darüber aufgeregt bin, in welcher Programmiersprache die Beispiele oder Artikel geschrieben sind. Solange es nicht in Brainfuck ist, werde ich wahrscheinlich genug verstehen davon, damit es sich lohnt.

Das Schreiben einer Implementierung einer Engine für reguläre Ausdrücke ist in der Tat eine recht komplexe Aufgabe.

Aber wenn Sie daran interessiert sind, wie es geht, auch wenn Sie nicht genug Details verstehen, um es tatsächlich zu implementieren, würde ich Ihnen empfehlen, zumindest diesen Artikel zu lesen:

Der Abgleich regulärer Ausdrücke kann einfach und schnell sein (ist jedoch in Java, Perl, PHP, Python, Ruby, ... langsam).

Es wird erklärt, wie viele der gängigen Programmiersprachen reguläre Ausdrücke auf eine Weise implementieren, die für einige reguläre Ausdrücke sehr langsam sein kann, und eine etwas andere Methode, die schneller ist. Der Artikel enthält einige Details zur Funktionsweise der vorgeschlagenen Implementierung, einschließlich des Quellcodes in C. Wenn Sie gerade erst anfangen, reguläre Ausdrücke zu lernen, ist das Lesen möglicherweise etwas schwierig, aber ich denke, es lohnt sich, den Unterschied zwischen beiden zu kennen nähert sich.

Ich habe Mark Byers bereits eine +1 gegeben - aber soweit ich mich erinnere, sagt das Papier nicht wirklich viel darüber aus, wie der Abgleich regulärer Ausdrücke funktioniert, außer zu erklären, warum ein Algorithmus schlecht und ein anderer viel besser ist. Vielleicht etwas in den Links?

Ich werde mich auf den guten Ansatz konzentrieren - endliche Automaten erstellen. Wenn Sie sich auf deterministische Automaten ohne Minimierung beschränken, ist dies nicht wirklich schwierig.

Was ich (sehr schnell) beschreiben werde, ist der Ansatz von Modern Compiler Design .

Stellen Sie sich vor, Sie haben den folgenden regulären Ausdruck ...

a (b c)* d

Die Buchstaben stehen für übereinstimmende Literalzeichen. Das * ist die übliche Übereinstimmung von null oder mehr Wiederholungen. Die Grundidee besteht darin, Zustände basierend auf gepunkteten Regeln abzuleiten. Zustand Null nehmen wir als den Zustand, in dem noch nichts abgeglichen wurde, also steht der Punkt vorne ...

0 : .a (b c)* d

Die einzig mögliche Übereinstimmung ist 'a', also ist der nächste Zustand, den wir ableiten, ...

1 : a.(b c)* d

Wir haben jetzt zwei Möglichkeiten - passen Sie das 'b' an (wenn es mindestens eine Wiederholung von 'b c' gibt) oder stimmen Sie andernfalls mit dem 'd' überein. Hinweis - Wir führen hier im Grunde genommen eine Digraphensuche durch (entweder zuerst Tiefe oder zuerst Breite oder was auch immer), aber wir entdecken den Digraphen, während wir ihn durchsuchen. Unter der Annahme einer Strategie mit der Breite zuerst müssen wir einen unserer Fälle für eine spätere Prüfung in die Warteschlange stellen, aber ich werde dieses Problem von nun an ignorieren. Wie auch immer, wir haben zwei neue Staaten entdeckt ...

2 : a (b.c)* d
3 : a (b c)* d.

Zustand 3 ist ein Endzustand (es kann mehr als einen geben). Für Zustand 2 können wir nur mit dem 'c' übereinstimmen, aber wir müssen danach mit der Punktposition vorsichtig sein. Wir erhalten "a. (Bc) * d" - das ist dasselbe wie Zustand 1, also brauchen wir keinen neuen Zustand.

IIRC, der Ansatz in Modern Compiler Design besteht darin, eine Regel zu übersetzen, wenn Sie einen Operator treffen, um die Behandlung des Punkts zu vereinfachen. Zustand 1 würde umgewandelt in ...

1 : a.b c (b c)* d
    a.d

Das heißt, Ihre nächste Option besteht darin, entweder der ersten Wiederholung zu entsprechen oder die Wiederholung zu überspringen. Die nächsten Zustände entsprechen den Zuständen 2 und 3. Ein Vorteil dieses Ansatzes besteht darin, dass Sie alle Ihre vergangenen Spiele (alles vor dem '.') Verwerfen können, da Sie sich nur um zukünftige Spiele kümmern. Dies ergibt typischerweise ein kleineres Zustandsmodell (aber nicht unbedingt ein minimales).

BEARBEITEN Wenn Sie bereits übereinstimmende Details verwerfen, ist Ihre Statusbeschreibung eine Darstellung der Zeichenfolgen, die ab diesem Zeitpunkt auftreten können.

In Bezug auf die abstrakte Algebra ist dies eine Art Mengenschluss. Eine Algebra ist im Grunde eine Menge mit einem (oder mehreren) Operatoren. Unser Satz besteht aus Zustandsbeschreibungen, und unsere Operatoren sind unsere Übergänge (Zeichenübereinstimmungen). Ein geschlossener Satz ist ein Satz, bei dem das Anwenden eines Operators auf ein Mitglied des Satzes immer ein anderes Mitglied erzeugt, das sich im Satz befindet. Das Schließen eines Satzes ist der minimal größere Satz, der geschlossen wird. Ausgehend vom offensichtlichen Startzustand konstruieren wir also im Grunde genommen die minimale Menge von Zuständen, die relativ zu unserer Menge von Übergangsoperatoren geschlossen ist - die minimale Menge von erreichbaren Zuständen.

Minimal bezieht sich hier auf den Schließvorgang - es kann kleinere äquivalente Automaten geben, die normalerweise als minimal bezeichnet werden.

Angesichts dieser Grundidee ist es nicht allzu schwierig zu sagen, "wenn ich zwei Zustandsmaschinen habe, die zwei Sätze von Zeichenfolgen darstellen, wie ich eine dritte ableiten kann, die die Vereinigung darstellt" (oder Schnittmenge oder Satzdifferenz ...). Anstelle von gepunkteten Regeln erhalten Ihre Zustandsdarstellungen einen aktuellen Zustand (oder eine Reihe von aktuellen Zuständen) von jedem Eingabeautomaten und möglicherweise zusätzliche Details.

Wenn Ihre regulären Grammatiken komplex werden, können Sie sie minimieren. Die Grundidee hier ist relativ einfach. Sie gruppieren alle Ihre Zustände in einer Äquivalenzklasse oder einem "Block". Anschließend testen Sie wiederholt, ob Sie Blöcke in Bezug auf einen bestimmten Übergangstyp teilen müssen (die Zustände sind nicht wirklich gleichwertig). Wenn alle Zustände in einem bestimmten Block eine Übereinstimmung mit demselben Zeichen akzeptieren und dabei denselben nächsten Block erreichen können, sind sie äquivalent.

Der Hopcrofts-Algorithmus ist ein effizienter Weg, um mit dieser Grundidee umzugehen.

Besonders interessant an der Minimierung ist, dass jeder deterministische endliche Automat genau eine Minimalform hat. Darüber hinaus erzeugt der Hopcrofts-Algorithmus dieselbe Darstellung dieser Minimalform, unabhängig davon, von welcher Darstellung der größere Fall ausgeht. Das heißt, dies ist eine "kanonische" Darstellung, die verwendet werden kann, um einen Hash abzuleiten oder für beliebige, aber konsistente Ordnungen. Dies bedeutet, dass Sie minimale Automaten als Schlüssel für Container verwenden können.

Das Obige ist wahrscheinlich eine etwas schlampige WRT-Definition. Stellen Sie daher sicher, dass Sie alle Begriffe selbst nachschlagen, bevor Sie sie selbst verwenden. Mit etwas Glück erhalten Sie jedoch eine recht schnelle Einführung in die Grundideen.

Übrigens - sehen Sie sich den Rest der Dick Grunes-Website an - er hat ein kostenloses PDF-Buch über Parsing-Techniken. Die erste Ausgabe von Modern Compiler Design ist IMO ziemlich gut, aber wie Sie sehen werden, steht eine zweite Ausgabe unmittelbar bevor.

Dieses Papier verfolgt einen interessanten Ansatz. Die Implementierung ist in Haskell angegeben, wurde jedoch mindestens einmal in Python neu implementiert .

In Beautiful Code von Brian Kernighan gibt es ein interessantes (wenn auch etwas kurzes) Kapitel mit dem passenden Namen "A Regular Expression Matcher". Darin diskutiert er einen einfachen Matcher, der mit wörtlichen Zeichen und den .^$*Symbolen übereinstimmen kann .

Ich bin damit einverstanden, dass das Schreiben einer Regex-Engine das Verständnis verbessert, aber haben Sie sich ANTLR angesehen? Es generiert die Parser automatisch für jede Art von Sprache. Vielleicht können Sie Ihre Hand versuchen , auf eines der aufgelisteten Sprache Grammatiken unter Grammatik Beispielen und durch den AST und Parser ausführen , dass es generiert. Es generiert einen wirklich komplizierten Code, aber Sie haben ein gutes Verständnis dafür, wie ein Parser funktioniert.