Wie simulieren Sie Rückreferenzen, Lookaheads und Lookbehinds in endlichen Automaten

  • Ich habe einen einfachen Lexer und Parser für reguläre Ausdrücke erstellt, um einen regulären Ausdruck zu verwenden und seinen Analysebaum zu generieren. Das Erstellen eines nicht deterministischen Finite-State-Automaten aus diesem Parser-Baum ist für grundlegende reguläre Ausdrücke relativ einfach. Ich kann mich jedoch scheinbar nicht darum kümmern, wie man Rückreferenzen, Lookaheads und LookHinds simuliert.

    Aus dem, was ich im lila Drachenbuch gelesen habe, habe ich das verstanden, um einen Lookahead zu simulieren $ r / s $ Wenn der reguläre Ausdruck $ r $ genau dann übereinstimmt, wenn auf den Treffer ein Match des regulären Ausdrucks $ s $ folgt, erstellen Sie einen nicht deterministischen endlichen Automaten, in dem $ / $ durch ersetzt wird $ \ varepsilon $. Ist es möglich, einen deterministischen Finite-State-Automaten zu erstellen, der dasselbe tut?

    Wie sieht es mit der Simulation negativer Lookaheads und Lookbehinds aus? Ich wäre wirklich dankbar, wenn Sie mich mit einer Ressource verlinken würden, in der beschrieben wird, wie dies ausführlich beschrieben wird.

    30 June 2012
    Raphael
