Wie ist REGEXP in Programmiersprachen implementiert?

7

Gibt es ein gutes allgemeines Papier über die Interpretation oder Kompilierung von REGEXP in Programmiersprachen für den Mustervergleich mit oder ohne Variablen? Ich bin nicht auf der Suche nach einer kurzen Erklärung zum Aufbau von DFAs, sondern nach einem echten Papier darüber, wie dies bei der Implementierung von Programmiersprachen tatsächlich gemacht wird und was als einfach oder schwierig angesehen wird. Ich gehe davon aus, dass Unterschiede zwischen den Sprachen einen Einfluss haben können. Ein formelles Papier darüber, wie die REGEXP-Implementierung durchgeführt werden sollte, ist ebenfalls nützlich :-)

programming-languages compilers regular-expressions matching interpreters babou
quelle
Natürlich ist dies eine alte Frage, aber ich dachte, ich würde hinzufügen, dass ich als Alternative zur Thompson-Konstruktion die Idee der Berry-Sethi-Konstruktion sehr mag, die genau einen Zustand mehr verwendet, als der Regex Terminalsymbole hat . Dies ist jedoch fast ein stummer Punkt, wenn man sieht, wie der Abgleich für NFAs erfolgt, indem die erreichbaren Zustände im laufenden Betrieb ermittelt werden. Vielleicht das Fehlen vonϵ-Übergänge ist ansprechend. Die einzige Referenz, die ich geben kann, sind diese Folien .
G. Bach
@ G.Bach Es gibt keine alte Frage, es sei denn, der technische Fortschritt hat das Thema selbst überholt. AFAIK, dies kann auch eine Antwort sein, wenn Sie es wirklich mit der REGEXP-Implementierung in Programmiersprachen in Verbindung bringen können. Es kann sich entweder um vorhandene Verwendungen oder um vorgeschlagene Verwendungen handeln. Die Programmiersprachenversionen von REGEXP verfügen über eine Vielzahl von Schnickschnack, die möglicherweise mit der Berry-Sethi-Methode kompatibel sind oder nicht. Ich denke, die Berry-Sethi-Konstruktion wird bei der Implementierung der Esterel-Sprache verwendet, aber nicht für REGEXP, AFAIK.
Babou
Ich denke nicht wirklich, dass eine separate Antwort verdient ist, es war eher als Bemerkung gedacht, dass "es andere Konstruktionen als die von Thompson gibt, die ähnlich effizient sind"; Ich weiß nicht wirklich, wo es in irgendwelchen Werkzeugen verwendet wird. Ich mochte die Idee nur, als ich davon erfuhr, was tatsächlich im Zusammenhang mit dem Erstellen eines Tools standϵ-freie NFA, die die Sprache eines regulären Ausdrucks akzeptiert.
G. Bach
@ G.Bach Ich dachte, es könnte nützlich sein, Leute an interessante Varianten zu erinnern. Aber es könnte tatsächlich eine Arbeit sein, daraus eine richtige Antwort auf die gestellte Frage zu machen. Danke trotzdem.
Babou

Antworten:

5

Ich glaube, die meisten interpretierten Matcher für reguläre Ausdrücke beginnen mit Thompsons Konstruktionsalgorithmus , um den regulären Ausdruck in nicht deterministische endliche Automaten umzuwandeln. Der Artikel, der diese zuerst beschrieb, ist: Ken Thompson, "Programmiertechniken: Suchalgorithmus für reguläre Ausdrücke", Communications of the ACM , 11 (6): 419-422, Juni 1968. Aber dieses Papier ist ein wenig schwer zu lesen, da er wurde zu Maschinencode kompiliert.

Mein Lieblings-Tutorial zur Implementierung regulärer Ausdrücke ist diese Reihe von Blog-Posts von Russ Cox , dem Autor der RE2-Bibliothek für reguläre Ausdrücke. Er gibt viele historische Diskussionen. Er argumentiert, dass der effizienteste Ansatz zur Simulation der NFA darin besteht, im laufenden Betrieb in DFA zu konvertieren, wobei nur die DFA-Zustände zwischengespeichert werden, die Sie tatsächlich erreichen. (Im Gegensatz zum Beispiel zur Implementierung regulärer Ausdrücke in Perl, die Backtracking verwenden.) Es gibt Fälle (z. B. wenn Sie erweiterte reguläre Ausdrücke mit Backreferences erhalten), in denen Sie Backtracking verwenden müssen, aber Cox empfiehlt dies Verwenden Sie Backtracking nur, wenn Sie dies benötigen.

Der andere Ort, den Sie vielleicht suchen, ist Henry Spencers Bibliothek für reguläre Ausdrücke . Laut dieser Website wurde dies in dem Buch beschrieben: Dale Schumacher (Hrsg.), Software Solutions In C , Academic Press, 1994.

Wanderlogik
quelle