Dlaczego nie można użyć wyrażenia regularnego do przeanalizowania HTML / XML: formalne wyjaśnienie w kategoriach laika

Nie ma dnia na SO, który upłynąłby bez pytania o parsowanie (X) HTML lub XML z zadawaniem wyrażeń regularnych.

Chociaż stosunkowo łatwo jest wymyślić przykłady, które demonstrują nierentowność wyrażeń regularnych dla tego zadania lub z kolekcją wyrażeń reprezentujących tę koncepcję, nadal nie mogłem znaleźć na SO formalnego wyjaśnienia, dlaczego nie jest to możliwe w przypadku laika. warunki.

Jedyne formalne wyjaśnienia, jakie do tej pory udało mi się znaleźć na tej stronie, są prawdopodobnie niezwykle dokładne, ale także dość tajemnicze dla samouka programisty:

błąd polega na tym, że HTML jest gramatyką Chomsky'ego typu 2 (gramatyka bezkontekstowa), a RegEx to gramatyka Chomsky'ego typu 3 (wyrażenie regularne)

lub:

Wyrażenia regularne mogą pasować tylko do zwykłych języków, ale HTML jest językiem bezkontekstowym.

lub:

Automat skończony (który jest strukturą danych leżącą u podstaw wyrażenia regularnego) nie ma pamięci poza stanem, w którym się znajduje, a jeśli masz dowolnie głębokie zagnieżdżenie, potrzebujesz dowolnego automatu skończonego, który koliduje z pojęciem automatu skończonego.

lub:

Lemat o pompowaniu dla zwykłych języków jest powodem, dla którego nie możesz tego zrobić.

[Aby być uczciwym: większość powyższych wyjaśnień prowadzi do stron Wikipedii, ale nie są one dużo łatwiejsze do zrozumienia niż same odpowiedzi].

Więc moje pytanie brzmi: czy ktoś mógłby dostarczyć tłumaczenie w warunkach laika formalnych wyjaśnień podanych powyżej, dlaczego nie jest możliwe użycie wyrażenia regularnego do analizowania (X) HTML / XML?

EDYCJA: Po przeczytaniu pierwszej odpowiedzi pomyślałem, że powinienem wyjaśnić: szukam „tłumaczenia”, które również krótko wyjaśnia pojęcia, które próbuje przetłumaczyć: na końcu odpowiedzi czytelnik powinien mieć przybliżony pomysł - na przykład - co oznaczają „język zwykły” i „gramatyka bezkontekstowa” ...

Skoncentruj się na tym:

Automat skończony (który jest strukturą danych leżącą u podstaw wyrażenia regularnego) nie ma pamięci poza stanem, w którym się znajduje, a jeśli masz dowolnie głębokie zagnieżdżenie, potrzebujesz dowolnego automatu skończonego, który koliduje z pojęciem automatu skończonego.

Definicji wyrażeń regularnych jest równoznaczne z tym, że to test, czy łańcuch pasuje do wzorca mogą być wykonywane przez automat skończony (jeden inny automat do każdego wzoru). Automat skończony nie ma pamięci - ani stosu, ani stosu, ani nieskończonej taśmy, na której można by pisać. Wszystko, co ma, to skończona liczba stanów wewnętrznych, z których każdy może odczytać jednostkę wejściową z testowanego ciągu i użyć jej do zdecydowania, do którego stanu przejść. W szczególnych przypadkach ma dwa stany zakończenia: „tak, to pasuje” i „nie, to nie pasuje”.

Z drugiej strony HTML ma struktury, które mogą zagnieżdżać się dowolnie głęboko. Aby określić, czy plik jest prawidłowym kodem HTML, czy nie, musisz sprawdzić, czy wszystkie znaczniki zamykające pasują do poprzedniego znacznika otwierającego. Aby to zrozumieć, musisz wiedzieć, który element jest zamykany. Bez możliwości „zapamiętania”, jakie otwierające tagi widziałeś, nie ma szans.

