Können Sie einige Beispiele dafür nennen, warum es schwierig ist, XML und HTML mit einem regulären Ausdruck zu analysieren? [geschlossen]

402

Ein Fehler , ich sehe Menschen , die über und immer wieder versucht , XML zu analysieren oder HTML mit einem regulären Ausdruck. Hier sind einige der Gründe, warum das Parsen von XML und HTML schwierig ist:

Die Benutzer möchten eine Datei als eine Folge von Zeilen behandeln, dies ist jedoch gültig:

<tag
attr="5"
/>

Die Leute wollen <oder <Tag als Anfang eines Tags behandeln, aber solche Dinge gibt es in freier Wildbahn:

<img src="imgtag.gif" alt="<img>" />

Menschen möchten häufig Start-Tags mit End-Tags abgleichen, aber XML und HTML ermöglichen es Tags, sich selbst zu enthalten (was herkömmliche Regexe überhaupt nicht verarbeiten können):

<span id="outer"><span id="inner">foo</span></span> 

Menschen möchten häufig mit dem Inhalt eines Dokuments übereinstimmen (z. B. das berühmte Problem "Alle Telefonnummern auf einer bestimmten Seite finden"), aber die Daten können markiert sein (auch wenn sie beim Anzeigen normal erscheinen):

<span class="phonenum">(<span class="area code">703</span>)
<span class="prefix">348</span>-<span class="linenum">3020</span></span>

Kommentare können schlecht formatierte oder unvollständige Tags enthalten:

<a href="foo">foo</a>
<!-- FIXME:
    <a href="
-->
<a href="bar">bar</a>

Welche anderen Fallstricke kennen Sie?

Chas. Owens
quelle
14
Webbrowser machen diese Art von Chaos millionenfach pro Sekunde Sinn. Kann nicht jemand eine Webseiten-Parser-Klasse für uns Sterbliche erstellen?
Jon Winstanley
24
Jon, das haben sie. In Perl gibt es viele HTML :: Parser, HTML :: TreeBuilder usw. Es gibt mit ziemlicher Sicherheit eine für Ihre Sprache.
Chas. Owens
12
Die beste Antwort ist, stackoverflow.com/a/1732454/135078 (Vorsicht Zalgo)
Kelly S. Französisch
3
Es gibt eine gute Erklärung, warum [Sie können [X] HTML nicht mit Regex analysieren] [1] [1]: stackoverflow.com/a/1732454/468725
Pavel P
4
Hier finden Sie eine gute Erklärung, wie Sie HTML mit Mustern analysieren können und warum Sie dies wahrscheinlich nicht möchten.
Tchrist

Antworten:

260

Hier ist ein lustiges, gültiges XML für Sie:

<!DOCTYPE x [ <!ENTITY y "a]>b"> ]>
<x>
    <a b="&y;>" />
    <![CDATA[[a>b <a>b <a]]>
    <?x <a> <!-- <b> ?> c --> d
</x>

Und dieses kleine Bündel Freude ist gültiges HTML:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd" [
    <!ENTITY % e "href='hello'">
    <!ENTITY e "<a %e;>">
]>
    <title>x</TITLE>
</head>
    <p id  =  a:b center>
    <span / hello </span>
    &amp<br left>
    <!---- >t<!---> < -->
    &e link </a>
</body>

Ganz zu schweigen von der browserspezifischen Analyse für ungültige Konstrukte.

Viel Glück beim Regex!

EDIT (Jörg W Mittag): Hier ist ein weiteres schönes Stück wohlgeformten, gültigen HTML 4.01:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
  "http://www.w3.org/TR/html4/strict.dtd"> 
<HTML/
  <HEAD/
    <TITLE/>/
    <P/>
