Beeinflusst Lookaround, welche Sprachen durch reguläre Ausdrücke abgeglichen werden können?

78

In modernen Regex-Engines gibt es einige Funktionen, mit denen Sie Sprachen zuordnen können, die ohne diese Funktion nicht übereinstimmen könnten. Beispielsweise stimmt der folgende reguläre Ausdruck mit Rückverweisen mit der Sprache aller Zeichenfolgen überein, die aus einem Wort bestehen, das sich wiederholt : (.+)\1. Diese Sprache ist nicht regulär und kann nicht mit einem regulären Ausdruck verglichen werden, der keine Rückverweise verwendet.

Beeinflusst Lookaround auch, welche Sprachen durch einen regulären Ausdruck abgeglichen werden können? Dh gibt es Sprachen, die mit Lookaround abgeglichen werden können, die sonst nicht abgeglichen werden könnten? Wenn ja, gilt dies für alle Arten von Lookaround (negativer oder positiver Lookahead oder Lookbehind) oder nur für einige von ihnen?

sepp2k
quelle
4
regulär-expressions.info/ lookaround.html besagt, dass "Lookarounds es Ihnen ermöglichen, reguläre Ausdrücke zu erstellen, die ohne sie nicht erstellt werden können oder die ohne sie sehr langwierig werden würden". Aber das einzige Beispiel in dieser Richtung ist über die Unmöglichkeit , zu finden und passen ein q nicht von einem gefolgt u . Dies sagt nichts darüber aus, ob es möglich ist , zu sagen , ob die Eingabezeichenfolge enthält eine q nicht von einem gefolgt u (ohne nur entsprechen zu haben , dass q ).
Christian Semrau
7
@ChristianSemrau: Es ist vielleicht nicht eine Programmiersprache Frage per se, aber die Voraussetzung ist nur „Programmierung im Zusammenhang “ und ich diese qualifiziert denken. Und für mich ist diese Frage aus praktischer Sicht interessant, da sie während der Programmierung auftauchte.
sepp2k
2
@Christian Semrau: Mein Hauptkriterium für "programmierbezogen" wäre, wenn die Frage auf einer ähnlichen Buchhaltungsseite zu Hause wäre (mit offensichtlich einfachen Substitutionen). Regexes sind ziemlich streng eine Programmiersache. Ich persönlich denke es zum Thema.
David Thornley
5
Anscheinend wurde die Frage, ob CS zum Stackoverflow gehört oder nicht, bereits zuvor diskutiert: meta.stackexchange.com/questions/26889/… . Persönlich hoffe ich, hier mehr CS-Fragen oder bei Bedarf eine Schwesterseite zu sehen.
Polygenelubricants
1
cs.stackexchange.com/questions/2557/…
Ciro Santilli 法轮功 冠状 病 六四. 法轮功

Antworten:

25

Wie die anderen Antworten behaupten, verleihen Lookarounds regulären Ausdrücken keine zusätzliche Kraft.

Ich denke, wir können dies folgendermaßen zeigen:

Ein Pebble 2-NFA (siehe den Abschnitt Einführung, der sich darauf bezieht).

Der 1-Pebble 2NFA behandelt keine verschachtelten Lookaheads, aber wir können eine Variante von Multi-Pebble 2NFAs verwenden (siehe Abschnitt unten).

Einführung

Ein 2-NFA ist ein nicht deterministischer endlicher Automat, der sich bei seiner Eingabe entweder nach links oder rechts bewegen kann.

Bei einer Ein-Kiesel-Maschine kann die Maschine einen Kiesel auf das Eingabeband legen (dh ein bestimmtes Eingabe-Symbol mit einem Kiesel markieren) und möglicherweise unterschiedliche Übergänge ausführen, je nachdem, ob sich an der aktuellen Eingabeposition ein Kiesel befindet oder nicht.

Es ist bekannt, dass der One Pebble 2-NFA die gleiche Leistung wie ein normaler DFA hat.

Nicht verschachtelte Lookaheads

Die Grundidee lautet wie folgt:

Mit dem 2NFA können wir zurückverfolgen (oder 'vordere Spur'), ​​indem wir uns im Eingabeband vorwärts oder rückwärts bewegen. Für einen Lookahead können wir also das Match für den regulären Lookahead-Ausdruck durchführen und dann zurückverfolgen, was wir verbraucht haben, indem wir den Lookahead-Ausdruck abgleichen. Um genau zu wissen, wann das Backtracking beendet werden muss, verwenden wir den Kiesel! Wir lassen den Kiesel fallen, bevor wir die dfa für den Lookahead betreten, um die Stelle zu markieren, an der das Zurückverfolgen aufhören muss.

