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

402

Одна ошибка, которую я вижу, что люди делают снова и снова, это попытка разобрать 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>

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

html xml regex Чес. Owens
источник
14
Веб-браузеры разбираются в подобных беспорядках миллионы раз в секунду, не может ли кто-нибудь создать класс анализатора веб-страниц для нас, простых смертных?
Джон Уинстанли
24
Джон, у них есть. В Perl есть много HTML :: Parser, HTML :: TreeBuilder и т. Д. Существует почти наверняка один для вашего языка.
час. Оуэнс
12
Лучший ответ: stackoverflow.com/a/1732454/135078 (Осторожно, Зальго)
Келли С. Френч
3
Есть хорошее объяснение, почему [вы не можете разобрать [X] HTML с регулярным выражением] [1] [1]: stackoverflow.com/a/1732454/468725
Павел P
4
Вот хорошее объяснение того, как вы, конечно, можете анализировать HTML с шаблонами , а также почему вы, вероятно, этого не хотите.
tchrist

Ответы:

260

Вот забавный действительный 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>

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

Удачи в борьбе с этим!

РЕДАКТИРОВАТЬ (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/>
bobince
источник
6
XML один? Там есть несколько разных конструкций, что неприятно? Внутреннее подмножество DTD? Это определяет новую & сущность; называется 'y', содержит последовательность ']>', которая обычно, если не в кавычках, заканчивает внутреннее подмножество.
bobince
16
(Это демонстрирует, что вам необходимо иметь достаточно глубокие знания о некоторых из более эзотерических и архаичных возможностей DTD XML, чтобы правильно анализировать документ, даже если вы не анализатор DTD-валидации.)
bobince
17
Примеры HTML используют редко известную функцию: короткие ярлыки. Узнайте больше на w3.org/QA/2007/10/shorttags.html
netvope
25
Каждый раз, когда кто-то пишет HTML, как показано выше, Тим Бернерс-Ли проливает одну слезу.
Fgysin восстановить Монику
5
Мне нравится, как подсветка синтаксиса Stackoverflow не срабатывает при первом появлении "]".
GlassGhost
71

Фактически

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

не является допустимым HTML, а также не является допустимым XML.

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

Это также недопустимый 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 заключается в том, что люди обычно не понимают все правила синтаксиса правильно. Тот факт, что ваш браузер интерпретирует ваш tagoup как HTML, не означает, что вы действительно написали правильный HTML.

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

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

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

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

LordOfThePigs
источник
8
Вам не нужно бежать> как> хотя.
Джои
8
Хорошо, s / valid / существует в дикой природе / г
Chas. Оуэнс
1
На самом деле, согласно спецификации вы должны экранировать> as> так же, как вы должны экранировать <as <& и & amp; а в атрибутах «as» и «as» просто так много парсеров
LordOfThePigs
19
Спецификация не говорит, что '>' должно быть экранировано - за исключением особого случая последовательности ']]>' в содержимом. По этой причине проще всего всегда избегать '>', но это не требуется спецификацией.
bobince
8
>знак полностью действителен в html stackoverflow.com/questions/94528/…
jfs
56

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

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

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

JaredPar
источник
20

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

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

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

Антон Гоголев
источник
Я думаю,
обратные ссылки
1
@RishulMatta: как? У вас есть только ограниченное количество обратных ссылок, и обратите внимание, что вам нужно поменять теги ... Более того, строгое определение регулярных выражений не допускает обратных ссылок.
Виллем Ван Онсем
.NET допускает балансировку выражений, которые всплывают и выдвигаются и теоретически могут использоваться для сопоставления иерархии. Но это все еще плохая идея.
Авель
9

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

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

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

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

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

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

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

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

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

Исаак Рабинович
источник
3
Это не так сложно, как C ++, хотя.
Коул Джонсон
6
@Cole "Cole9" Джонсон Я бы тоже не использовал RE для разбора C ++.
Исаак Рабинович
2
Если XML является синхротроном, C ++ был бы Большим адронным коллайдером.
Кевин Костлан
4

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

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

Еще немного информации из Википедии: Хомская Иерархия

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

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

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

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

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

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

Майкл Кей
источник
1

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

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

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

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

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

Erutan409
источник