Należy jednak zauważyć, że większość bibliotek „regex” w rzeczywistości pozwala na coś więcej niż tylko ścisłą definicję wyrażeń regularnych. Jeśli potrafią dopasować odniesienia wsteczne, to wyszli poza zwykły język. Więc powód, dla którego nie powinieneś używać biblioteki wyrażeń regularnych w HTML jest trochę bardziej złożony niż prosty fakt, że HTML nie jest zwykły.

Fakt, że HTML nie reprezentuje zwykłego języka, to czerwony śledź. Wyrażenia regularne i języki regularne brzmią podobnie , ale nie są - mają to samo pochodzenie, ale istnieje znaczny dystans między akademickimi „językami regularnymi” a obecną mocą dopasowywania silników. W rzeczywistości prawie wszystkie współczesne silniki wyrażeń regularnych obsługują nieregularne funkcje - prosty przykład to (.*)\1. który używa odwołań wstecznych do dopasowania powtarzającej się sekwencji znaków - na przykład 123123lub bonbon. Dopasowywanie rekurencyjnych / zrównoważonych struktur sprawia, że ​​jest to jeszcze przyjemniejsze.

Wikipedia ładnie to ujmuje, cytując Larry'ego Wall'a :

„Wyrażenia regularne” […] są tylko marginalnie związane z prawdziwymi wyrażeniami regularnymi. Niemniej jednak termin ten urósł wraz z możliwościami naszych silników dopasowywania wzorców, więc nie zamierzam tutaj walczyć z koniecznością językową. Ogólnie będę jednak nazywać je „wyrażeniami regularnymi” (lub „wyrażeniami regularnymi”, kiedy jestem w nastroju anglosaskim).

„Wyrażenie regularne można dopasować tylko do języków regularnych”, jak widać, to nic innego jak powszechnie stosowany błąd.

Więc dlaczego nie?

Dobrym powodem, dla którego nie należy dopasowywać kodu HTML do wyrażeń regularnych, jest to, że „tylko dlatego, że możesz, nie znaczy, że powinieneś”. Chociaż może to być możliwe - istnieją po prostu lepsze narzędzia do tego zadania . Wobec:

• Prawidłowy HTML jest trudniejszy / bardziej złożony niż myślisz.
• Istnieje wiele typów „prawidłowego” HTML-a - na przykład to, co jest prawidłowe w HTML, nie jest poprawne w XHTML.
• Większość wolnego formatu HTML znalezionego w Internecie i tak nie jest poprawna . Biblioteki HTML również dobrze sobie z nimi radzą i zostały przetestowane pod kątem wielu z tych typowych przypadków.

• Bardzo często niemożliwe jest dopasowanie części danych bez ich analizy jako całości. Na przykład, możesz szukać wszystkich tytułów i zakończyć dopasowanie wewnątrz komentarza lub literału ciągu. <h1>.*?</h1>może być odważną próbą znalezienia głównego tytułu, ale może znaleźć:

  <!-- <h1>not the title!</h1> -->

  Lub nawet:

  <script>
  var s = "Certainly <h1>not the title!</h1>";
  </script>
  

Ostatni punkt jest najważniejszy:

• Używanie dedykowanego parsera HTML jest lepsze niż jakikolwiek regex, który możesz wymyślić. Bardzo często XPath pozwala na bardziej wyrazisty sposób znajdowania potrzebnych danych, a użycie parsera HTML jest znacznie łatwiejsze niż większość ludzi zdaje sobie sprawę .

Dobre podsumowanie tematu i ważny komentarz dotyczący mieszania Regex i HTML mogą być odpowiednie, można znaleźć na blogu Jeffa Atwooda: Parsing Html The Cthulhu Way .

Kiedy lepiej jest używać wyrażeń regularnych do analizowania kodu HTML?

W większości przypadków lepiej jest używać XPath na strukturze DOM, którą oferuje biblioteka. Mimo to, wbrew popularnej opinii, jest kilka przypadków, w których zdecydowanie zalecałbym używanie wyrażenia regularnego, a nie biblioteki parsera:

Biorąc pod uwagę kilka z tych warunków:

