Парсер HTML на PHP без регулярных выражений с ноля?

Question

[R Z]

Прежде всего, не нужно мне кидать ссылки на расширения PHP и уж тем более на тормозную либу Simple html dom и прочие!
Я не собираюсь городить велосипеды, а только хочу получить навыки и опыт путем реализации чего-то относительно простого.
Многие утверждают, что писать сложные парсеры на регэкспах - извращение. Я полностью согласен с теми людьми. И поэтому хочу понять как, к примеру, браузере анализируют код html, какие алгоритмы испольщуют и т.д. не на регэкспах ведь они это делают.

Какая последовательность анализа html страницы, средствами php, должна быть осущестлена? К примеру, получили мы страницу, очистили ее от всякого мусора, такого как лишние пробелы, переносы.... А дальше что делать? Страницы могут быть огромными и не хотелось бы держать их в памяти. Представим, что полученная страница валидная и мы записали ее в файл и т.к. само по себе содержимое уже имеет иерархию (html теги) то по какому алгоритму осуществлять поиск того или иного тега и все его содержимое? Или все это как то по другому должно работать? Если да, то как? Какие подходы и алгоритмы применять, куда копать?

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

Answer 1

[Rsa97]

Для начала нужно реализовать лексер - модуль, принимающий на вход текст на HTML и выдающий список лексем с их параметрами, например

<div id="test">
Привет
<div>

может быть превращено в

OPEN_TAG_START, DIV, ID, EQUALS, STRING(test), TAG_END, TEXT(Привет), 
CLOSE_TAG_START, DIV, TAG_END

Затем второй модуль, парсер, по полученным лексемам строит синтаксическое дерево. Это гораздо более сложная часть, особенно если учесть, что для HTML необходимо как-то обрабатывать некорректные варианты, наподобие <b><i>Тест</b></i>.
В результате должно получиться DOM-дерево, скомпилированное из исходного HTML.
Начать вникать в компиляторы можно по Книге красного дракона

Comments

[R Z]

Тот же самый лексер нужно писать чтением файла как бинарный и посимвольным сопоставлением?

[Rsa97]

sergey_zhuravlev_89: А как угодно. Чаще всего реализуется смесь конечного автомата и простого сравнения строк. Для скорости файл считывается в оперативку и разбирается простым перемещением указателя на текущую точку разбора.

[R Z]

Rsa97: а вот после разбора на лексемы, как потом все это записать обратно в файл? Я имею в виду, какая лучше структура данных подойлет, чтобы потом уже по этому файлу искать нужные узлы?

[Rsa97]

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

[R Z]

Rsa97: спасибо. Буду копать, смотреть

Answer 2

[Максим Тимофеев]

как, к примеру, браузере анализируют код html, какие алгоритмы испольщуют и т.д. не на регэкспах ведь они это делают.

Конечно же нет. И конечно же не на php это делают. Но это лирика, все что Вам надо - уметь читать и эта ссылка:
https://habrahabr.ru/post/174057/

ПС: Боюсь что разобравшись глубоко в теме, вы напишите все тот же SimpleHtmlDom. Громоздкий и тормозной. Если посмотреть на современные браузеры - увидите, что они кушают намного больше оперативки, чем замечательная SimpleHtmlDom.

Comments

[R Z]

Не робят там ссылки

[Максим Тимофеев]

sergey_zhuravlev_89: Отлично все работает

[R Z]

Я уже написал для себя библиотеку (на регэкспах) , которая в 30 раз быстрее simple html dom и некорректный код разбирает куда лучше. Я не зочу останавливаться, хочу по человечески ошупать то, как все должно работать.

Answer 3

[xmoonlight]

Представим, что полученная страница валидная и мы записали ее в файл и т.к. само по себе содержимое уже имеет иерархию (html теги) то по какому алгоритму осуществлять поиск того или иного тега и все его содержимое?

Единственный верный ответ: если структура документа древовидная - значит нахождение нужного узла - это обход такого "дерева".
Далее - мы используем знания из документации W3C для понимания всевозможных вариантов открытия и закрытия тега - "узла". Это будут наши виртуальные "скобки".

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

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

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