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

Я каждый день вижу вопросы, в которых спрашивают, как разобрать или извлечь что-то из некоторой HTML-строки, и первым ответом / комментарием всегда будет «Не используйте RegEx для синтаксического анализа HTML, чтобы не почувствовать гнев!» (последняя часть иногда опускается).

Меня это сбивает с толку, я всегда думал, что в целом лучший способ разобрать любую сложную строку - использовать регулярное выражение. Так как же работает парсер HTML? Разве для анализа не используются регулярные выражения.

Одним из конкретных аргументов в пользу использования регулярного выражения является то, что не всегда есть альтернатива синтаксического анализа (например, JavaScript, где DOMDocument не является универсально доступным вариантом). Например, jQuery отлично справляется с использованием регулярного выражения для преобразования строки HTML в узлы DOM.

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

Обычно с помощью токенизатора. В проекте спецификации HTML5 есть обширный алгоритм для обработки «реального HTML».

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

Ну нет.

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

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

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

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

Хорошо, этого достаточно для HTML? К сожалению нет. Может быть, для супер-пупер-проверенного XML, на самом деле, в котором все теги всегда идеально выстраиваются в линию. В реальном HTML вы можете легко найти такие фрагменты, как <b><i>wow!</b></i>. Очевидно, что это не гнездо, поэтому для правильного анализа стек просто недостаточно мощный.

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

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

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

Регулярные выражения - это лишь одна из форм синтаксического анализатора. Честно говоря, анализатор HTML будет значительно сложнее, чем может быть выражен в регулярных выражениях, с использованием рекурсивного спуска , предсказания и нескольких других методов для правильной интерпретации текста. Если вы действительно хотите вникнуть в это, вы можете попробовать lex & yacc и аналогичные инструменты.

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

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

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

Причина в том, что это правильный HTML:

<ul>
<li>One
<li>Two
<li>Three
</ul>

Но так это:

<ul>
<li>One</li>
<li>Two</li>
<li>Three</li>
</ul>

Если вас устраивает «90% -ное решение»: тогда можно использовать XML-анализатор для загрузки документа. Или с помощью Regex (хотя xml проще, если вы тогда являетесь мастером содержимого).