Bobince
quelle
6
Das XML? Es gibt dort ein paar verschiedene Konstrukte, was ist problematisch? Die interne DTD-Teilmenge? Das definiert eine neue & Entität; genannt 'y', enthält eine ']>' Sequenz, die normalerweise, wenn nicht in Anführungszeichen, die interne Teilmenge beenden würde.
Bobince
16
(Dies zeigt, dass Sie über einige der esoterischeren und archaischeren DTD-Funktionen von XML verfügen müssen, um ein Dokument ordnungsgemäß zu analysieren, auch wenn Sie kein DTD-validierender Parser sind.)
Bobince
17
Die HTML-Beispiele verwenden eine selten bekannte Funktion: Shorttags. Lesen Sie mehr unter w3.org/QA/2007/10/shorttags.html
netvope
25
Jedes Mal, wenn jemand HTML schreibt, wie oben gezeigt, vergießt Tim Berners-Lee eine einzelne Träne.
Fgysin wieder Monica
5
Ich finde es toll, wie der Syntax-Textmarker von Stackoverflow beim ersten Auftreten von "]" fehlschlägt.
GlassGhost
71

Tatsächlich

<img src="imgtag.gif" alt="<img>" />

ist kein gültiges HTML und auch kein gültiges XML.

Es ist kein gültiges XML, da '<' und '>' keine gültigen Zeichen in Attributzeichenfolgen sind. Sie müssen mit den entsprechenden XML-Entitäten & lt; und & gt;

Es ist auch kein gültiges HTML, da das kurze Abschlussformular in HTML nicht zulässig ist (aber in XML und XHTML korrekt ist). Das 'img'-Tag ist auch ein implizit geschlossenes Tag gemäß der HTML 4.01-Spezifikation. Dies bedeutet, dass das manuelle Schließen tatsächlich falsch ist und dem zweimaligen Schließen eines anderen Tags entspricht.

Die richtige Version in HTML ist

<img src="imgtag.gif" alt="&lt;img&gt;">

und die richtige Version in XHTML und XML ist

<img src="imgtag.gif" alt="&lt;img&gt;"/>

Das folgende Beispiel ist ebenfalls ungültig

<
tag
attr="5"
/>

Dies ist auch kein gültiges HTML oder XML. Der Name des Tags muss direkt hinter dem '<' stehen, obwohl die Attribute und das schließende '>' beliebig sein können. Das gültige XML ist also tatsächlich

<tag
attr="5"
/>

Und hier ist noch eine funkigere: Sie können entweder "oder" als Attribut-Anführungszeichen verwenden

<img src="image.gif" alt='This is single quoted AND valid!'>

Alle anderen Gründe, die veröffentlicht wurden, sind korrekt, aber das größte Problem beim Parsen von HTML ist, dass die Leute normalerweise nicht alle Syntaxregeln richtig verstehen. Die Tatsache, dass Ihr Browser Ihre Tag-Gruppe als HTML interpretiert, bedeutet nicht, dass Sie tatsächlich gültiges HTML geschrieben haben.

Bearbeiten: Und sogar stackoverflow.com stimmt mir hinsichtlich der Definition von gültig und ungültig zu. Ihr ungültiges XML / HTML wird nicht hervorgehoben, während meine korrigierte Version ist.

Grundsätzlich ist XML nicht dafür ausgelegt, mit regulären Ausdrücken analysiert zu werden. Es gibt aber auch keinen Grund dazu. Es gibt viele, viele XML-Parser für jede Sprache. Sie haben die Wahl zwischen SAX-Parsern, DOM-Parsern und Pull-Parsern. All dies ist garantiert viel schneller als das Parsen mit einem regulären Ausdruck, und Sie können dann coole Technologien wie XPath oder XSLT für den resultierenden DOM-Baum verwenden.

Meine Antwort lautet daher: Das Parsen von XML mit regulären Ausdrücken ist nicht nur schwierig, sondern auch eine schlechte Idee. Verwenden Sie einfach einen der Millionen vorhandenen XML-Parser und nutzen Sie alle erweiterten Funktionen von XML.

HTML ist einfach zu schwer, um es selbst zu analysieren. Erstens hat die legale Syntax viele kleine Feinheiten, die Sie vielleicht nicht kennen, und zweitens ist HTML in freier Wildbahn nur ein riesiger stinkender Haufen (Sie verstehen meine Abweichung). Es gibt eine Vielzahl von laxen Parser-Bibliotheken, die gute Arbeit im Umgang mit HTML wie Tag-Suppe leisten. Verwenden Sie einfach diese.

