Можете ли вы привести некоторые примеры того, почему трудно анализировать XML и HTML с помощью регулярных выражений?

395

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

Люди хотят обрабатывать файл как последовательность строк, но это действительно:

<tag
attr="5"
/>

Люди хотят лечить < или < тег в качестве начала тега, но такие вещи существуют в природе:

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

Люди часто хотят сопоставлять начальные теги с конечными тегами, но теги XML и HTML позволяют содержать теги (какие традиционные регулярные выражения не могут обрабатывать вообще):

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

Люди часто хотят сопоставлять содержимое документа (например, известная проблема "найти все номера телефонов на заданной странице" ), но данные могут быть помечены (даже если это выглядит нормально, если смотреть)

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

Комментарии могут содержать плохо отформатированные или неполные теги:

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

Какие еще ошибки вы знаете?

  • 13
    Веб-браузеры разбираются в подобных беспорядках миллионы раз в секунду, не может ли кто-нибудь создать класс анализатора веб-страниц для нас, простых смертных?
  • 24
    Джон, у них есть. В Perl есть много HTML :: Parser, HTML :: TreeBuilder и т. Д. Существует почти наверняка один для вашего языка.
Показать ещё 5 комментариев
Теги:

12 ответов

247
Лучший ответ

Вот вам полезный XML-код:

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

И этот маленький пучок радости действителен 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>

Не говоря уже обо всех зависящих от браузера синтаксических разборах для недопустимых конструкций.

Удачи с помощью регулярных выражений против этого!

EDIT (Jörg W Mittag): Вот еще один хороший фрагмент хорошо сформированного, действительного HTML 4.01:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
  "http://www.w3.org/TR/html4/strict.dtd"> 
<HTML/
  <HEAD/
    <TITLE/>/
    <P/>
  • 0
    Я понятия не имею, что происходит в первом примере, не могли бы вы добавить пояснительный текст?
  • 6
    XML один? Там есть несколько разных конструкций, что неприятно? Внутреннее подмножество DTD? Это определяет новую & сущность; называется 'y' и содержит последовательность ']>', которая обычно, если не в кавычках, заканчивает внутреннее подмножество.
Показать ещё 7 комментариев
61

На самом деле

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

недействителен HTML и не является допустимым XML.

Недействителен XML, потому что '<' и ' > ' не являются допустимыми символами внутри строк атрибутов. Они должны быть экранированы с использованием соответствующих объектов XML & lt; и >

Недопустимый HTML либо потому, что короткая закрывающая форма не разрешена в HTML (но правильная в XML и XHTML). Тег 'img' также является неявным закрытым тегом в соответствии со спецификацией HTML 4.01. Это означает, что ручное закрытие на самом деле неверно и эквивалентно закрытию любого другого тега дважды.

Правильная версия в HTML

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

и правильная версия в XHTML и XML

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

Следующий приведенный ниже пример также недействителен

<
tag
attr="5"
/>

Это неверный HTML или XML. Имя тега должно быть прямо за "<", хотя атрибуты и закрытие " > " могут быть там, где они хотят. Таким образом, действительный XML на самом деле

<tag
attr="5"
/>

И вот еще один более забавный: вы можете на самом деле выбрать либо "или", как свой атрибут, указывающий символ

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

Все остальные причины, которые были опубликованы, являются правильными, но самая большая проблема с разбором HTML заключается в том, что люди обычно не понимают все правила синтаксиса правильно. Тот факт, что ваш браузер интерпретирует ваши метки как HTML, не означает, что вы действительно написали допустимый HTML.

Изменить: И даже stackoverflow.com согласен со мной относительно определения действительного и недействительного. Ваш недопустимый XML/HTML не подсвечивается, а моя исправленная версия.

