Jak działają analizy HTML, jeśli nie używają wyrażenia regularnego?

96

Codziennie widzę pytania pytające, jak przeanalizować lub wyodrębnić coś z jakiegoś ciągu HTML, a pierwsza odpowiedź / komentarz zawsze brzmi: „Nie używaj RegEx do analizowania HTML, żebyś nie poczuł gniewu!” (ta ostatnia część jest czasami pomijana).

Jest to dla mnie dość mylące, zawsze myślałem, że ogólnie najlepszym sposobem przeanalizowania każdego skomplikowanego ciągu jest użycie wyrażenia regularnego. Jak więc działa parser HTML? Czy nie używa wyrażeń regularnych do analizowania.

Jednym z argumentów przemawiających za używaniem wyrażenia regularnego jest to, że nie zawsze istnieje alternatywa dla analizowania (np. JavaScript, gdzie DOMDocument nie jest powszechnie dostępną opcją). Na przykład jQuery wydaje się radzić sobie dobrze, używając wyrażenia regularnego do konwersji ciągu HTML na węzły DOM.

Nie jestem pewien, czy to CW, czy nie, jest to prawdziwe pytanie, na które chcę odpowiedzieć, a nie zamierzam być wątkiem dyskusyjnym.

Andy E.
źródło
Zmieniono tag, aby dodać parsowanie i parsowanie html - @Andy E, mam nadzieję, że z tobą wszystko w porządku - pomyślałem, że to będzie pomocne.
JXG
@JXG: W porządku, dziękuję :-)
Andy E

Odpowiedzi:

65

Zwykle za pomocą tokenizera. Projekt specyfikacji HTML5 zawiera rozbudowany algorytm obsługi „rzeczywistego kodu HTML”.

Quentin
źródło
1
Dobre znalezisko ... cytując: „Aby obsłużyć takie przypadki, parsery mają poziom zagnieżdżenia skryptu, który musi być początkowo ustawiony na zero, oraz flagę pauzy analizatora składni, która musi być początkowo ustawiona na wartość false”. - Innymi słowy, musisz sam to powtórzyć i mieć wiele niestandardowej logiki: P
Timothy Khouri
1
Głosuj za. Lepiej jest położyć nacisk na złożoność algorytmiczną zamiast jakiejś technologii.
Arnis Lapsa
1
Samodzielne iterowanie z dużą ilością niestandardowej logiki nie jest najlepszym pomysłem. Jeśli możesz, użyj biblioteki obsługującej standardowy algorytm. np. search.cpan.org/~tobyink/HTML-HTML5-Parser-0.03/lib/HTML/HTML5/… / code.google.com/p/html5lib
Quentin
8
Podstawowym problemem związanym z parserami HTML jest to, że po napotkaniu błędu nie możesz wypluć „błędu analizy” i na tym poprzestać. Wchodzisz w tryb dziwactw i starasz się wyciągnąć jak najwięcej z napotkanego bałaganu, w tym niedopasowanych tagów, przeplotu w stylu [{]} i wszelkiego rodzaju dziwactw, starając się, aby wynik wyglądał jak najlepiej i nieunikniony porażka najmniej bolesna ... nie można tego zrobić za pomocą wyrażeń regularnych.
SF.
7
@Timothy K: „Uwaga: ze względu na sposób, w jaki ten algorytm powoduje zmianę rodziców w elementach, został nazwany„ algorytmem agencji adopcyjnej ”(w przeciwieństwie do innych możliwych algorytmów postępowania z niepoprawnymi treściami, w tym„ algorytmu kazirodztwa ”), „algorytm tajnej sprawy” i „algorytm Heisenberga”) ”.
JXG
133

Jak więc działa parser HTML? Czy nie używa wyrażeń regularnych do analizowania?

Więc nie.

Jeśli wrócisz w swoim mózgu do teorii kursu obliczeniowego, jeśli wziąłeś udział w kursie kompilatorów lub czymś podobnym, możesz przypomnieć sobie, że istnieją różne rodzaje języków i modeli obliczeniowych. Nie mam kwalifikacji, by wchodzić we wszystkie szczegóły, ale mogę omówić z tobą kilka głównych punktów.

Najprostszym rodzajem języka i obliczeń (do tych celów) jest język zwykły. Można je generować za pomocą wyrażeń regularnych i rozpoznawać za pomocą automatów skończonych. Zasadniczo oznacza to, że „analizowanie” łańcuchów w tych językach używa stanu, ale nie pamięci pomocniczej. HTML z pewnością nie jest zwykłym językiem. Jeśli się nad tym zastanowić, lista tagów może być dowolnie zagnieżdżona głęboko. Na przykład tabele mogą zawierać tabele, a każda tabela może zawierać wiele zagnieżdżonych tagów. W przypadku wyrażeń regularnych możesz wybrać parę tagów, ale z pewnością nie będzie to dowolne zagnieżdżenie.

Klasyczny prosty język, który nie jest regularny, jest poprawnie dopasowany do nawiasów. Mimo prób, nigdy nie będziesz w stanie zbudować wyrażenia regularnego (lub automatu skończonego), które zawsze będzie działać. Potrzebujesz pamięci do śledzenia głębokości zagnieżdżenia.

Maszyna stanów ze stosem pamięci to kolejna siła modelu obliczeniowego. Nazywa się to automatem przesuwającym w dół i rozpoznaje języki generowane przez gramatykę bezkontekstową. W tym miejscu możemy rozpoznać poprawnie dopasowane nawiasy - rzeczywiście, stos jest dla niego idealnym modelem pamięci.