• Gdy potrzebujesz jednorazowej aktualizacji plików HTML i wiesz, że struktura jest spójna.
• Gdy masz bardzo mały fragment kodu HTML.
• Kiedy nie masz do czynienia z plikiem HTML, ale podobnym silnikiem szablonów (w takim przypadku może być bardzo trudno znaleźć parser).
• Jeśli chcesz zmienić część HTML, ale nie całość - parser, o ile wiem, nie może odpowiedzieć na to żądanie: przeanalizuje cały dokument i zapisze cały dokument, zmieniając części, których nigdy nie chciałeś zmieniać.

Ponieważ HTML może mieć nieograniczone zagnieżdżanie, <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>a wyrażenie regularne nie może sobie z tym poradzić, ponieważ nie może śledzić historii tego, do czego się wywodzi i z czego wychodzi.

Prosta konstrukcja, która ilustruje trudność:

<body><div id="foo">Hi there!  <div id="bar">Bye!</div></div></body>

99,9% uogólnionych procedur wyodrębniania opartych na wyrażeniach regularnych nie będzie w stanie poprawnie podać wszystkiego wewnątrz elementu divz identyfikatorem foo, ponieważ nie mogą odróżnić tagu zamykającego dla tego elementu div od tagu zamykającego dla elementu bardiv. Dzieje się tak, ponieważ nie mają możliwości powiedzenia „okej, zszedłem teraz do drugiego z dwóch elementów div, więc następny element zamykający, który widzę, przenosi mnie z powrotem do jednego, a następny jest znacznikiem zamykającym dla pierwszego” . Programiści zazwyczaj odpowiadają, opracowując foowyrażenia regularne dla specjalnych przypadków dla konkretnej sytuacji, które następnie psują się, gdy tylko zostanie wprowadzonych więcej tagów i muszą zostać rozwiązane z ogromnym kosztem czasu i frustracji. To dlatego ludzie się wściekają.

Język regularny to język, do którego można dopasować skończoną maszynę stanów.

(Zrozumienie maszyn skończonych, maszyn przesuwających się w dół i maszyn Turinga jest w zasadzie programem nauczania kursu CS na czwartym roku uczelni).

Rozważmy następującą maszynę, która rozpoznaje napis „cześć”.

(Start) --Read h-->(A)--Read i-->(Succeed)
  \                  \
   \                  -- read any other value-->(Fail) 
    -- read any other value-->(Fail)

To jest prosta maszyna do rozpoznawania zwykłego języka; Każde wyrażenie w nawiasach to stan, a każda strzałka to przejście. Zbudowanie takiej maszyny pozwoli ci przetestować dowolny ciąg wejściowy w języku regularnym - stąd wyrażenie regularne.

HTML wymaga więcej informacji niż tylko tego, w jakim jesteś stanie - wymaga historii tego, co widziałeś wcześniej, aby dopasować zagnieżdżenie tagów. Możesz to osiągnąć, jeśli dodasz stos do maszyny, ale wtedy nie będzie on już „zwykły”. Nazywa się to maszyną przesuwającą w dół i rozpoznaje gramatykę.

Wyrażenie regularne to maszyna ze skończoną (i zazwyczaj raczej małą) liczbą dyskretnych stanów.

Aby przeanalizować XML, C lub jakikolwiek inny język z dowolnym zagnieżdżeniem elementów języka, musisz pamiętać, jak głęboko jesteś. Oznacza to, że musisz być w stanie policzyć nawiasy klamrowe / nawiasy / tagi.

Nie możesz liczyć ze skończoną pamięcią. Poziomów nawiasów klamrowych może być więcej niż stanów! Możesz być w stanie przeanalizować podzbiór swojego języka, który ogranicza liczbę poziomów zagnieżdżenia, ale byłoby to bardzo żmudne.

Gramatyka to formalna definicja tego, gdzie mogą się znaleźć słowa. Na przykład przymiotniki poprzedzają rzeczowniki in English grammar, ale następują po rzeczownikach en la gramática española. Bezkontekstowy oznacza, że ​​gramofon jest uniwersalny we wszystkich kontekstach. Wrażliwość na kontekst oznacza, że ​​w niektórych kontekstach istnieją dodatkowe reguły.