В принципе, XML не обрабатывается регулярными выражениями. Но нет оснований для этого. Для каждого языка существует множество XML-парсеров. У вас есть выбор между SAX-парсерами, DOM-парсерами и парсерами Pull. Все они гарантированно будут намного быстрее, чем синтаксический анализ с регулярным выражением, и затем вы можете использовать классные технологии, такие как XPath или XSLT, в результирующем дереве DOM.

Мой ответ поэтому: не только синтаксический анализ XML с регулярными выражениями, но и плохая идея. Просто используйте один из миллионов существующих синтаксических анализаторов XML и воспользуйтесь всеми расширенными функциями XML.

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

  • 8
    Вам не нужно бежать> как> хотя.
  • 8
    Хорошо, s / valid / существует в дикой природе / г
Показать ещё 4 комментария
50

Я написал всю запись в блоге на эту тему: Ограничения регулярного выражения

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

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

19

В ваш список не входит одно свойство: атрибуты могут появляться в любом порядке, поэтому, если ваше регулярное выражение ищет ссылку с href "foo" и классом "bar", они могут поступать в любом порядке и иметь любые количество других вещей между ними.

  • 0
    Ах, да, это был даже вопрос, который побудил меня задать этот вопрос (первая ссылка).
15

Это зависит от того, что вы подразумеваете под "разбором". Вообще говоря, XML не может быть проанализирован с использованием регулярного выражения, поскольку грамматика XML отнюдь не является регулярной. Проще говоря, регулярные выражения не могут рассчитывать (ну, регулярные выражения Perl могли бы действительно подсчитывать вещи), поэтому вы не можете балансировать теги open-close.

  • 0
    я думаю, обратные ссылки могут решить проблему открытых и закрытых тегов
  • 1
    @RishulMatta: как? У вас есть только ограниченное количество обратных ссылок, и обратите внимание, что вам нужно поменять теги ... Более того, строгое определение регулярных выражений не допускает обратных ссылок.
Показать ещё 1 комментарий
9

Люди действительно ошибаются, используя регулярное выражение, или это просто достаточно хорошо для задачи, которую они пытаются достичь?

Я полностью согласен с тем, что разбор html и xml с использованием регулярного выражения невозможен, как ответили другие люди.

Однако, если ваше требование состоит не в том, чтобы разобрать html/xml, а просто получить один маленький бит данных в "известном хорошем" бите html/xml, то, возможно, регулярное выражение или даже еще более простая "подстрока" достаточно хорошо.

  • 7
    Определите «достаточно хорошо». Неизбежно, простое регулярное выражение не будет работать. Не соответствует ли что-то или совпадает с чем-то, что не должно быть ошибкой? Если это так, то использование регулярных выражений является ошибкой. HTML и XML парсеры не сложны в использовании. Избегать изучения их - ложная экономика.
  • 1
    хорошо, определите «достаточно хорошо». Допустим, у меня есть веб-страница, которая сообщает мне IP-адрес клиента. Это все, что он делает. Теперь мне нужно написать приложение для клиентского компьютера, которое сообщит мне его IP-адрес. Я захожу на этот сайт, ищу IP-адрес и возвращаю его. Разбор HTML не нужен!
Показать ещё 4 комментария
6

Я соблазн сказать "не изобретать колесо". Кроме того, что XML - действительно очень сложный формат. Поэтому, может быть, я должен сказать "не изобретать синхротрон".

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

Потому что синтаксический анализ XML затруднен. Любые усилия, которые вы сохраняете, не имея необходимости учиться использовать библиотеку синтаксического анализа XML, будут более чем компенсированы количеством творческой работы и ошибкой, которую вам придется делать. Ради вас, Google "библиотека XML" и использовать кого-то еще.

  • 3
    Это не так сложно, как в C ++.
  • 6
    @Cole "Cole9" Джонсон Я бы тоже не использовал RE для разбора C ++.
Показать ещё 1 комментарий
6

