Как стать автором
Обновить

Искусство парсинга или DOM своими руками

C++ *XML *Алгоритмы *HTML *
Tutorial
Привет, Хабр! Недавно я задался идеей создать простой язык разметки наподобие markdown, который отлично подходил бы для моих задач, а именно — быстрого написания лекций с форматированием и возможностью вставки математических формул «на лету», с применением одной лишь клавиатуры. Чтобы перевести текст, написанный в таком формате, в более понятную форму, например, документ LibreOffice Writer, нужен синтаксический анализатор, проще говоря — парсер. Поскольку я привык делать велосипеды, то направился в поисковые системы с запросами «parser example», «html to DOM», «how to parse html» и др. К моему разочарованию, на всех найденных ресурсах либо приводились элементарные примеры типа калькулятора Страуструпа с рекурсивным спуском, либо использовались готовые решения, такие как flex, bison, llvm и yacc. Библиотек, предназначенных для парсинга строго определённых языков, нашлось ещё больше (gumbo, jsoup, rapidjson, инструменты Qt и др.) Ни то, ни другое не входило в мои планы по написанию парсера своей разметки на C++ с использованием лишь стандартной библиотеки, поэтому моим источником знаний об искусстве парсинга вместо электронных ресурсов стали методички технических институтов. О том, как взять текст и построить из него AST (абстрактное синтаксическое дерево), о некоторых подводных камнях, на которые я натыкался в процессе, о возможных ошибках я сегодня и расскажу.

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

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

  1. Лексический разбор текста на токены — небольшие куски этого текста, имеющие определённое синтаксическое значение.
  2. Синтаксический разбор — построение из токенов на основе их значений абстрактного синтаксического дерева (AST — abstract syntax tree), или объектной модели документа (DOM — document object model).

Но давайте по порядку. Перед тем, как открывать свою любимую IDE и писать код, нужно разработать грамматику будущего языка. Из формальных контекстно-свободных грамматик самые известные — форма Бэкуса-Наура (БНФ) и расширенная форма Бэкуса-Наура. Я использовал их симбиоз, взяв лучшее от обеих форм. Любое выражение можно определить через другие выражения так:

<сумма> = <выражение_1> <знак_плюс> <выражение_2>

Здесь одно выражение определено через три других, следующих одно за другим. Их, в свою очередь, тоже необходимо представить через «третьи» выражения и т.д.

Когда же остановиться?

Описание синтаксиса любого языка в формальных грамматиках состоит из двух типов лексем: терминалов и нетерминалов. Нетерминалы — выражения, требующие определения:

<выражение_1> = <число> (<знак_умножения> | <знак_деления>) <число>

Терминалы самодостаточны, их не нужно определять. Выше приведённые примеры можно записать так:

<сумма> = <выражение_1> "+" <выражение_2>
<выражение_1> = <число> ("*" | "/") <число>

где "+", "*", "/" — терминалы.
Выделить из грамматики терминалы нужно сразу, можно даже выписать их в отдельный список внизу основных определений, — они пригодятся позже.

Полное описание БНФ доступно в Википедии здесь и здесь. Составление грамматики языка — важная стадия создания языка, не терпящая легкомыслия. Одна ошибка в ней может привести к полностью нерабочему коду, который придётся переписывать с нуля. Поэтому, прежде чем делать следующий шаг, убедитесь, что в составленной грамматике не осталось спорных моментов. Если у вас два монитора, будет удобно на всё оставшееся время работы занять документом с грамматикой один монитор, чтобы иметь возможность быстро перемещаться глазами на него, когда будете кодить. Поверьте, так придётся делать постоянно. Вот составленная мной грамматика HTML5 в форме БНФ:

(* document *)
<document> = {<document_part>} <END>
<document_part> = <block> | <empty_tag> | <comment> | <macro_tag> | <text>
<block> = <opening_tag> {<document_part>} <closing_tag>

