Sind reguläre Ausdrücke eine Programmiersprache?

Qualifizieren sich reguläre Ausdrücke im akademischen Sinne als Programmiersprache?

Die Motivation für meine Neugier ist eine SO-Frage, die ich gerade angeschaut habe und die gefragt wurde: "Can Regex Do X?" und es hat mich gefragt, was im allgemeinen Sinne über die möglichen Lösungen gesagt werden kann, die sie verwenden.

_{Grundsätzlich frage ich: "Sind reguläre Ausdrücke vollständig?"}

Reguläre Ausdrücke sind eine bestimmte Art der formalen Grammatik , mit der Zeichenfolgen und andere Textinformationen analysiert werden, die in der formalen Sprachtheorie als "reguläre Sprachen" bezeichnet werden. Sie sind keine Programmiersprache als solche. Sie sind eher eine Abkürzung für das Codieren, deren Implementierung ansonsten äußerst mühsam und noch verwirrender wäre als das manchmal arkane Regex.

Programmiersprachen werden normalerweise als Sprachen definiert, die Turing Complete sind . Solche Sprachen müssen jede berechenbare Funktion verarbeiten können . Regex passt nicht in diese Kategorie.

Wenn Sie eine Sprache wünschen, die wie Regex aussieht, versuchen Sie J.

Es ist schwierig, Fragen vom Typ zu beantworten „ist X ein Y “, wenn die Teilnehmer der Debatte verwenden unterschiedliche Definitionen von X und Y . Es kann sein, dass für einige Definitionen die Antwort "Ja" lautet und für einige Definitionen die Antwort "Nein" lautet. Vor allem, wenn die Antwort von technischen Details abhängt, bei denen sich die Definitionen unterscheiden. Auch diese Diskussion enthält einige Fehlinformationen, bitte haben Sie etwas Geduld mit einer längeren Antwort.

Was meinen wir mit einer " Programmiersprache "?

Eine einfache Antwort könnte "eine Sprache sein, die zum Erstellen von Programmen verwendet wird". Klar, aber: welche Art von Programmen? Was ist mit einer Sprache, die zum Erstellen einiger Arten von Programmen verwendet werden kann, aber nicht für andere Arten von Programmen? Hier sind zwei spezifische Beispiele zur Veranschaulichung der Extremfälle:

1) Eine imaginäre Sprache mit dem Namen M funktioniert folgendermaßen: Wenn das Programm den einzelnen Buchstaben "m" enthält, wird eine Partie Minesweeper erstellt. Alles andere ist ein Syntaxfehler.

Intuitiv ist dies nicht das, was wir mit "einer Programmiersprache" meinen. Aber die Marketingabteilung von M könnte argumentieren, dass es die Definition technisch erfüllt, weil es verwendet werden kann, um ein Programm zu erstellen. Sicher, der Compiler übernimmt einige wichtige Aufgaben für Sie, aber genau das tun Compiler, nicht wahr? Ein Compiler der C-Sprache übersetzt auch einige einfache Wörter in Dutzende von Prozessoranweisungen. Der M-Compiler geht noch weiter und macht Ihre Arbeit noch einfacher.

2) Wenn Sie die Originalversion des berühmten Turbo Pascal installieren, können Sie viele Arten von Programmen schreiben. Sie können jedoch kein Spiel schreiben, das im Webbrowser ausgeführt wird, da die erforderliche API einfach nicht vorhanden ist.

Was genau macht Turbo Pascal zu einer Programmiersprache, aber M hat es nicht? Einfach gesagt, können Sie mehr in Pascal als in M. Aber stellen wir eine M.NET haben, die ein Sweeper Spiel in einem Webbrowser ausgeführt wird erstellt. Nun haben wir also etwas, was Pascal und M.NET nicht können, aber wir haben auch etwas, was M.NET und Pascal nicht können. Warum sollten wir die Vorteile von Pascal für wichtig und die Vorteile von M.NET für irrelevant halten?

Die Antwort ist, dass Sie alle Arten von Algorithmen in Pascal schreiben können, aber Sie können keine Algorithmen in M oder M.NET schreiben . Sicher, M kompiliert Ihren Befehl "m" und C kompiliert Ihren Befehl "strcmp". Aber Sie können "strcmp" in einen größeren Kontext stellen, z. B. zwei Dateien zeilenweise vergleichen oder tausend Zeichenfolgen lesen und sie alphabetisch sortieren oder ... nun, Millionen anderer Dinge. Und genau diese Fähigkeit, gegebene Befehle in jedem Algorithmus zu verwenden , macht den Kern einer Programmiersprache aus.

