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

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

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

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

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

или:

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

или:

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

или:

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

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

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

EDIT: после прочтения первого ответа я подумал, что должен уточнить: я ищу "перевод", который также кратко объясняется в понятия, которые он пытается перевести: в конце ответа читатель должен иметь приблизительное представление - например - о том, что означают "обычный язык" и "контекстно-свободная грамматика"...

8 94
regex language-agnostic

8 ответов:

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

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

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

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

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

92

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

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

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

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

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

хорошая причина не сопоставлять 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 намного проще, чем большинство людей понимают.

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

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

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

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

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

потому что 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. Это потому, что они не могут сказать: "Хорошо, теперь я спустился во второй из двух дивов, поэтому следующий div close, который я вижу, возвращает меня обратно, а тот, который после этого, является закрытым тегом для первого". Программисты обычно отвечают, разрабатывая специальные регистры для конкретной ситуации, которые затем ломаются, как только больше тегов вводится внутри foo и должны быть unsnarled по огромной цене во времени и разочарования. Вот почему люди злятся на целое вещь.

17

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

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

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

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

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

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

8

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

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

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"");
    }
    ";
}
6

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

<price>10.65</price>

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

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

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

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

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

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

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

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

3

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

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

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

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

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

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

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

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

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

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

2