Reguläre Ausdrücke und 'Klammern erfassen' mit 'Rückreferenzen'

7

Wir wissen, dass reguläre Ausdrücke (RE) mit endlichen Automaten (FA) implementiert werden. In einigen Sprachen (wie JavaScript) in RE gibt es Funktionen wie "Erfassen von Klammern" mit "Rückreferenzen":

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses

(x) Entspricht 'x' und merkt sich die Übereinstimmung, wie das folgende Beispiel zeigt. Die Klammern werden als Erfassungsklammern bezeichnet. Die '(foo)' und '(bar)' im Muster / (foo) (bar) \ 1 \ 2 / stimmen überein und merken sich die ersten beiden Wörter in der Zeichenfolge "foo bar foo bar". Die \ 1 und \ 2 im Muster stimmen mit den letzten beiden Wörtern der Zeichenfolge überein.

Ich möchte wissen, ob dieses Muster /(foo) (bar) \1 \2/tatsächlich ein RE gemäß der Definition von RE ist, die wir in der theoretischen formalen Sprache haben, oder ob es etwas Mächtigeres ist. Und wenn ja, würde ich gerne wissen, ob diese Art von Funktion auch mit FA oder auf andere Weise implementiert ist (insbesondere wie sie implementiert wird).

asv
quelle
Unter swtch.com/~rsc/regexp/regexp1.html finden Sie eine ausführliche Beschreibung der tatsächlichen Auswirkungen dieses Unterschieds auf die Leistung (Implementierungsebene). (Bearbeiten: Ich sehe, dass es bereits von dieser Antwort verlinkt wurde .)
Wildcard

Antworten:

7

Die RE in der Automatentheorie entsprechen FA, aber für die Programmiersprachen (Regexp) gilt dies nicht mehr.

Die regulären Ausdrücke in den Programmiersprachen (wie PCRE) sind weitaus leistungsfähiger als die regulären Ausdrücke (Typ 3) in der Automatentheorie.

Die übereinstimmende Klammer ist weder regulär noch kontextfrei, sondern eine kontextsensitive Funktion. Der RegExp aus der Frage unterstützt jedoch Typ 2 oder Typ 1 nicht vollständig.

Der Bracket Matching wird nicht über FA implementiert. Im Falle von PCRE wird es durch Raten und Zurückverfolgen implementiert.

Schauen Sie sich die Beschreibung von Perl Monks zu PCRE an .

Böse
quelle
Vielen Dank. In diesem Fall ist RegExp ein Missbrauch der (formalen) Sprache.
ASV
5
Nun, es ist die Namenskollision. Die allererste Idee war so etwas wie RE, aber selbst als sie sich entwickelte, blieb der Name erhalten.
Böse
1
@asv: Für einige Zeit nach Einführung der Erfassung wurde der RE mit Erfassungsgruppen als erweiterter regulärer Ausdruck oder ERE bezeichnet. Dann, einige Zeit nachdem Perl seine Version von RE eingeführt hatte, wurde sie Regex genannt, um sie von POSIX-standardisiertem Regexp und ERE zu unterscheiden (beachten Sie Regex vs Regexp). Heutzutage ist es den Leuten egal.
Slebetman
9

Diese erweiterten Begriffe regulärer Ausdrücke erfassen mehr als nur die regulären Sprachen. Entspricht beispielsweise ([ab]*)\1der Sprache , die nicht regulär und nicht einmal kontextfrei ist (Beispiel 2.38 von Sipser, Einführung in die Theorie von Berechnung , 3. Auflage).{www{a,b}}

"Reguläre" Ausdrücke, die nicht mit regulären Sprachen übereinstimmen, können nicht in endliche Automaten übersetzt werden, da endliche Automaten nur mit den regulären Sprachen übereinstimmen. Ein Nebeneffekt davon ist, dass viele Bibliotheken nicht einmal versuchen, zu Automaten zu kompilieren, was zu einer extrem langsamen Übereinstimmung führen kann, selbst wenn ein "regulärer" Ausdruck ein echter regulärer Ausdruck ist. Russ Cox hat einen ausgezeichneten Artikel darüber geschrieben, der auch einen großen Teil der Geschichte betrifft.

