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

Я бы сделал это с помощью регулярных выражений.

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

• A становится /<A[^>]*>$/
• A#someid становится /<A[^>]*id="someid"[^>]*>$/
• A.someclass становится /<A[^>]*class="[^"]*(?<= |")someclass(?= |")[^"]*"[^>]*>$/
• A > B становится /<A[^>]*><B[^>]*>$/
• A B становится /<A[^>]*>(?:<[^>]*>)*<B[^>]*>$/

И так далее. Обратите внимание, что все регулярные выражения заканчиваются на $, но не начинаются на ^; это соответствует тому, что селекторы CSS не должны совпадать с корнем документа. Также обратите внимание, что в коде сопоставления классов есть некоторые функции просмотра назад и просмотра вперед, которые необходимы, чтобы вы случайно не сопоставили «someclass-super-duper», когда вам нужен совершенно отличный класс «someclass».

Если вам нужно больше примеров, пожалуйста, дайте мне знать.

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

<x><a>Stuff goes here</a><y id="boo"><z class="bar">Content here</z></y></x>

Ваша строка состояния стека будет проходить через следующие значения в порядке ввода каждого элемента:

1. <x>
2. <x><a>
3. <x><y id="boo">
4. <x><y id="boo"><z class="bar">

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

Проблемы, на которые следует обратить внимание:

• Двойные кавычки внутри атрибутов. Чтобы обойти это, примените кодировку объекта html к значениям атрибутов при создании регулярного выражения и к значениям атрибутов при создании строки состояния стека.

• Порядок атрибутов. При построении как регулярного выражения, так и строки состояния используйте некоторый канонический порядок атрибутов (проще всего в алфавитном порядке). В противном случае вы можете обнаружить, что ваше регулярное выражение для селектора a#someid.someclass, которое ожидает <a id="someid" class="someclass">, к сожалению, терпит неудачу, когда ваш синтаксический анализатор переходит в <a class="someclass" id="someid">.

• Чувствительность к регистру. Согласно HTML-спецификации, класс и Атрибуты id учитывают регистр (обратите внимание на маркер «CS» в соответствующих разделах). Таким образом, вы должны использовать сопоставление регулярных выражений с учетом регистра. Однако в HTML имена элементов не чувствительны к регистру, хотя они и представлены в XML. Если вы хотите сопоставление имен элементов, подобное HTML, без учета регистра, то канонизируйте имена элементов либо в верхнем, либо в нижнем регистре как в регулярном выражении селектора, так и в строке стека состояния.

• Дополнительная магия необходима для работы с шаблонами селекторов, которые предполагают наличие или отсутствие родственных элементов, а именно A:first-child и A + B. Вы можете сделать это, добавив к тегу специальный атрибут, содержащий имя непосредственно предшествующего тега, или "", если этот тег является первым дочерним. Также есть общий селектор родственных элементов, A ~ B; Я не совсем уверен, как справиться с этим.

РЕДАКТИРОВАНИЕ. Если вам не нравится хакерство с использованием регулярных выражений, вы все равно можете использовать этот подход для решения проблемы, только используя свою собственную конечную машину вместо механизма регулярных выражений. В частности, селектор CSS может быть реализован как недетерминированный конечный автомат, что является пугающим -звучащий термин, но на практике означает следующее:

1. Может быть более одного возможного перехода из любого заданного состояния
2. Машина пробует один из них, и если это не срабатывает, то отступает и пробует другой.
3. Самый простой способ реализовать это - сохранить стек для машины, в который вы вставляете каждый раз, когда следуете по пути, и извлекаете из него всякий раз, когда вам нужно вернуться. Это сводится к тому же, что и при поиске в глубину.

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

Посетите nokogiri. С их страницы:

Nokogiri — это парсер HTML, XML, SAX и Reader. Среди множества функций Nokogiri — возможность поиска документов с помощью селекторов XPath или CSS3».

Это на Ruby, но вы сказали, что вам нужен алгоритм, а Ruby отлично подходит для чтения. Или просто вызовите его из того, над чем вы работаете.

Что делает браузер для создания DOM из потока? Я предполагаю, что в этом и заключается ответ на ваш вопрос, потому что он должен хранить обнаруженные элементы в форме, которая облегчает запрос селектора CSS. Если вы можете позволить себе прочитать исходный код парсера браузера с открытым исходным кодом, я думаю, вы можете использовать его повторно.

Я бы не стал так делать, честно. Скорее я бы повторно использовал существующий парсер на основе SAX (возможно, вы перепишите другой с помощью perl), и это пройдет по всей строке. Когда обработчики срабатывают, используйте их для создания в памяти базы данных для элементов. Создайте виртуальную «таблицу» для каждого элемента с его #number [для ссылок] , tagName, родительским #number, next #number и его смещением символа открывающего тега в исходной материнской строке. Кроме того, создайте таблицу для каждого найденного атрибута и заполните ее записью для каждого тега со значением этого атрибута.

Теперь все о процессе создания базы данных, таблиц и индексов.