Обычно люди по умолчанию используют жадные шаблоны, что довольно часто приводит к непродуманному. * размывание больших кусков файла в максимально возможное foo > . * </foo> .

  • 2
    Наряду с ленивостью повторения с помощью .*?< , Вы можете исправить это, используя отрицательный класс символов, такой как [^<]*< . (Отказ от ответственности: очевидно, что это еще не надежно, что является вопросом вопроса.)
4

Я верю, что этот классический имеет информацию, которую вы ищете. Вы можете найти точку в одном из комментариев:

Я думаю, что недостаток в том, что HTML - это грамматика типа Хомского типа 2 (контекстная свободная грамматика), а RegEx - грамматика Хомского типа 3 (обычная выражение). Поскольку грамматика типа 2 существенно сложнее, чем грамматика 3-го типа - вы не можете надеяться сделать эту работу. Но многие попробует, некоторые будут претендовать на успех, а другие найдут ошибку и полностью запутайте вас.

Дополнительная информация из Википедии: Иерархия Хомского

  • 6
    «Регулярное выражение» не имеет точно такого же значения в обсуждениях формальной грамматики, как здесь. Большинство существующих движков регулярных выражений являются более мощными, чем грамматики Хомского типа 3 (например, сопоставление без жадности, обратные ссылки). Некоторые движки регулярных выражений (например, Perl) завершены по Тьюрингу. Это правда, что даже это плохие инструменты для разбора HTML, но этот часто цитируемый аргумент не является причиной, почему.
3

Я думаю, что проблемы сводятся к следующему:

  • Регулярное выражение почти всегда неверно. Есть законные входы, которые он не сможет правильно сопоставить. Если вы достаточно усердно работаете, вы можете сделать это на 99% правильным, или 99,999%, но сделать его на 100% правильным почти невозможно, хотя бы из-за странных вещей, которые позволяет XML с помощью сущностей.

  • Если регулярное выражение неверно, даже для 0.00001% входов, то у вас есть проблема с безопасностью, потому что кто-то может обнаружить один вход, который нарушит ваше приложение.

  • Если регулярное выражение достаточно корректно, чтобы охватить 99,99% случаев, то оно будет полностью нечитаемым и недостижимым.

  • Очень вероятно, что регулярное выражение будет работать очень плохо на входных файлах среднего размера. Моя первая встреча с XML заключалась в замене Perl script, который (неправильно) анализировал входящие XML-документы с помощью правильного синтаксического анализа XML, и мы заменили не только 300 строк нечитаемого кода на 100 строк, которые могли бы понять все, но мы улучшили пользователь время отклика от 10 секунд до 0,1 секунды.

1

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

1

Вообще говоря, XML не может быть проанализирован с использованием regex, поскольку грамматика XML отнюдь не является регулярной. Проще говоря, регулярные выражения не могут рассчитывать (ну, регулярные выражения Perl могли бы действительно подсчитывать вещи), поэтому вы не можете балансировать теги open-close.

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

Здесь Я показал пример регулярного выражения, чтобы избежать синтаксического анализа ошибок в первом сообщении.

  • 0
    Во-первых, рекурсивные регулярные выражения не являются регулярными выражениями (если вы посмотрите в скобках, вы увидите, что я признаю, что регулярные выражения Perl, которые являются рекурсивными, могут считать вещи, необходимые для обработки HTML). Во-вторых, ваш пример для XHTML или XML, который хорошо сформирован. HTML не очень хорошо сформирован. В-третьих, вы должны спросить себя: проще ли расширять и поддерживать синтаксический анализатор, написанный на рекурсивном языке регулярных выражений или языке программирования общего назначения.
  • 0
    В-четвертых, даже ваш пример тривиально испорчен, оставаясь при этом действительным XML. Добавьте один пробел между content_block и id, и это не удастся. Я уверен, что если бы я потратил еще несколько минут, я обнаружил бы еще одну структурную ошибку в вашем коде. Это просто не очень хорошая идея.

Ещё вопросы

Сообщество Overcoder
Наверх
Меню