Na przykład w C # usingoznacza coś innego w using System;górnej części plików niż using (var sw = new StringWriter (...)). Bardziej odpowiednim przykładem jest następujący kod w kodzie:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

Istnieje jeszcze jeden praktyczny powód, dla którego nie należy używać wyrażeń regularnych do analizowania XML i HTML, który nie ma nic wspólnego z teorią informatyki: twoje wyrażenie regularne będzie albo ohydnie skomplikowane, albo będzie błędne.

Na przykład bardzo dobrze jest napisać pasujące wyrażenie regularne

<price>10.65</price>

Ale jeśli twój kod ma być poprawny, to:

• Musi dopuszczać spację po nazwie elementu zarówno w znaczniku początkowym, jak i końcowym

• Jeśli dokument znajduje się w przestrzeni nazw, powinien umożliwiać użycie dowolnego prefiksu przestrzeni nazw

• Powinien prawdopodobnie dopuszczać i ignorować wszelkie nieznane atrybuty pojawiające się w tagu początkowym (w zależności od semantyki danego słownictwa)

• Może być konieczne dopuszczenie białych znaków przed i po wartości dziesiętnej (ponownie, w zależności od szczegółowych reguł określonego słownika XML).

• Nie powinno pasować do czegoś, co wygląda jak element, ale w rzeczywistości znajduje się w komentarzu lub sekcji CDATA (staje się to szczególnie ważne, jeśli istnieje możliwość, że złośliwe dane próbują oszukać parser).

• Może być konieczne wykonanie diagnostyki, jeśli dane wejściowe są nieprawidłowe.

Oczywiście część z tego zależy od stosowanych przez Ciebie standardów jakości. Widzimy wiele problemów w StackOverflow, gdzie ludzie muszą generować XML w określony sposób (na przykład bez spacji w tagach), ponieważ jest on odczytywany przez aplikację, która wymaga, aby był napisany w określony sposób. Jeśli twój kod ma jakąkolwiek długowieczność, ważne jest, aby był w stanie przetwarzać przychodzące XML napisane w dowolny sposób, na jaki pozwala standard XML, a nie tylko jeden przykładowy dokument wejściowy, na którym testujesz swój kod.

W sensie czysto teoretycznym wyrażenia regularne nie mogą analizować XML. Są zdefiniowane w sposób, który nie pozwala im zapamiętać żadnego poprzedniego stanu, uniemożliwiając w ten sposób poprawne dopasowanie dowolnego znacznika i nie mogą wnikać w dowolną głębokość zagnieżdżenia, ponieważ zagnieżdżenie musiałoby być wbudowane w wyrażenie regularne.

Jednak nowoczesne parsery wyrażeń regularnych są zbudowane z myślą o użyteczności dla programistów, a nie na zgodności z precyzyjną definicją. W związku z tym mamy takie rzeczy, jak odwołania wsteczne i rekurencja, które wykorzystują wiedzę o poprzednich stanach. Korzystając z nich, niezwykle łatwo jest utworzyć wyrażenie regularne, które może eksplorować, weryfikować lub analizować XML.

Rozważmy na przykład

(?:
    <!\-\-[\S\s]*?\-\->
    |
    <([\w\-\.]+)[^>]*?
    (?:
        \/>
        |
        >
        (?:
            [^<]
            |
            (?R)
        )*
        <\/\1>
    )
)

Spowoduje to odnalezienie następnego prawidłowo uformowanego znacznika XML lub komentarza i znajdzie go tylko wtedy, gdy cała jego zawartość jest odpowiednio uformowana. (To wyrażenie zostało przetestowane przy użyciu Notepad ++, który używa biblioteki regex Boost C ++, która jest bardzo zbliżona do PCRE.)

Oto jak to działa:

