Ist „regex“ in modernen Programmiersprachen wirklich „kontextsensitive Grammatik“?

Question

Im Laufe der Jahre „regex“ Pattern-Matching immer mächtiger zu dem Punkt, wurde immer, wo ich frage mich: Ist es wirklich nur kontextsensitive-Grammatik Matching? Ist es eine Variation / Erweiterung der kontextfreien Grammatik-Matching? Wo ist es jetzt, und warum wir es nicht einfach anrufen, dass anstelle des alten, restriktiv „regulären Ausdrucks“?

Answer 1

Insbesondere Rückreferenzierungen zur Erfassung Klammern machen regulären Ausdrücken komplexer als reguläre, kontextfrei oder kontextsensitive Grammatiken. Der Name ist einfach historisch gewachsen (so viele Wörter). Siehe auch dieser Abschnitt in Wikipedia und diese Erklärung mit einem Beispiel von Perl.

Answer 2

So wie ich es sehe:

• Reguläre Sprachen:
  • Matched von Zustandsmaschinen. Es kann nur eine Variable verwendet werden, um den Strom zu repräsentieren „Standort“ in der Grammatik angepasst werden: Rekursion kann nicht umgesetzt werden
• Kontextfreie Sprachen:
  • Matched durch eine Stapelmaschine. Der aktuelle „Standort“ in der Grammatik wird von einem Stapel in der einen oder anderen Form dargestellt. Kann nicht „erinnern“ alles, was vor aufgetreten
• Kontextsensitive Sprachen:
  • Die meisten Programmiersprachen
  • Alle Die meisten menschlichen Sprachen

Ich weiß von regulären Ausdruck Parser, die es Ihnen ermöglichen, gegen etwas passen der Parser bereits begegnet ist, so etwas wie eine kontextsensitive Grammatik zu erreichen.

Dennoch regulärer Ausdruck Parser, aber anspruchsvoll sie auch sein mögen, läßt keine rekursive Anwendung von Regeln, die eine bestimmte Anforderung für kontextfreie Grammatiken ist.

Der Ausdruck regex , meiner Meinung nach, bezieht sich vor allem auf die Syntax verwendet, um diejenigen regulären Grammatiken zum Ausdruck bringt (die Sterne und Fragezeichen).

Answer 3

Es gibt Funktionen in modernen regulären Ausdruck Implementierungen, die die Regeln des klassischen regulären Ausdruck brechen Definition .

Zum Beispiel Microsofts .NET Balancing-Gruppe (?< name1 - name2 > … ) :

^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$

Das hat entsprechen die Sprache L ₀₁ = { ε , 01, 0011, 000111, ...}. Aber diese Sprache nicht regulär ist nach dem Pumping Lemma .