Reguläre Ausdrücke sind es nicht

36

Fragen Sie sogar jemanden mit einem Hintergrund in der Informatik, was ein regulärer Ausdruck ist, und die Antwort geht wahrscheinlich über die Beschränkung hinaus, in Reichweite eines Automaten mit endlichen Zuständen zu sein.

Zum Beispiel der "reguläre Ausdruck"

/^1?$|^(11+?)\1+$/

Erstellt von der bekannten Perl-Persönlichkeit Abigail (und Teil von Perls Testsuite seit 2002) beschreibt eine Maschine, die nur zusammengesetzte unäre Zahlen akzeptiert, aber Übung 4.5 (b) in der dritten Ausgabe von Peter Linz ' Einführung in formale Sprachen und Automaten wird vom Leser verwendet das pumpende Lemma, um das zu beweisen

L={an:n is not a prime number}

ist keine reguläre Sprache.

Was sollen wir in Kontexten, in denen die Unterscheidung wichtig ist, die streng mächtigeren Ausdrücke nennen?

Greg Bacon
quelle

Antworten:

46

Larry Wall schlug vor, für den von Kleene vorgeschlagenen Formalismus "reguläre Ausdrücke" und für Ausdrücke für die weit verbreiteten Erweiterungen "reguläre Ausdrücke" zu verwenden. Es ist eine ziemlich weit verbreitete Konvention. Wenn Sie klarstellen möchten, dass es sich um reguläre Ausdrücke im Sinne einer formalen Sprache handelt, ist es in der Regel nicht schwierig, diese in reguläre Sprachen zu übersetzen.

Die Kraft von Regexen beruht auf dem Backtracking, und es wurde an Automaten für reguläre Sprachen mit Backtracking gearbeitet. Siehe insbesondere Becchi & Crowley, 2008, Erweiterung endlicher Automaten, um Perl-kompatible reguläre Ausdrücke effizient abzugleichen .

Charles Stewart
quelle
5
Ich bin damit einverstanden, dass etwas wie "Perl-Regex" ("POSIX-Regex" usw.) im Vergleich zu "reguläre Sprache" klar genug sein sollte, um mögliche Fehlinterpretationen zu vermeiden.
Jukka Suomela
Perl-Regexes haben viel mehr zusätzliche Funktionen als nur das Zurückverfolgen.
Reinierpost
@reinierpost Stimmt, aber ich denke, Backtracking ist aus formaler Sicht die wichtigste. Perl-Regexes haben Funktionen wie das Ausführen von beliebigem Perl-Code, aber ich denke, Regexes sollten so interpretiert werden, dass sie PCREs abdecken. PCREs enthalten solche Kuriositäten wie rekursive Muster, aber dies sind dunkle Künste, die Sie weit aus dem Bereich der regulären Sprachen herausführen. Ich könnte jedoch meine Antwort aktualisieren, um diese abzudecken.
Charles Stewart
18

Diese Ausdrücke wurden von Aho (Handbook of Theoretical Computer Science, Bd. A, S. 5) und Campeanu, Salomaa, Yu ("Eine formale Studie über praktische reguläre Ausdrücke", International Journal of Foundations of Computer Science, 14: 1007) untersucht –1018, 2003) sowie einige Folgepapiere.

Aho nennt die mächtigeren Ausdrücke "rewbr" (regulärer Ausdruck mit Rückbezügen), Campeanu et al. Verwenden Sie "Erweiterter regulärer Ausdruck" sowie "Praktischer regulärer Ausdruck". Wie es scheint, ist "erweiterter regulärer Ausdruck" der in der neueren Literatur am häufigsten verwendete Begriff.

Aufbauend auf dem Begriff "rationaler Ausdruck" der französischen Schule und angesichts der Tatsache, dass diese Ausdrücke in der realen Welt verwendet werden, mag ich selbst "echten Ausdruck".

