Python-Bibliothek, um Regex in AST zu parsen?

9

Um zu betonen, ich möchte nicht "mit einem Regex parsen" - Ich möchte "einen Regex in einen symbolischen Baum parsen". (Das Suchen hat nur das erstere hervorgebracht ...)

Mein Anwendungsfall: Um eine Regex-Suche über eine Datenbank zu beschleunigen, möchte ich einen Regex wie (foo|bar)baz+(bat)* analysieren und alle Teilstrings, die in einer Übereinstimmung erscheinen MÜSSEN. (In diesem Fall ist es nur baz , weil foo / bar abwechselnd sind und Fledermaus 0 mal vorkommen kann.)

Um dies zu tun, brauche ich ein Verständnis von Regex-Operatoren / Semantik. re.DEBUG kommt am nächsten:

%Vor%

Es wird jedoch nur gedruckt, und die c-Implementierung behält die Struktur nachher nicht bei, soweit ich das beurteilen kann. Irgendwelche Ideen, wie ich das analysieren kann, ohne meinen Besitzer-Parser zu schreiben?

    
munchybunch 30.12.2015, 05:16
quelle

1 Antwort

2

Sie können eine (klassische) Regex nur mit einer kontextfreien Grammatik angeben:

%Vor%

Dies bedeutet, dass Sie eine Regex nicht mit einer Regex analysieren können (Perl ist eine Ausnahme, aber dann sind seine "Regexes" weit über "klassisch" hinaus erweitert.

Um einen Regex zu parsen, müssen Sie also einen eigenen Parser erstellen und eine Art Baum (re.Debug kommt ziemlich nah) oder die magische Bibliothek, auf die Sie hoffen, erstellen.

Ich vermute, das ist der einfache Teil. Das ist nicht sehr schwer selbst zu tun; sehen Gibt es eine Alternative für Flex / Bison, die auf 8-Bit-Embedded-Systemen verwendet werden kann? für ein einfaches Schema zum Aufbau solcher Parser.

Um die Semantik der Regex zu verstehen (z. B. um "notwendige Teilstrings" herauszufinden), können Sie möglicherweise einen Analyzer erstellen Der Pfad über den Parse-Baum und für jeden Teilbaum (von unten nach oben) berechnet die Common-String. Andernfalls müssen Sie möglicherweise die klassische NDFA-Konstruktion implementieren und dann darüber hinweggehen oder die NDFA in die DFA-Konstruktion implementieren und über die DFA gehen. Echte Regexes enthalten viele unordentliche Komplikationen wie eingebaute Zeichensätze, Capture-Gruppen, etc.

Die "allgemeine Zeichenkette" ist möglicherweise nicht nur eine zusammenhängende Folge von Zeichen, obwohl Sie sie als solche eng definieren könnten. Es könnte mehrere konstante Teilzeichenfolgen enthalten, die durch Zeichenlücken mit fester oder variabler Länge getrennt sind, z. B. könnte Ihre notwendige Teilzeichenfolge immer selbst als "einfache Formel" der Form ausgedrückt werden:

%Vor%     
Ira Baxter 30.12.2015 10:51
quelle

Tags und Links