1. Pierwsza porcja pasuje do komentarza. Konieczne jest, aby było to pierwsze, aby poradziło sobie z każdym zakomentowanym kodem, który w przeciwnym razie mógłby spowodować zawieszenie się.
2. Jeśli to nie pasuje, będzie szukać początku tagu. Zwróć uwagę, że do przechwycenia nazwy używa nawiasów.
3. Ten tag kończy się na a />, tym samym uzupełniając tag, lub na a >, w którym to przypadku będzie kontynuowany, sprawdzając zawartość tagu.
4. Będzie kontynuował analizowanie, aż osiągnie a <, w którym to momencie wróci do początku wyrażenia, pozwalając mu zająć się komentarzem lub nowym znacznikiem.
5. Będzie kontynuował pętlę, dopóki nie dotrze do końca tekstu lub do miejsca, <którego nie może przeanalizować. Brak dopasowania spowoduje oczywiście rozpoczęcie procesu od nowa. W przeciwnym razie <przypuszczalnie jest początkiem znacznika zamykającego dla tej iteracji. Używając odniesienia wstecznego wewnątrz znacznika zamykającego <\/\1>, dopasuje on tag otwierający dla bieżącej iteracji (głębokość). Jest tylko jedna grupa do przejmowania, więc ten mecz to prosta sprawa. Dzięki temu jest niezależna od nazw użytych tagów, chociaż w razie potrzeby możesz zmodyfikować grupę przechwytywania, aby przechwytywała tylko określone znaczniki.
6. W tym momencie albo wyskoczy z bieżącej rekursji na następny poziom, albo zakończy się dopasowaniem.

Ten przykład rozwiązuje problemy związane z białymi znakami lub identyfikacją odpowiedniej treści za pomocą grup znaków, które jedynie negują <lub >, w przypadku komentarzy, używając [\S\s], które dopasuje wszystko, w tym powrót karetki i nowe wiersze, nawet w jednowierszowych tryb, kontynuując, aż osiągnie -->. Dlatego po prostu traktuje wszystko jako ważne, dopóki nie osiągnie czegoś znaczącego.

W większości przypadków takie wyrażenie regularne nie jest szczególnie przydatne. Sprawdza, czy XML jest poprawnie sformułowany, ale to wszystko, co naprawdę robi, i nie uwzględnia właściwości (chociaż byłoby to łatwe dodanie). To tylko takie proste, ponieważ pomija rzeczywiste problemy, takie jak ten, a także definicje nazw tagów. Dopasowanie go do prawdziwego użytku uczyniłoby go o wiele bardziej bestią. Ogólnie rzecz biorąc, prawdziwy parser XML byłby znacznie lepszy. Ten prawdopodobnie najlepiej nadaje się do nauczania, jak działa rekurencja.

Krótko mówiąc: używaj parsera XML do prawdziwej pracy i używaj go, jeśli chcesz bawić się wyrażeniami regularnymi.

Nie parsuj XML / HTML za pomocą wyrażenia regularnego, użyj odpowiedniego parsera XML / HTML i potężnego xpath pytanie.

teoria:

Zgodnie z teorią kompilacji, XML / HTML nie może być analizowany przy użyciu wyrażenia regularnego opartego na skończonej maszynie stanów . Ze względu na hierarchiczną konstrukcję XML / HTML musisz używać automatu przesuwającego w dół i manipulować gramatyką LALR za pomocą narzędzia takiego jak YACC .

Narzędzie realLife © ® ™ do codziennego użytku w formacie muszla :

Możesz użyć jednego z następujących:

xmllint często jest domyślnie instalowany z libxml2, xpath1 (sprawdź, czy moje opakowanie ma dane wyjściowe rozdzielane znakami nowej linii

xmlstarlet może edytować, wybierać, przekształcać ... Domyślnie nie jest instalowany, xpath1

xpath zainstalowany przez moduł perla XML :: XPath, xpath1

xidel xpath3

saxon-lint mój własny projekt, opakowanie na bibliotekę Java Saxon-HE @ Michaela Kaya, xpath3

lub możesz użyć języków wysokiego poziomu i odpowiednich bibliotek, myślę o:

pyton's lxml( from lxml import etree)

perl„y XML::LibXML, XML::XPath, XML::Twig::XPath,HTML::TreeBuilder::XPath

rubin nokogiri, sprawdź ten przykład

php DOMXpath, sprawdź ten przykład

Sprawdź: Używanie wyrażeń regularnych z tagami HTML