Was genau ist ein Algorithmus und was ist "irgendein Algorithmus"? In der Informatik verwenden wir die Wörter Turing-complete . Die Idee ist, dass es eine Reihe von Computersprachen gibt, in denen jeder von ihnen alle simulieren kann. Eine dieser Sprachen ist die Turing-Maschine, weshalb sie so genannt werden. Pascal ist da, C ist da, Java ist da, Python ist da, Lisp ist da, Smalltalk ist da, sogar XSLT ist da. Unser hypothetisches M und M.NET sind nicht da. Sie können an jeder Universität, die einen anständigen Informatikkurs anbietet, mehr darüber lernen, aber die Idee ist, dass eine Turing-vollständige Sprache alles kanndas kann eine andere Turing-complete-Sprache, wenn Sie ihnen die minimal notwendige API geben. (Wenn Sie Pascal eine Webbrowser-API geben, können Sie alle Arten von Spielen im Webbrowser erstellen. Wenn Sie M eine Webbrowser-API geben, können Sie immer noch nur Minesweeper erstellen.) Wir könnten metaphorisch sagen, dass wenn Wenn Sie alle APIs aus einer Programmiersprache entfernen, bleibt das Wichtigste übrig.

Was meinen wir mit " regulären Ausdrücken "?

Verschiedene Programmiersprachen implementieren sie leicht unterschiedlich. Die ursprüngliche Idee war jedoch, dass reguläre Ausdrücke sogenannte reguläre Sprachen ausdrücken . Beachten Sie, dass wir hier nicht über Programmiersprachen sprechen, sondern über (pseudo-) menschliche Sprachen. Stellen Sie sich vor, Sie finden einen exotischen Stamm, der eine Sprache spricht, die nur aus den Wörtern "ba", "baba", "bababa" usw. besteht. Sie könnten diese Sprache verbal beschreiben als "eine Silbe 'ba', die ein oder mehrere Male wiederholt wird" oder einen regulären Ausdruck als "(ba) +" verwenden.

Die regulären Ausdrücke sollen ausdrücken: "nichts", "dieser Buchstabe", "dies, gefolgt von jenem", "dies oder jenem", "dies, wiederholt ein- oder mehrmals" und "nicht dies". - Das ist die mathematische Definition. Alles andere ist nur eine praktische Verknüpfung, die aus den vorherigen Komponenten erstellt wurde. Zum Beispiel kann "dies, zwei- oder dreimal wiederholt" mit "dies, gefolgt von diesem, gefolgt von (dies oder nichts)" übersetzt werden, aber es könnte praktischer sein, "ba {2,3}" als "baba" zu schreiben (ba)? "

Im wirklichen Leben implementiert eine typische Implementierung von "regulären Ausdrücken" mehr als dies. Verwenden Sie beispielsweise die mathematische Definition, eine Sprache von "aba", "aabaa", "aaabaaa" usw. - eine beliebige Anzahl von "a", gefolgt von einem "b", gefolgt von der gleichen Anzahl von "a" "s - ist keine reguläre Sprache. Viele "reguläre Ausdrücke", die heute verwendet werden, können dies jedoch erkennen, indem sie das zusätzliche Konzept "das Gleiche, was wir zuvor gefunden haben" verwenden, das als "(a +) b \ 1" geschrieben wurde. Mit diesem zusätzlichen Konzept können wir einige coole Dinge tun, zum Beispiel Wörter erkennen, die aus einer Primzahl von Buchstaben bestehen. Trotzdem können wir keinen Algorithmus ausführen ... für eine Erklärung, warum,

Zurück zum ursprünglichen Thema: Sind reguläre Ausdrücke (definiert als: Ausdrücke, die reguläre Sprachen in der Chomsky-Hierarchie beschreiben, oder als: erstere plus die Operation \ 1) eine Programmiersprache (definiert als: Turing-complete)? Die Antwort lautet nein . Nein, Sie können keinen Algorithmus mit regulären Ausdrücken implementieren , und die Fähigkeit, einen Algorithmus zu implementieren , wird von Menschen, die Informatik studieren, normalerweise als das Wesen der Programmiersprache verstanden.

Natürlich kann jeder die Antwort ändern, indem er auf einer anderen Definition besteht . Wie ich zu Beginn schrieb, sind hier die technischen Details wichtig. Wenn Sie sie falsch verstehen, erhalten Sie eine falsche Antwort.

Und wenn Sie nicht an technischen Details interessiert sind , könnte die Antwort lauten: Können Sie reguläre Ausdrücke (und sonst nichts) verwenden, um ein Programm zu erstellen? Warum also Programmiersprache? (Eine Antwort wie diese wurde jedoch hier heruntergeladen und gelöscht, weshalb ich diese längere Version geschrieben habe.)

BEARBEITEN: Außerdem kann jeder eine Bibliothek erstellen, die seine eigene neue Variante von "regulären Ausdrücken" mit einigen neuen Funktionen implementiert. Irgendwann werden die neuen Funktionen können für das gesamte System zu werden Turing-vollständig genug sein. Ein triviales Beispiel wäre die Einbettung einer Turing-vollständigen Sprache mit einer neuen Syntax. es kann aber auch weniger offensichtlich vorkommen. Vielleicht ist es schon passiert.

In .Net kann Regex nicht nur mehrere Formen von Bedingungen verarbeiten, indem verschiedene Kombinationen von Alternativen und Lookarounds verwendet werden, sondern auch seinen eigenen Stapel bearbeiten.

(?xm)
    (?>
        <(?<Tagname>table)[^>]*>
    )
