Es gibt keinen Tag auf SO, an dem keine Frage zum Parsen von (X) HTML oder XML mit regulären Ausdrücken gestellt wird.
Obwohl es relativ einfach ist, Beispiele zu finden, die die Nichtdurchführbarkeit von Regexen für diese Aufgabe oder eine Sammlung von Ausdrücken zur Darstellung des Konzepts demonstrieren , konnte ich auf SO immer noch keine formale Erklärung dafür finden, warum dies bei Laien nicht möglich ist Begriffe.
Die einzigen formalen Erklärungen, die ich bisher auf dieser Site finden konnte, sind wahrscheinlich äußerst genau, aber für den autodidaktischen Programmierer auch ziemlich kryptisch:
Der Fehler hierbei ist, dass HTML eine Chomsky-Typ-2-Grammatik (kontextfreie Grammatik) und RegEx eine Chomsky-Typ-3-Grammatik (regulärer Ausdruck) ist.
oder:
Reguläre Ausdrücke können nur mit regulären Sprachen übereinstimmen, HTML ist jedoch eine kontextfreie Sprache.
oder:
Ein endlicher Automat (die Datenstruktur, die einem regulären Ausdruck zugrunde liegt) hat außer dem Zustand, in dem er sich befindet, keinen Speicher. Wenn Sie eine beliebig tiefe Verschachtelung haben, benötigen Sie einen beliebig großen Automaten, der mit der Vorstellung eines endlichen Automaten kollidiert.
oder:
Das Pumping-Lemma für reguläre Sprachen ist der Grund, warum Sie das nicht können.
[Um fair zu sein: Der Großteil der obigen Erklärung verweist auf Wikipedia-Seiten, aber diese sind nicht viel einfacher zu verstehen als die Antworten selbst].
Meine Frage lautet also: Könnte jemand bitte eine Übersetzung der oben gegebenen formalen Erklärungen in Laienbegriffe liefern, warum es nicht möglich ist, Regex zum Parsen von (X) HTML / XML zu verwenden?
EDIT: Nachdem ich die erste Antwort gelesen hatte, dachte ich, ich sollte klarstellen: Ich suche eine "Übersetzung", die auch kurz die Konzepte erklärt, die sie zu übersetzen versucht: Am Ende einer Antwort sollte der Leser eine grobe Idee haben - zum Beispiel - was "reguläre Sprache" und "kontextfreie Grammatik" bedeuten ...
Antworten:
Konzentrieren Sie sich auf dieses:
Die Definition von regulären Ausdrücken entspricht der Tatsache, dass ein Test, ob eine Zeichenfolge mit dem Muster übereinstimmt, von einem endlichen Automaten durchgeführt werden kann (ein anderer Automat für jedes Muster). Ein endlicher Automat hat keinen Speicher - keinen Stapel, keinen Haufen, kein unendliches Band zum Kritzeln. Alles, was es hat, ist eine endliche Anzahl von internen Zuständen, von denen jeder eine Eingabeeinheit aus der zu testenden Zeichenfolge lesen und diese verwenden kann, um zu entscheiden, in welchen Zustand als nächstes übergegangen werden soll. Als Sonderfälle gibt es zwei Beendigungszustände: "Ja, das stimmte überein" und "Nein, das stimmte nicht überein".
HTML hingegen hat Strukturen, die beliebig tief verschachtelt werden können. Um festzustellen, ob eine Datei gültiges HTML ist oder nicht, müssen Sie überprüfen, ob alle schließenden Tags mit einem vorherigen öffnenden Tag übereinstimmen. Um es zu verstehen, müssen Sie wissen, welches Element geschlossen wird. Ohne Mittel, sich zu "erinnern", welche Eröffnungs-Tags Sie gesehen haben, keine Chance.
Beachten Sie jedoch, dass die meisten "Regex" -Bibliotheken tatsächlich mehr als nur die strikte Definition regulärer Ausdrücke zulassen. Wenn sie mit Rückverweisen übereinstimmen können, sind sie über eine normale Sprache hinausgegangen. Der Grund, warum Sie keine Regex-Bibliothek für HTML verwenden sollten, ist etwas komplexer als die einfache Tatsache, dass HTML nicht regulär ist.
quelle
Die Tatsache, dass HTML keine reguläre Sprache darstellt, ist ein roter Hering. Regulärer Ausdruck und reguläre Sprachen klingen ähnlich , sind es aber nicht - sie haben denselben Ursprung, aber es gibt eine bemerkenswerte Distanz zwischen den akademischen "regulären Sprachen" und der aktuellen Matching-Leistung von Motoren. Tatsächlich unterstützen fast alle modernen Engines für reguläre Ausdrücke nicht reguläre Funktionen - ein einfaches Beispiel ist
(.*)\1
. Dies verwendet die Rückreferenzierung, um eine wiederholte Zeichenfolge abzugleichen - zum Beispiel123123
oderbonbon
. Durch das Anpassen von rekursiven / ausgeglichenen Strukturen macht dies noch mehr Spaß.Wikipedia bringt dies in einem Zitat von Larry Wall auf den Punkt :
"Regulärer Ausdruck kann nur mit regulären Sprachen übereinstimmen" ist, wie Sie sehen, nichts weiter als ein allgemeiner Irrtum.
Warum also nicht?
Ein guter Grund, HTML nicht mit regulären Ausdrücken abzugleichen, ist, dass "nur weil Sie können, heißt das nicht, dass Sie sollten". Möglicherweise ist dies möglich - es gibt einfach bessere Tools für den Job . In Anbetracht:
Sehr oft ist es unmöglich, einen Teil der Daten abzugleichen, ohne sie als Ganzes zu analysieren. Beispielsweise suchen Sie möglicherweise nach allen Titeln und finden sie in einem Kommentar oder einem Zeichenfolgenliteral wieder.
<h1>.*?</h1>
mag ein mutiger Versuch sein, den Haupttitel zu finden, aber es könnte sein:Oder auch:
Letzter Punkt ist der wichtigste:
Eine gute Zusammenfassung des Themas und ein wichtiger Kommentar zum Mischen von Regex und HTML finden Sie in Jeff Atwoods Blog: Parsing Html The Cthulhu Way .
Wann ist es besser, einen regulären Ausdruck zum Parsen von HTML zu verwenden?
In den meisten Fällen ist es besser, XPath für die DOM-Struktur zu verwenden, die eine Bibliothek Ihnen geben kann. Entgegen der landläufigen Meinung gibt es jedoch einige Fälle, in denen ich die Verwendung eines regulären Ausdrucks und nicht einer Parser-Bibliothek dringend empfehlen würde:
Angesichts einiger dieser Bedingungen:
quelle
Weil HTML unbegrenzt verschachtelt werden kann
<tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>
und Regex damit nicht wirklich fertig wird, weil es keinen Verlauf dessen verfolgen kann, in was es hineingekommen ist und aus dem es herauskommt.Ein einfaches Konstrukt, das die Schwierigkeit veranschaulicht:
99,9% der verallgemeinerten Regex-basierten Extraktionsroutinen können mir nicht alles innerhalb der
div
ID korrekt gebenfoo
, da sie das schließende Tag für dieses Div nicht vom schließenden Tag für dasbar
Div unterscheiden können. Das liegt daran, dass sie nicht sagen können: "Okay, ich bin jetzt in die zweite von zwei Divs hinabgestiegen. Der nächste Div-Abschluss, den ich sehe, bringt mich wieder heraus, und der danach ist der Close-Tag für den ersten." . Programmierer reagieren in der Regel mit Regexes für Sonderfälle für die jeweilige Situation, die dann unterbrochen werden, sobald mehr Tags im Inneren eingeführt werden,foo
und müssen mit enormen Zeit- und Frustrationskosten entwirrt werden. Deshalb werden die Leute wütend auf die ganze Sache.quelle
<(\w+)(?:\s+\w+="[^"]*")*>(?R)*</\1>|[\w\s!']+
passt zu Ihrem Codebeispiel.Eine reguläre Sprache ist eine Sprache, die von einer endlichen Zustandsmaschine abgeglichen werden kann.
(Das Verständnis von Finite-State-Maschinen, Push-Down-Maschinen und Turing-Maschinen ist im Grunde der Lehrplan eines CS-Kurses im vierten Studienjahr.)
Betrachten Sie die folgende Maschine, die die Zeichenfolge "hi" erkennt.
Dies ist eine einfache Maschine, um eine reguläre Sprache zu erkennen. Jeder Ausdruck in Klammern ist ein Zustand und jeder Pfeil ist ein Übergang. Wenn Sie eine Maschine wie diese erstellen, können Sie jede Eingabezeichenfolge anhand einer regulären Sprache testen - daher eines regulären Ausdrucks.
HTML erfordert, dass Sie mehr als nur wissen, in welchem Zustand Sie sich befinden - es erfordert einen Verlauf dessen, was Sie zuvor gesehen haben, um die Tag-Verschachtelung abzugleichen. Sie können dies erreichen, wenn Sie dem Computer einen Stapel hinzufügen, der dann jedoch nicht mehr "normal" ist. Dies wird als Push-Down-Maschine bezeichnet und erkennt eine Grammatik.
quelle
Ein regulärer Ausdruck ist eine Maschine mit einer endlichen (und typischerweise eher kleinen) Anzahl diskreter Zustände.
Um XML, C oder eine andere Sprache mit willkürlicher Verschachtelung von Sprachelementen zu analysieren, müssen Sie sich daran erinnern, wie tief Sie sind. Das heißt, Sie müssen in der Lage sein, geschweifte Klammern / Klammern / Tags zu zählen.
Sie können nicht mit endlichem Speicher zählen. Möglicherweise gibt es mehr Klammerstufen als Sie haben! Möglicherweise können Sie eine Teilmenge Ihrer Sprache analysieren, die die Anzahl der Verschachtelungsebenen einschränkt, dies wäre jedoch sehr mühsam.
quelle
Eine Grammatik ist eine formale Definition, wohin Wörter gehen können. Zum Beispiel gehen Adjektive Substantiven voraus
in English grammar
, folgen aber Substantivenen la gramática española
. Kontextfrei bedeutet, dass der Grammatiker in allen Kontexten universell ist. Kontextsensitiv bedeutet, dass in bestimmten Kontexten zusätzliche Regeln gelten.In C #
using
bedeutet beispielsweiseusing System;
oben in den Dateien etwas anderes alsusing (var sw = new StringWriter (...))
. Ein relevanteres Beispiel ist der folgende Code innerhalb des Codes:quelle
Es gibt noch einen weiteren praktischen Grund dafür, keine regulären Ausdrücke zum Parsen von XML und HTML zu verwenden, der überhaupt nichts mit der Theorie der Informatik zu tun hat: Ihr regulärer Ausdruck wird entweder schrecklich kompliziert oder falsch sein.
Zum Beispiel ist es sehr gut, einen passenden regulären Ausdruck zu schreiben
Aber wenn Ihr Code korrekt sein soll, dann:
Es muss Leerzeichen nach dem Elementnamen sowohl im Start- als auch im End-Tag zulassen
Befindet sich das Dokument in einem Namespace, sollte die Verwendung eines beliebigen Namespace-Präfixes zulässig sein
Es sollte wahrscheinlich alle unbekannten Attribute zulassen und ignorieren, die im Start-Tag erscheinen (abhängig von der Semantik des jeweiligen Vokabulars).
Möglicherweise muss vor und nach dem Dezimalwert ein Leerzeichen zugelassen werden (wiederum abhängig von den detaillierten Regeln des jeweiligen XML-Vokabulars).
Es sollte nicht mit etwas übereinstimmen, das wie ein Element aussieht, sondern sich tatsächlich in einem Kommentar- oder CDATA-Abschnitt befindet (dies ist besonders wichtig, wenn die Möglichkeit besteht, dass böswillige Daten versuchen, Ihren Parser zu täuschen).
Möglicherweise muss eine Diagnose bereitgestellt werden, wenn die Eingabe ungültig ist.
Natürlich hängt ein Teil davon von den Qualitätsstandards ab, die Sie anwenden. Bei StackOverflow treten viele Probleme auf, wenn Benutzer XML auf eine bestimmte Art und Weise generieren müssen (z. B. ohne Leerzeichen in den Tags), da es von einer Anwendung gelesen wird, für die eine bestimmte Schreibweise erforderlich ist. Wenn Ihr Code eine lange Lebensdauer hat, ist es wichtig, dass er eingehendes XML verarbeiten kann, das auf eine Weise geschrieben wurde, die der XML-Standard zulässt, und nicht nur das eine Beispiel für ein Eingabedokument, auf dem Sie Ihren Code testen.
quelle
Rein theoretisch ist es für reguläre Ausdrücke unmöglich, XML zu analysieren. Sie sind so definiert, dass sie keinen Speicher eines vorherigen Zustands speichern können, wodurch die korrekte Übereinstimmung eines beliebigen Tags verhindert wird, und sie können nicht bis zu einer beliebigen Verschachtelungstiefe vordringen, da die Verschachtelung in den regulären Ausdruck eingebaut werden müsste.
Moderne Regex-Parser werden jedoch eher für den Entwickler als für die Einhaltung einer genauen Definition entwickelt. Als solche haben wir Dinge wie Rückverweise und Rekursion, die das Wissen über frühere Zustände nutzen. Mit diesen ist es bemerkenswert einfach, einen regulären Ausdruck zu erstellen, der XML untersuchen, validieren oder analysieren kann.
Betrachten Sie zum Beispiel:
Dadurch wird das nächste ordnungsgemäß erstellte XML-Tag oder -Kommentar gefunden, und es wird nur gefunden, wenn der gesamte Inhalt ordnungsgemäß erstellt wurde. (Dieser Ausdruck wurde mit Notepad ++ getestet, das die Regex-Bibliothek von Boost C ++ verwendet, die PCRE sehr nahe kommt.)
So funktioniert das:
/>
, wodurch das Tag vervollständigt wird, oder es endet mit a>
. In diesem Fall wird der Inhalt des Tags weiter untersucht.<
. An diesem Punkt kehrt es zum Anfang des Ausdrucks zurück und kann entweder einen Kommentar oder ein neues Tag verarbeiten.<
Punkt ankommt , den es nicht analysieren kann. Wenn die Übereinstimmung nicht hergestellt wird, wird der Prozess natürlich von vorne gestartet. Andernfalls ist das<
vermutlich der Beginn des schließenden Tags für diese Iteration. Wenn Sie die Rückreferenz in einem schließenden Tag verwenden<\/\1>
, stimmt sie mit dem öffnenden Tag für die aktuelle Iteration (Tiefe) überein. Es gibt nur eine Eroberungsgruppe, daher ist dieses Match eine einfache Sache. Dies macht es unabhängig von den Namen der verwendeten Tags. Sie können die Erfassungsgruppe jedoch so ändern, dass bei Bedarf nur bestimmte Tags erfasst werden.Dieses Beispiel löst Probleme beim Umgang mit Leerzeichen oder beim Identifizieren relevanter Inhalte durch die Verwendung von Zeichengruppen, die lediglich negieren,
<
oder>
oder im Fall von Kommentaren durch die Verwendung von Zeichengruppen[\S\s]
, die mit allen übereinstimmen, einschließlich Zeilenumbrüchen und neuen Zeilen, auch in einzeiligen Zeilen Modus, weiter, bis es a erreicht-->
. Daher behandelt es einfach alles als gültig, bis es etwas Sinnvolles erreicht.Für die meisten Zwecke ist eine solche Regex nicht besonders nützlich. Es wird überprüft, ob XML ordnungsgemäß erstellt wurde, aber das ist alles, was es wirklich tun wird, und es berücksichtigt keine Eigenschaften (obwohl dies eine einfache Ergänzung wäre). Es ist nur so einfach, weil es solche Probleme der realen Welt sowie Definitionen von Tag-Namen auslässt. Wenn man es für den echten Gebrauch anpasst, wird es viel mehr zu einem Biest. Im Allgemeinen wäre ein echter XML-Parser weit überlegen. Dieser ist wahrscheinlich am besten geeignet, um zu lehren, wie Rekursion funktioniert.
Lange Rede, kurzer Sinn: Verwenden Sie einen XML-Parser für echte Arbeit und verwenden Sie diesen, wenn Sie mit regulären Ausdrücken herumspielen möchten.
quelle
Analysieren Sie XML / HTML nicht mit Regex, sondern verwenden Sie einen geeigneten XML / HTML-Parser und einen leistungsstarken xpath Abfrage.
Theorie:
realLife © ® ™ Alltagswerkzeug in a Schale ::
Sie können eine der folgenden Optionen verwenden:
xmllint wird häufig standardmäßig mit
libxml2
xpath1 installiert (überprüfen Sie meinen Wrapper, um die Ausgabe durch Zeilenumbrüche zu begrenzenxmlstarlet kann bearbeiten, auswählen, transformieren ... Nicht standardmäßig installiert, xpath1
xpath installiert über das Perl-Modul XML :: XPath, xpath1
xidel xpath3
saxon-lint mein eigenes Projekt, Wrapper über @Michael Kays Saxon-HE Java-Bibliothek, xpath3
oder Sie können Hochsprachen und richtige Bibliotheken verwenden, denke ich an:
Python's
lxml
(from lxml import etree
)perl‚s
XML::LibXML
,XML::XPath
,XML::Twig::XPath
,HTML::TreeBuilder::XPath
Rubin nokogiri, Lesen Sie in diesem Beispiel
php
DOMXpath
, Lesen Sie in diesem BeispielÜberprüfen Sie: Verwenden Sie reguläre Ausdrücke mit HTML-Tags
quelle