So implementieren Sie Assertionen/Lookarounds für reguläre Ausdrücke (d. H. \ B style word boundary) mit einem regulären DFA-Expressionsvergleicher

Question

Ich möchte "Wortgrenzen" -Matches in einem DFA-basierten regulären Ausdrucksmatcher implementieren. Kann mir jemand sagen, wie das geht?

Um etwas Hintergrund zu geben, verwende ich derzeit die Bibliothek "dk.brics.automaton", aber es unterstützt keine Assertionen (z. B. \b, Wortgrenze). Ich muss eine DFA-basierte Engine verwenden, da mein Hauptziel darin besteht, die Äquivalenz von regulären Ausdrücken zu bestimmen und nicht die tatsächliche Übereinstimmung.

Zusätzlich ist die Antwort auf die folgende Frage scheint dies möglich ist, um anzuzeigen. DFA based regular expression matching - how to get all matches? von

„Wieder sagen wir das schaffen, indem sie ein Epsilon-Übergang mit speziellen Anweisungen an den Simulator Hinzufügen Wenn die Assertion besteht, dann wird der Statuszeiger fortgesetzt, andernfalls wird er verworfen. "

Ich kann nicht ganz herausfinden, was das bedeutet, jedoch. Schlägt es vor, dass es nur mit einem speziellen Typ von Epsilon-Übergang gemacht werden kann, der seine Endpunkte betrachtet und nur durchlaufen werden kann, wenn sein Endpunkt die Behauptung erfüllt, oder kann es mit "normalen" Epsilon-Übergängen gemacht werden, die irgendwie konfiguriert sind? Wenn ich diese "spezielle" Art von Epsilon-Übergängen benötige, wie können diese dann determiniert werden (d. H. In einen Standard-DFA umgewandelt werden)?

Zeiger zu irgendwelchen Beschreibungen, wie man das wirklich durchführt, werden sehr geschätzt.

Answer 1

Sie können keine reguläre Expression-Engine vom Typ Lookaround mit einer reinen DFA-Implementierung verwenden. Da Sie den Überblick behalten müssen, was vorher gesehen wurde, machen Sie die Engine zu einem anderen Biest, das Kontext im Speicher hält, um den Mustervergleich zu machen.

Damit ein regulärer Ausdruck-Engine dies handhabt, muss es spezielle Übergänge haben, die den Kontext dessen betrachten, was bereits analysiert wurde. Ein normaler DFA kann dies nicht tun, da dieser Kontext verworfen wird. Das ist auch der Grund, warum Capture-Gruppen langsam sind und warum das Matching (.*)something(.*) bei einigen Engines tödlich langsam ist, da es viele Zeichen in Puffer kopieren wird, um diesen Kontext beizubehalten.

Ich nehme an, dass Sie versuchen werden, zwei resultierende DFAs zu minimieren und zu sehen, ob sie gleich sind, um Ihr Problem zu lösen. Dies kann immer noch erreichbar sein, wenn Sie jeden "speziellen" Übergang als einzigartig behandeln und nur mit einem Übergang zusammenführen, der bei der Durchführung des Zustandsminimierungsalgorithmus gleich ist.