Почему невозможно использовать регулярные выражения для разбора HTML / XML: формальное объяснение в терминах непрофессионала - PullRequest
105 голосов
/ 19 июля 2011

Нет ни одного дня в SO, который бы проходил без вопросов о разборе (X) HTML или XML с запрашиваемыми регулярными выражениями.

Хотя относительно просто придумать примеров, демонстрирующих невозможность регулярных выражений для этой задачи или набор выражений для представления концепции, я все еще не мог найдите на SO формальное объяснение того, почему это невозможно сделать с точки зрения непрофессионала.

Единственные формальные объяснения, которые я мог найти до сих пор на этом сайте, вероятно, чрезвычайно точны, но также довольно загадочны для программиста-самоучки:

недостаток в том, что HTML является грамматикой Хомского типа 2 (не зависит от контекста) грамматика) и RegEx - грамматика Хомского типа 3 (регулярное выражение)

или

Регулярные выражения могут соответствовать только обычным языкам, но HTML контекстно-свободный язык.

или

Конечный автомат (структура данных, лежащая в основе регулярного выражение) не имеет памяти, кроме состояния, в котором он находится, и если у вас сколь угодно глубокая вложенность, нужно как угодно большое автомат, который сталкивается с понятием конечного автомата.

или

Лемма Pumping для обычных языков - причина, почему вы не можете сделать что.

[Справедливости ради: большинство вышеприведенных пояснений ссылаются на страницы Википедии, но их не намного легче понять, чем сами ответы].

Итак, мой вопрос: Может ли кто-нибудь предоставить перевод в терминах непрофессионала формальных объяснений, приведенных выше, почему невозможно использовать регулярные выражения для анализа (X) HTML / XML?

РЕДАКТИРОВАТЬ: После прочтения первого ответа я подумал, что должен уточнить: я ищу "перевод", который также кратко объясняет концепции, которые он пытается перевести: на В конце ответа читатель должен иметь приблизительное представление - например, о том, что означает «обычный язык» и «контекстно-свободная грамматика» ...

Ответы [ 9 ]

102 голосов
/ 19 июля 2011

Сконцентрируйтесь на этом:

У конечного автомата (который является структурой данных, лежащей в основе регулярного выражения) нет памяти, кроме состояния, в котором он находится, и если у вас сколь угодно глубокая вложенность,вам нужен сколь угодно большой автомат, который вступает в противоречие с понятием конечного автомата.

Определение регулярных выражений эквивалентно тому факту, что проверка соответствия строкишаблон может быть выполнен конечным автоматом (один отдельный автомат для каждого шаблона).У конечного автомата нет памяти - нет стека, нет кучи, нет бесконечной ленты, чтобы писать.Все, что у него есть - это конечное число внутренних состояний, каждое из которых может прочитать единицу ввода из тестируемой строки и использовать ее, чтобы решить, в какое состояние перейти в следующее.В особых случаях он имеет два состояния завершения: «да, это соответствует» и «нет, что не соответствует».

HTML, с другой стороны, имеет структуры, которые могут вкладываться произвольно глубоко.Чтобы определить, является ли файл действительным HTML или нет, необходимо проверить, что все закрывающие теги соответствуют предыдущему открывающему тегу.Чтобы понять это, вам нужно знать, какой элемент закрывается.Без каких-либо средств «запомнить», какие открывающие теги вы видели, нет никаких шансов.

Однако обратите внимание, что большинство библиотек «регулярных выражений» на самом деле допускают не только строгое определение регулярных выражений.Если они могут соответствовать обратным ссылкам, то они вышли за рамки обычного языка.Поэтому причина, по которой вам не следует использовать библиотеку регулярных выражений в HTML, немного сложнее, чем простой факт, что HTML не является регулярным.

52 голосов
/ 19 июля 2011

Тот факт, что HTML не представляет обычный язык, является красной сельдью.Регулярные выражения и регулярные языки звучат примерно как , но это не так - они имеют одно и то же происхождение, но между академическими "обычными языками" и текущей мощностью соответствия движков есть заметное расстояние.Фактически, почти все современные движки регулярных выражений поддерживают нерегулярные функции - простой пример - (.*)\1.который использует обратную ссылку для соответствия повторяющейся последовательности символов - например, 123123 или bonbon.Сопоставление рекурсивных / сбалансированных структур делает их еще более увлекательными.