LordOfThePigs
quelle
8
Sie müssen jedoch nicht entkommen.
Joey
8
Okay, s / valid / existiert in freier Wildbahn / g
Chas. Owens
1
Tatsächlich müssen Sie gemäß der Spezifikation> als> entkommen, genauso wie Sie <als <& und & amp; und in den Attributen "as" und "as" sind es nur so viele Parser
LordOfThePigs
19
Die Spezifikation besagt nicht, dass '>' maskiert werden muss - mit Ausnahme des Sonderfalls der Sequenz ']]>' im Inhalt. Aus diesem Grund ist es am einfachsten, immer '>' zu entkommen, aber es wird nicht von der Spezifikation verlangt.
Bobince
8
>Zeichen ist vollkommen gültig in HTML stackoverflow.com/questions/94528/…
jfs
56

Ich habe einen ganzen Blogeintrag zu diesem Thema geschrieben: Einschränkungen für reguläre Ausdrücke

Der Kern des Problems besteht darin, dass HTML und XML rekursive Strukturen sind, für deren korrekte Analyse Zählmechanismen erforderlich sind. Ein echter Regex kann nicht zählen. Sie müssen eine kontextfreie Grammatik haben, um zählen zu können.

Der vorige Absatz enthält eine leichte Einschränkung. Bestimmte Regex-Implementierungen unterstützen jetzt die Idee der Rekursion. Sobald Sie jedoch anfangen, Ihren Regex-Ausdrücken Rekursion hinzuzufügen, erweitern Sie wirklich die Grenzen und sollten einen Parser in Betracht ziehen.

JaredPar
quelle
20

Ein Problem, das nicht auf Ihrer Liste steht, ist, dass Attribute in beliebiger Reihenfolge angezeigt werden können. Wenn Ihr regulärer Ausdruck also nach einem Link mit dem href "foo" und der Klasse "bar" sucht, können sie in beliebiger Reihenfolge und mit einer beliebigen Anzahl anderer Attribute angezeigt werden Dinge zwischen ihnen.

AmbroseChapel
quelle
Ah, ja, das war sogar die Frage, die mich dazu veranlasste, diese zu stellen (der erste Link).
Chas. Owens
16

Es hängt davon ab, was Sie unter "Parsen" verstehen. Im Allgemeinen kann XML nicht mit Regex analysiert werden, da die XML-Grammatik keineswegs regelmäßig ist. Um es einfach auszudrücken: Regexes können nicht zählen (Perl-Regexes können möglicherweise tatsächlich Dinge zählen), sodass Sie Open-Close-Tags nicht ausgleichen können.

Anton Gogolev
quelle
Ich denke, Rückreferenzen können das Problem des Öffnens und Schließens von Tags lösen
Rishul Matta
1
@RishulMatta: wie? Sie haben nur eine begrenzte Anzahl von Rückreferenzen und beachten, dass Sie die Tags umkehren müssen ... Darüber hinaus erlaubt die strikte Definition von Regexen keine Rückreferenzen.
Willem Van Onsem
.NET ermöglicht das Ausgleichen von Ausdrücken, die Pop und Push sind, und kann theoretisch zum Abgleichen der Hierarchie verwendet werden. Aber es ist immer noch eine schlechte Idee.
Abel
9

Machen die Leute tatsächlich einen Fehler, wenn sie einen regulären Ausdruck verwenden, oder ist er einfach gut genug für die Aufgabe, die sie zu erfüllen versuchen?

Ich stimme voll und ganz zu, dass das Parsen von HTML und XML mit einem regulären Ausdruck nicht möglich ist, da andere Personen geantwortet haben.

Wenn Sie jedoch nicht HTML / XML analysieren möchten, sondern nur ein kleines Datenbit in einem "bekanntermaßen guten" Bit HTML / XML abrufen möchten, ist möglicherweise ein regulärer Ausdruck oder sogar ein noch einfacherer "Teilstring" ausreichend.