Am Ende des Durchlaufens unseres Strings durch den Kiesel 2NFA wissen wir also, ob wir mit dem Lookahead-Ausdruck übereinstimmen oder nicht, und die verbleibende Eingabe (dh was noch verbraucht werden muss) ist genau das, was erforderlich ist, um mit dem verbleibenden übereinzustimmen.

Also für einen Lookahead der Form u (? = V) w

Wir haben die DFAs für u, v und w.

Vom akzeptierenden Zustand (ja, wir können annehmen, dass es nur einen gibt) von DFA für u machen wir einen e-Übergang zum Startzustand von v und markieren die Eingabe mit einem Kieselstein.

Von einem akzeptierenden Zustand für v e-transtion in einen Zustand, der die Eingabe nach links bewegt, bis sie einen Kieselstein findet, und dann in den Startzustand von w übergeht.

Von einem ablehnenden Zustand von v gehen wir in einen Zustand über, der sich weiter nach links bewegt, bis er den Kiesel findet, und transtionen in den akzeptierenden Zustand von u (dh wo wir aufgehört haben).

Der Beweis, der für reguläre NFAs verwendet wird, um r1 | zu zeigen r2 oder r * etc übertragen für diese einen Kiesel 2nfas. Siehe http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa für weitere Informationen darüber , wie die Komponentenmaschinen zusammengesetzt werden , um die größere Maschine zu geben , für den r * Ausdruck etc.

Der Grund, warum die obigen Beweise für r * usw. funktionieren, ist, dass das Backtracking sicherstellt, dass sich der Eingabezeiger immer an der richtigen Stelle befindet, wenn wir die Komponente nfas zur Wiederholung eingeben. Wenn ein Kieselstein verwendet wird, wird er von einer der Lookahead-Komponentenmaschinen verarbeitet. Da es keine Übergänge von Lookahead-Maschine zu Lookahead-Maschine gibt, ohne den Kiesel vollständig zurückzuverfolgen und zurückzugewinnen, ist nur eine Ein-Kiesel-Maschine erforderlich.

Betrachten Sie beispielsweise ([^ a] | a (? = ... b)) *

und die Zeichenfolge abbb.

Wir haben abbb, das die peb2nfa für a (? = ... b) durchläuft, an dessen Ende wir uns im Zustand befinden: (bbb, Matched) (dh in der Eingabe bleibt bbb übrig, und es hat 'a' abgeglichen gefolgt von '..b'). Aufgrund des * kehren wir nun zum Anfang zurück (siehe die Konstruktion im obigen Link) und geben die dfa für [^ a] ein. Match b, gehe zurück zum Anfang, gib zweimal zweimal [^ a] ein und akzeptiere dann.

Umgang mit verschachtelten Lookaheads

Um verschachtelte Lookaheads zu verarbeiten, können wir eine eingeschränkte Version von k-pebble 2NFA verwenden, wie hier definiert: Komplexitätsergebnisse für Zweiwege- und Multi-Pebble-Automaten und ihre Logik (siehe Definition 4.1 und Satz 4.2).

Im Allgemeinen können 2 Kieselautomaten nicht reguläre Mengen akzeptieren, aber mit den folgenden Einschränkungen kann gezeigt werden, dass k-Kieselautomaten regulär sind (Satz 4.2 im obigen Artikel).

Wenn die Kieselsteine ​​P_1, P_2, ..., P_K sind

  • P_ {i + 1} darf nicht platziert werden, es sei denn, P_i befindet sich bereits auf dem Band, und P_ {i} darf nicht aufgenommen werden, es sei denn, P_ {i + 1} befindet sich nicht auf dem Band. Grundsätzlich müssen die Kieselsteine ​​LIFO-artig verwendet werden.

  • Zwischen dem Zeitpunkt, an dem P_ {i + 1} platziert wird, und dem Zeitpunkt, an dem entweder P_ {i} aufgenommen oder P_ {i + 2} platziert wird, kann der Automat nur das Unterwort durchlaufen, das sich zwischen dem aktuellen Standort von P_ {i} befindet und das Ende des Eingabeworts, das in der Richtung von P_ {i + 1} liegt. Darüber hinaus kann der Automat in diesem Unterwort nur als 1-Kiesel-Automat mit Pebble P_ {i + 1} fungieren. Insbesondere ist es nicht gestattet, das Vorhandensein eines anderen Kiesels anzuheben, zu platzieren oder gar zu spüren.