Википедия прекрасно описывает это в цитате Ларри Уолла :

'Регулярные выражения' [...] лишь незначительно связаны с реальными регулярными выражениями.Тем не менее, этот термин вырос с возможностями наших механизмов сопоставления с образцом, поэтому я не буду пытаться бороться с лингвистической необходимостью здесь.Однако я обычно называю их «регулярными выражениями» (или «регулярными выражениями», когда я нахожусь в англосаксонском настроении).

«Регулярное выражение может соответствовать только обычным языкам», поскольку выПонимаете, это не более чем общепринятая ошибка.

Так почему бы и нет?

Хорошая причина не сопоставлять HTML с регулярным выражением состоит в том, что «только потому, что вы можете, не можетезначит ты должен ".Хотя это возможно - , есть просто лучшие инструменты для работы .Принимая во внимание:

  • Допустимый HTML сложнее / сложнее, чем вы думаете.
  • Существует много типов «допустимого» HTML - то, что допустимо в HTML, например, isn 'Действителен в XHTML.
  • Большая часть HTML-кода свободной формы, найденного в Интернете, в любом случае недействительна .Библиотеки HTML хорошо справляются и с ними, и были протестированы для многих из этих распространенных случаев.
  • Очень часто невозможно сопоставить часть данных без их анализа в целом,Например, вы можете искать все заголовки и в конечном итоге сопоставлять их внутри комментария или строкового литерала.<h1>.*?</h1> может быть смелой попыткой найти главный заголовок, но он может найти:

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

    Или даже:

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

Последний пункт - этосамое важное:

  • Использование выделенного анализатора HTML лучше, чем любое регулярное выражение, которое вы можете придумать.Очень часто XPath предоставляет более выразительный способ поиска необходимых данных, и с помощью HTML-парсера гораздо проще, чем большинство людей понимают .

Хорошее краткое изложение предметаи важный комментарий о том, когда может быть уместным смешивать Regex и HTML, можно найти в блоге Джеффа Этвуда: Парсинг Html Путь Ктулху .

Когда лучше использовать регулярное выражениедля анализа HTML?

В большинстве случаев лучше использовать XPath в структуре DOM, которую может предоставить библиотека.Тем не менее, вопреки распространенному мнению, есть несколько случаев, когда я настоятельно рекомендовал бы использовать регулярное выражение, а не библиотеку синтаксического анализатора:

Учитывая некоторые из следующих условий:

  • Когда вам нужнооднократное обновление ваших HTML-файлов, и вы знаете, что структура последовательна.
  • Когда у вас очень маленький фрагмент HTML.
  • Когда вы не имеете дело с HTML-файлом, но похожий шаблонизатор (в этом случае может быть очень трудно найти анализатор).
  • Когда вы хотите изменить части HTML, но не все из них - aПарсер, насколько мне известно, не может ответить на этот запрос: он проанализирует весь документ и сохранит весь документ, изменяя части, которые вы никогда не хотели изменять.
18 голосов
/ 19 июля 2011

Потому что HTML может иметь неограниченное вложение <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>, и регулярное выражение не может справиться с этим, потому что не может отследить историю того, во что он спустился и откуда вышел.

Простая конструкция, котораяиллюстрирует трудность:

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

99,9% обобщенных процедур извлечения на основе регулярных выражений не смогут правильно дать мне все внутри div с идентификатором foo, потому что они не могут сказать закрытиетег для этого div из закрывающего тега для bar div.Это потому, что у них нет никакого способа сказать: «Хорошо, теперь я спустился во второй из двух дивов, поэтому следующее закрытие дива, которое я вижу, возвращает меня к одному, а следующий за ним тег закрытия для первого»,Программисты обычно отвечают, разрабатывая регулярные выражения в особых случаях для конкретной ситуации, которые затем ломаются, как только в foo вводятся дополнительные теги, и им приходится разбираться с огромными затратами времени и разочарований.Вот почему люди злятся на все это.

8 голосов
/ 19 июля 2011