Robin Day
quelle
7
Definieren Sie "gut genug". Der einfache reguläre Ausdruck wird unweigerlich nicht funktionieren. Passt etwas nicht zusammen oder passt etwas nicht zu einem Fehler? Wenn ja, ist die Verwendung von regulären Ausdrücken ein Fehler. HTML- und XML-Parser sind nicht schwer zu verwenden. Es ist eine falsche Wirtschaft, sie nicht zu lernen.
Chas. Owens
1
ok, definiere "gut genug". Nehmen wir an, ich habe eine Webseite, auf der die IP-Adresse des Kunden angegeben ist. Das ist alles was es tut. Jetzt muss ich eine Anwendung für den Client-Computer schreiben, die mir die IP-Adresse mitteilt. Ich gehe zu dieser Site, suche nach einer IP-Adresse und gebe sie zurück. Das Parsen des HTML wird nicht benötigt!
Robin Day
2
Wenn Sie eine beliebige Zeichenfolge haben, deren Format vollständig unter Ihrer Kontrolle steht, ist die Tatsache, dass es sich bei der Zeichenfolge um wohlgeformtes XML handelt, wirklich nicht relevant. In diese Kategorie fallen jedoch fast keine Anwendungsfälle für XML.
Robert Rossney
15
Ich kann Ihnen aus schmerzhafter Erfahrung sagen, dass es die meiste Zeit möglich ist, mithilfe absurder komplexer Regex-Muster das zu bekommen, was Sie wollen. Bis die Website eine lustige kleine Änderung erfährt und Sie diesen regulären Ausdruck, der Sie zwei Tage lang zum Weinen gebracht hat, aus dem Fenster werfen und neu beginnen können.
Thomasz
@ Robert: "Fast keine Anwendungsfälle" ist eine Übertreibung. Nach meiner Erfahrung gibt es häufig genug Anwendungsfälle. YAGNI gilt hier ... manchmal. Der Trick besteht darin, zu wissen, wie kugelsicher und langlebig Ihre Lösung für die jeweilige Aufgabe sein muss, die Sie ansprechen. Robin hat einen guten Punkt. Er sagt nur, dass sich eine vollständige XML-Analyse nicht immer lohnt ... was auch dann zutrifft, wenn Sie wissen, wie man es verwendet.
LarsH
6

Normalerweise schreiben die Leute standardmäßig gierige Muster, was oft genug zu einem unüberlegten Durchführen führt. * Schlürfen großer Dateiblöcke in das größtmögliche <foo>. * </ Foo>.

Chaos
quelle
2
.*?<Sie können die Wiederholung nicht nur faul machen , sondern auch eine negierte Zeichenklasse wie verwenden [^<]*<. (Haftungsausschluss: Offensichtlich ist das immer noch nicht narrensicher, worum es geht.)
Rory O'Kane
6

Ich bin versucht zu sagen "Erfinde das Rad nicht neu". Nur dass XML ein sehr, sehr komplexes Format ist. Vielleicht sollte ich sagen "Erfinde das Synchrotron nicht neu."

Vielleicht beginnt das richtige Klischee "wenn Sie nur einen Hammer haben ..." Sie wissen, wie man reguläre Ausdrücke verwendet, reguläre Ausdrücke können gut analysiert werden. Warum sollten Sie sich also die Mühe machen, eine XML-Analysebibliothek zu lernen?

Weil das Parsen von XML schwierig ist . Jeder Aufwand, den Sie sparen, wenn Sie nicht lernen müssen, eine XML-Analysebibliothek zu verwenden, wird durch die Menge an kreativer Arbeit und Fehlerbehebung, die Sie ausführen müssen, mehr als wettgemacht. Gehen Sie für sich selbst auf "XML-Bibliothek" und nutzen Sie die Arbeit eines anderen.

Isaac Rabinovitch
quelle
3
Es ist jedoch nicht so komplex wie C ++.
Cole Johnson
6
@Cole "Cole9" Johnson Ich würde REs auch nicht zum Parsen von C ++ verwenden.
Isaac Rabinovitch
2
Wenn XML ein Synchrotron ist, wäre C ++ der Large Hadron Collider.
Kevin Kostlan
4

Ich glaube das Klassiker hat die Informationen, die Sie suchen. Sie finden den Punkt in einem der Kommentare dort:

Ich denke, der Fehler hier ist, dass HTML eine Chomsky-Typ-2-Grammatik (kontextfreie Grammatik) und RegEx eine Chomsky-Typ-3-Grammatik (regulärer Ausdruck) ist. Da eine Typ-2-Grammatik grundlegend komplexer ist als eine Typ-3-Grammatik, können Sie unmöglich hoffen, dass dies funktioniert . Aber viele werden es versuchen, einige werden Erfolg beanspruchen und andere werden den Fehler finden und dich total durcheinander bringen.

