von WoNáDo
Nach monatelanger Pause habe ich jetzt ein bisschen Zeit den dritten Teil dieses einführenden Überblicks zu schreiben. Offen ist noch die Frage nach der Überprüfung, also ob ein Text einer vorgegebenen Beschreibung genügt. Beim Versuch der Beantwortung beschränke ich mich jetzt auf reguläre Ausdrücke und deren Erweiterungen.
Dieser Teil ist auch ein wenig subjektiver als alle anderen Beiträge. Ich habe bisher (hoffentlich) immer Beispiele und Beschreibungen gebracht und die Frage, ob ein Einsatz in bestimmten Situationen sinnvoll ist, restlos dem Leser überlassen. Das basierte auf der Voraussetzung, dass ein Benutzer regulärer Ausdrücke schon wissen wird, warum er sie einsetzen will (oder durch Dritte erzwungen einsetzen muss).
Diese Basis bleibt bestehen, nur werde ich bezüglich der Anwendung erweiterter regulärer Ausdrücke auf ein paar Probleme eingehen, die meiner Meinung nach die sinnvollen Einsatzbereiche begrenzen.
Also los...
Im Teil 0.1 habe ich eine Definition echter regulärer Ausdrücke aufgeführt. Diese haben eine ganz besondere Eigenschaft, sie sind nämlich zu Chomsky-3-Grammatiken, deterministischen finiten Automaten und nichtdeterministischen finiten Automaten äquivalent. Wer mehr darüber wissen möchte findet umfangreiche Beiträge in praktisch allen Büchern zur Theoretischen Informatik.
Dies hat ausgesprochen praktische Konsequenzen. Zuerst einmal lässt sich relativ leicht untersuchen, ob ein echter regulärer Ausdruck genau das erkennt, was man erkennen will. Dies ist bei vielen Anwendungen (siehe weiter unten) sehr wichtig. Die weitere Konsequenz ist, dass jeder echte reguläre Ausdruck mittels eines Algorithmus in einen deterministischen finiten Automaten überführt werden kann. Auf diese Art und Weise kann ein String sehr effektiv untersucht werden, weil (ausser bei hier nicht interessierenden Sonderfällen) jedes Zeichen des Strings genau einmal angefasst werden muss, Backtracking also entfällt. Wen es interessiert - der (f)lex ist auf diese Art und Weise implementiert (und dort tritt auch die Besonderheit im Zusammenhang mit einem look-ahead auf).
Ich gehe auf all das aber nicht näher ein, weil Ruby (wie auch Perl, Python, etc.) erweiterte reguläre Ausdrücke erlaubt, die nur noch mittels Backtracking-Algorithmen auf Strings angewandt werden können. Daher kommt auch das Problem, dass scheinbar harmlos aussehende Ausdrücke quasi Endlosschleifen produzieren (in Wirklichkeit laufen sie nicht endlos, sondern nur ein paar Jahrtausende). Wer Details dazu wissen will, sollte zuerst einmal den schon oft erwähnten Friedl lesen, und zwar sehr ausführlich. Wer gerne in C-Programmen rumwühlt kann sich ja auch mal PCRE-Library ansehen, die eine allgemeine Implementierung der Perl-kompatiblen erweiterten regulären Ausdrücke enthält.
Die auftretenden Probleme mit erweiterten regulären Ausdrücken werden in den Sprachen deshalb in Kauf genommen, weil die echten regulären Ausdrücke für Pattern-Matching-Anwendungen einfach zu wenig können - es gibt ja nicht einmal einfangende Gruppen, die später im Programm benutzt werden können.
Die Pattern-Matching-Möglichkeiten von Ruby basieren seit Ruby 1.9 auf der Oniguruma-Maschine, welche ausgesprochen umfangreiche Erweiterungen beinhaltet. Auf die Möglichkeiten bin ich schon in einigen Artikeln eingegangen, weitere werden noch folgen.
Inwieweit man die vorhandenen Möglichkeiten auch ausnutzen sollte ist eine andere Frage, auf die ich in den letzten beiden Abschnitten eingehen werde.
Es gibt Anwendungen, bei denen es nicht so extrem wichtig ist, wenn durch komplizierte erweiterte reguläre Ausdrücke zu viel erkannt wird. Der zweite Teil der Bezeichnung, die oft als Erklärung der Abkürzung Perl genannt wird, nennt einen wichtigen Teil dieser Anwendungen: Practical Extraction and Report Language.
Was sind denn die charakteristischen Eigenschaften von Report-Anwendungen? - Ein Report wird erstellt, damit Menschen, also urteilsfähige intelligente Wesen (man nehme dies hier als Axiom und nicht als zu beweisende Aussage), nicht ungeheure Datenmengen nach bestimmten Informationen per Hand durchsuchen müssen, sondern eine übersichtliche Zusammenfassung erhalten, die irrelevante Fakten von vornherein ausblendet. Erweiternd schliesse ich auch eine Aufarbeitung der extrahierten Daten in diese Definition mit ein, so dass auch Statistiken dazu gehören. Eventuell dienen solche Reports auch als Rohdaten, die nach gegebenenfalls manueller Aufarbeitung, durch weitere Anwendungen verarbeitet werden.
Nehmen wir ein kleines Beispiel. Eine Protokolldatei über laufende Prozesse eines LAN sei 2000000 Zeile lang, wobei jede Zeile diverse Informationen zu jeweils einem Prozess enthält. So etwas kann ein Mensch nicht wirklich lesen. Wenn nun mittels eines Dreizeilers, der auch einen komplexen regulären Ausdruck beinhaltet, ein nur noch 150 Zeilen umfassender Report über bestimmte Prozesse erstellt wird, dann macht es praktisch nichts aus, wenn ein paar Zeilen zu viel erkannt wurden - diese kann ein lesender Mensch sehr schnell erkennen und manuell beseitigen.
Jemand, der solch ein Programm erstellt, hat also einen Vorteil, wenn er unter Einsatz aller Tricks erweiterter regulärer Ausdrücke in wenigen Minuten ein Programm erstellt, welches ein wenig zuviel in den Report schreibt. Würde er stattdessen eine Anwendung erstellen, die wirklich nur genau die erwünschten Zeilen in den Report schreibt, wäre er mit Sicherheit erst viel später fertig.
Der entscheidende Punkt bei diesen Anwendungen ist, dass der zugehörige erweiterte reguläre Ausdruck die Strings in drei Kategorien einteilt:
Da hinter den erweiterten regulären Ausdrücken keine Theorie steckt, macht es oft Probleme Verfahren zu finden, die die dritte genannte Kategorie ausschliessen.
Nur - und das ist des Pudels Kern - das stört ja nicht wirklich, weil ein intelligenter Mensch die zur dritten Kategorie gehörenden Texte leicht sieht und per Hand löschen kann. Dies ist für mich der Einsatzbereich für exotische erweiterte reguläre Ausdrücke.
Das sind nun die Anwendungen, bei denen ein regulärer Ausdruck wirklich nur genau das erkennen darf, was er soll. Praktisch alle Anwendungen im Web-Bereich gehören dazu. Das liegt ganz klar darin begründet, dass ein fertiges dummes handelndes Programm ohne Beurteilungsmöglichkeiten verlässliche true/false-Entscheidungen vom match-Versuch erhalten muss - ansonsten ist Einbruchsversuchen Tür und Tor geöffnet.
Das ist wohl jedem Leser an dieser Stelle klar, so dass ich zum Sachverhalt nichts weiter schreiben muss.
Im Zusammenhang mit regulären Ausdrücken kann ich hier nur die Vorgehensweise MISS (Make It Simple Stupid) empfehlen, weshalb ich auch das Wort "erweiterte" weggelassen habe. Echte reguläre Ausdrücke lassen sich recht gut analysieren. Wenn komplexere Analysen notwendig sein sollten, sind echte Parsing-Algorithmen der angebrachte Implementierungsweg, Ausnahmen gibt es durchaus welche - ich habe mal ein Beispiel zur Erkennung arithmetischer Ausdrücke in einem Beitrag vorgestellt, welches sauber funktioniert - aber diese bedürfen einer angemessenen Erarbeitung und Überprüfung und können in manchen Fällen wie ein Kaninchen aus dem Zylinder gezaubert werden. Der allgemeine Weg ist das aber meiner Meinung nach nicht.
Nun ist die RegEx-Laberei endlich beendet und ich kann mich weiteren Artikeln wieder auf handfestere Sachen aus dem Bereich der Anwendung (erweiterter) regulärer Ausdrücke konzentrieren. Ich hoffe aber, dass diese drei kurzen Beiträge für den einen oder anderen Leser interessant sind.
Kommentar schreiben