Обычный язык - это язык, которому может соответствовать конечный автомат.

(Понимание машин конечного состояния, машин Push-down и машин Тьюринга в основном является учебным планом курса CS четвертого курса колледжа.)

Рассмотрим следующую машину, которая распознает строку».

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

Это простая машина для распознавания обычного языка;Каждое выражение в скобках - это состояние, а каждая стрелка - это переход.Построение машины, подобной этой, позволит вам проверить любую входную строку на обычном языке - следовательно, на регулярном выражении.

HTML требует, чтобы вы знали больше, чем просто в каком состоянии вы находитесь - для этого требуется историяиз того, что вы видели раньше, чтобы соответствовать вложенности тега.Вы можете сделать это, если добавите стек к машине, но тогда он больше не будет «обычным».Это называется автоматом, который распознает грамматику.

6 голосов
/ 19 июля 2011

Грамматика - это формальное определение того, куда могут идти слова. Например, прилагательные предшествуют существительным in English grammar, но следуют за существительными en la gramática española. Контекстно-свободный означает, что грамматика универсальна во всех контекстах. Контекстно-зависимый означает, что в определенных контекстах существуют дополнительные правила.

Например, в C # using означает что-то другое в using System; вверху файлов, чем using (var sw = new StringWriter (...)). Более уместным примером является следующий код в коде:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}
6 голосов
/ 19 июля 2011

Регулярное выражение - это машина с конечным (и обычно довольно небольшим) числом дискретных состояний.

Чтобы проанализировать XML, C или любой другой язык с произвольной вложенностью языковых элементов, вам нужно помнить, насколько вы глубоки.То есть вы должны иметь возможность считать скобки / скобки / теги.

Вы не можете считать с конечной памятью.Может быть больше уровней скобок, чем у вас есть состояния!Возможно, вы сможете проанализировать подмножество вашего языка, которое ограничивает количество уровней вложенности, но это будет очень утомительно.

4 голосов
/ 13 июня 2018

Существует еще одна практическая причина не использовать регулярные выражения для анализа XML и HTML, которая вообще не имеет ничего общего с теорией информатики: ваше регулярное выражение будет либо ужасно сложным, либо ошибочным.

Например, все очень хорошо пишет регулярное выражение для соответствия

<price>10.65</price>

Но если ваш код должен быть правильным, то:

  • Это должно разрешить пробелпосле имени элемента в начальном и конечном тегах

  • Если документ находится в пространстве имен, он должен позволять использовать любой префикс пространства имен

  • Вероятно, он должен разрешать и игнорировать любые неизвестные атрибуты, появляющиеся в начальном теге (в зависимости от семантики конкретного словаря)

  • Возможно, потребуется разрешить пробел до и после десятичного значения(опять же, в зависимости от подробных правил конкретного словаря XML).

  • Оно не должно совпадать с чем-то похожим наэлемент n, но фактически находится в разделе комментариев или CDATA (это становится особенно важным, если существует вероятность того, что вредоносные данные пытаются обмануть ваш анализатор).

  • Возможно, потребуется провести диагностикуесли ввод неверен.

Конечно, отчасти это зависит от применяемых вами стандартов качества.Мы видим много проблем в StackOverflow с людьми, которые должны генерировать XML особым образом (например, без пробелов в тегах), потому что он читается приложением, которое требует, чтобы он был написан определенным образом.Если ваш код имеет какой-либо срок службы, важно, чтобы он мог обрабатывать входящий XML, написанный любым способом, который допускает стандарт XML, а не только один образец входного документа, на котором вы тестируете свой код.

2 голосов
/ 20 июня 2018

В чисто теоретическом смысле регулярные выражения не могут проанализировать XML.Они определены таким образом, что не позволяют им запоминать какое-либо предыдущее состояние, тем самым предотвращая правильное сопоставление произвольного тега, и они не могут проникнуть на произвольную глубину вложенности, поскольку вложенность должна быть встроена в регулярное выражение.

Современные парсеры регулярных выражений, однако, созданы для их удобства для разработчика, а не для их соблюдения точного определения.Таким образом, у нас есть такие вещи, как обратные ссылки и рекурсия, которые используют знания предыдущих состояний.Используя их, очень просто создать регулярное выражение, которое может исследовать, проверять или анализировать XML.

