Biblioteka Pythona do parsowania regex do AST?

Question

Podkreślam, że nie chcę "analizować za pomocą wyrażeń regularnych" - chcę "parsować wyrażenie regularne w symboliczne drzewo". (Przeszukiwanie przyniosło tylko poprzednie ...)

Mój przypadek użycia: aby przyspieszyć wyszukiwanie wyrażenia regularnego w bazie danych, chciałbym przetworzyć wyrażenie regularne takie jak (foo|bar)baz+(bat)* i wyciągnąć wszystkie podciągi, które MUSZĄ pojawić się w mecz. (W tym przypadku jest to tylko baz, ponieważ foo/bar są zmiennymi, a bat może pojawić się 0 razy.)

Aby to zrobić, potrzebuję zrozumienia operatorów/semantyki regex. re.DEBUG jest najbliższe:

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 

Jednak to tylko drukowanie i c-realizacja nie zachowuje strukturę potem o ile mogę powiedzieć. Wszelkich pomysłów, w jaki sposób można przeanalizować to bez pisania parser właściciela?

Answer 1

Można określić tylko (Classic) regex przy użyciu gramatyka bezkontekstowa:

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

Oznacza to, że nie można analizować regex przy użyciu regex (Perl jest wyjątek, ale wtedy jego „Wyrażenia regularne "są rozszerzone poza" klasyczne ").

Aby przetworzyć wyrażeń regularnych, musisz zbudować własny parser i zbudować drzewo (reDebug jest dość blisko) lub magiczną bibliotekę, na którą masz nadzieję.

Podejrzewam, że to łatwa część. To nie jest trudne do zrobienia; zobacz Is there an alternative for flex/bison that is usable on 8-bit embedded systems? dla prostego schematu budowania takich parserów.

zrozumieć semantyka z regex (na przykład dowiedzieć się, „niezbędne podciągi”), może być w stanie uciec z budynku analizatora że podchodzi do drzewa parsowania, i dla każdego poddrzewa (dno w górę), oblicza wspólny ciąg. W przeciwnym razie konieczne może być wdrożenie klasycznej konstrukcji NDFA, a następnie przejście przez nią lub wdrożenie NDFA do konstrukcji DFA i przejście przez DFA. Rzeczywiste wyrażenia regularne zwykle zawierają wiele nieporządanych komplikacji, takich jak wbudowane zestawy znaków, grupy przechwytywania itp.

"Wspólny ciąg znaków" może nie być tylko ciągłym ciągiem znaków, chociaż można go zdefiniować jako taki. Może ona obejmować kilka stałych podciągi rozdzielone stałe lub zmienne luki liczbę znaków, na przykład, twój konieczne podciąg zawsze może sama być eksprymowanej jako „prostego wyrażenia regularnego” w postaci:

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