Как синтаксические анализы HTML работают, если они не используют regexp?

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

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

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

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

Ну, нет.

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

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

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

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

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

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

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

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

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