(* tags *)
<opening_tag> = "<" {<ws>} <block_tag_name> [<attributes_list>] {<ws>} ">"
<closing_tag> = "<" "/" {<ws>} <block_tag_name> {<ws>} ">"
<empty_tag> = "<" "!" {<ws>} <empty_tag_name> [<attributes_list] {<ws>} ["/"] ">"
<comment> = "<" "!" "--" <comment_text> "--" ">"
<macro_tag> = "<" "?" <macro_text> "?" ">"
<block_tag_name> =  "a" | "abbr" | "address" | "article" | "aside" | "audio" | "b" | "bdo" | "blockquote" | "body" | "button" | "canvas" | "caption" | "cite" | "code" | "colgroup" | "data" | "datalist" | "dd" | "del" | "details" | "dfn" | "dialog" | "div" | "dl" | "dt" | "em" | "fieldset" | "figcaption" | "figure" | "footer" | "form" | "h1" | "h2" | "h3" | "h4" | "h5" | "h6" | "head" | "header" | "html" | "i" | "iframe" | "ins" | "kbd" | "label" | "legend" | "li" | "main" | "map" | "mark" | "meter" | "nav" | "noscript" | "object" | "ol" | "optgroup" | "option" | "output" | "p" | "picture" | "pre" | "progress" | "q" | "ruby" | "rb" | "rt" | "rtc" | "rp" | "s" | "samp" | "script" | "section" | "select" | "small" | "span" | "strong" | "style" | "sub" | "summary" | "sup" | "table" | "tbody" | "td" | "template" | "textarea" | "tfoot" | "th" | "thead" | "time" | "title" | "tr" | "track" | "u" | "ul" | "var" | "video"
<empty_tag_name> = "area" | "base" | "br" | "col" | "embed" | "hr" | "img" | "input" | "link" | "menuitem" | "meta" | "param" | "source" | "track" | "wbr"

(* attributes *)
<attributes_list> = <ws> {<ws>} <attribute> {<ws> {<ws>} <attribute>}
<attribute> = <empty_attribute> | <unquoted_attribute> | <single_quoted_attribute> | <double_quoted_attribute>
<empty_attribute> = <attribute_name>
<unquoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} <unquoted_attribute_value>
<single_quoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} "'" <single_quoted_attribute_value> "'"
<double_quoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} "\"" <double_quoted_attribute_value> "\""
<attribute_name> = (<letter> | <digit>) {<letter> | <digit>}

{* attribute values *)
<unquoted_attribute_value> = /^[\s"'=<>/]/ {/^[\s"'=<>/]/}
<single_quoted_attribute_value> = /^[']/ {/^[']/}
<double_quoted_attribute_value> = /^["]/ {/^["]/}

(* nonterminals *)
<text> = {/^[<>]/}
<comment_text> = ...
<macro_text> = ...
<letter> = /[a-zA-Z]/
<digit> = /[0-9]/
<ws> = " " | "\t" | "\n"

(* terminals *)
"<", ">", "/", "!", "?", " ", "\t", "\n"