Wenn also v ein verschachtelter Lookahead-Ausdruck der Tiefe k ist, dann ist (? = V) ein verschachtelter Lookahead-Ausdruck der Tiefe k + 1. Wenn wir eine Lookahead-Maschine betreten, wissen wir genau, wie viele Kieselsteine ​​bisher platziert worden sein müssen, und können so genau bestimmen, welche Kieselsteine ​​platziert werden sollen, und wenn wir diese Maschine verlassen, wissen wir, welche Kieselsteine ​​angehoben werden müssen. Alle Maschinen in der Tiefe t werden durch Platzieren des Kiesels t eingegeben und durch Entfernen des Kiesels t verlassen (dh wir kehren zur Verarbeitung einer Maschine der Tiefe t-1 zurück). Jeder Lauf der gesamten Maschine sieht aus wie ein rekursiver dfs-Aufruf eines Baums, und die beiden oben genannten Einschränkungen der Multi-Pebble-Maschine können berücksichtigt werden.

Wenn Sie nun Ausdrücke für rr1 kombinieren, müssen die Kieselzahlen von r1 um die Tiefe von r erhöht werden, da Sie sich darauf konzentrieren. Für r * und r | r1 bleibt die Kieselnummerierung gleich.

Somit kann jeder Ausdruck mit Lookaheads in eine äquivalente Multi-Pebble-Maschine mit den oben genannten Einschränkungen bei der Platzierung von Kieselsteinen konvertiert werden und ist daher regelmäßig.

Fazit

Dies behebt im Wesentlichen den Nachteil von Francis 'ursprünglichem Beweis: Es kann verhindert werden, dass die Lookahead-Ausdrücke alles verbrauchen, was für zukünftige Spiele erforderlich ist.

Da Lookbehinds nur endliche Zeichenfolgen sind (nicht wirklich Regexs), können wir uns zuerst mit ihnen und dann mit den Lookaheads befassen.

Entschuldigen Sie die unvollständige Beschreibung, aber ein vollständiger Beweis würde das Zeichnen vieler Zahlen beinhalten.

Es sieht für mich richtig aus, aber ich werde mich über Fehler freuen (die ich anscheinend gern habe :-)).

Aryabhatta
quelle
Ich bin mir nicht sicher, ob dies mehrere Lookaheads handhabt, z. B. u(?=v)(?=w)(?=x)z?
Francis Davey
Wenn wir den Pebble 2NFA für einen Lookahead verlassen, befinden wir uns wieder im Eingangsbandstatus, in den wir eingetreten sind, mit einem zu verwendenden Pebble. Je nachdem, ob der Lookahead übereinstimmt oder nicht, befinden wir uns in einem von zwei verschiedenen Zuständen (dh wir können) sagen, ob es eine Übereinstimmung gab). Es scheint also so, als würde es funktionieren, wenn nur die Automaten verkettet werden (mit den zusätzlichen Zuständen mit E-Übergängen, die wir hinzugefügt haben), da wir immer den Kiesel zurückbekommen. Aber ich denke, es hängt davon ab, wie Sie diesen Ausdruck interpretieren. Ist es dasselbe wie u (? = Vwx) z? oder ((u (? = v))? = w) ... etc?
Der Ausdruck stimmt mit au überein, dem alle drei v, w und x (wobei v, w und x alle allgemeine reguläre Ausdrücke sind) und a z folgen müssen (nicht verbrauchen). Nachdem ich versucht habe, etwas zu bauen, das dieses Problem löst, bin ich ziemlich davon überzeugt, dass Sie es nicht kompositorisch tun können (dh indem Sie Lösungen verketten).
Francis Davey
@Francis: Wenn es mit allen übereinstimmen muss, funktioniert die Verkettung (glaube ich). wir bezeichnen es als dfa (u) -> peb2ndfa (v) -> peb2ndfa (w) -> dfa (x). Wenn wir nach dem Abgleich mit u nicht mit v oder w übereinstimmen, gehen wir zurück zu u und machen dort weiter, wo wir aufgehört haben. Wenn wir mit v übereinstimmen, können wir, weil wir zurückverfolgen, nachdem v fertig ist, w erneut abgleichen (was wiederum zurückverfolgt) und dann x abgleichen. Der Schlüssel ist, dass der 2NDFA es uns ermöglicht, den Track zurückzuverfolgen, und der Kieselstein ermöglicht es zu wissen, wann der Backtrack beendet werden muss.
@ sepp2k: Hast du die Gelegenheit bekommen, diese Antwort zu lesen? Wenn Sie Fragen / Erläuterungen / Gegenbeispiele haben, stehe ich Ihnen gerne zur Verfügung.
27

Die Antwort auf die Frage, die Sie stellen, ob eine größere Klasse von Sprachen als die regulären Sprachen mit regulären Ausdrücken erkannt werden kann, die durch Lookaround ergänzt werden, lautet Nein.

Ein Beweis ist relativ einfach, aber ein Algorithmus zum Übersetzen eines regulären Ausdrucks, der Lookarounds enthält, in einen Ausdruck ohne ist unübersichtlich.