(?(Tagname)
    (
        </(?(?!\k'Tagname')(?<-Tagname>))*\k'Tagname'>(?<-Tagname>)
    |
        (?>
            <(?<Tagname>[a-z][^\s>]*)[^>]*>
        )
    |
        [^<]+
    )+?
    (?(Tagname)(?!))
)

Dies ist zum Beispiel ein kleiner Ausschnitt, den ich geschrieben habe, um eine HTML-Tabelle abzurufen. Im Gegensatz zu anderen Regex-Modulen wird hiermit der Stapel der Erfassungssammlungen (Push, Peek und Pop) gesteuert und es können verschachtelte Objekte verarbeitet werden. Ich habe ein komplexeres, aber es ist irgendwie proprietär.

Ich denke, in diesem Beispiel kann Regex als mit allen grundlegenden Anforderungen einer Programmiersprache angesehen werden. Es verfügt über Variablen, Inline-Speicher, Bedingungen, Ein- und Ausgabe und wird mit einer von mehreren Regex-Kompilierungsengines (in diesem Fall .Net) kompiliert.

Als Reaktion auf das überstrapazierte Quietschen, um HTML mit Regex zu analysieren (NIE), habe ich eine vorab eingegebene Antwort gepostet, die ich posten kann: Parsing HTML

Ein weiteres Beispiel (nur eine Demonstration) ist das folgende:

Function Regex("<(td>)((?:[^<]*(?(?!</\1)<))*)</\1")
    Group(0) = "<"
    Group(1) = "td>"
    Group(0) += Group(1)
    Group(2) = LoopMethod()
    Group(0) += Group(2)
    Group(0) += "</" & Group(1)
    Return Group()
End Function

Function LoopMethod()
    retGroup = ""
    Do
        tmpGroup = Everything that is NOT an Opening HTML Delimeter
        If the Text following tmpGroup Does NOT Equal "</" & Group(1) Then
            tmpGroup += "<"
            retGroup += tmpGroup
        Else
            Exit Do
        End If
    Loop
    Return retGroup
End Function

Wieder für die HTML-Papageien: Analysieren von HTML

Dies zeigt einen einfacheren Regex, der Schleifen und Bedingungen ausführt (Algorithmen?). Das einzige, was fehlt, ist die tatsächliche mathematische Berechnung. Dies ist ein detaillierterer regulärer Ausdruck, mit dem eine TD-Zelle effizienter abgerufen wird als mit der typischen Methode "(. *?)".

Aber selbst als Regex-Enthusiast und selbsternannter Meister würde ich niemandem erzählen, dass Regex eine Programmiersprache ist. Mein eigenes Argument gegen mich ist, dass es nicht alleine stehen kann, es muss durch seine eigene Engine laufen, während es von einer anderen Programmiersprachen-Engine unterstützt wird.

Obwohl ein Suchen / Ersetzen in regulären Ausdrücken keine Turing-vollständige Programmiersprache ist, wie in den vorherigen Antworten erläutert, können Sie, wenn Sie wiederholte Aktionen des Ersetzens durch reguläre Ausdrücke zulassen, jede Turing-Maschine mit regulären Ausdrücken codieren:

Wiederholtes Suchen / Ersetzen durch reguläre Ausdrücke ist eine Programmiersprache, die Turing vollständig macht

Infolgedessen können Sie jede berechenbare Funktion mit derselben Suche berechnen und den regulären JavaScript-Ausdruck immer wieder ersetzen.

Um die Turing-Vollständigkeit zu beweisen, genügt es, eine Turing-Maschine in regulären Ausdrücken zu suchen / ersetzen. Angenommen, der Status des Editors lautet:

0000#12345:01-5:0#0000000

was als ein Band von Symbolen mit einem Leser gelesen werden kann:

[left symbols]#[set of states]:[set of symbols]-[current state]:[current symbol]#[right symbols]

Für die Regel 0 in Zustand 5 lesen, 1 schreiben und ihren Zustand in 3 ändern und sich nach links bewegen, abstrahieren wir sie unter Verwendung der folgenden Notation:

5:0 => 1, 3:[left]

Wir kodieren die vorherige Notation in einen regulären Suchausdruck:

(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#

und sein Ersetzungsausdruck (javascript-like)

#12345:01-$4:$1#$8

Ok, wie codiere ich nun viele Regeln? Wir verwenden die Verkettung mit dem orOperator |für die Suche nach regulären Ausdrücken und kombinieren die Ergebnisse in Ersetzungsgruppennummern mit Offsets. Betrachten wir zum Beispiel den Satz von vier Regeln.

5:0 => 1, 3:left
3:0 => 1, 5:right
5:1 => 1, 5:right
3:1 => 1: 3:stop

Wir codieren sie in einem Suchen und Ersetzen-Ausdruck:

Search:
(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#

Replace by:
$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8

Probieren Sie es in Ihrer Lieblings-Javascript-Engine aus:

function turingstep(s) {
  return s.replace(/(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#/g,"$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8");
}

var tape = "0000#12345:01-5:0#0000000"
for(var i = 0; i < 6; i++) {
  console.log(tape)
  tape = turingstep(tape)
}