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":
(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).
Antworten:
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 .
quelle
Diese erweiterten Begriffe regulärer Ausdrücke erfassen mehr als nur die regulären Sprachen. Entspricht beispielsweise{ww∣w∈{a,b}∗}
([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)."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.
quelle
Die Antworten beantworten wahrscheinlich, was Sie fragen möchten , aber nicht, was Sie fragen.
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 bewertenbar.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.)quelle
Bestimmte Regex-Implementierungen erstellen keinen DFA. Bei der
java.util.regexOpenJDK- 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.quelle