Nachtrag: Ein Kapitel meiner Doktorarbeit befasst sich mit dieser Klasse formaler Sprachen (die entsprechende Arbeit soll auf der STACS 2011 erscheinen). Während ich dieses Kapitel und das Papier schrieb, experimentierte ich mit verschiedenen Begriffen. Schließlich entschied ich mich, erweiterte reguläre Ausdrücke für das Modell mit Rückverweisen und richtige reguläre Ausdrücke für die netten und normalen regulären Ausdrücke zu verwenden. Da es ziemlich ärgerlich ist, die Terminologie in einem Artikel zu ändern, der bereits vollständig (oder größtenteils) geschrieben ist, denke ich, dass einige an den Erfahrungen interessiert sein könnten, die zu meiner Wahl geführt haben:

Erstens rollen Regex und Rebr nicht wirklich mit der Zunge, und ihre wiederholte Verwendung im Verlauf eines ganzen Papiers war sehr mühsam zu schreiben und zu lesen, insbesondere wenn eine der möglichen Pluralformen verwendet wurde. PERL-ähnliche reguläre Ausdrücke waren auch ziemlich unhandlich. Natürlich bin ich kein Muttersprachler, also YMMV.

Zweitens, sobald man über beide Modelle sprechen möchte, ist es zweckmäßig, Begriffe zu verwenden, die eine Variation des regulären Ausdrucks darstellen , da man auf diese Weise Ähnlichkeiten oder Unterschiede nach Bedarf hervorheben kann (z. B. "ein regulärer Ausdruck, sei es richtig oder") verlängert"). Darüber hinaus kann der Sonderfall "erweiterte reguläre Ausdrücke ohne Rückverweise" leicht hervorgehoben werden, wenn über Sonderfälle in der gesamten Klasse gesprochen wird, anstatt verschiedene Modelle zu vergleichen.

Drittens habe ich es vorgezogen, einen Begriff zu verwenden, der bereits in der Literatur verwendet wird, anstatt eines neu geprägten Begriffs, so dass ich die Wahl zwischen erweiterten regulären Ausdrücken und praktischen regulären Ausdrücken hatte . Die zweite Wahl implizierte (zumindest implizit), dass korrekte reguläre Ausdrücke irgendwie unpraktisch sind, was sich ziemlich seltsam anfühlte (zumal Googles RE2 keine Backrefs verwendet und ziemlich praktisch zu sein scheint).

Natürlich ist diese Auswahl nur mein "persönliches lokales Maximum", und je nach Bedarf sind andere Auswahlmöglichkeiten möglicherweise besser geeignet.

Dominik D. Freydenberger
quelle
7
Leider wird der Begriff " erweiterter regulärer Ausdruck" bereits von POSIX verwendet. Dabei wird zwischen " grundlegender regulärer Ausdruck" (BRE) und " erweiterter regulärer Ausdruck" (ERE) unterschieden , die beide gemäß Ihrer Definition erweiterte reguläre Ausdrücke sind.
Jörg W Mittag
Jörg @: Eigentlich nach dieser weder erweitert noch grundlegende POSIX reguläre Ausdrücke sind mächtiger als normale reguläre Ausdrücke. Und reines (nicht-GNU) BRE scheint tatsächlich weniger mächtig zu sein als reguläre Ausdrücke (ohne einen Alternationsoperator).
7.
In "Über erweiterte reguläre Ausdrücke" von Carle und Narendran (2009) finden Sie neuere Ergebnisse zu diesem "rewbr": portal.acm.org/citation.cfm?id=1533235
Jakob,
Weitere aktuelle Ergebnisse zu dieser Sprachklasse: "Über den Schnittpunkt von Regex-Sprachen mit regulären Sprachen" von Campeanu und Santean (TCS 410, 2009) "Ein polynomieller Zeitvergleichstest für große Klassen erweiterter regulärer Ausdrücke" von Reidenbach und Schmid (CIAA 2010) ) und "Extended Regular Expressions: Prägnanz und Entscheidbarkeit" (von mir, erscheint auf der STACS 2011).
Dominik D. Freydenberger
6

