Wie funktionieren HTML-Parses, wenn sie keinen regulären Ausdruck verwenden?

96

Ich sehe jeden Tag Fragen, wie man etwas aus einer HTML-Zeichenfolge analysiert oder extrahiert, und die erste Antwort / der erste Kommentar lautet immer "Verwenden Sie RegEx nicht zum Analysieren von HTML, damit Sie nicht den Zorn spüren!" (Dieser letzte Teil wird manchmal weggelassen).

Das ist ziemlich verwirrend für mich. Ich dachte immer, dass der beste Weg, eine komplizierte Zeichenfolge zu analysieren, im Allgemeinen die Verwendung eines regulären Ausdrucks ist. Wie funktioniert ein HTML-Parser? Verwendet es keine regulären Ausdrücke zum Parsen?

Ein besonderes Argument für die Verwendung eines regulären Ausdrucks ist, dass es nicht immer eine Parsing-Alternative gibt (z. B. JavaScript, bei dem DOMDocument keine allgemein verfügbare Option ist). jQuery zum Beispiel scheint mit einem regulären Ausdruck zum Konvertieren einer HTML-Zeichenfolge in DOM-Knoten einwandfrei zu funktionieren.

Ich bin mir nicht sicher, ob ich dies tun soll oder nicht, es ist eine echte Frage, die ich beantworten möchte und die eigentlich nicht als Diskussionsthread gedacht ist.

Andy E.
quelle
Retagged, um Parsing und HTML-Parsing hinzuzufügen - @Andy E, ich hoffe, das ist in Ordnung für Sie - ich dachte, es wäre hilfreich.
JXG
@JXG: Das ist gut für mich, danke :-)
Andy E

Antworten:

65

Normalerweise mit einem Tokeniser. Der Entwurf der HTML5-Spezifikation enthält einen umfangreichen Algorithmus für den Umgang mit "realem HTML".

QUentin
quelle
1
Guter Fund ... um zu zitieren "Um diese Fälle zu behandeln, haben Parser eine Skriptverschachtelungsebene, die anfänglich auf Null gesetzt werden muss, und ein Parser-Pausenflag, das anfänglich auf false gesetzt werden muss." - Mit anderen Worten, Sie müssen es selbst wiederholen und viele benutzerdefinierte Logik haben: P
Timothy Khouri
1
Upvote. Es ist besser, die algorithmische Komplexität zu betonen, als irgendeine Technologie.
Arnis Lapsa
1
Es ist keine so gute Idee, es selbst mit viel benutzerdefinierter Logik zu wiederholen. Verwenden Sie eine Bibliothek, die den Standardalgorithmus unterstützt, wenn Sie können. zB search.cpan.org/~tobyink/HTML-HTML5-Parser-0.03/lib/HTML/HTML5/… / code.google.com/p/html5lib
Quentin
8
Das Hauptproblem bei HTML-Parsern besteht darin, dass Sie bei Auftreten eines Fehlers nicht in der Lage sind, "Analysefehler" auszuspucken und dabei zu belassen. Sie wechseln in den Mackenmodus und versuchen, das Beste aus dem Chaos herauszuholen, auf das Sie gestoßen sind, einschließlich nicht übereinstimmender Tags, [{]} Interlace-Stil und allerlei Verrücktheiten, um das Ergebnis so gut wie möglich und unvermeidlich zu machen Misserfolg am wenigsten schmerzhaft ... das kann man nicht mit Regexen machen.
SF.
7
@Timothy K: 'Hinweis: Aufgrund der Art und Weise, wie dieser Algorithmus dazu führt, dass Elemente die Eltern wechseln, wurde er als "Adoptionsagentur-Algorithmus" bezeichnet (im Gegensatz zu anderen möglichen Algorithmen für den Umgang mit falsch verschachtelten Inhalten, einschließlich des "Inzest-Algorithmus"). der "Secret-Affair-Algorithmus" und der "Heisenberg-Algorithmus"). "
JXG
133