David Richerby
quelle
Vielen Dank für Ihr Beispiel und für diese Informationen. :)
asv
8

Die Antworten beantworten wahrscheinlich, was Sie fragen möchten , aber nicht, was Sie fragen.

Ich möchte wissen, ob dieses Muster /(foo) (bar) \1 \2/tatsächlich ein RE gemäß der Definition von RE ist, die wir in der theoretischen formalen Sprache haben, oder ob es etwas Mächtigeres ist. Und wenn ja, würde ich gerne wissen, ob diese Art von Funktion auch mit FA oder auf andere Weise implementiert ist (insbesondere wie sie implementiert wird).

In der Tat dies ist ein regulärer Ausdruck, mit einem endlichen Automaten realisiert werden kann, da \1ist garantiert , um zu bewerten , foound \2wird garantiert , um zu bewerten bar.

Daher könnte eine Regex-Engine diese Tatsache nutzen, um tatsächlich einen endlichen Automaten zu erstellen, der die von Ihnen vorgeschlagene Sprache genau beschreibt.

Wenn Sie jedoch Aufnahmen von Bedingungen abhängig machen , kann dies falsch werden, wie andere bereits erwähnt haben.

(Beachten Sie, dass ich Sie können Schwierigkeiten haben, weil eine Sprache wie /(a(aa|aa)|(aa|aa)a)\1\2/kann noch über einen FA beschrieben. Ich nur gab eine notwendige Bedingung, keine ausreichende ein. Edit: Es ist einfach fiel mir ein , dass eine bedingte aufweist , ist weder notwendig noch ausreichend, da /(a*)\1/es auch in einen endlichen Automaten verwandelt werden /(ab*)\1/kann, wohingegen dies nicht möglich ist. Ich denke, es war nur eine Faustregel.)

user541686
quelle
Ok, ein bestimmtes Muster mit 'Capturing-Klammer' kann RE sein. Gute Beobachtung.
Asv
@asv: Ja. Ich denke auch, dass eine andere Sache, die bei allen Antworten hier (einschließlich meiner) irreführend ist, ist, dass das Problem nicht die Erfassung von Klammern selbst ist, sondern die Rückverweise, die sich auf sie beziehen. Ich erinnere mich, dass ich gelesen habe, dass das Erfassen von Klammern ohne Rückverfolgung behandelt werden kann, solange es keine Rückverweise gibt. Ich weiß jedoch nicht genau, ob dies wirklich mit endlichen Automaten möglich ist oder nicht (ich habe den Eindruck, dass dies möglich ist, aber ich weiß nicht genau, wie). Es sollte aber auch andere Möglichkeiten geben, mit ihnen umzugehen, ohne sie zurückzuverfolgen, z. B. über LR-Parsing oder ähnliches.
user541686
Ja, die Frage ist: Rückreferenzen
asv
0

Bestimmte Regex-Implementierungen erstellen keinen DFA. Bei der java.util.regex OpenJDK- Implementierung ist dies beispielsweise nicht der Fall. Infolgedessen ist die Übereinstimmungszeit langsamer als bei einer DFA-kompilierten Implementierung wie dk.brics.automaton . Letzteres unterstützt jedoch die Erfassung von Gruppen aufgrund der zugrunde liegenden Implementierung nicht.

vuamitom
quelle
Denken Sie daran, dass die NFA-> DFA-Konstruktion sehr teuer sein kann (2 ^ # Knoten).
Mevets
Oh ja, danke, dass Sie darauf hingewiesen haben. Ich habe meine Antwort aktualisiert, um zu berücksichtigen, dass nur die Übereinstimmungszeit von DFA-basierten Geräten kürzer ist.
Vuamitom