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

Question

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

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

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

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

Answer 1

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

Ну, нет.

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Answer 5

Если вы хотите иметь 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 проще, если вы являетесь владельцем контента).