Wie funktioniert ein HTML-Parser? Verwendet es keine regulären Ausdrücke zum Parsen?

Nun, nein.

Wenn Sie in Ihrem Gehirn auf einen Kurs zur Theorie der Berechnung zurückgreifen, wenn Sie einen Kurs oder einen Compilerkurs oder ähnliches belegt haben, können Sie sich daran erinnern, dass es verschiedene Arten von Sprachen und Rechenmodellen gibt. Ich bin nicht qualifiziert, auf alle Details einzugehen, aber ich kann einige der wichtigsten Punkte mit Ihnen besprechen.

Die einfachste Art von Sprache und Berechnung (für diese Zwecke) ist eine reguläre Sprache. Diese können mit regulären Ausdrücken generiert und mit endlichen Automaten erkannt werden. Grundsätzlich bedeutet dies, dass das "Parsen" von Zeichenfolgen in diesen Sprachen den Status, jedoch nicht den Hilfsspeicher verwendet. HTML ist sicherlich keine reguläre Sprache. Wenn Sie darüber nachdenken, kann die Liste der Tags beliebig tief verschachtelt werden. Beispielsweise können Tabellen Tabellen enthalten, und jede Tabelle kann viele verschachtelte Tags enthalten. Mit regulären Ausdrücken können Sie möglicherweise ein Paar Tags auswählen, aber sicherlich nichts, was willkürlich verschachtelt ist.

Eine klassische einfache Sprache, die nicht regulär ist, besteht aus korrekt übereinstimmenden Klammern. Versuchen Sie es wie Sie möchten, Sie werden niemals in der Lage sein, einen regulären Ausdruck (oder einen endlichen Automaten) zu erstellen, der immer funktioniert. Sie benötigen Speicher, um die Verschachtelungstiefe zu verfolgen.

Eine Zustandsmaschine mit einem Stapel für Speicher ist die nächste Stärke des Rechenmodells. Dies wird als Push-Down-Automat bezeichnet und erkennt Sprachen, die durch kontextfreie Grammatiken generiert werden. Hier können wir korrekt übereinstimmende Klammern erkennen - tatsächlich ist ein Stapel das perfekte Speichermodell dafür.

Ist das gut genug für HTML? Traurigerweise Nein. Vielleicht für Super-Duper sorgfältig validiertes XML, in dem alle Tags immer perfekt ausgerichtet sind. In echtem HTML können Sie leicht Schnipsel wie finden<b><i>wow!</b></i> . Dies ist offensichtlich nicht verschachtelt. Um es richtig zu analysieren, ist ein Stapel einfach nicht leistungsfähig genug.

Die nächste Rechenebene sind Sprachen, die von allgemeinen Grammatiken generiert und von Turing-Maschinen erkannt werden. Es wird allgemein angenommen, dass dies das stärkste Rechenmodell ist, das es gibt - eine Zustandsmaschine mit Hilfsspeicher, deren Speicher überall geändert werden kann. Dies können Programmiersprachen. Dies ist der Grad der Komplexität, in dem HTML lebt.

Um hier alles in einem Satz zusammenzufassen: Um allgemeines HTML zu analysieren, benötigen Sie eine echte Programmiersprache, keinen regulären Ausdruck.

HTML wird genauso analysiert wie andere Sprachen: Lexing und Parsing. Der Lexing-Schritt zerlegt den Strom einzelner Zeichen in aussagekräftige Token. Der Analyseschritt fasst die Token unter Verwendung von Status und Speicher zu einem logisch zusammenhängenden Dokument zusammen, auf das reagiert werden kann.

JXG
quelle
22

Reguläre Ausdrücke sind nur eine Form des Parsers. Ein ehrlicher HTML-Parser ist erheblich komplizierter als in regulären Ausdrücken ausgedrückt werden kann, indem rekursiver Abstieg , Vorhersage und verschiedene andere Techniken verwendet werden, um den Text richtig zu interpretieren. Wenn Sie sich wirklich darauf einlassen möchten, sollten Sie sich lex & yacc ansehen und ähnliche Tools .