Es ist bekannt, dass Perls sogenannter regulärer Ausdruck mächtig genug ist, um Turing vollständig zu machen. Es gibt sogar einen Compiler für Perl RegExp.

Daher bezweifle ich, dass es sinnvoll ist, nach einem Namen für diese Art von "regulären Ausdrücken" zu suchen.

Schauen Sie sich zum Beispiel http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm an

Arthur MILCHIOR
quelle
Hast du ein paar Hinweise?
András Salamon
5
@ András: Ich denke, Arthur spricht über Perls ?{CODE}Direktive, mit der Pattern-Ausdrücke Programmcode in reguläre Ausdrücke einbetten können. Ich verstehe, dass PCREs üblicherweise als "deklarativer" Teil der Sprache definiert werden, wobei die gesamte Sprache als Mustersprache bezeichnet wird. Laut WP, Aho, 1990, zeigen "Algorithmen zum Auffinden von Mustern in Strings", dass das Zugehörigkeitsproblem für reguläre Sprachen mit Backtracking NP vollständig ist. Für deklarative PCREs gibt es keine weiteren harten Funktionen.
Charles Stewart
Ich habe den Link hinzugefügt. Ich habe mir den Quellcode nicht angesehen, daher weiß ich nicht wirklich, wie es funktioniert und ob es Beweise dafür gibt, dass die Kompilierung wirklich korrekt ist.
Arthur MILCHIOR
1
Es tut uns leid, aber Ihrem Argument zufolge war es nicht sinnvoll, einen Namen dafür zu suchen, da Lambda-Kalkül Turing-vollständig ist. Gleiches gilt für alle anderen Turing-vollständigen Berechnungsformalismen und -sprachen. Turing-Vollständigkeit beschreibt nicht, wie aussagekräftig eine Sprache ist, und es macht keinen Sinn, Sprachen zu identifizieren, nur weil sie Turing-vollständig sind. Mein Beispiel zur Lambda-Rechnung war natürlich ein extremes.
Blaisorblade
2

Ich denke, der beste Begriff für "regulären Ausdruck im Kontext von Automaten" ist "rationaler Ausdruck", wie er beispielsweise in Sakarovitchs Elementen der Automatentheorie oder im Handbuch der gewichteten Automaten verwendet wird.

Michaël Cadilhac
quelle
1
Nicht sehr häufig verwendet, IMHO.
Blaisorblade
Es wird in der Theorie der gewichteten Automaten häufig verwendet, siehe en.wikipedia.org/wiki/Rational_language . Ich habe es einige Male im Bereich der Sprachen über Gruppen hinweg gesehen.
Michaël Cadilhac,
1

In Anbetracht der anderen Antworten würde ich vorschlagen, dass "reguläre Sprachen" sicher sind, und nach kurzer Bemerkung des Unterschieds über "praktische reguläre Ausdrücke" für reguläre Ausdrücke (mit Rückverfolgung) zu sprechen.

Beachten Sie auch, dass derselbe reguläre und der praktische Ausdruck für reguläre Ausdrücke unterschiedliche Semantiken haben kann, da im letzteren Fall die Semantiken als Backtracking definiert werden und unterschiedliche Ergebnisse liefern. Details würden vom Thema abweichen, aber ich werde antworten, wenn Sie eine andere Frage dazu stellen (vielleicht auf SO anstatt hier, keine Ahnung) und mich durch einen Kommentar benachrichtigen.

Blaisorblade
quelle
0

Wir könnten sie Musterausdrücke nennen . Dies kann zu Verwechslungen mit Mustersprachen führen, die jedoch weniger häufig sind.

Raphael
quelle
2
Grundsätzlich stimme ich mit Ihrer Argumentation, aber Campeanu, Santean und Yu haben bereits die Bezeichnung für Muster Ausdrücke bezeichneten eine ähnliche Klasse von Sprachen mit „sauberen“ Definition (siehe „Pattern Ausdrücke und Muster - Automaten“, 92 IPL (2004 )
Dominik D. Freydenberger