Рассмотрим, например,

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

. Здесь будет найден следующий правильно сформированный тег XML иликомментарий, и он найдет его, только если все его содержимое правильно сформировано. (Это выражение было протестировано с использованием Notepad ++, который использует библиотеку регулярных выражений Boost C ++, которая очень похожа на PCRE.)

Вот как это работает:

  1. Первоечанк соответствует комментарию.Это необходимо сделать первым, чтобы иметь дело с любым закомментированным кодом, который в противном случае мог бы вызвать зависания.
  2. Если это не совпадает, он будет искать начало тега.Обратите внимание, что для захвата имени используются круглые скобки.
  3. Этот тег будет либо заканчиваться на />, таким образом заканчивая тег, либо заканчиваться на >, и в этом случае он будет продолжен путем изучениясодержимое тега.
  4. Он продолжит синтаксический анализ, пока не достигнет <, после чего он вернется к началу выражения, позволяя ему иметь дело либо с комментарием, либо с новым тегом.
  5. Он будет продолжаться в цикле, пока не достигнет конца текста или значения <, которое не может быть проанализировано.Несоответствие, конечно, заставит его начать процесс заново.В противном случае <, вероятно, является началом закрывающего тега для этой итерации.Используя обратную ссылку внутри закрывающего тега <\/\1>, он будет соответствовать открывающему тегу для текущей итерации (глубина).Есть только одна группа захвата, так что это совпадение очень просто.Это делает его независимым от имен используемых тегов, хотя вы можете изменить группу захвата для захвата только определенных тегов, если вам нужно.
  6. В этот момент он либо выйдет из текущей рекурсии, вверхперейти к следующему уровню или завершиться совпадением.

В этом примере решаются проблемы, связанные с пробелами или идентификацией соответствующего содержимого, с помощью групп символов, которые просто сводят на нет < или >, или вв случае комментариев, используя [\S\s], который будет соответствовать чему угодно, включая возврат каретки и новые строки, даже в однострочном режиме, продолжая, пока не достигнет -->.Следовательно, он просто обрабатывает все как допустимые, пока не достигнет чего-то значимого.

Для большинства целей такое выражение не особенно полезно.Он подтвердит, что XML сформирован правильно, но это все, что он действительно сделает, и не учитывает свойства (хотя это было бы простым дополнением).Это так просто, потому что не учитывает такие проблемы реального мира, как определения имен тегов.Приспособление этого к реальному использованию сделало бы это намного больше зверя.Вообще, настоящий парсер XML был бы намного лучше.Этот, вероятно, лучше всего подходит для обучения работе рекурсии.

Короче говоря: используйте парсер XML для реальной работы и используйте его, если вы хотите поиграть с регулярными выражениями.

0 голосов
/ 03 апреля 2019

Не анализируйте XML / HTML с регулярным выражением, используйте правильный синтаксический анализатор XML / HTML и мощный запрос.

теория:

Согласно теории компиляции, XML / HTML не может быть проанализирован с помощью регулярных выражений на основе конечного автомата . Из-за иерархического построения XML / HTML вам необходимо использовать автомат с нажатием и манипулировать грамматикой LALR с помощью такого инструмента, как YACC .

realLife © ® ™ повседневный инструмент в оболочке :

Вы можете использовать один из следующих вариантов:

xmllint часто устанавливается по умолчанию с libxml2, xpath1 (установите флажок my wrapper , чтобы иметь вывод строки с разделителями

xmlstarlet можно редактировать, выбирать, преобразовывать ... По умолчанию не установлено, xpath1

xpath , установленный через модуль Perl XML :: XPath, xpath1

xidel xpath3

saxon-lint мой собственный проект, обертка для библиотеки Java Saxon-HE @Michael Kay, xpath3

или вы можете использовать языки высокого уровня и соответствующие библиотеки, я думаю:

х lxml (from lxml import etree)

XML::LibXML, XML::XPath, XML::Twig::XPath, HTML::TreeBuilder::XPath

, проверьте этот пример

DOMXpath, проверьте этот пример


Проверка: Использование регулярных выражений с тегами HTML

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...