Weitere Infos aus Wikipedia: Chomsky Hierarchy

Adam Arold
quelle
6
"Regulärer Ausdruck" hat in formalen Grammatikdiskussionen nicht genau die gleiche Bedeutung wie hier. Die meisten vorhandenen Regex-Engines sind leistungsfähiger als Chomsky-Typ-3-Grammatiken (z. B. nicht gieriges Matching, Backrefs). Einige Regex-Engines (wie Perls) sind vollständig. Es ist wahr, dass selbst dies schlechte Tools zum Parsen von HTML sind, aber dieses oft zitierte Argument ist nicht der Grund dafür.
Dubiousjim
4

Ich denke, die Probleme laufen auf Folgendes hinaus:

  1. Die Regex ist fast immer falsch. Es gibt legitime Eingaben, die nicht korrekt übereinstimmen. Wenn Sie hart genug arbeiten, können Sie es zu 99% oder zu 99,999% korrekt machen, aber es ist fast unmöglich, es zu 100% korrekt zu machen, schon allein aufgrund der seltsamen Dinge, die XML durch die Verwendung von Entitäten zulässt.

  2. Wenn der reguläre Ausdruck selbst für 0,00001% der Eingaben falsch ist, liegt ein Sicherheitsproblem vor, da jemand die eine Eingabe ermitteln kann, die Ihre Anwendung beschädigt.

  3. Wenn der reguläre Ausdruck korrekt genug ist, um 99,99% der Fälle abzudecken, ist er völlig unlesbar und nicht wartbar.

  4. Es ist sehr wahrscheinlich, dass ein Regex bei mittelgroßen Eingabedateien eine sehr schlechte Leistung erbringt. Meine allererste Begegnung mit XML bestand darin, ein Perl-Skript, das eingehende XML-Dokumente (fälschlicherweise) analysierte, durch einen geeigneten XML-Parser zu ersetzen. Wir haben nicht nur 300 Zeilen unlesbaren Codes durch 100 Zeilen ersetzt, die jeder verstehen konnte, sondern auch die Reaktionszeit der Benutzer verbessert von 10 Sekunden bis etwa 0,1 Sekunden.

Michael Kay
quelle
1

Im Allgemeinen kann XML nicht mit Regex analysiert werden, da die XML-Grammatik keineswegs regelmäßig ist. Um es einfach auszudrücken: Regexes können nicht zählen (Perl-Regexes können möglicherweise tatsächlich Dinge zählen), sodass Sie Open-Close-Tags nicht ausgleichen können.

Ich stimme dir nicht zu. Wenn Sie in Regex rekursiv verwenden, können Sie leicht offene und geschlossene Tags finden.

Hier habe ich ein Beispiel für Regex gezeigt, um Analysefehler von Beispielen in der ersten Nachricht zu vermeiden.

Maxim Suslov
quelle
Erstens sind rekursive Regexe keine regulären Ausdrücke (wenn Sie in die Klammern schauen, werden Sie sehen, dass ich zugebe, dass Perls Regexes, die rekursiv sind, Dinge zählen können, die für den Umgang mit HTML erforderlich sind). Zweitens ist Ihr Beispiel für XHTML oder XML, das gut geformt ist. HTML ist nicht gut geformt. Drittens müssen Sie sich fragen, ob es einfacher ist, einen Parser zu erweitern und zu pflegen, der in einer rekursiven Regex-Sprache oder einer Allzweck-Programmiersprache geschrieben ist.
Chas. Owens
Viertens ist sogar Ihr Beispiel trivial kaputt, während es noch gültiges XML ist. Fügen Sie ein Leerzeichen zwischen content_block und id hinzu, und es schlägt fehl. Ich bin sicher, wenn ich noch ein paar Minuten verbringen würde, würde ich einen anderen strukturellen Fehler in Ihrem Code finden. Es ist einfach keine gute Idee.
Chas. Owens
1

Ich habe eine vereinfachte Antwort auf dieses Problem hier . Obwohl die 100% -Marke nicht berücksichtigt wird, erkläre ich, wie es möglich ist, wenn Sie bereit sind, Vorverarbeitungsarbeiten durchzuführen.

Erutan409
quelle