Compiler für reguläre Ausdrücke

Question

Bei meiner Arbeit habe ich nur wenige Male reguläre Ausdrücke verwenden müssen. In diesen wenigen Fällen habe ich jedoch eine sehr leistungsfähige Ausdrucksform entdeckt, mit der ich einige äußerst nützliche Dinge tun kann.

Das Problem ist, dass die für reguläre Ausdrücke verwendete Sprache falsch ist - Punkt.

Aus psychologischer Sicht ist dies falsch - die Verwendung von körperlosen Symbolen ist nur für Menschen mit einem eidetischen Gedächtnis eine nützliche Referenz. Die syntaktischen Regeln sind zwar klar umrissen, aber nach meiner Erfahrung und dem, was ich von anderen gelernt habe, kann sich die Entwicklung eines erfolgreich funktionierenden regulären Ausdrucks in allen außer den trivialsten Situationen als schwierig erweisen. Dies ist verständlich, da es sich um ein symbolisches Analogon zur Mengenlehre handelt, die eine ziemlich komplizierte Sache ist.

Es kann sich als schwierig erweisen, den Ausdruck, an dem Sie arbeiten, in seine einzelnen Teile aufzulösen. Aufgrund der Beschaffenheit der Sprache ist es möglich, einen regulären Ausdruck auf mehrere Arten zu lesen, wenn man sein primäres Ziel nicht versteht, so dass die Interpretation der Regexes anderer Leute kompliziert ist. In der Lehre von der natürlichen Sprache wird dies als Pragmatik bezeichnet.

Die Frage, die ich stellen möchte, lautet also: Gibt es so etwas wie einen Compiler für reguläre Ausdrücke? Oder kann man überhaupt einen bauen?

Man könnte Regexe, metaphorisch gesehen, als Assembler betrachten - es gibt einige Ähnlichkeiten. Könnte man einen Compiler entwickeln, der eine natürlichere Sprache - eine höhere Sprache - in reguläre Ausdrücke umwandelt? Dann könnte ich in meinem Code meine Regexe unter Verwendung der höheren Sprache in einer Header-Datei definieren und sie bei Bedarf durch eine symbolische Referenz referenzieren. Ich und andere könnten von meinem Code aus auf die Header-Datei verweisen und leichter verstehen, was ich mit meinen Regexes erreichen will.

Ich weiß, dass es von einem logischen Standpunkt aus möglich ist, sonst wären Computer nicht möglich, aber wenn Sie bis hierher gelesen haben, würden Sie dann in Erwägung ziehen, die Zeit zu investieren, um es zu realisieren?

Answer 1

Compiler für reguläre Ausdrücke:

ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/83/972/CS-TR-83-972.pdf

Answer 2

Wenn Sie das Dragon Book für Compiler lesen, erfahren Sie, dass Sie Regex zum Analysieren und Parsen Ihrer höheren Sprache verwenden sollten. Regexs scheinen also eher etwas auf niedrigerer Ebene zu sein. Ich verwende sie sehr oft in meiner täglichen Arbeit für die Frontend-/Backend-Entwicklung, und ja, ich fand einige von ihnen etwas kryptisch. Das macht Regex jedoch nicht falsch, man kann immer eine neue Sprache schreiben, wenn man sie nicht mag, vorausgesetzt 1) man hat die Zeit 2) man ist bereit, die entsprechenden Anstrengungen zu unternehmen 3) die Kraft ist stark in einem :)

Answer 3

Dies ist ein altes Thema, aber ich fühle mich zu einem Kommentar genötigt. Regex sind definitiv problematisch für viele Aufgaben, wie z.B. die Extraktion von interessanten Mustern, die sich über viele Textzeilen erstrecken, die Extraktion von Inhalten aus kontextfreien Mustern, die reguläre Untermuster enthalten, usw. Tatsache ist, dass sich in diesem Bereich seit den 70er Jahren mit awk, grep usw. nicht viel geändert hat.

Ich habe lange und intensiv nach einem einfachen Compiler für reguläre Ausdrücke gesucht, der es ermöglicht, reguläre Muster in Form des vollständigen Komplements der Operationen auszudrücken, unter denen reguläre Mengen geschlossen sind. Mein Ziel war es, damit Transducer zu bauen, die reguläre Sequenzen (z.B. Textstrom) auf Zieleffektoren abbilden (einfache Funktionen, die ein einzelnes Eingabesymbol (z.B. UNICODE-Ordinal) empfangen und es verwenden, um eine Aktion an einem Zielobjekt durchzuführen, das an die Transduktion gebunden ist. Eine breite Palette einfacher Datenextraktionsaufgaben kann mit einer kleinen Handvoll einfacher Auswählen/Ausschneiden/Kopieren/Einfügen/Löschen-Effektoren durchgeführt werden.

Das Schöne daran ist, dass dies eine klare Trennung zwischen Syntax (Erklärung des Quellmusters) und Semantik (Ziel-/Effektorimplementierungen) ermöglicht. Die Transduktionslaufzeit bietet einen Transduktionsstapel, der es ermöglicht, komplexe oder kontextfreie Muster als Baum von einfacheren Transducern auszudrücken, und einen Eingabestapel, der es aufgerufenen Transducern ermöglicht, sinnvolle Signale an den Aufrufer zurückzugeben. Und der Ziel-/Effektorkomplex hat vollen Anwendungszugriff auf die Host-Laufzeit und das RAM, so dass viel mehr erreicht werden kann als mit reinen Text-zu-Text-Transducern.

Ich konnte nur einen solchen Compiler finden, und ich habe den Autor davon überzeugt, ihn in einem Open-Source-Forum zu veröffentlichen. Sie können ihn hier finden: https://github.com/ntozubod/ginr . Es wurde ursprünglich in den späten 1980er Jahren geschrieben und hat sich seitdem kaum verändert, aber ich habe es ausgiebig und ohne Probleme verwendet. Es wurde einmal verwendet, um einen Transducer mit >1M Transitionen zu erstellen, der auf den Prepress-Korpus (mit Proprietray-Markup) des Oxford English Dictionary to SGML angewendet wurde. Wie ich schon sagte, verwende ich es, um Transducer zu definieren, die ich verpacke und zur Laufzeit hier einsetze: https://github.com/jrte/ribose (ein WIP).

Ein paar Beispiele.

HelloWorld = (nil, out[`hello world`]);

Fibonacci = (
   # ~r, ~q, ~p are sequences of 0s preset to empty string ^
   (
      # fib(0): ~q <- 0
      ('0', select[`~q`] paste)
      # fib(n>1): cycle (~r) <- (~q) <- (~p) <- (~p)(~r), (~r) <- ^
      ('0', select[`~r`] cut[`~p`] select[`~p`] copy[`~q`] select[`~q`] cut[`~r`])*
   )?
   # (~q) is empty or selected and holds the result, so append nl and print result
   (nl, paste out stop)
);

(Fibonacci$(0,1 2)):prsseq;

(START)  0  [ select ~q paste ]                                     1
(START)  nl [ paste out stop ]                                      (FINAL)
1        0  [ select ~r cut ~p select ~p copy ~q select ~q cut ~r ] 1
1        nl [ paste out stop ]                                      (FINAL)

$ for n in '' 0 00 000 0000 00000 000000 0000000 00000000 000000000; do echo $n | jrte Fibonacci; done

0
0
00
000
00000
00000000
0000000000000
000000000000000000000
0000000000000000000000000000000000