Das Verbot, Regexes für das HTML-Parsen zu verwenden, sollte wahrscheinlich korrekter geschrieben werden als: "Verwenden Sie keine naiven regulären Ausdrücke, um HTML zu analysieren ..." (damit Sie den Zorn nicht spüren) "... und behandeln Sie die Ergebnisse mit Vorsicht." Für bestimmte spezifische Ziele mag ein Regex durchaus ausreichend sein, aber Sie müssen sehr vorsichtig sein, um die Einschränkungen Ihres Regex zu kennen und so vorsichtig zu sein, wie es für die Quelle des zu analysierenden Textes angemessen ist (z. B. wenn dies der Fall ist) Benutzereingaben, seien Sie in der Tat sehr vorsichtig).

TJ Crowder
quelle
+1, eine gute Antwort. Ich muss zugeben, ich habe schon früher reguläre Ausdrücke verwendet, auch wenn ich nicht die Kontrolle über HTML hatte, aber nicht in irgendeiner öffentlich veröffentlichten Anwendung. Ich habe auch "den Zorn gefühlt", weil es naiv war. Aber das ist lange her :-)
Andy E
6

Das Parsen von HTML ist die Umwandlung eines linearen Textes in eine Baumstruktur. Reguläre Ausdrücke können im Allgemeinen keine Baumstrukturen verarbeiten. Der reguläre Ausdruck, den Sie an jedem Punkt benötigen, um das nächste Token zu erhalten, ändert sich ständig. Sie können reguläre Ausdrücke in einem Parser verwenden, benötigen jedoch für jeden möglichen Parsing-Status eine ganze Reihe regulärer Ausdrücke.

Svante
quelle
2

Wenn Sie eine 100% ige Lösung wünschen: Sie müssen Ihren eigenen benutzerdefinierten Code schreiben, der den HTML-Code zeichenweise durchläuft, und Sie müssen über eine enorme Menge an Logik verfügen, um zu bestimmen, ob Sie den aktuellen Knoten stoppen und den Knoten starten sollten Nächster.

Der Grund ist, dass dies gültiges HTML ist:

<ul>
<li>One
<li>Two
<li>Three
</ul>

Aber so ist das:

<ul>
<li>One</li>
<li>Two</li>
<li>Three</li>
</ul>

Wenn Sie mit "90% -Lösung" einverstanden sind: Die Verwendung eines XML-Parsers zum Laden eines Dokuments ist in Ordnung. Oder mit Regex (obwohl die XML einfacher ist, wenn Sie dann den Inhalt beherrschen).

Timothy Khouri
quelle
4
Ein XML-Parser ähnelt eher einer 1% -Lösung. Die Anzahl der HTML-Dokumente, bei denen es sich um gut geformtes XML handelt, ist gering.
Quentin
4
Ja, sie nehmen "Charakter für Charakter" nicht wörtlich, da Sie versuchen können, Dinge zu streamen. Mein Punkt ist jedoch, dass Sie Ihren eigenen Parser schreiben müssen. Programmierer im neuen Alter sind es nicht gewohnt, diese Art von Code zu schreiben ... wir sind an "HtmlDocumentUtility.Load" und ähnliches gewöhnt :)
Timothy Khouri
4
@Andy E: Regexes sind keine Magie, sie funktionieren auch Zeichen für Zeichen, wie jede andere Art des Parsens oder zum Teufel jede andere Zeichenfolgenfunktion.
Bart van Heukelom
1
Übrigens: Ihr erstes Beispiel ist nicht nur "halbgültiges HTML". Es ist tatsächlich gültig HTML 4.01 Strict. Sie können dies beispielsweise mit dem W3C-Validator überprüfen. Das schließende Tag ist für <li> offiziell optional (siehe HTML 4-Spezifikation).
Sleske
2
@Bart: Guter Punkt, manchmal vergisst mein Gehirn jede Logik und denkt, dass die Dinge durch Magie funktionieren.
Andy E