Erstens: Beachten Sie, dass Sie einen regulären Ausdruck (über ein endliches Alphabet) immer negieren können. Bei einem Automaten mit endlichen Zuständen, der die durch den Ausdruck erzeugte Sprache erkennt, können Sie einfach alle akzeptierenden Zustände gegen nicht akzeptierende Zustände austauschen, um eine FSA zu erhalten, die genau die Negation dieser Sprache erkennt, für die es eine Familie äquivalenter regulärer Ausdrücke gibt .

Zweitens: Da reguläre Sprachen (und damit reguläre Ausdrücke) unter Negation geschlossen sind, werden sie auch unter Schnitt geschlossen, da A B = neg (neg (A) union neg (B)) nach de Morgans Gesetzen schneidet. Mit anderen Worten, wenn zwei reguläre Ausdrücke gegeben sind, können Sie einen anderen regulären Ausdruck finden, der beiden entspricht.

Auf diese Weise können Sie Lookaround-Ausdrücke simulieren. Zum Beispiel stimmt u (? = V) w nur mit Ausdrücken überein, die mit uv und uw übereinstimmen.

Für einen negativen Lookahead benötigen Sie den regulären Ausdruck, der der Mengenlehre A \ B entspricht, die nur A schneidet (neg B) oder äquivalent neg (neg (A) Vereinigung B) ist. Somit können Sie für alle regulären Ausdrücke r und s einen regulären Ausdruck rs finden, der mit den Ausdrücken übereinstimmt, die mit r übereinstimmen und nicht mit s übereinstimmen. In negativen Lookahead-Begriffen: u (?! V) w stimmt nur mit den Ausdrücken überein, die mit uw - uv übereinstimmen.

Es gibt zwei Gründe, warum Lookaround nützlich ist.

Erstens, weil die Negation eines regulären Ausdrucks zu etwas viel weniger Ordentlichem führen kann. Zum Beispiel q(?!u)=q($|[^u]).

Zweitens sind reguläre Ausdrücke mehr als Übereinstimmungsausdrücke, sie verbrauchen auch Zeichen aus einer Zeichenfolge - oder zumindest denken wir so gerne über sie. Zum Beispiel in Python interessieren mich .start () und .end (), also natürlich:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

Drittens, und ich denke, dies ist ein ziemlich wichtiger Grund, hebt sich die Negation regulärer Ausdrücke nicht gut über die Verkettung. neg (a) neg (b) ist nicht dasselbe wie neg (ab), was bedeutet, dass Sie einen Lookaround nicht aus dem Kontext heraus übersetzen können, in dem Sie ihn finden - Sie müssen den gesamten String verarbeiten. Ich denke, das macht es für Menschen unangenehm, mit ihnen zu arbeiten, und bricht die Intuition der Menschen über reguläre Ausdrücke.

Ich hoffe, ich habe Ihre theoretische Frage beantwortet (es ist spät in der Nacht, also verzeihen Sie mir, wenn ich unklar bin). Ich stimme einem Kommentator zu, der sagte, dass dies praktische Anwendungen hat. Ich bin auf das gleiche Problem gestoßen, als ich versucht habe, einige sehr komplizierte Webseiten zu kratzen.

BEARBEITEN

Ich entschuldige mich dafür, dass ich nicht klarer bin: Ich glaube nicht, dass Sie durch strukturelle Induktion einen Beweis für die Regelmäßigkeit regulärer Ausdrücke + Lookarounds liefern können. Mein u (?! V) w-Beispiel sollte genau das sein, ein Beispiel und ein einfaches dabei. Der Grund, warum eine strukturelle Induktion nicht funktioniert, ist, dass sich Lookarounds nicht kompositorisch verhalten - der Punkt, den ich oben über Negationen ansprechen wollte. Ich vermute, dass jeder direkte formale Beweis viele unordentliche Details enthalten wird. Ich habe versucht, einen einfachen Weg zu finden, um es zu zeigen, kann mir aber keinen aus dem Kopf machen.

Um dies anhand von Joshs erstem Beispiel zu veranschaulichen, ^([^a]|(?=..b))*$entspricht dies einer DFSA mit 7 Staaten, wobei alle Staaten Folgendes akzeptieren:

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

Der reguläre Ausdruck für Zustand A allein sieht wie folgt aus:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

Mit anderen Worten, jeder reguläre Ausdruck, den Sie durch das Eliminieren von Lookarounds erhalten, ist im Allgemeinen viel länger und unordentlicher.

