Python-Bibliothek, um Regex in AST zu analysieren?

Question

Um zu betonen, möchte ich nicht "parse mit einem Regex" - Ich möchte "eine Regex in einen symbolischen Baum zu analysieren." (Suche hat nur die ehemalige herauf gebracht ...)

Mein Anwendungsfall: Um eine Regex-Suche über eine Datenbank zu beschleunigen, würde ich gerne einen Regex wie (foo|bar)baz+(bat)* analysieren und alle Teilstrings herausziehen, die in einem erscheinen müssen Spiel. (In diesem Fall ist es nur baz, weil foo/bar sind Alternationen und bat kann 0 mal erscheinen.)

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

In [7]: re.compile('(foo|bar)baz+(bat)', re.DEBUG) 
subpattern 1 
    branch 
    literal 102 
    literal 111 
    literal 111 
    or 
    literal 98 
    literal 97 
    literal 114 
literal 98 
literal 97 
max_repeat 1 4294967295 
    literal 122 
subpattern 2 
    literal 98 
    literal 97 
    literal 116 

Allerdings ist es den Ausdruck nur, und die c-Implementierung erhält nicht die Struktur danach soweit ich das beurteilen kann. Irgendwelche Ideen, wie ich das analysieren kann, ohne meinen Parser zu schreiben?

Answer 1

Sie können nur einen (klassisch) Regex mit einer kontextfreien Grammatik angeben:

regex = { alternatives }; 
alternatives = primitive { '|' alternatives } ; 
primitive = '(' regex ')' | '[' character_set ']' | ... 

Das heißt, Sie einen regulären Ausdruck mit einem regex nicht analysieren kann (Perl ist eine Ausnahme, aber dann seine „Regexes "sind weit über" klassisch "hinaus").

Also, um eine Regex zu parsen, müssen Sie Ihren eigenen Parser erstellen und eine Art Baum (re.Debug kommt ziemlich nah) oder die magische Bibliothek, die Sie sich erhoffen.

Ich vermute, das ist der einfache Teil. Das ist nicht sehr schwer selbst zu tun; siehe Is there an alternative for flex/bison that is usable on 8-bit embedded systems? für ein einfaches Schema zum Aufbau solcher Parser.

Um die Semantik der Regex zu verstehen (zB „notwendig Substrings“, um herauszufinden), Sie könnten in der Lage sein, um wegzukommen mit einem Analysator die Spaziergänge über den Parsing-Baum bauen, und für jeden Unterbaum (unten up), 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 neigen dazu, viele unordentliche Komplikationen wie integrierte Zeichensätze, Erfassungsgruppen usw. zu enthalten.

Die "gemeinsame 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 Teil durch feste oder variable Länge Lücken von Zeichen getrennt sind zB Ihre notwendigen Teilzeichenfolge könnte sich immer als eine „einfache regex“ der Form ausdrückbar sein:

(<character>+ ?+) <character>+