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
ist keine reguläre Sprache.
Was sollen wir in Kontexten, in denen die Unterscheidung wichtig ist, die streng mächtigeren Ausdrücke nennen?
quelle
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.
quelle
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
quelle
?{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.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.
quelle
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.
quelle
Wir könnten sie Musterausdrücke nennen . Dies kann zu Verwechslungen mit Mustersprachen führen, die jedoch weniger häufig sind.
quelle