Um auf Joshs Kommentar zu antworten - ja, ich denke, der direkteste Weg, die Äquivalenz zu beweisen, ist über die FSA. Was dieses Chaos noch schlimmer macht, ist, dass die übliche Art, eine FSA zu konstruieren, über eine nicht deterministische Maschine erfolgt - es ist viel einfacher, u | v als einfach die Maschine auszudrücken, die aus Maschinen für u und v mit einem Epsilon-Übergang zu beiden konstruiert ist. Dies entspricht natürlich einer deterministischen Maschine, birgt jedoch die Gefahr eines exponentiellen Aufblasens von Zuständen. Während Negation über eine deterministische Maschine viel einfacher ist.

Der allgemeine Beweis besteht darin, das kartesische Produkt von zwei Maschinen zu nehmen und die Zustände auszuwählen, die Sie an jedem Punkt beibehalten möchten, an dem Sie einen Lookaround einfügen möchten. Das obige Beispiel zeigt, was ich bis zu einem gewissen Grad meine.

Ich entschuldige mich dafür, dass ich keine Konstruktion geliefert habe.

WEITERE BEARBEITUNG: Ich habe einen Blog-Beitrag gefunden, der einen Algorithmus zum Generieren eines DFA aus einem regulären Ausdruck beschreibt, der mit Lookarounds erweitert ist. Es ist ordentlich, weil der Autor die Idee eines NFA-e auf offensichtliche Weise um "markierte Epsilon-Übergänge" erweitert und dann erklärt, wie ein solcher Automat in einen DFA umgewandelt wird.

Ich dachte, so etwas wäre ein Weg, aber ich freue mich, dass jemand es geschrieben hat. Es war mir ein Rätsel, etwas so Ordentliches zu erfinden.

Francis Davey
quelle
2
Ich stimme Francis zu, dass Lookaround regelmäßig ist, aber ich denke, der Beweis ist falsch. Das Problem ist, dass Sie einen regulären Ausdruck mit Lookaround im Allgemeinen nicht in zwei reguläre Ausdrücke A und B aufteilen können. Francis hat dies getan, indem er sich u(?!v)win uwund verwandelt hat uv, aber ich glaube nicht, dass es einen Algorithmus gibt, der dies im Allgemeinen tut. Stattdessen können Sie Lookahead oder Neg (Lookahead) an der Stelle an den ursprünglichen DFA anhängen, an der es mit einem Epsilon-Übergang auftritt. Die Details sind etwas knifflig, aber ich denke, es funktioniert.
Josh Haberman
1
Betrachten Sie zum Beispiel den regulären Ausdruck ^([^a]|a(?=..b))*$. Mit anderen Worten, alle Zeichen sind zulässig, aber jedem "a" muss drei Zeichen später ein "b" folgen. Ich glaube nicht, dass Sie dies auf zwei reguläre Ausdrücke A und B reduzieren können, die Sie über Union kombinieren. Ich denke, Sie müssen den positiven Lookahead Teil der NFA-Konstruktion machen.
Josh Haberman
1
@Josh, sepp2k: Für jede reguläre Sprache L gibt es einen äquivalenten regulären Ausdruck und umgekehrt. Jetzt ist a (? = .. b) regulär, es entspricht einem Ausdruck, sagen wir r. Jetzt haben Sie ([^ a] | r) *, was wieder regulär ist. Ich glaube, das hat Kleene bewiesen. Überprüfen Sie dies: coli.uni-saarland.de/projects/milca/courses/coal/html/… . Der Beweis durch Induktion funktioniert. Was Sie anscheinend aufgehängt haben, ist eine grundlegende Tatsache über reguläre Ausdrücke und Sprachen (mein erster Satz in diesem Kommentar).
3
@Moron: Sie gehen davon aus, dass Lookahead-Ausdrücke genauso zusammengesetzt sind wie reguläre Ausdrücke. Sie nehmen an, dass dies ([^a]|r)*mit derselben Sprache übereinstimmt wie ([^a]|a(?=..b)), was nicht der Fall ist , auch wenn es rmit derselben Sprache wie übereinstimmt a(?=..b). Wenn Sie die DFA-Erweiterung selbst durchführen, werden Sie sehen. Da Lookahead Zeichen entspricht, ohne sie zu verbrauchen, wird es nicht so komponiert wie reguläre Ausdrücke. Wenn Sie davon noch nicht überzeugt sind, werde ich später eine aktuelle DFA-Erweiterung veröffentlichen.
Josh Haberman
2
Betrachten Sie als kurzen Beweis dafür, dass dies a(?=..b)die leere Sprache ist, weil a ∩ a..b = ϵ. Wenn wir also Ihrer Argumentation folgen r = ϵund ([^a]|a(?=..b))*gleich ([^a]|ϵ)*oder gerecht sind [^a]*. Dies ist jedoch eindeutig falsch, da es aaabmit dem ursprünglichen regulären Ausdruck übereinstimmt, jedoch nicht mit dem angeblich äquivalenten.
Josh Haberman
10