4 answers
  • Zunächst können Rückreferenzen nicht von endlichen Automaten simuliert werden, da Sie nicht-reguläre Sprachen beschreiben können. Beispielsweise stimmt ([ab]^*)\1 mit $ \ {ww \ mid w \ in \ {a, b \} ^ * \} $ überein, was nicht einmal kontextfrei ist.

    Look-Ahead und Look-Behind sind in der Welt der endlichen Automaten nichts Besonderes, da wir hier nur ganze -Eingaben finden. Daher ist die spezielle Semantik "Nur prüfen, aber nicht konsumieren" bedeutungslos. Sie verketten und / oder kreuzen die überprüfenden und verbrauchenden Ausdrücke und verwenden die resultierenden Automaten. Die Idee ist, die Look-Ahead- oder Look-Behind-Ausdrücke zu überprüfen, während Sie die Eingabe "verbrauchen" und das Ergebnis in einem Status speichern.

    Beim Implementieren von Regex-Ausdrücken möchten Sie ausführen die Eingabe durch einen Automaten und erhalten Start- und Endindizes von Übereinstimmungen zurück. Dies ist eine ganz andere Aufgabe, daher gibt es für endliche Automaten keine Konstruktion. Sie bauen Ihren Automaten so auf, als ob der Look-Ahead- oder der Look-Behind-Ausdruck verbrauchend wäre, und ändern Ihre Indexspeicherung bzw. den Indexspeicher. Berichterstattung entsprechend.

    Nehmen Sie beispielsweise Rückblicke. Wir können die Regex-Semantik nachahmen, indem wir den überprüfenden Regex gleichzeitig mit dem implizit "allgegenwärtigen" Regex ausführen. Nur aus Staaten, in denen sich der Automat des Look-Behind-Ausdrucks in einem Endzustand befindet, kann der Automat des überwachten Ausdrucks eingegeben werden. Beispiel: Der Ausdruck /(?=c)[ab]+/ (vorausgesetzt, dass $ \ {a, b, c \} $ das vollständige Alphabet ist). Beachten Sie, dass es in den regulären Ausdruck $ \ {a, b, c \} ^ * c \ übersetzt wird. {a, b \} ^ + \ {a, b, c \} ^ * $ - könnte mit

    Wie simulieren Sie Rückreferenzen, Lookaheads und Lookbehinds in endlichen Automaten
    <übereinstimmen sup> [ source ]

    und Sie müssen

    • den aktuellen Index als $ i $ speichern, wenn Sie $ q_2 $ eingeben (anfänglich oder ab $ q_2) $) und
    • melden eine (maximale) Übereinstimmung zwischen $ i $ und dem aktuellen Index ($ -1 $), wenn Sie (q) $ q_2 $ drücken.

    Beachten Sie, wie der linke Teil von

    20 January 2014
    Raphael
  • Die maßgebliche Referenz zu den pragmatischen Aspekten der Implementierung von Regex-Engines ist eine Reihe von drei Blogbeiträgen von Russ Cox . Wie dort beschrieben, werden Sie, da Rückreferenzen Ihre Sprache nicht regulär machen, mit Backtracking implementiert.

    Lookaheads und Lookbehinds passen wie viele Features von Regex-Pattern-Matching-Engines nicht ganz in das Paradigma der Entscheidung, ob eine Zeichenfolge Mitglied einer Sprache ist oder nicht . Bei Regex suchen wir normalerweise nach Teilstrings innerhalb eines größeren Strings. Die "Übereinstimmungen" sind Teilzeichenfolgen, die Mitglieder der Sprache sind, und der Rückgabewert ist der Anfangs- und Endpunkt der Teilzeichenfolge innerhalb der größeren Zeichenfolge.

    Der Punkt von Lookaheads und Lookbehinds ist nicht so sehr die Möglichkeit, nicht-reguläre Sprachen abzugleichen, sondern stattdessen anzupassen, wo die Engine die Start- und Endpunkte des übereinstimmenden Teilstrings meldet.

    Ich verlasse mich darauf auf der Beschreibung unter http://www.regular-expressions.info/lookaround.html . Die Regex-Engines, die diese Funktion unterstützen (Perl, TCL, Python, Ruby, ...), scheinen alle auf Backtracking zu basieren (d. H. Sie unterstützen eine viel größere Anzahl von Sprachen als nur die regulären Sprachen). Sie scheinen dieses Feature als eine relativ "einfache" Erweiterung des Backtracking zu implementieren, anstatt echte endliche Automaten für die Ausführung der Aufgabe zu konstruieren.

    Positive Lookahead

    Die Syntax für positive Lookahead lautet (?= Regex ). Zum Beispiel stimmt q(?=u) nur mit q überein, wenn auf u folgt, aber nicht mit u übereinstimmt. Ich kann mir vorstellen, dass sie dies mit einer Variante des Backtracking implementieren. Erstellen Sie einen FSM für den Ausdruck vor dem positiven Lookahead. Wenn das stimmt, erinnere dich, wo es endete und fange ein neues anFSM, der den Ausdruck im positiven Lookahead darstellt. Wenn dies zutrifft, haben Sie ein "Match", aber das Match "endet" kurz vor der Position, an der der positive Lookahead-Match begann.

    Der einzige Teil davon wäre schwierig ohne Backtracking ist, dass Sie sich den Punkt in der Eingabe merken müssen, an dem der Lookahead beginnt, und Ihr Eingabeband an diese Position zurückschieben, wenn Sie mit dem Abgleich fertig sind / h2>

    Die Syntax für negative Lookahead lautet (?! regex ). Zum Beispiel stimmt q(?!u) nur mit q überein, wenn auf u nicht gefolgt wird. Dies kann entweder ein q sein, gefolgt von einem anderen Zeichen, oder ein q ganz am Ende des Strings. Ich stelle mir vor, dass dies implementiert wird, indem ein NFA für den Lookahead-Ausdruck erstellt wird und dann nur erfolgreich ist, wenn der NFA nicht mit dem nachfolgenden String übereinstimmt.

    Wenn Sie dies tun möchten, ohne sich auf Backtracking zu verlassen Sie könnten die NFA des Lookahead-Ausdrucks negieren und dann genauso behandeln, wie Sie mit einem positiven Lookahead umgehen.

    Positives Lookbehind

    The Syntax für positives Aussehen ist (?<= Regex ). So stimmt beispielsweise (?=q)u mit u überein, jedoch nur, wenn q vorangestellt ist, jedoch nicht mit q übereinstimmt. Anscheinend wird dies als kompletter Hack implementiert, bei dem die Regex-Engine tatsächlich $ n $ -Zeichen sichert und versucht, regex mit diesen $ n $ -Zeichen abzugleichen. Dies bedeutet, dass regex so sein muss, dass nur Zeichenfolgen der Länge $ n $ übereinstimmen.

    Sie können dies möglicherweise ohne Backtracking implementieren, indem Sie die Schnittpunkt von "string, der mit regex " endet, mit dem Teil des regulären Ausdrucks, der vor dem lookbehind -Operator steht. Dies wird jedoch schwierig, da das lookbehind regex möglicherweise weiter zurückschauen muss als der aktuelle Anfang der Eingabe.

    Negativ Lookbehind

    Das sy

    04 March 2015
    Wandering Logic
  • Zumindest für Rückreferenzen ist dies nicht möglich. Beispielsweise steht der Regex (.*)\1 für eine nicht reguläre Sprache. Dies bedeutet, dass es unmöglich ist, einen endlichen Automaten (deterministisch oder nicht) zu erstellen, der diese Sprache erkennt. Wenn Sie dies formal beweisen möchten, können Sie das Pumping Lemma verwenden.

    30 June 2012
    Michael Haren
  • Ich habe das selbst untersucht, und Sie sollten Lookahead mit einem Abwechselnde Finite Automaton . Wenn Sie auf Lookahead stoßen, führen Sie den Lookahead und den Rest des Ausdrucks nicht deterministisch aus und akzeptieren nur, wenn beide -Pfade akzeptieren. Sie können einen AFA in einen NFA mit angemessener Vergrößerung (und damit in einen DFA) umwandeln, obwohl ich nicht bestätigt habe, dass die offensichtliche Konstruktion gut mit Capture-Gruppen spielt.

    Lookbehind mit fester Breite sollte ohne Backtracking problemlos möglich sein. Sei n die Breite. Ausgehend von dem Punkt in Ihrem NFA, an dem der Lookbehind begann, spalteten Sie die Status nach hinten ab, so dass jeder Pfad in den Lookbehind mit n Zeichen im Wert von Status endete, die nur sind ging in den Look zurück. Fügen Sie dann an den Anfang dieser Zustände Lookahead hinzu (und kompilieren Sie den Subgraph sofort von AFA zu NFA, falls gewünscht).

    Rückreferenzen sind, wie andere bereits erwähnt haben, nicht regelmäßig kann nicht von einem endlichen Automaten implementiert werden. Sie sind tatsächlich NP-vollständig. Bei der Implementierung, an der ich gerade arbeite, ist ein schnelles Ja / Nein-Matching von größter Bedeutung, daher habe ich mich entschieden, überhaupt keine Rückreferenzen zu implementieren.

    02 February 2017
    Thom Smith