Czy to wystarczy dla HTML? Niestety nie. Może dla super-dupera, właściwie sprawdzonego XML-a, w którym wszystkie tagi zawsze są idealnie dopasowane. W prawdziwym HTML możesz łatwo znaleźć fragmenty, takie jak <b><i>wow!</b></i>. To oczywiście nie zagnieździ się, więc aby go przeanalizować poprawnie, stos nie jest wystarczająco silny.

Następnym poziomem obliczeń są języki generowane przez gramatykę ogólną i rozpoznawane przez maszyny Turinga. Ogólnie przyjmuje się, że jest to faktycznie najsilniejszy dostępny model obliczeniowy - maszyna stanu z pamięcią pomocniczą, której pamięć można modyfikować w dowolnym miejscu. To właśnie potrafią języki programowania. To jest poziom złożoności, na którym żyje HTML.

Podsumowując wszystko w jednym zdaniu: aby przeanalizować ogólny HTML, potrzebujesz prawdziwego języka programowania, a nie wyrażenia regularnego.

HTML jest parsowany w taki sam sposób, jak inne języki: leksowanie i parsowanie. Etap leksowania dzieli strumień pojedynczych znaków na znaczące tokeny. Etap analizy składa tokeny, używając stanów i pamięci, w logicznie spójny dokument, na którym można działać.

JXG
źródło
22

Wyrażenia regularne to tylko jedna z form parsera. Parser HTML typu „szczery do dobroci” będzie znacznie bardziej skomplikowany, niż można to wyrazić w wyrażeniach regularnych, używając rekursywnego zejścia , przewidywania i kilku innych technik do prawidłowej interpretacji tekstu. Jeśli naprawdę chcesz się w to zagłębić , możesz sprawdzić lex & yacc i podobne narzędzia.

Zakaz używania wyrażeń regularnych do analizowania kodu HTML powinien być prawdopodobnie napisany bardziej poprawnie jako: „Nie używaj naiwnych wyrażeń regularnych do analizowania kodu HTML…” (aby nie odczuwać gniewu) „… i traktuj wyniki z ostrożnością”. W przypadku niektórych konkretnych celów wyrażenie regularne może być całkowicie odpowiednie, ale musisz być bardzo ostrożny, aby zdawać sobie sprawę z ograniczeń swojego wyrażenia regularnego i być tak ostrożnym, jak jest to właściwe dla źródła tekstu, który analizujesz (np. dane wejściowe użytkownika, naprawdę bądź bardzo ostrożny).

TJ Crowder
źródło
+1, dobra odpowiedź. Muszę przyznać, że wcześniej używałem wyrażeń regularnych, nawet gdy nie kontrolowałem HTML-a, ale nie w żadnej publicznie wydanej aplikacji. Ja też „poczułem gniew”, bo to było naiwne. Ale to było dawno temu :-)
Andy E
6

Parsowanie HTML to przekształcenie liniowego tekstu w strukturę drzewa. Wyrażenia regularne zasadniczo nie obsługują struktur drzewiastych. Wyrażenie regularne, którego potrzebujesz w każdym momencie, aby uzyskać następny token, zmienia się przez cały czas. Możesz używać wyrażeń regularnych w parserze, ale będziesz potrzebować całej tablicy wyrażeń regularnych dla każdego możliwego stanu analizowania.

Svante
źródło
2

Jeśli chcesz mieć 100% rozwiązanie: musisz napisać własny niestandardowy kod, który iteruje po kodzie HTML znak po znaku, i musisz mieć ogromną ilość logiki, aby określić, czy powinieneś zatrzymać bieżący węzeł i uruchomić Kolejny.

Powodem jest to, że jest to poprawny HTML:

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

Ale tak jest:

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

Jeśli nie masz nic przeciwko „rozwiązaniu 90%”: W takim razie użycie parsera XML do załadowania dokumentu jest w porządku. Lub używając Regex (chociaż XML jest łatwiejszy, jeśli jesteś wtedy mistrzem treści).

Timothy Khouri
źródło
4
Parser XML jest bardziej jak 1% rozwiązanie. Liczba dobrze sformułowanych dokumentów HTML w formacie XML jest niewielka.
Quentin
4
Tak, robią… nie traktuj „znak po znaku” dosłownie, ponieważ możesz próbować przesyłać strumieniowo. Ale chodzi mi o to, że musisz napisać swój własny parser. Nowe wieku programiści nie są używane do tego rodzaju pisania kodu ... jesteśmy przyzwyczajeni do „HtmlDocumentUtility.Load” i takie tam :)
Timothy Khouri
4
@Andy E: Regeksy nie są magiczne, działają również znak po znaku, jak każdy inny rodzaj analizowania lub do cholery, każda inna funkcja ciągu.
Bart van Heukelom
1
BTW: Twój pierwszy przykład to nie tylko „pół-poprawny kod HTML”. Właściwie jest to poprawny HTML 4.01 Strict. Możesz użyć np. Walidatora W3C, aby to zweryfikować. Tag zamykający jest oficjalnie opcjonalny dla <li> (zobacz specyfikację HTML 4).
sleske
2
@Bart: słuszna uwaga, czasami mój mózg zapomina o całej logice i myśli, że rzeczy działają dzięki magii.
Andy E