Ich stimme den anderen Posts zu, dass Lookaround regulär ist (was bedeutet, dass es regulären Ausdrücken keine grundlegende Fähigkeit hinzufügt), aber ich habe ein Argument dafür, das IMO einfacher ist als die anderen, die ich gesehen habe.

Ich werde zeigen, dass Lookaround regelmäßig ist, indem ich eine DFA-Konstruktion bereitstelle. Eine Sprache ist genau dann regulär, wenn sie einen DFA hat, der sie erkennt. Beachten Sie, dass Perl DFAs nicht intern verwendet (Details finden Sie in diesem Dokument: http://swtch.com/~rsc/regexp/regexp1.html ), aber wir erstellen einen DFA zum Zwecke des Beweises.

Die traditionelle Methode zum Erstellen eines DFA für einen regulären Ausdruck besteht darin, zunächst eine NFA mithilfe des Thompson-Algorithmus zu erstellen. Bei zwei Fragmenten regulärer Ausdrücke r1und r2bietet Thompsons Algorithmus Konstruktionen für die Verkettung ( r1r2), Alternation ( r1|r2) und Wiederholung ( r1*) regulärer Ausdrücke. Auf diese Weise können Sie Stück für Stück eine NFA erstellen, die den ursprünglichen regulären Ausdruck erkennt. Weitere Informationen finden Sie im obigen Dokument.

Um zu zeigen, dass positiver und negativer Lookahead regelmäßig sind, werde ich eine Konstruktion zur Verkettung eines regulären Ausdrucks umit positivem oder negativem Lookahead bereitstellen : (?=v)oder (?!v). Nur die Verkettung erfordert eine besondere Behandlung. Die üblichen Wechsel- und Wiederholungskonstruktionen funktionieren einwandfrei.

Die Konstruktion ist sowohl für u (? = V) als auch für u (?! V):

http://imgur.com/ClQpz.png

Mit anderen Worten, verbinden Sie jeden Endzustand der vorhandenen NFA für usowohl mit einem Akzeptanzzustand als auch mit einer NFA für v, ändern Sie ihn jedoch wie folgt. Die Funktion f(v)ist definiert als:

  • Sei aa(v)eine Funktion auf einer NFA v, die jeden Akzeptanzzustand in einen "Anti-Akzeptanz-Zustand" ändert. Ein Anti-Akzeptanz-Status ist definiert als ein Status, der dazu führt, dass die Übereinstimmung fehlschlägt, wenn ein Pfad durch die NFA für eine bestimmte Zeichenfolge in diesem Status endet s, selbst wenn ein anderer Pfad durch vfür seinen Akzeptanzstatus endet.
  • Sei loop(v)eine Funktion auf einer NFA v, die bei jedem Akzeptanzzustand einen Selbstübergang hinzufügt. Mit anderen Worten, sobald ein Pfad zu einem Akzeptanzzustand führt, kann dieser Pfad für immer im Akzeptanzzustand bleiben, unabhängig davon, welcher Eingabe folgt.
  • Für negative Lookahead , f(v) = aa(loop(v)).
  • Für einen positiven Lookahead f(v) = aa(neg(v)).

Um ein intuitives Beispiel dafür zu geben, warum dies funktioniert, werde ich den regulären Ausdruck verwenden (b|a(?:.b))+, der eine leicht vereinfachte Version des regulären Ausdrucks ist, den ich in den Kommentaren von Francis 'Beweis vorgeschlagen habe. Wenn wir meine Konstruktion zusammen mit den traditionellen Thompson-Konstruktionen verwenden, erhalten wir:

Alt-Text

Die es sind Epsilon-Übergänge (Übergänge, die ohne Eingabe vorgenommen werden können) und die Anti-Akzeptanz-Zustände sind mit einem gekennzeichnet X. In der linken Hälfte des Diagramms sehen Sie die Darstellung von (a|b)+: any aoder bversetzt das Diagramm in einen Akzeptanzzustand, ermöglicht aber auch einen Übergang zurück in den Anfangszustand, damit wir es erneut ausführen können. Beachten Sie jedoch, dass wir jedes Mal, wenn wir mit einem übereinstimmen a, auch die rechte Hälfte des Diagramms eingeben, in der wir uns in einem Zustand ohne Akzeptanz befinden, bis wir mit "any" übereinstimmen, gefolgt von a b.

Dies ist keine traditionelle NFA, da traditionelle NFAs keine Anti-Akzeptanz-Zustände haben. Wir können jedoch den traditionellen NFA-> DFA-Algorithmus verwenden, um diesen in einen traditionellen DFA umzuwandeln. Der Algorithmus funktioniert wie gewohnt, wobei wir mehrere Läufe der NFA simulieren, indem wir dafür sorgen, dass unsere DFA-Zustände Teilmengen der NFA-Zustände entsprechen, in denen wir uns möglicherweise befinden. Die eine Wendung besteht darin, dass wir die Regel für die Entscheidung, ob ein DFA-Zustand ein ist, geringfügig erweitern (End-) Zustand akzeptieren oder nicht. Im traditionellen Algorithmus ist ein DFA-Zustand ein Akzeptanzzustand, wenn einer der NFA-Zustände ein Akzeptanzzustand war. Wir ändern dies, um zu sagen, dass ein DFA-Status genau dann ein Akzeptanzstatus ist, wenn:

  • = 1 NFA-Status ist ein Akzeptanzstatus und

  • 0 NFA-Zustände sind Anti-Akzeptanz-Zustände.

Dieser Algorithmus gibt uns einen DFA, der den regulären Ausdruck mit Lookahead erkennt. Ergo ist Lookahead regelmäßig. Beachten Sie, dass Lookbehind einen separaten Beweis erfordert.

Josh Haberman
quelle
In der Maschine, die Sie gegeben haben, akzeptieren Sie a. Welches ist nicht in (b | a (? =. B)). Auch ein Anti-Akzeptanz-Zustand ist ein Akzeptanz-Zustand, in dem eine Übereinstimmung fehlschlägt? Dann gibt es per Definition des Akzeptanzzustands keine Anti-Akzeptanz-Zustände! Oder fehlt mir etwas?
@Moron: Ich denke, Sie vermissen die Bedeutung meiner Anti-Akzeptanz-Zustände. Hier ist das gleiche Diagramm, jedoch mit nummerierten Zuständen: imgur.com/ho4C8.png Mein Computer akzeptiert dies nicht a, da awir nach dem Abgleich in die Zustände 4, 3, 1 und 5 übergehen können (unter Verwendung des NFA-> DFA-Algorithmus). Aber Zustand 5 ist ein Anti-Akzeptanz-Zustand, daher ist der DFA-Zustand, der den Zuständen 4, 3, 1 und 5 entspricht, gemäß den Regeln am Ende meiner Beschreibung kein Akzeptanzzustand.
Josh Haberman
@ Josh: Ist die Definition von nicht aa(v)abhängig von der Zeichenfolge s? dh das Set aa(v)kann variieren mit s. Sie sagen auch, dass ein Anti-Akzeptanz-Zustand zunächst ein Akzeptanz-Zustand ist. Wie kann eine Übereinstimmung fehlschlagen, wenn die Maschine in diesem Zustand endet? Entschuldigung, wenn ich es falsch lese.
@Moron: aa(v)kippt stattdessen einfach alle Akzeptanzzustände um, um Anti-Akzeptanzzustände zu sein, also sollte es nicht davon abhängen s. Beide vund aa(v)sind NFAs, keine Mengen. Ich folge Ihrem letzten Kommentar nicht: Es ist wahr, dass ves Akzeptanzzustände gibt, aber aa(v)keine Akzeptanzzustände hat, und das aa(v)ist es, was tatsächlich in der endgültigen NFA endet.
Josh Haberman
@Josh: Ihre Definition: "Sei aa (v) eine Funktion auf einem NFA v, die jeden Akzeptanzzustand in einen Anti-Akzeptanz-Zustand ändert ." Sie ändern also einen Akzeptanzzustand P in einen Nichtakzeptanzzustand, wenn die Maschine v bei einem Lauf im Zustand P endet und die Übereinstimmung fehlschlägt. Aber per Definition (Anmerkung v ist immer noch eine NFA) des akzeptierten Zustands ist die Übereinstimmung bestanden, wenn die Maschine dort endet! Und mit Menge, die ich meinte, der Menge von Zuständen in v, müssen Sie sich in Anti-Akzeptieren verwandeln, um v in aa (v) zu verwandeln. Würde das nicht von der Saite abhängen s? Ich hoffe ich bin jetzt klarer.
2

Ich habe das Gefühl, dass hier zwei unterschiedliche Fragen gestellt werden:

  • Sind Regex-Engines, die "Lookaround" enthalten, leistungsstärker als Regex-Engines, die dies nicht tun?
  • Ermöglicht "Lookaround" einer Regex-Engine die Analyse von Sprachen, die komplexer sind als diejenigen, die aus einer regulären Chomsky-Typ-3-Grammatik generiert wurden ?

Die Antwort auf die erste Frage im praktischen Sinne lautet ja. Lookaround bietet einer Regex-Engine, die diese Funktion verwendet, grundlegend mehr Leistung als eine, die dies nicht tut. Dies liegt daran, dass es einen umfangreicheren Satz von "Ankern" für den Abgleichsprozess bietet. Mit Lookaround können Sie einen gesamten Regex als möglichen Ankerpunkt definieren (Zusicherung einer Breite von Null). Sie können einen ziemlich guten Überblick über die Leistung dieser Funktion erhalten hier .

Lookaround ist zwar leistungsstark, hebt die Regex-Engine jedoch nicht über die theoretischen Grenzen einer Typ-3-Grammatik hinaus. Beispielsweise können Sie eine Sprache, die auf einer kontextfreien Grammatik vom Typ 2 basiert, mit einer mit Lookaround ausgestatteten Regex-Engine niemals zuverlässig analysieren . Regex-Engines sind auf die Leistung einer Finite-State-Automatisierung beschränkt. Dies schränkt die Ausdruckskraft jeder Sprache, die sie analysieren können, grundlegend auf das Niveau einer Typ-3-Grammatik ein. Unabhängig davon, wie viele "Tricks" zu Ihrer Regex-Engine hinzugefügt werden, werden Sprachen über eine kontextfreie Grammatik generiert wird immer über seine Möglichkeiten bleiben. Parsing Context Free - Typ 2-Grammatik erfordert Pushdown-Automatisierung, um sich zu "merken", wo sie sich in einem rekursiven Sprachkonstrukt befindet. Alles, was eine rekursive Auswertung der Grammatikregeln erfordert, kann nicht mit Regex-Engines analysiert werden.

Zusammenfassend lässt sich sagen, dass Lookaround Regex-Engines einige praktische Vorteile bietet, das Spiel jedoch theoretisch nicht "verändert".

BEARBEITEN

Gibt es eine Grammatik mit einer Komplexität zwischen Typ 3 (regulär) und Typ 2 (kontextfrei)?

Ich glaube die Antwort ist nein. Der Grund dafür ist, dass die Größe der NFA / DFA, die zur Beschreibung einer regulären Sprache erforderlich ist, theoretisch nicht begrenzt ist. Es kann beliebig groß werden und daher unpraktisch zu verwenden (oder zu spezifizieren). Hier sind Ausweichmanöver wie "Lookaround" nützlich. Sie bieten einen Kurzmechanismus, um anzugeben, was sonst zu sehr großen / komplexen NFA / DFA-Spezifikationen führen würde. Sie erhöhen nicht die Ausdruckskraft regulärer Sprachen, sondern machen sie nur praktischer. Sobald Sie diesen Punkt erreicht haben, wird klar, dass es viele "Funktionen" gibt, die Regex-Engines hinzugefügt werden könnten, um sie im praktischen Sinne nützlicher zu machen - aber nichts wird sie in die Lage versetzen, die Grenzen einer regulären Sprache zu überschreiten .

Der grundlegende Unterschied zwischen einer regulären und einer kontextfreien Sprache besteht darin, dass eine reguläre Sprache keine rekursiven Elemente enthält. Um eine rekursive Sprache auszuwerten, benötigen Sie eine Push-Down-Automatisierung, um sich zu "merken", wo Sie sich in der Rekursion befinden. Ein NFA / DFA stapelt keine Statusinformationen und kann daher die Rekursion nicht verarbeiten. Bei einer nicht rekursiven Sprachdefinition gibt es also NFA / DFA (aber nicht unbedingt einen praktischen Regex-Ausdruck), um dies zu beschreiben.

NealB
quelle
1
Stimmt es notwendigerweise, dass eine Grammatik, die leistungsfähiger als eine normale Grammatik ist, genauso leistungsfähig wie kontextfrei sein muss? dh. Ist bekannt, dass es keine Grammatik "zwischen" den beiden gibt?
BlueRaja - Danny Pflughoeft
@ BlueRaja: Genau das, was ich gedacht habe: die 'Grammatik-Kontinuum-Hypothese' :-)
@Moron @BlueRaja - Ich habe meine Antwort für Sie bearbeitet. Ich hoffe es hilft.
NealB
4
Natürlich gibt es viele Klassen von Grammatiken, die streng zwischen der Klasse der regulären Grammatiken und der Klasse der kontextfreien Grammatiken liegen, einschließlich trivialer Beispiele wie der Klasse der regulären Grammatiken zusammen mit den Grammatiken für die Sprache der ausgeglichenen Klammern. Die deterministischen kontextfreien Grammatiken sind ein nützlicheres Beispiel.
Christian Semrau
An NFA/DFA does not stack state information so cannot handle the recursion.Ja. Hören Sie also bitte auf, HTML mit regulären Ausdrücken zu analysieren!
Cruncher