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

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

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

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

  • Лексический разбор текста на токены — небольшие куски этого текста, имеющие определённое синтаксическое значение.
  • Синтаксический разбор — построение из токенов на основе их значений абстрактного синтаксического дерева (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. Залил в публичный доступ исходники. Имхо, сыроватые, поэтому буду обстругивать до полноценной библиотеки.

    Оставить комментарий