Im Laufe der Jahre, "Regex" Mustererkennung wurde immer leistungsfähiger zu dem Punkt, wo ich frage mich: Ist es wirklich nur kontextsensitiv-Grammatik-Abgleich? Ist es eine Variation/Erweiterung der kontextfreien Grammatik? Wo ist es jetzt und warum nennen wir es nicht einfach den alten, restriktiven "regulären Ausdruck"?Ist "Regex" in modernen Programmiersprachen wirklich "kontextsensitive Grammatik"?
Insbesondere Rückreferenzen zum Erfassen von Klammern machen reguläre Ausdrücke komplexer als normale, kontextfreie oder kontextsensitive Grammatiken. Der Name ist einfach historisch gewachsen (so viele Wörter). Siehe auch this section in Wikipedia und dieses explanation with an example von Perl.
So wie ich es sehe:
Ich weiß von regelmäßigen
Dennoch erlauben reguläre Ausdrucksparser, so ausgeklügelt sie auch sein mögen, keine rekursive Anwendung von Regeln, was eine unabdingbare Voraussetzung für kontextfreie Grammatiken ist.
Der Begriff regex, meiner Meinung nach, bezieht sich vor allem auf die Syntax verwendet, um diese regulären Grammatiken (die Sterne und Fragezeichen) auszudrücken.
Lookahead/Lookbehind und Benennungen fügen definitiv etwas hinzu, das außerhalb von regulären regulären Ausdrücken liegt - Speicher. Sind wir nicht auf PDA-Ebene? – notnot
Es ist im allgemeinen nicht wahr, dass die natürliche Sprache kontextsensitive ist, siehe http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf –
ah, das ist die guten Sachen – notnot
Es gibt Funktionen in modernen Regular Expression-Implementierungen, die die Regeln der classic regular expression definition brechen.
Zum Beispiel Microsoft’s .NET Balancing Group(?<name1-name2> …):
^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$
Diese tut die Sprache entsprechen L ₀₁ = {ε, 01, 0011, 000111, ...}. Aber diese Sprache ist gemäß der Pumping Lemma nicht regelmäßig.
Ich weiß, dass es über den klassischen Regex hinausgeht, aber ich frage mich, wie viel weiter. Fabians Link oben ist interessant. – notnot
Könnten Sie bitte den Unterschied zwischen "regulärer Sprache" und "regulärem Ausdruck" erklären? –
Ist es wirklich mächtiger als CSG? Kannst du ein Beispiel geben? – notnot
Eine reguläre Sprache kann durch eine reguläre Grammatik beschrieben werden (siehe http://en.wikipedia.org/wiki/Regular_grammar), während reguläre Ausdrücke eine Mustersprache sind, die weniger eingeschränkt und daher komplexer zu verarbeiten ist. –