Сосредоточьтесь на этом:

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

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

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

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

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

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

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

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

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

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

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

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

  .*?

  может быть смелой попыткой найти главный заголовок, но он может найти:

  Или даже:

Последний момент является самым важным:

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

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

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

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

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

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

Поскольку HTML может иметь неограниченное nested расположение и regex не может справиться с этим, потому что он не может отслеживать историю того, с чем он спустился и вышел из него.

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

 
Hi there! 
Bye! 

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

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

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

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

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

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

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

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

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

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

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

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

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

 10.65 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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