Когда грамматика готова, можно приступать к лексическому анализатору (другое название лексического разборщика, т.к. помимо разбора, он выявляет в документе лексические ошибки). На первый взгляд всё просто: поглощать символы, записывать в буфер и при обнаружении ключевого терминала определять полученную лексему как токен с определённым типом, так? Да, только тип токена здесь имеет большее значение, чем символ. Сейчас поясню. Само собой, процедура disassemble(ifsteam &file) должна содержать цикл, читающий по одному символу из входного потока и отправляющий его в процедуру process(const char &c), где этот символ обрабатывается. Кажется, что процедуре process нужно содержать switch©, где на каждый ключевой символ определены свои функции в зависимости от текущего типа токена. На самом деле всё наоборот: лучше с помощью switch проверять именно тип токена, а функции определять для символов. Более того, текущий токен чаще всего имеет неопределённый тип, один из многих. Например, после открытия угловой скобки может идти: открывающий, закрывающий, пустой теги, а также комментарий в стиле HTML или макро тег (сценарий PHP, заключённый в "<?… ?>". И для всех таких объединений нужен свой case. Как такое реализовать? С помощью битовых флагов. Пусть задано конечное число типов токена (чем больше — тем лучше, так как задача лексического анализатора — оставить как можно меньше работы синтаксическому). Для каждого типа задано уникальное число степени двойки (1, 2, 4, 8 и т.д). Тогда в двоичном формате они будут выглядеть так: 0001, 0010, 0100 и т.д., и при побитовом сложении любого числа любых типов получится уникальное число. Если текстовое описание сложно для понимания, приведу код. Вот определение типов:

enum Token_type {
    END = 1, TEXT = 2,
    OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO_TAG = 64,
    ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBLE_QUOTED_ATTRIBUTE_VALUE = 1024
};

Урезанная процедура process:

void Lexer::process (const char &c) {
    switch (curr_token_type) {
    case END: {
        throw string("unexpected ending!");
    break; }
    case TEXT: {
        if (c == '>')
            throw string("unexpected symbol: \">\"!");

        else if (c == '<') {
            if (!buffer.empty()) {
                add(buffer, TEXT);
                buffer.clear();
            }
            curr_token_type = OPENING_BLOCK_TAG_NAME | CLOSING_BLOCK_TAG_NAME | EMPTY_TAG_NAME | COMMENT | MACRO_TAG;

        } else
            buffer.push_back(c);
    break; }
    case OPENING_BLOCK_TAG_NAME: {
        throw string("error!");
    break; }
    case CLOSING_BLOCK_TAG_NAME: {
        if (c == '<')
            throw string("unexpected symbol: \"<\"!");
        else if (c == '/')
            throw string("unexpected symbol: \"<\"!");
        else if (c == '!')
            throw string("unexpected symbol: \"!\"!");
        else if (c == '?')
            throw string("unexpected symbol: \"?\"!");
        else if (c == ' ')
            throw string("unexpected symbol: \" \"!");
        else if (c == '\t')
            throw string("unexpected symbol: \"\\t\"!");
        else if (c == '\n')
            throw string("unexpected symbol: \"\\n\"!");
        else if (c == '>') {
            for (unsigned int i(0); i < BLOCK_TAGS_COUNT; i++)
                if (buffer == block_tags[i]) {
                    add(buffer, CLOSING_BLOCK_TAG_NAME);
                    buffer.clear();
                    curr_token_type = TEXT;
                    break;
                }
        } else
            buffer.push_back(c);
    break; }
    case EMPTY_TAG_NAME: {
        throw string("error!");
    break; }
    case COMMENT: {
        ...
    break; }
    case MACRO_TAG: {
        ...
    break; }
    case OPENING_BLOCK_TAG_NAME | CLOSING_BLOCK_TAG_NAME | EMPTY_TAG_NAME | COMMENT | MACRO_TAG: {
        ...
    break; }
    case EMPTY_TAG_NAME | COMMENT: {
        ...
    break; }
    case ATTRIBUTE_NAME: {
        ...
    break; }
    case ATTRIBUTE_NAME | UNQUOTED_ATTRIBUTE_VALUE | SINGLE_QUOTED_ATTRIBUTE_VALUE | DOUBLE_QUOTED_ATTRIBUTE_VALUE: {
        ...
    break; }
    case UNQUOTED_ATTRIBUTE_VALUE | SINGLE_QUOTED_ATTRIBUTE_VALUE | DOUBLE_QUOTED_ATTRIBUTE_VALUE: {
        ...
    break; }
    case UNQUOTED_ATTRIBUTE_VALUE: {
        ...
    break; }
    case SINGLE_QUOTED_ATTRIBUTE_VALUE: {
        ...
    break; }
    case DOUBLE_QUOTED_ATTRIBUTE_VALUE: {
        ...
    break; }
    }
}

Проверяем с помощью switch тип ожидаемого токена (или токенов), а внутри каждого case определяем процедуры для каждого из ключевых терминалов. Функций не так много, все выполняют простые действия: либо добавление символа к буферу, либо слив буфера в очередной токен, либо смену ожидаемого типа токена (токенов), либо выброс исключения. Определить нужную процедуру легко по написанной выше грамматике при помощи текстового редактора с возможностью поиска. Просто ищем все включения ожидаемого токена (токенов) в определения других выражений, затем включения этих выражений в «третьи» и т.д. Вот пример для открывающего тега в текстовом редакторе gedit:

ориентирование в формальной грамматике

Вначале ориентироваться в грамматике сложно, но со временем и опытом она становится не сложнее деления столбиком. А вот и процедура disassemble:

void Lexer::disassemble (ifstream &file) {
    tokens_count = 0;
    curr_token_type = 0;

    unsigned long line(1), pos(1);
    try {
        char c;
        curr_token_type = TEXT;

        while ((c = file.get()) != EOF) {
            if (c == '\n') {
                pos = 1;
                line++;
            } else
                pos++;
            process(c);
        }

        if (buffer.size() != 0) {
            if (!(curr_token_type | TEXT))
                throw string("text was expected!");
            add(buffer, TEXT);
            buffer.clear();
        }

        add("", END);
    } catch (const string &error) {
        throw string("lexer: " + to_string(line) + "," + to_string(pos) + ": " + error);
    }
}

Первому ожидаемому токену очевидно необходимо задать тип TEXT, а в конце добавить токен типа END с любым текстом (или пустой, как здесь).

Для примера я взял один из своих шаблонов HTML-документа с комментарием, добавил к нему псевдо-скрипт PHP, обработал лексером и вывел список токенов в формате "[ "<текст_токена>": <тип_токена> ]". Вот что получилось:

Сам документ
<!DOCTYPE html>
<html lang="ru">
<head>
	<meta http-equiv="content-type" content="text/html" charset="utf-8" />
	<meta name="author" content="Interquadro" />
	<meta name="description" content="" />
	<meta name="keywords" content="">
	<meta name="viewport" content="width=device-width, initial-scale=1" />
	<meta name="format-detection" content="telephone=no" />
	<meta http-equiv="x-rim-auto-match" content="telephone=none" />
	<meta name="referrer" content="no-referrer" />
	<meta name="_suburl" content="" />
	
	<title></title>
	<link rel="shortcut icon" href=".ico" />
	<link rel="stylesheet" type="text/css" href=".css" title="" />

	<!--[if lt IE 9]>
	<script src="http://html5shiv.googlecode.com/svn/trunk/html5-els.js"></script>
	<![endif]-->
</head>

<body>
	<header>
		<div id="intro">

		</div>
	</header>
	<nav>
		<ul id="nav">
			<li class="nav"><a href="#"> Главная </a></li>
			<li class="nav"><a href="#"> Обзор </a></li>
			<li class="nav"><a href=""> Помощь </a></li>
		</ul>
	</nav>

	<main id="content">
		<?php ?>
	</main>

	<footer>
		<hr />
		<small id="copyright">Copyright © 2019. Все права защищены.</small>
	</footer>
</body>

</html>


Список токенов
[ "!DOCTYPE" : EMPTY_TAG_NAME ]
[ "html" : ATTRIBUTE_NAME ]
[ "
" : TEXT ]
[ "html" : OPENING_BLOCK_TAG_NAME ]
[ "lang" : ATTRIBUTE_NAME ]
[ "ru" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
" : TEXT ]
[ "head" : OPENING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "http-equiv" : ATTRIBUTE_NAME ]
[ "content-type" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "text/html" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "charset" : ATTRIBUTE_NAME ]
[ "utf-8" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "author" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "Interquadro" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "description" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "keywords" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "viewport" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "width=device-width, initial-scale=1" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "format-detection" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "telephone=no" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "http-equiv" : ATTRIBUTE_NAME ]
[ "x-rim-auto-match" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "telephone=none" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "referrer" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "no-referrer" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "meta" : EMPTY_TAG_NAME ]
[ "name" : ATTRIBUTE_NAME ]
[ "_suburl" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "content" : ATTRIBUTE_NAME ]
[ "" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	
	" : TEXT ]
[ "title" : OPENING_BLOCK_TAG_NAME ]
[ "title" : CLOSING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "link" : EMPTY_TAG_NAME ]
[ "rel" : ATTRIBUTE_NAME ]
[ "shortcut icon" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "href" : ATTRIBUTE_NAME ]
[ ".ico" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
	" : TEXT ]
[ "link" : EMPTY_TAG_NAME ]
[ "rel" : ATTRIBUTE_NAME ]
[ "stylesheet" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "type" : ATTRIBUTE_NAME ]
[ "text/css" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "href" : ATTRIBUTE_NAME ]
[ ".css" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "title" : ATTRIBUTE_NAME ]
[ "" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "

	" : TEXT ]
[ "[if lt IE 9]>
	<script src="http://html5shiv.googlecode.com/svn/trunk/html5-els.js"></script>
	<![endif]" : COMMENT ]
[ "
" : TEXT ]
[ "head" : CLOSING_BLOCK_TAG_NAME ]
[ "

" : TEXT ]
[ "body" : OPENING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "header" : OPENING_BLOCK_TAG_NAME ]
[ "
		" : TEXT ]
[ "div" : OPENING_BLOCK_TAG_NAME ]
[ "id" : ATTRIBUTE_NAME ]
[ "intro" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "

		" : TEXT ]
[ "div" : CLOSING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "header" : CLOSING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "nav" : OPENING_BLOCK_TAG_NAME ]
[ "
		" : TEXT ]
[ "ul" : OPENING_BLOCK_TAG_NAME ]
[ "id" : ATTRIBUTE_NAME ]
[ "nav" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
			" : TEXT ]
[ "li" : OPENING_BLOCK_TAG_NAME ]
[ "class" : ATTRIBUTE_NAME ]
[ "nav" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "a" : OPENING_BLOCK_TAG_NAME ]
[ "href" : ATTRIBUTE_NAME ]
[ "#" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ " Главная " : TEXT ]
[ "a" : CLOSING_BLOCK_TAG_NAME ]
[ "li" : CLOSING_BLOCK_TAG_NAME ]
[ "
			" : TEXT ]
[ "li" : OPENING_BLOCK_TAG_NAME ]
[ "class" : ATTRIBUTE_NAME ]
[ "nav" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "a" : OPENING_BLOCK_TAG_NAME ]
[ "href" : ATTRIBUTE_NAME ]
[ "#" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ " Обзор " : TEXT ]
[ "a" : CLOSING_BLOCK_TAG_NAME ]
[ "li" : CLOSING_BLOCK_TAG_NAME ]
[ "
			" : TEXT ]
[ "li" : OPENING_BLOCK_TAG_NAME ]
[ "class" : ATTRIBUTE_NAME ]
[ "nav" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "a" : OPENING_BLOCK_TAG_NAME ]
[ "href" : ATTRIBUTE_NAME ]
[ "" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ " Помощь " : TEXT ]
[ "a" : CLOSING_BLOCK_TAG_NAME ]
[ "li" : CLOSING_BLOCK_TAG_NAME ]
[ "
		" : TEXT ]
[ "ul" : CLOSING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "nav" : CLOSING_BLOCK_TAG_NAME ]
[ "

	" : TEXT ]
[ "main" : OPENING_BLOCK_TAG_NAME ]
[ "id" : ATTRIBUTE_NAME ]
[ "content" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "
		" : TEXT ]
[ "php " : MACRO_TAG ]
[ "
	" : TEXT ]
[ "main" : CLOSING_BLOCK_TAG_NAME ]
[ "

	" : TEXT ]
[ "footer" : OPENING_BLOCK_TAG_NAME ]
[ "
		" : TEXT ]
[ "hr" : EMPTY_TAG_NAME ]
[ "
		" : TEXT ]
[ "small" : OPENING_BLOCK_TAG_NAME ]
[ "id" : ATTRIBUTE_NAME ]
[ "copyright" : DOUBLE_QUOTED_ATTRIBUTE_VALUE ]
[ "Copyright © 2019. Все права защищены." : TEXT ]
[ "small" : CLOSING_BLOCK_TAG_NAME ]
[ "
	" : TEXT ]
[ "footer" : CLOSING_BLOCK_TAG_NAME ]
[ "
" : TEXT ]
[ "body" : CLOSING_BLOCK_TAG_NAME ]
[ "

" : TEXT ]
[ "html" : CLOSING_BLOCK_TAG_NAME ]
[ "
" : TEXT ]
[ "" : END ]



Теперь мы готовы приступить ко второй части — построению синтаксического дерева. Поскольку наши теги имеют аттрибуты, то узлы дерева кроме связи с другими узлами будут содержать массивы пар ключ-значение. Получившаяся конструкция сможет полноправно называться объектной моделью документа DOM, упомянутой в заголовке статьи.

Сколько нужно классов для реализации всех свойств HTML-элементов?

В идеале — по одному классу для каждого элемента, чтобы можно было определять для них каскадные таблицы стилей, но мы ограничимся тремя — пустым тегом «Node», унаследованным от него блоком «Block» (контент, заключённый между двумя парными тегами) и унаследованным от него корнем дерева «Root». Также определим в парсере массив тегов, которые могут содержать текст, такие, как <p>, <li>, <strong> и др, чтобы отсеять токены с неразмеченным текстом. Теперь дело за малым. Если вы хорошо проработали лексический анализатор, то задача синтаксического — просто поглощать токены и выполнять в открытом узле одну из трёх операций: добавить в него пустой узел, открыть новый или закрыть самого, вернув указатель на родителя. Для последней потребуется, чтобы все классы, начиная с базового Node, содержали такой указатель, получаемый при создании элемента. Этот процесс называется нисходящим синтаксическим разбором.

Процедура парсинга:

void Parser::parse (const Lexer &lexer) {
    Block * open_block = (Block*) tree;
    Node * last_node = (Node*) tree;

    try {
        unsigned long long size = lexer.count();
        for (unsigned long long i(0); i < size-2; i++) {
            switch (lexer[i].type) {
            case Lexer::TEXT: {
                for (unsigned int j(0); j < TEXT_TAGS_COUNT; j++)
                    if (open_block->get_name() == text_tags[j])
                        last_node = open_block->add("TEXT", lexer[i].lexeme);
            break; }
            case Lexer::OPENING_BLOCK_TAG_NAME: {
                last_node = open_block = open_block->open(lexer[i].lexeme);
            break; }
            case Lexer::CLOSING_BLOCK_TAG_NAME: {
                if (lexer[i].lexeme != open_block->get_name())
                    throw string("unexpected closing tag: </" + lexer[i].lexeme + ">");
                open_block = open_block->close();
            break; }
            case Lexer::EMPTY_TAG_NAME: {
                last_node = open_block->add(lexer[i].lexeme);
            break; }
            case Lexer::COMMENT: {
                last_node = open_block->add("COMMENT", lexer[i].lexeme);
            break; }
            case Lexer::MACRO_TAG: {
                last_node = open_block->add("MACRO", lexer[i].lexeme);
            break; }
            case Lexer::ATTRIBUTE_NAME: {
                last_node->add_attr(lexer[i].lexeme, lexer[i].lexeme);
            break; }
            case Lexer::UNQUOTED_ATTRIBUTE_VALUE: {
                last_node->set_last_attr(lexer[i].lexeme);
            break; }
            case Lexer::SINGLE_QUOTED_ATTRIBUTE_VALUE: {
                last_node->set_last_attr(lexer[i].lexeme);
            break; }
            case Lexer::DOUBLE_QUOTED_ATTRIBUTE_VALUE: {
                last_node->set_last_attr(lexer[i].lexeme);
            break; }
            case Lexer::END: {
                if (open_block->get_type() != Node::ROOT)
                    throw string("unexpected ending!");
                open_block->close();
            }
            }
        }
    } catch (const string &error) {
        throw string("parser: " + error);
    }
}

Вот и всё! Если вы всё сделали правильно, полученное дерево можно вывести на экран:

| 
+--<ROOT>
  | 
  +--<!DOCTYPE>
  | 
  +--<html>
    | 
    +--<head>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<meta>
    | | 
    | +--<title>
    | | 
    | +--<link>
    | | 
    | +--<link>
    | | 
    | +--<COMMENT>
    | 
    +--<body>
      | 
      +--<header>
      | | 
      | +--<div>
      | 
      +--<nav>
      | | 
      | +--<ul>
      |   | 
      |   +--<li>
      |   | | 
      |   | +--<a>
      |   | 
      |   +--<li>
      |   | | 
      |   | +--<a>
      |   | 
      |   +--<li>
      |     | 
      |     +--<a>
      | 
      +--<main>
      | | 
      | +--<MACRO>
      | 
      +--<footer>
        | 
        +--<hr>
        | 
        +--<small>


Однако, хотя полученное дерево действительно можно назвать DOM, до полноценных jQuery, Jsoup, beautifulsoup или Gumbo нашему парсеру далеко, в частности потому, что он не может правильно обрабатывать текст, расположенный между парными тегами <style> и <script>, а потому исходников пока не привожу. Но обязательно добавлю, если хабровчане изъявят такое желание. Успехов.

P.S. Залил в публичный доступ исходники. Имхо, сыроватые, поэтому буду обстругивать до полноценной библиотеки.

P.S.S. Вторая часть.
Теги:
Хабы:
Всего голосов 22: ↑15 и ↓7 +8
Просмотры 13K
Комментарии 17
Комментарии Комментарии 17