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

Question

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

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

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

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

или же:

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

или же:

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

или же:

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

• Действительный HTML сложнее / сложнее, чем вы думаете.
• Существует много типов "допустимого" HTML - то, что допустимо в HTML, например, недопустимо в 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 может быть уместным, можно найти в блоге Джеффа Этвуда: Parsing Html The Cthulhu Way.

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

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

Учитывая несколько из этих условий:

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

Грамматика - это формальное определение того, куда могут идти слова. Например, прилагательные предшествуют существительным 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"");
    }
    ";
}

Answer 7

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

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

<price>10.65</price>

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

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

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

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

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

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

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

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

Answer 8

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

теория:

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

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

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

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

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

xpath устанавливается через модуль perl XML:: XPath, xpath1

xidel xpath3

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

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

питона lxml (from lxml import etree)

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

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

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

---

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

Answer 9

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

Есть несколько отличных ресурсов о том, что такое конечный автомат, но короче говоря, основополагающая статья в области компьютерных наук доказала, что базовая грамматика регулярных выражений (стандартные, используемые grep, а не расширенные, такие как PCRE) всегда могут быть манипулируют в конечный автомат, то есть «машину», в которой вы всегда находитесь в коробке и имеете ограниченное количество способов перейти к следующей коробке. Короче говоря, вы всегда можете сказать, что вам нужно сделать дальше, просто посмотрев на текущего персонажа. (И да, даже когда речь идет о таких вещах, как «сопоставить не менее 4, но не более 5 раз», вы все равно можете создать такую ​​машину) (я должен отметить, что машина, которую я здесь описываю, технически является всего лишь подтип конечных автоматов, но он может реализовать любой другой подтип, так что ...)

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

Так что же такого хорошего в стандартном регулярном выражении? Ну, любое данное регулярное выражение может соответствовать строке длины N не более чем за O(N) раз (это означает, что удвоение длины вашего ввода удваивает время, которое требуется: оно ничего не говорит о скорости для данного ввода) (конечно , некоторые из них быстрее: регулярное выражение * может соответствовать в O(1), что означает константа, время). Причина проста: помните, поскольку в системе есть только несколько путей из каждого состояния, вы никогда не «возвращаетесь», и вам нужно только один раз проверить каждый символ. Это означает, что даже если я передам вам 100-гигабайтный файл, вы все равно сможете быстро его обработать: и это здорово!

Теперь довольно ясно, почему вы не можете использовать такую ​​машину для синтаксического анализа произвольного XML: у вас может быть бесконечное количество тегов в тегах, а для правильного синтаксического анализа вам потребуется бесконечное количество состояний. Но, если вы разрешаете рекурсивные замены, PCRE завершается по Тьюрингу: поэтому он может полностью анализировать HTML! Даже если вы этого не сделаете, PCRE может анализировать любую контекстно-свободную грамматику, включая XML. Так что ответ - «да, можно». Теперь это может занять экспоненциальное время (вы не можете использовать наш аккуратный конечный автомат, поэтому вам нужно использовать большой причудливый синтаксический анализатор, который может перематывать назад, а это означает, что созданное выражение займет века в большом файле), но все же . Возможный.

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

А XML, конечно, сложен. Довольно легко найти примеры в некоторых других ответах: вы не можете сопоставить материалы в полях комментариев и т. Д. Представление всего этого на языке программирования требует работы: и это с учетом преимуществ переменных и функций! PCRE, несмотря на все их особенности, не могут приблизиться к этому. Любая ручная реализация будет содержать ошибки: сканировать капли метасимволов для проверки соответствия скобкам сложно, и вы не можете комментировать свой код. Было бы проще определить метаязык и скомпилировать его до регулярного выражения: и в этот момент вы могли бы просто взять язык, на котором вы написали свой мета-компилятор, и написать синтаксический анализатор XML. Вам будет легче, быстрее бежать и в целом лучше.

Чтобы узнать больше об этом, посетите этот сайт. Он отлично объясняет все это в терминах непрофессионала.

Answer 10

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

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

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

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

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

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

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

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

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

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