Искусство парсинга 2 или транслитерация собственной разметки

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

+БОНУС: как включать классы друг в друга в C++


Привет, Хабр! Эта статья — прямое продолжение статьи Искусство парсинга или DOM собственными руками, где мы разобрали HTML-документ и построили на его основе абстрактное синтаксическое дерево (AST) с доступом к любому элементу через индексацию при помощи лишь стандартной библиотеки C++, проще говоря, научились самостоятельно парсить XML-подобные штуки. Напомню, что процесс парсинга, или синтаксического анализа/разбора состоит из двух этапов: лексического разбора (разбора текста на токены) и построения AST. Если первый мы рассмотрели очень подробно, с примерами и исходниками, то описание второго похоже на пустую куколку бабочки, у которой есть только оболочка, а прекрасное содержимое автор извлёк перед публикацией. На то была причина, для HTML построить дерево действительно просто, нужно всего 4 класса: пустой тег, блок, текстовый узел и корень документа, наследуемый от блока. Сегодня мы оставим такую простоту позади и построим дерево, где свойства элементов, и пустых, и блочных, будут содержаться не в атрибутах тегов, а непосредственно в классах, а для этого классов придётся создать много. Действительно много. Строить будем не из простых известных языков разметки, а создадим свой, с правилами, показанными на изображении под катом. Плюс в конце ещё переведём, или, говоря правильнее, транслитируем документ с предыдущей статьёй, размеченной нашим языком, в HTML, а в качестве бонуса я отвечу начинающим программистам C++ на тривиальный, но труднонаходимый вопрос: как включать классы «друг в друга»?



Примечания в грамматике


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

...
<ordered_list_item> = <number_marker> <div>
<number_marker> = <number> "." {<number> "."} " "
<number> = <digit> {<digit>}

!! link ending ">" and image/span ending "]" can't follow "\n" or document start

Перевод: окончания ссылки ">" и изображения/встроенного элемента "]" не могут следовать сразу за началом строки или документа.

То есть, если в начале строки лексер встретит "]" или ">", мы должны дать ему установку проигнорировать особое значение этих символов и работать с ними как с обычным текстом. Такой способ добавления замечаний в грамматику не единственный, вы можете делать это по своему. В конце концов, файл с описанием синтаксиса — не курсовая работа, никто не заставляет соблюдать все правила и важно только, чтобы именно вам было удобно с ним работать. Главное, не забывать о сделанных замечаниях и отразить их в нужных участках кода.

Давайте рассмотрим полное описание данного языка:

<article> = {<article_item>}
<article_item> = <underline> | <section>

(* ARTICLE ITEMS *)
<underline> = "___" {"_"} "\n"
<section> = <div> {<div>}
<div> = <paragraphs> | <title> | <quote> | <cite> | <unordered_list> | <ordered_list>

(* SECTION ITEMS *)
<paragraphs> = <paragraph> {"\n" <paragraph>}
<paragraph> = <span> {<span>} ("\n" | <END>)
<span> = <bold> | <italic> | <underlined> | <overlined> | <throwlined> | <subscript> | <superscript> | <marked> | <monospace> | <text> | <image> | <link> | <notification>
<title> = <number signs> <left_angle_bracket> {<span>} <right_angle_bracket> ("\n" | <END>)
<number signs> "######" | "#####" | "####" | "###" | "##" | "#"
<quote> = "> " {<span>} ("\n" | <END>)
<cite> = ">>" <number> ("\n" | <END>)
<number> = <digit> {<digit>}

(* PARAGRAPH ITEMS *)
<bold> = "*[" {<span>} "]"
<italic> = "%[" {<span>} "]"
<underlined> = "_[" {<span>} "]"
<overlined> = "^[" {<span>} "]"
<throwlined> = "~[" {<span>} "]"
<subscript> = "&[" {<span>} "]"
<superscript> = "+[" {<span>} "]"
<marked> = "=[" {<span>} "]"
<monospace> = "`[" {<span>} "]"
<text> = <textline> "\n" {<textline> "\n"}
<textline> = <symbol> {<symbol>}
<symbol> = /^[\n]/
<link> = "<<" <text> ">" {<span>} ">"
<image> = "[<" <text> ">" [<text>] "]"
<notification> = (" " | "\n") "@" <word> (" " | "\n" | <END>)
<word> = (<letter> | <digit>) {<letter> | <digit>}
<letter> = "a" | "b" | "c" | "d" | ... | "_" | "-"
<digit> = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

(* LISTS *)
<unordered_list> = <unordered_list_item> {<unordered_list_item>}
<ordered_list> = <ordered_list_item> {<ordered_list_item>}
<unordered_list_item> = <marker> <div>
<marker> = ("*" {"*"}) | ("+" {"+"}) " "
<ordered_list_item> = <number_marker> <div>
<number_marker> = <number> "." {<number> "."} " "
<number> = <digit> {<digit>}

!! link ending ">" and image/span ending "]" can't follow "\n" or document start

В прошлый раз нужно было выписать терминалы и проверять каждый входящий символ на соответствие одному из них. Но тогда терминалы были односимвольные! Теперь необходимо кроме выделения терминалов разделить их самих на ключи — то есть, символы. Почему «ключи»? Они имеют ключевое значение для лексера. В результате всех действий у нас в файле с грамматикой появятся строчки:

(* TERMINALS *)
"___...", "\n", "\n\n", "> ", ">>...", "###...[", "*[", "%[", "_[", "^[", "~[", "&[", "+[", "=[", "`[", "]", "<<", "[<", ">", " @... ", "\n@...\n", " @...\n", "\n@... ", "***... ", "+++... ", "123.56. "

(* KEYS *)
"_", "\n" ">", "#", "*", "%", "^", "~", "&", "+", "=", "`", "<", "[", "]", " ", "@", "1..9", ".", <END>

Стек ожидаемых типов токенов


В прошлый раз, опять же, всё было проще, у нас было всего 10 типов токенов, не считая конца, и было меньше шансов запутаться в этом зоопарке лексем. Теперь типов, очевидно, больше. Напомню, что задача лексера — оставить парсеру как можно меньше работы, в идеале, лишь построение дерева. Поэтому набор типов токенов должен как можно точнее отражать их сущность. В первой статье я привёл пример хорошего набора, в этой приведу его вместе с «антипримером». Видите терминалы, начинающие встроенные текстовые элементы (полужирный — bold, курсив — italic и т.д.)? Мы могли бы разобрать их на пару токенов: ведущий ("*", "%" и др.) и ведомый ("[") и в такой форме передать парсеру. Легко догадаться, что лучше сделать точное определение текстового элемента на уровне лексера, т.е. определить "*[" как «bold_start», "%[" как «italic_start» и и.д. Чем больше типов и чем точнее они отражают самих себя — тем лучше. При этом второе важнее первого. Например, мы могли бы разобрать нотификацию на символ "@" и имя пользователя, но, очевидно, лучше оставить их совмещёнными в одной лексеме.
Ну вот мы определились с типами. С чего начать процедуру разбора текста на токены? Как и тогда, начните с начала. Что может следовать сразу за началом разбираемого документа? Не спешите загибать пальцы. В отличие от HTML, все 22 типа здесь могут дать старт. Ничего страшного, вооружившись битовой унификацией, так и пишем:

curr_token_type = TEXT | UNDERLINE | TITLE_START | QUOTE_START | CITE | BOLD_START | ...

а в функции обработки символа:

case TEXT | UNDERLINE | TITLE_START | QUOTE_START | CITE | ...

Если не понимаете, о чём идёт речь, прочитайте первую статью.

Не бойтесь длинного обобщённого типа ожидаемого токена. Первый символ строки сразу сократит его длину до 2-4 типов. Так как наши терминалы многосимвольны, определение идёт по ключам.

Всё просто, посмотрите сами:


        if (c == '_') {
            buffer.push_back('_');
            curr_token_type = TEXT | UNDERLINE | UNDERLINED_START;

Нижнее подчёркивание сразу определило строящийся токен к одному из трёх типов: простого текста, горизонтальной черте или начало подчёркнутого текста ("_[").

Возвращаясь к проблеме, как уследить за всеми обобщёнными типами и не забыть обработать их все? Заведите стек… в блокноте! Именно так, записывайте все обобщённые типы, появляющиеся после «curr_token_type = ...» в список, и после обработки одного берите из этого списка другой с конца. Можно организовать работу со списком и как с очередью, это большого значения не имеет. Главное, что так вы не забудете, какие типы уже обработаны, а какие ещё предстоит обработать.

Дерево классов


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


Node { Node * parent, Node_type type } #-
	Root { Root_item[] children, ulong children_count }

Так мы определили будущий базовый класс всех нод и его производный — корень дерева, то есть, сам документ. Документ (см. БНФ выше) состоит из двух типов нод: раздела (section) и горизонтальной линии (underline). Определим для них базовый класс Root_item и опишем каждый так же, как мы описали корень. Кроме того, здесь же, в блокноте, сразу указываем все другие поля классов, если они есть. Для корня это число «детей» — т.е. внутренних разделов и горизонтальных линий. Раздел состоит из элементов, для которых мы определим базовый класс Div и так далее, двигаясь рекурсивно по грамматике, определим все нужные классы. Перед тем, как писать код, определим здесь же все включения заголовков. Это просто: все прямые наследники базовых обобщённых классов должны включаться в содержащие их классы.

Обозначим эти зависимости в виде списков после решётки, и у нас получится такой документ:

Node { Node * parent, Node_type type } #-
	Root { Root_item[] children, ulong children_count } #Underline, #Section

	Root_item {} #-
		Underline {}
		Section { Div[] children, ulong children_count } #Paragraph, #Title, #Quote, #Cite, #Unordered_list, #Ordered_list

	Div {} #-
		Paragraph { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Title { char level, Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Quote { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Cite { ulong number } #-
		Unordered_list { Div } #Paragraph, #Title, #Quote, #Cite, #Ordered_list
			Ordered_list { Div } #Paragraph, #Title, #Quote, #Cite, Unordered list
		
	Span {} #-
		Bold { Span[] children, ulong children_count } #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Italic { Span[] children, ulong children_count } #Bold, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Underlined { Span[] children, ulong children_count } #Bold, #Italic, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Overlined { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Throwlined { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Subscript { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Superscript { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
		Marked { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Monospace, #Text, #Image, #Link, #Notification
		Monospace { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Text, #Image, #Link, #Notification
		Text { string text } #-
		Image { string src, string alt } #-
		Link { string URL, Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Notification
		Notification { string user } #-

Здесь я пометил "#-" отсутствие зависимостей и убрал включения классов в самих себя.
Замечаем, что все классы встроенного форматирования (Bold, Italic, ...) зависимы друг от друга и, кроме того, от класса Link, который так же зависим от них! В похожем положении находятся Unordered_list и Ordered_list. Включение заголовков друг в друга не просто приведёт к игнорированию одного из них, как ожидалось бы, но и не пройдёт валидацию препроцессором, а одностороннее включение не позволит нам объявить внутри включаемого класса функцию открытия элемента класса включающего и возвращения ссылки на оный. Как быть? Есть два способа.

Включение классов друг в друга


Сначала посмотрим на классы Bold, Italic и так до Monospace. Они похожи. Настолько, что могут быть объединены в один класс «Inline». Возможно, такое решение вызовет сомнения. У меня тоже вызывало, но на практике различие между ними влияло лишь на форму представления в виде дерева в терминале и на теги в HTML. Если вы видите, что некоторые классы содержат одинаковые поля, имеют одинаковые зависимости и вообще схожее описание в формальной грамматике, смело объединяйте их. Так вы облегчите работу себе и процессору.

Но такой трюк не пройдёт с классом Link, ведь он содержит дополнительное поле — строку URL. Воспользуемся вторым способом.

Все знают, что хорошим тоном в программировании на C++ является разделение классов на объявление и определение? В заголовке с расширением .h или .hpp — объявление, в исходнике с расширением .cpp — определение, так? А теперь обращаюсь к новичкам в программировании: сядьте и пристегните ремни безопасности, потому что будет неприятно. Ведь то, что мы прописываем в файле с расширением .h — не что иное, как определение класса. А в файле .cpp — уже реализация методов этого класса. Не понятно? В школе нас обманывали. Класс объявляется так же, как функция, одной строкой, если не содержит шаблонов.

Даже проще функции, ведь у него нет аргументов. Вот типичное объявление класса:

class MyClass;

И всё! А объявления полей и методов — уже его определение.

Этим мы и воспользуемся. Включим заголовок класса Inline в заголовок класса Link, а в нём самом объявим класс Link перед определением класса Inline. Выглядеть файл inline.h должен так:


#ifndef INLINE_H
#define INLINE_H
#include "AST/span.h"
#include "AST/text.h"
#include "AST/image.h"
#include "AST/notification.h"

class Link;

class Inline : public Span {
public:
    static const unsigned long MAX_CHILDREN_COUNT = 0xFFFFFF;

private:
    Span ** children;
    unsigned long children_count;
    unsigned long extended;

    void extend();

public:
    Inline(const Node * parent, const Node_type &type);
    Inline(const Span * span);
   ~Inline();

    Inline * add_text(const string &text);
    Inline * add_image(const string &src, const string &alt);
    Inline * add_notification(const string &user);
    Link * open_link(const string &URL);
...

Класс Inline ещё ничего не знает о классе Link, о его полях и методах, но точно знает о его существовании. Поэтому мы можем объявлять методы, возвращающие указатель на объект класса Link, либо принимающие его в качестве аргумента. Слово указатель выделено не случайно, класс Inline ещё не умеет строить объекты типа Link, так как не имеет доступа к его конструктору, зато может работать со всеми указателями, т.к. у них у всех одинаковый интерфейс. Но нам здесь объекты и не нужны. А вот в реализации метода open_link создаётся объект типа Link и возвращается указатель на него, а значит, к моменту вхождения препроцессора в этот метод конструктор и остальные методы Link, которые могут понадобиться методу open_link, должны быть объявлены. Здесь воспользуемся преимуществом разделения исходного кода на отдельные файлы с заголовками и реализацией. В файл inline.cpp включён («подинклюден») файл inline.h, но файл link.h не включён в inline.h. Значит, включение его в inline.cpp будет первым включением для препроцессора. Тогда файл inline.cpp будет начинаться так:


#include "inline.h"
#include "link.h"
...

Повторю всё вышесказанное. Заголовок класса A.h включаем в заголовок класса B.h как обычно, а класс B объявляем перед классом A и включаем его заголовок в исходник A.cpp. Данный способ не единственный, но самый простой, по моему мнению.

Замечу, что такое взаимное включение классов не мешает наследовать класс B от класса A, если именно его объявление мы записали перед определением класса A. Именно так я и сделал, унаследовав Ordered_list от Unordered_list.

Построение дерева


Итак, мы добрались до построения абстрактного синтаксического дерева. В прошлой статье функция уместилась в 50 строк. Спойлер: на этот раз она выросла почти до 1400. Принцип работы тот же: проверяем тип каждого токена и в зависимости от него выполняем определённый участок кода, храня в памяти открытый узел дерева. Вот только если для разбора HTML почти все участки содержали одну и только одну из трёх команд: добавить пустой узел внутрь открытого, открыть новый узел в открытом и закрыть открытый узел, вернув его родителя, то здесь нужное действие ещё зависит от типа открытого узла. Например, если на обработку поступил токен «горизонтальная линия», а открытый узел — корень документа, то всё, что нужно, — добавить в этот открытый узел с помощью кастования и функции с условным названием add_line() линию, примерно так:


if (type == Node::ROOT)
    static_case<Root*>(open_node)->add_line();

Но если открытый узел — абзац (Paragraph), то сначала нужно закрыть его и всех возможных предков (маркированные и нумерованные списки), пока открытый узел не станет иметь тип «раздел», а затем закрыть и его:


else if (type == Node::PARAGRAPH) {
    open_node = static_cast<Paragraph*>(open_node)->close();
    while (open_node->get_type() != Node::SECTION) {
        if (open_node->get_type() == Node::UNORDERED_LIST)
            open_node = static_cast<Unordered_list*>(open_node)->close();
        else if (open_node->get_type() == Node::UNORDERED_LIST)
            open_node = static_cast<Unordered_list*>(open_node)->close();
        else if (open_node->get_type() == Node::PARAGRAPH)
            open_node = static_cast<Paragraph*>(open_node)->close();
    }
    open_node = static_cast<Section*>(open_node)->close();
    open_node = tree->add_line();
}

Если открытый узел — подпись к изображению, то горизонтальная линия вообще нарушает грамматику, и необходимо выбросить исключение, а если открытый узел — не ссылка, а входящий токен ">" имеет тип «LINK_FINISH», его следует обработать не как конец ссылки, а как текст и т.д.

Таким образом, дерево switch/case, проверяющее тип входящего токена, должно содержать ещё одно дерево switch/case, проверяющее тип открытого узла. Вначале за такую конструкцию сложно взяться, но не обязательно начинать с начала, с первого условия. Можно создать типовый документ, размеченный вашим языком / содержащий сценарий на вашем языке и реализовывать условия по ходу документа, проверяя результат выводом псевдографического дерева в терминал. Я в качестве такого документа взял предыдущую статью, самый первый поступивший токен — начало заголовка. Значит, обрабатываем токен с типом TITLE_START. Следом идут текст заголовка и закрывающая квадратная скобка, обрабатываем токены типов TEXT и SPAN_OR_IMAGE_FINISH.

После этого у нас уже получится такое мини-деревце:

<article>
| 
+-<section>
  | 
  +-<h1>
    | 
    +-"Искусство парсинга или DOM своими руками"


По ходу дела вы заметите, что некоторые классы включают в себя одинаковые методы с одинаковыми алгоритмами. Например, классы абзаца Paragraph и цитаты Quote одинаково открывают ссылки и добавляют в себя текст. В таких случаях лучшим решением будет при рефакторинге создать один класс с данными методами и унаследовать от него нужные ноды. Я попытался такое реализовать, но моих навыков не хватило, и я запутался в неоднозначности при кастовании, поэтому просто привожу результаты работы лексера и парсера:

Сама статья
@2che
>>442964
#[Искусство парсинга или DOM своими руками]

Привет, Хабр! Недавно я задался идеей создать простой язык разметки наподобие 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> = <число> ("*" | "/") <число>]

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

Полное описание БНФ доступно в Википедии <<https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0>здесь> и <<https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0>здесь>. Составление грамматики языка — важная стадия создания языка, не терпящая легкомыслия. Одна ошибка в ней может привести к полностью нерабочему коду, который придётся переписывать с нуля. Поэтому, прежде чем делать следующий шаг, убедитесь, что в составленной грамматике не осталось спорных моментов. Если у вас два монитора, будет удобно на всё оставшееся время работы занять документом с грамматикой один монитор, чтобы иметь возможность быстро перемещаться глазами на него, когда будете кодить. Поверьте, так придётся делать постоянно. Вот составленная мной грамматика HTML5 в форме БНФ:
> `[stub]

Когда грамматика готова, можно приступать к лексическому анализатору (другое название лексического разборщика, т.к. помимо разбора, он выявляет в документе лексические ошибки). На первый взгляд всё просто: поглощать символы, записывать в буфер и при обнаружении ключевого терминала определять полученную лексему как токен с определённым типом, так? Да, только тип токена здесь имеет большее значение, чем символ. Сейчас поясню. Само собой, процедура 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:
> `[stub]

Проверяем с помощью switch тип ожидаемого токена (или токенов), а внутри каждого case определяем процедуры для каждого из ключевых терминалов. Функций не так много, все выполняют простые действия: либо добавление символа к буферу, либо слив буфера в очередной токен, либо смену ожидаемого типа токена (токенов), либо выброс исключения. Определить нужную процедуру легко по написанной выше грамматике при помощи текстового редактора с возможностью поиска. Просто ищем все включения ожидаемого токена (токенов) в определения других выражений, затем включения этих выражений в «третьи» и т.д. Вот пример для открывающего тега в текстовом редакторе gedit:
[<https://hsto.org/webt/72/fw/tw/72fwtwt_waeie4ulzftkxua356w.png>]

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

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

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

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

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

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

Процедура парсинга:
> `[stub]

Вот и всё! Если вы всё сделали правильно, полученное дерево можно вывести на экран:
`[| 
+--<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. Залил в публичный доступ <<https://gitlab.com/2che/nyHTML>исходники>. Имхо, сыроватые, поэтому буду обстругивать до полноценной библиотеки.

Токены от лексера
0: [ "2che" : NOTIFICATION ]
1: [ "
" : NEWLINE ]
2: [ "442964" : CITE ]
3: [ "#[" : TITLE_START ]
4: [ "Искусство парсинга или DOM своими руками" : TEXT ]
5: [ "]" : SPAN_OR_IMAGE_FINISH ]
6: [ "

" : DOUBLE_NEWLINE ]
7: [ "Привет, Хабр! Недавно я задался идеей создать простой язык разметки наподобие markdown, который отлично подходил бы для моих задач, а именно — быстрого написания лекций с форматированием и возможностью вставки математических формул «на лету», с применением одной лишь клавиатуры. Чтобы перевести текст, написанный в таком формате, в более понятную форму, например, документ LibreOffice Writer, нужен " : TEXT ]
8: [ "%[" : ITALIC_START ]
9: [ "синтаксический анализатор" : TEXT ]
10: [ "]" : SPAN_OR_IMAGE_FINISH ]
11: [ ", проще говоря — " : TEXT ]
12: [ "%[" : ITALIC_START ]
13: [ "парсер" : TEXT ]
14: [ "]" : SPAN_OR_IMAGE_FINISH ]
15: [ ". Поскольку я привык делать велосипеды, то направился в поисковые системы с запросами «parser example», «html to DOM», «how to parse html» и др. К моему разочарованию, на всех найденных ресурсах либо приводились элементарные примеры типа калькулятора Страуструпа с рекурсивным спуском, либо использовались готовые решения, такие как flex, bison, llvm и yacc. Библиотек, предназначенных для парсинга строго определённых языков, нашлось ещё больше (gumbo, jsoup, rapidjson, инструменты Qt и др.) Ни то, ни другое не входило в мои планы по написанию парсера своей разметки на C++ с использованием лишь стандартной библиотеки, поэтому моим источником знаний об искусстве парсинга вместо электронных ресурсов стали методички технических институтов. О том, как взять текст и построить из него AST (абстрактное синтаксическое дерево), о некоторых подводных камнях, на которые я натыкался в процессе, о возможных ошибках я сегодня и расскажу." : TEXT ]
16: [ "

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

" : DOUBLE_NEWLINE ]
19: [ "Прежде всего, парсинг, или " : TEXT ]
20: [ "%[" : ITALIC_START ]
21: [ "синтаксический разбор" : TEXT ]
22: [ "]" : SPAN_OR_IMAGE_FINISH ]
23: [ " — не синоним полного процесса превращения текста в объектную модель. Сам процесс состоит из двух этапов:" : TEXT ]
24: [ "
" : NEWLINE ]
25: [ "1. " : ORDERED_LIST_ITEM_MARKER ]
26: [ "*[" : BOLD_START ]
27: [ "Лексический разбор" : TEXT ]
28: [ "]" : SPAN_OR_IMAGE_FINISH ]
29: [ " текста на токены — небольшие куски этого текста, имеющие определённое синтаксическое значение." : TEXT ]
30: [ "
" : NEWLINE ]
31: [ "2. " : ORDERED_LIST_ITEM_MARKER ]
32: [ "*[" : BOLD_START ]
33: [ "Синтаксический разбор" : TEXT ]
34: [ "]" : SPAN_OR_IMAGE_FINISH ]
35: [ " — построение из токенов на основе их значений " : TEXT ]
36: [ "%[" : ITALIC_START ]
37: [ "абстрактного синтаксического дерева" : TEXT ]
38: [ "]" : SPAN_OR_IMAGE_FINISH ]
39: [ " (AST — abstract syntax tree), или " : TEXT ]
40: [ "%[" : ITALIC_START ]
41: [ "объектной модели документа" : TEXT ]
42: [ "]" : SPAN_OR_IMAGE_FINISH ]
43: [ " (DOM — document object model)." : TEXT ]
44: [ "

" : DOUBLE_NEWLINE ]
45: [ "Но давайте по порядку. Перед тем, как открывать свою любимую IDE и писать код, нужно разработать грамматику будущего языка. Из формальных контекстно-свободных грамматик самые известные — " : TEXT ]
46: [ "%[" : ITALIC_START ]
47: [ "форма Бэкуса-Наура (БНФ)" : TEXT ]
48: [ "]" : SPAN_OR_IMAGE_FINISH ]
49: [ " и " : TEXT ]
50: [ "%[" : ITALIC_START ]
51: [ "расширенная форма Бэкуса-Наура" : TEXT ]
52: [ "]" : SPAN_OR_IMAGE_FINISH ]
53: [ ". Я использовал их симбиоз, взяв лучшее от обеих форм. Любое выражение можно определить через другие выражения так:" : TEXT ]
54: [ "
" : NEWLINE ]
55: [ "> " : QUOTE_START ]
56: [ "`[" : MONOSPACE_START ]
57: [ "<сумма" : TEXT ]
58: [ ">" : LINK_FINISH ]
59: [ " = <выражение_1" : TEXT ]
60: [ ">" : LINK_FINISH ]
61: [ " <знак_плюс" : TEXT ]
62: [ ">" : LINK_FINISH ]
63: [ " <выражение_2" : TEXT ]
64: [ ">" : LINK_FINISH ]
65: [ "]" : SPAN_OR_IMAGE_FINISH ]
66: [ "

" : DOUBLE_NEWLINE ]
67: [ "Здесь одно выражение определено через три других, следующих одно за другим. Их, в свою очередь, тоже необходимо представить через «третьи» выражения и т.д." : TEXT ]
68: [ "

" : DOUBLE_NEWLINE ]
69: [ "Когда же остановиться?" : TEXT ]
70: [ "

" : DOUBLE_NEWLINE ]
71: [ "Описание синтаксиса любого языка в формальных грамматиках состоит из двух типов лексем: " : TEXT ]
72: [ "%[" : ITALIC_START ]
73: [ "терминалов" : TEXT ]
74: [ "]" : SPAN_OR_IMAGE_FINISH ]
75: [ " и " : TEXT ]
76: [ "%[" : ITALIC_START ]
77: [ "нетерминалов" : TEXT ]
78: [ "]" : SPAN_OR_IMAGE_FINISH ]
79: [ ". " : TEXT ]
80: [ "*[" : BOLD_START ]
81: [ "Нетерминалы" : TEXT ]
82: [ "]" : SPAN_OR_IMAGE_FINISH ]
83: [ " — выражения, требующие определения:" : TEXT ]
84: [ "
" : NEWLINE ]
85: [ "> " : QUOTE_START ]
86: [ "`[" : MONOSPACE_START ]
87: [ "<выражение_1" : TEXT ]
88: [ ">" : LINK_FINISH ]
89: [ " = <число" : TEXT ]
90: [ ">" : LINK_FINISH ]
91: [ " (<знак_умножения" : TEXT ]
92: [ ">" : LINK_FINISH ]
93: [ " | <знак_деления" : TEXT ]
94: [ ">" : LINK_FINISH ]
95: [ ") <число" : TEXT ]
96: [ ">" : LINK_FINISH ]
97: [ "]" : SPAN_OR_IMAGE_FINISH ]
98: [ "

" : DOUBLE_NEWLINE ]
99: [ "*[" : BOLD_START ]
100: [ "Терминалы" : TEXT ]
101: [ "]" : SPAN_OR_IMAGE_FINISH ]
102: [ " самодостаточны, их не нужно определять. Выше приведённые примеры можно записать так:" : TEXT ]
103: [ "
" : NEWLINE ]
104: [ "> " : QUOTE_START ]
105: [ "`[" : MONOSPACE_START ]
106: [ "<сумма" : TEXT ]
107: [ ">" : LINK_FINISH ]
108: [ " = <выражение_1" : TEXT ]
109: [ ">" : LINK_FINISH ]
110: [ " "+" <выражение_2" : TEXT ]
111: [ ">" : LINK_FINISH ]
112: [ "
" : NEWLINE ]
113: [ "<выражение_1" : TEXT ]
114: [ ">" : LINK_FINISH ]
115: [ " = <число" : TEXT ]
116: [ ">" : LINK_FINISH ]
117: [ " ("*" | "/") <число" : TEXT ]
118: [ ">" : LINK_FINISH ]
119: [ "]" : SPAN_OR_IMAGE_FINISH ]
120: [ "

" : DOUBLE_NEWLINE ]
121: [ "где "+", "*", "/" — терминалы." : TEXT ]
122: [ "
" : NEWLINE ]
123: [ "Выделить из грамматики терминалы нужно сразу, можно даже выписать их в отдельный список внизу основных определений, — они пригодятся позже." : TEXT ]
124: [ "

" : DOUBLE_NEWLINE ]
125: [ "Полное описание БНФ доступно в Википедии " : TEXT ]
126: [ "<<" : LINK_START ]
127: [ "https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0" : TEXT ]
128: [ ">" : LINK_FINISH ]
129: [ "здесь" : TEXT ]
130: [ ">" : LINK_FINISH ]
131: [ " и " : TEXT ]
132: [ "<<" : LINK_START ]
133: [ "https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0" : TEXT ]
134: [ ">" : LINK_FINISH ]
135: [ "здесь" : TEXT ]
136: [ ">" : LINK_FINISH ]
137: [ ". Составление грамматики языка — важная стадия создания языка, не терпящая легкомыслия. Одна ошибка в ней может привести к полностью нерабочему коду, который придётся переписывать с нуля. Поэтому, прежде чем делать следующий шаг, убедитесь, что в составленной грамматике не осталось спорных моментов. Если у вас два монитора, будет удобно на всё оставшееся время работы занять документом с грамматикой один монитор, чтобы иметь возможность быстро перемещаться глазами на него, когда будете кодить. Поверьте, так придётся делать постоянно. Вот составленная мной грамматика HTML5 в форме БНФ:" : TEXT ]
138: [ "
" : NEWLINE ]
139: [ "> " : QUOTE_START ]
140: [ "`[" : MONOSPACE_START ]
141: [ "stub" : TEXT ]
142: [ "]" : SPAN_OR_IMAGE_FINISH ]
143: [ "

" : DOUBLE_NEWLINE ]
144: [ "Когда грамматика готова, можно приступать к лексическому анализатору (другое название лексического разборщика, т.к. помимо разбора, он выявляет в документе лексические ошибки). На первый взгляд всё просто: поглощать символы, записывать в буфер и при обнаружении ключевого терминала определять полученную лексему как токен с определённым типом, так? Да, только тип токена здесь имеет большее значение, чем символ. Сейчас поясню. Само собой, процедура disassemble(ifsteam &file) должна содержать цикл, читающий по одному символу из входного потока и отправляющий его в процедуру process(const char &c), где этот символ обрабатывается. Кажется, что процедуре process нужно содержать switch, где на каждый ключевой символ определены свои функции в зависимости от текущего типа токена. На самом деле всё наоборот: лучше с помощью switch проверять именно тип токена, а функции определять для символов. Более того, текущий токен чаще всего имеет неопределённый тип, один из многих. Например, после открытия угловой скобки может идти: открывающий, закрывающий, пустой теги, а также комментарий в стиле HTML или макро тег (сценарий PHP, заключённый в "<?… ?" : TEXT ]
145: [ ">" : LINK_FINISH ]
146: [ "". И для всех таких объединений нужен свой case. Как такое реализовать? С помощью битовых флагов. Пусть задано конечное число типов токена (чем больше — тем лучше, так как задача лексического анализатора — оставить как можно меньше работы синтаксическому). Для каждого типа задано уникальное число степени двойки (1, 2, 4, 8 и т.д). Тогда в двоичном формате они будут выглядеть так: 0001, 0010, 0100 и т.д., и при побитовом сложении любого числа любых типов получится уникальное число. Если текстовое описание сложно для понимания, приведу код. Вот определение типов:" : TEXT ]
147: [ "
" : NEWLINE ]
148: [ "> " : QUOTE_START ]
149: [ "`[" : MONOSPACE_START ]
150: [ "enum Token_type {" : TEXT ]
151: [ "
" : NEWLINE ]
152: [ "    END = 1, TEXT = 2," : TEXT ]
153: [ "
" : NEWLINE ]
154: [ "    OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO_TAG = 64," : TEXT ]
155: [ "
" : NEWLINE ]
156: [ "    ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBLE_QUOTED_ATTRIBUTE_VALUE = 1024" : TEXT ]
157: [ "
" : NEWLINE ]
158: [ "};" : TEXT ]
159: [ "]" : SPAN_OR_IMAGE_FINISH ]
160: [ "

" : DOUBLE_NEWLINE ]
161: [ "Урезанная процедура process:" : TEXT ]
162: [ "
" : NEWLINE ]
163: [ "> " : QUOTE_START ]
164: [ "`[" : MONOSPACE_START ]
165: [ "stub" : TEXT ]
166: [ "]" : SPAN_OR_IMAGE_FINISH ]
167: [ "

" : DOUBLE_NEWLINE ]
168: [ "Проверяем с помощью switch тип ожидаемого токена (или токенов), а внутри каждого case определяем процедуры для каждого из ключевых терминалов. Функций не так много, все выполняют простые действия: либо добавление символа к буферу, либо слив буфера в очередной токен, либо смену ожидаемого типа токена (токенов), либо выброс исключения. Определить нужную процедуру легко по написанной выше грамматике при помощи текстового редактора с возможностью поиска. Просто ищем все включения ожидаемого токена (токенов) в определения других выражений, затем включения этих выражений в «третьи» и т.д. Вот пример для открывающего тега в текстовом редакторе gedit:" : TEXT ]
169: [ "
" : NEWLINE ]
170: [ "[<" : IMAGE_START ]
171: [ "https://hsto.org/webt/72/fw/tw/72fwtwt_waeie4ulzftkxua356w.png" : TEXT ]
172: [ ">" : LINK_FINISH ]
173: [ "]" : SPAN_OR_IMAGE_FINISH ]
174: [ "

" : DOUBLE_NEWLINE ]
175: [ "Вначале ориентироваться в грамматике сложно, но со временем и опытом она становится не сложнее деления столбиком. А вот и процедура disassemble:" : TEXT ]
176: [ "
" : NEWLINE ]
177: [ "> " : QUOTE_START ]
178: [ "`[" : MONOSPACE_START ]
179: [ "stub" : TEXT ]
180: [ "]" : SPAN_OR_IMAGE_FINISH ]
181: [ "

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

" : DOUBLE_NEWLINE ]
184: [ "Для примера я взял один из своих шаблонов HTML-документа с комментарием, добавил к нему псевдо-скрипт PHP, обработал лексером и вывел список токенов в формате "[ "<текст_токена" : TEXT ]
185: [ ">" : LINK_FINISH ]
186: [ "": <тип_токена" : TEXT ]
187: [ ">" : LINK_FINISH ]
188: [ " " : TEXT ]
189: [ "]" : SPAN_OR_IMAGE_FINISH ]
190: [ "". Вот что получилось:" : TEXT ]
191: [ "
" : NEWLINE ]
192: [ "> " : QUOTE_START ]
193: [ "=[" : MARKED_START ]
194: [ "Сам документ" : TEXT ]
195: [ "`[" : MONOSPACE_START ]
196: [ "stub" : TEXT ]
197: [ "]" : SPAN_OR_IMAGE_FINISH ]
198: [ "]" : SPAN_OR_IMAGE_FINISH ]
199: [ "
" : NEWLINE ]
200: [ "=[" : MARKED_START ]
201: [ "Список токенов" : TEXT ]
202: [ "`[" : MONOSPACE_START ]
203: [ "stub" : TEXT ]
204: [ "]" : SPAN_OR_IMAGE_FINISH ]
205: [ "]" : SPAN_OR_IMAGE_FINISH ]
206: [ "

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

" : DOUBLE_NEWLINE ]
209: [ "Сколько нужно классов для реализации всех свойств HTML-элементов?" : TEXT ]
210: [ "

" : DOUBLE_NEWLINE ]
211: [ "В идеале — по одному классу для каждого элемента, чтобы можно было определять для них каскадные таблицы стилей, но мы ограничимся тремя — пустым тегом «Node», унаследованным от него блоком «Block» (контент, заключённый между двумя парными тегами) и унаследованным от него корнем дерева «Root». Также определим в парсере массив тегов, которые могут содержать текст, такие, как <p" : TEXT ]
212: [ ">" : LINK_FINISH ]
213: [ ", <li" : TEXT ]
214: [ ">" : LINK_FINISH ]
215: [ ", <strong" : TEXT ]
216: [ ">" : LINK_FINISH ]
217: [ " и др, чтобы отсеять токены с неразмеченным текстом. Теперь дело за малым. Если вы хорошо проработали лексический анализатор, то задача синтаксического — просто поглощать токены и выполнять в открытом узле одну из трёх операций: добавить в него пустой узел, открыть новый или закрыть самого, вернув указатель на родителя. Для последней потребуется, чтобы все классы, начиная с базового Node, содержали такой указатель, получаемый при создании элемента. Этот процесс называется " : TEXT ]
218: [ "%[" : ITALIC_START ]
219: [ "нисходящим синтаксическим разбором" : TEXT ]
220: [ "]" : SPAN_OR_IMAGE_FINISH ]
221: [ "." : TEXT ]
222: [ "

" : DOUBLE_NEWLINE ]
223: [ "Процедура парсинга:" : TEXT ]https://gitlab.com/2che/markedit
224: [ "
" : NEWLINE ]
225: [ "> " : QUOTE_START ]
226: [ "`[" : MONOSPACE_START ]
227: [ "stub" : TEXT ]
228: [ "]" : SPAN_OR_IMAGE_FINISH ]
229: [ "

" : DOUBLE_NEWLINE ]
230: [ "Вот и всё! Если вы всё сделали правильно, полученное дерево можно вывести на экран:" : TEXT ]
231: [ "
" : NEWLINE ]
232: [ "`[" : MONOSPACE_START ]
233: [ "| " : TEXT ]
234: [ "
" : NEWLINE ]
235: [ "+--<ROOT" : TEXT ]
236: [ ">" : LINK_FINISH ]
237: [ "
" : NEWLINE ]
238: [ "  | " : TEXT ]
239: [ "
" : NEWLINE ]
240: [ "  +--<!DOCTYPE" : TEXT ]
241: [ ">" : LINK_FINISH ]
242: [ "
" : NEWLINE ]
243: [ "  | " : TEXT ]
244: [ "
" : NEWLINE ]
245: [ "  +--<html" : TEXT ]
246: [ ">" : LINK_FINISH ]
247: [ "
" : NEWLINE ]
248: [ "    | " : TEXT ]
249: [ "
" : NEWLINE ]
250: [ "    +--<head" : TEXT ]
251: [ ">" : LINK_FINISH ]
252: [ "
" : NEWLINE ]
253: [ "    | | " : TEXT ]
254: [ "
" : NEWLINE ]
255: [ "    | +--<meta" : TEXT ]
256: [ ">" : LINK_FINISH ]
257: [ "
" : NEWLINE ]
258: [ "    | | " : TEXT ]
259: [ "
" : NEWLINE ]
260: [ "    | +--<meta" : TEXT ]
261: [ ">" : LINK_FINISH ]
262: [ "
" : NEWLINE ]
263: [ "    | | " : TEXT ]
264: [ "
" : NEWLINE ]
265: [ "    | +--<meta" : TEXT ]
266: [ ">" : LINK_FINISH ]
267: [ "
" : NEWLINE ]
268: [ "    | | " : TEXT ]
269: [ "
" : NEWLINE ]
270: [ "    | +--<meta" : TEXT ]
271: [ ">" : LINK_FINISH ]
272: [ "
" : NEWLINE ]
273: [ "    | | " : TEXT ]
274: [ "
" : NEWLINE ]
275: [ "    | +--<meta" : TEXT ]
276: [ ">" : LINK_FINISH ]
277: [ "
" : NEWLINE ]
278: [ "    | | " : TEXT ]
279: [ "
" : NEWLINE ]
280: [ "    | +--<meta" : TEXT ]
281: [ ">" : LINK_FINISH ]
282: [ "
" : NEWLINE ]
283: [ "    | | " : TEXT ]
284: [ "
" : NEWLINE ]
285: [ "    | +--<meta" : TEXT ]
286: [ ">" : LINK_FINISH ]
287: [ "
" : NEWLINE ]
288: [ "    | | " : TEXT ]
289: [ "
" : NEWLINE ]
290: [ "    | +--<meta" : TEXT ]
291: [ ">" : LINK_FINISH ]
292: [ "
" : NEWLINE ]
293: [ "    | | " : TEXT ]
294: [ "
" : NEWLINE ]
295: [ "    | +--<meta" : TEXT ]
296: [ ">" : LINK_FINISH ]
297: [ "
" : NEWLINE ]
298: [ "    | | " : TEXT ]
299: [ "
" : NEWLINE ]
300: [ "    | +--<title" : TEXT ]
301: [ ">" : LINK_FINISH ]
302: [ "
" : NEWLINE ]
303: [ "    | | " : TEXT ]
304: [ "
" : NEWLINE ]
305: [ "    | +--<link" : TEXT ]
306: [ ">" : LINK_FINISH ]
307: [ "
" : NEWLINE ]
308: [ "    | | " : TEXT ]
309: [ "
" : NEWLINE ]
310: [ "    | +--<link" : TEXT ]
311: [ ">" : LINK_FINISH ]
312: [ "
" : NEWLINE ]
313: [ "    | | " : TEXT ]
314: [ "
" : NEWLINE ]
315: [ "    | +--<COMMENT" : TEXT ]
316: [ ">" : LINK_FINISH ]
317: [ "
" : NEWLINE ]
318: [ "    | " : TEXT ]
319: [ "
" : NEWLINE ]
320: [ "    +--<body" : TEXT ]
321: [ ">" : LINK_FINISH ]
322: [ "
" : NEWLINE ]
323: [ "      | " : TEXT ]
324: [ "
" : NEWLINE ]
325: [ "      +--<header" : TEXT ]
326: [ ">" : LINK_FINISH ]
327: [ "
" : NEWLINE ]
328: [ "      | | " : TEXT ]
329: [ "
" : NEWLINE ]
330: [ "      | +--<div" : TEXT ]
331: [ ">" : LINK_FINISH ]
332: [ "
" : NEWLINE ]
333: [ "      | " : TEXT ]
334: [ "
" : NEWLINE ]
335: [ "      +--<nav" : TEXT ]
336: [ ">" : LINK_FINISH ]
337: [ "
" : NEWLINE ]
338: [ "      | | " : TEXT ]
339: [ "
" : NEWLINE ]
340: [ "      | +--<ul" : TEXT ]
341: [ ">" : LINK_FINISH ]
342: [ "
" : NEWLINE ]
343: [ "      |   | " : TEXT ]
344: [ "
" : NEWLINE ]
345: [ "      |   +--<li" : TEXT ]
346: [ ">" : LINK_FINISH ]
347: [ "
" : NEWLINE ]
348: [ "      |   | | " : TEXT ]
349: [ "
" : NEWLINE ]
350: [ "      |   | +--<a" : TEXT ]
351: [ ">" : LINK_FINISH ]
352: [ "
" : NEWLINE ]
353: [ "      |   | " : TEXT ]
354: [ "
" : NEWLINE ]
355: [ "      |   +--<li" : TEXT ]
356: [ ">" : LINK_FINISH ]
357: [ "
" : NEWLINE ]
358: [ "      |   | | " : TEXT ]
359: [ "
" : NEWLINE ]
360: [ "      |   | +--<a" : TEXT ]
361: [ ">" : LINK_FINISH ]
362: [ "
" : NEWLINE ]
363: [ "      |   | " : TEXT ]
364: [ "
" : NEWLINE ]
365: [ "      |   +--<li" : TEXT ]
366: [ ">" : LINK_FINISH ]
367: [ "
" : NEWLINE ]
368: [ "      |     | " : TEXT ]
369: [ "
" : NEWLINE ]
370: [ "      |     +--<a" : TEXT ]
371: [ ">" : LINK_FINISH ]
372: [ "
" : NEWLINE ]
373: [ "      | " : TEXT ]
374: [ "
" : NEWLINE ]
375: [ "      +--<main" : TEXT ]
376: [ ">" : LINK_FINISH ]
377: [ "
" : NEWLINE ]
378: [ "      | | " : TEXT ]
379: [ "
" : NEWLINE ]
380: [ "      | +--<MACRO" : TEXT ]
381: [ ">" : LINK_FINISH ]
382: [ "
" : NEWLINE ]
383: [ "      | " : TEXT ]
384: [ "
" : NEWLINE ]
385: [ "      +--<footer" : TEXT ]
386: [ ">" : LINK_FINISH ]
387: [ "
" : NEWLINE ]
388: [ "        | " : TEXT ]
389: [ "
" : NEWLINE ]
390: [ "        +--<hr" : TEXT ]
391: [ ">" : LINK_FINISH ]
392: [ "
" : NEWLINE ]
393: [ "        | " : TEXT ]
394: [ "
" : NEWLINE ]
395: [ "        +--<small" : TEXT ]
396: [ ">" : LINK_FINISH ]
397: [ "]" : SPAN_OR_IMAGE_FINISH ]
398: [ "
" : NEWLINE ]
399: [ "        " : TEXT ]
400: [ "
" : NEWLINE ]
401: [ "Однако, хотя полученное дерево действительно можно назвать DOM, до полноценных jQuery, Jsoup, beautifulsoup или Gumbo нашему парсеру далеко, в частности потому, что он не может правильно обрабатывать текст, расположенный между парными тегами <style" : TEXT ]
402: [ ">" : LINK_FINISH ]
403: [ " и <script" : TEXT ]
404: [ ">" : LINK_FINISH ]
405: [ ", а потому исходников пока не привожу. Но обязательно добавлю, если хабровчане изъявят такое желание. Успехов." : TEXT ]
406: [ "

" : DOUBLE_NEWLINE ]
407: [ "P.S. Залил в публичный доступ " : TEXT ]
408: [ "<<" : LINK_START ]
409: [ "https://gitlab.com/2che/nyHTML" : TEXT ]
410: [ ">" : LINK_FINISH ]
411: [ "исходники" : TEXT ]
412: [ ">" : LINK_FINISH ]
413: [ ". Имхо, сыроватые, поэтому буду обстругивать до полноценной библиотеки." : TEXT ]
414: [ "
" : NEWLINE ]
415: [ "" : END ]


Синтаксическое дерево
<pre><article>
| 
+-<section>
  | 
  +-<p>
  | | 
  | +-@2che
  | | 
  | +-"\n"
  | 
  +->>442964
  | 
  +-<h1>
  | | 
  | +-"Искусство парсинга или DOM своими руками"
  | 
  +-<p>
  | | 
  | +-"Привет, Хабр! Недавно я задался идеей создать простой я..."
  | | 
  | +-<i>
  | | | 
  | | +-"синтаксический анализатор"
  | | 
  | +-", проще говоря — "
  | | 
  | +-<i>
  | | | 
  | | +-"парсер"
  | | 
  | +-". Поскольку я привык делать велосипеды, то направился в..."
  | 
  +-<p>
  | | 
  | +-"Сразу оговорюсь, — если ваша цель — свой скриптовый яз..."
  | 
  +-<p>
  | | 
  | +-"Прежде всего, парсинг, или "
  | | 
  | +-<i>
  | | | 
  | | +-"синтаксический разбор"
  | | 
  | +-" — не синоним полного процесса превращения текста в об..."
  | | 
  | +-"\n"
  | | 
  | +-<b>
  | | | 
  | | +-"Лексический разбор"
  | | 
  | +-" текста на токены — небольшие куски этого текста, имею�..."
  | | 
  | +-"\n"
  | | 
  | +-<b>
  | | | 
  | | +-"Синтаксический разбор"
  | | 
  | +-" — построение из токенов на основе их значений "
  | | 
  | +-<i>
  | | | 
  | | +-"абстрактного синтаксического дерева"
  | | 
  | +-" (AST — abstract syntax tree), или "
  | | 
  | +-<i>
  | | | 
  | | +-"объектной модели документа"
  | | 
  | +-" (DOM — document object model)."
  | 
  +-<p>
  | | 
  | +-"Но давайте по порядку. Перед тем, как открывать свою лю�..."
  | | 
  | +-<i>
  | | | 
  | | +-"форма Бэкуса-Наура (БНФ)"
  | | 
  | +-" и "
  | | 
  | +-<i>
  | | | 
  | | +-"расширенная форма Бэкуса-Наура"
  | | 
  | +-". Я использовал их симбиоз, взяв лучшее от обеих форм. Л�..."
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"<сумма"
  |   | 
  |   +-">"
  |   | 
  |   +-" = <выражение_1"
  |   | 
  |   +-">"
  |   | 
  |   +-" <знак_плюс"
  |   | 
  |   +-">"
  |   | 
  |   +-" <выражение_2"
  |   | 
  |   +-">"
  | 
  +-<p>
  | | 
  | +-"Здесь одно выражение определено через три других, след..."
  | 
  +-<p>
  | | 
  | +-"Когда же остановиться?"
  | 
  +-<p>
  | | 
  | +-"Описание синтаксиса любого языка в формальных граммат..."
  | | 
  | +-<i>
  | | | 
  | | +-"терминалов"
  | | 
  | +-" и "
  | | 
  | +-<i>
  | | | 
  | | +-"нетерминалов"
  | | 
  | +-". "
  | | 
  | +-<b>
  | | | 
  | | +-"Нетерминалы"
  | | 
  | +-" — выражения, требующие определения:"
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"<выражение_1"
  |   | 
  |   +-">"
  |   | 
  |   +-" = <число"
  |   | 
  |   +-">"
  |   | 
  |   +-" (<знак_умножения"
  |   | 
  |   +-">"
  |   | 
  |   +-" | <знак_деления"
  |   | 
  |   +-">"
  |   | 
  |   +-") <число"
  |   | 
  |   +-">"
  | 
  +-<p>
  | | 
  | +-<b>
  | | | 
  | | +-"Терминалы"
  | | 
  | +-" самодостаточны, их не нужно определять. Выше приведён�..."
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"<сумма"
  |   | 
  |   +-">"
  |   | 
  |   +-" = <выражение_1"
  |   | 
  |   +-">"
  |   | 
  |   +-" "+" <выражение_2"
  |   | 
  |   +-">"
  |   | 
  |   +-"\n"
  |   | 
  |   +-"<выражение_1"
  |   | 
  |   +-">"
  |   | 
  |   +-" = <число"
  |   | 
  |   +-">"
  |   | 
  |   +-" ("*" | "/") <число"
  |   | 
  |   +-">"
  | 
  +-<p>
  | | 
  | +-"где "+", "*", "/" — терминалы."
  | | 
  | +-"\n"
  | | 
  | +-"Выделить из грамматики терминалы нужно сразу, можно да..."
  | 
  +-<p>
  | | 
  | +-"Полное описание БНФ доступно в Википедии "
  | | 
  | +-<a>
  | | | 
  | | +-"здесь"
  | | 
  | +-" и "
  | | 
  | +-<a>
  | | | 
  | | +-"здесь"
  | | 
  | +-". Составление грамматики языка — важная стадия создан�..."
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Когда грамматика готова, можно приступать к лексическ�..."
  | | 
  | +-">"
  | | 
  | +-"". И для всех таких объединений нужен свой case. Как такое ..."
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"enum Token_type {"
  |   | 
  |   +-"\n"
  |   | 
  |   +-"    END = 1, TEXT = 2,"
  |   | 
  |   +-"\n"
  |   | 
  |   +-"    OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO..."
  |   | 
  |   +-"\n"
  |   | 
  |   +-"    ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBL..."
  |   | 
  |   +-"\n"
  |   | 
  |   +-"};"
  | 
  +-<p>
  | | 
  | +-"Урезанная процедура process:"
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Проверяем с помощью switch тип ожидаемого токена (или ток�..."
  | | 
  | +-"\n"
  | 
  +-<p>
  | | 
  | +-<img />
  | 
  +-<p>
  | | 
  | +-"Вначале ориентироваться в грамматике сложно, но со вре..."
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Первому ожидаемому токену очевидно необходимо задать ..."
  | 
  +-<p>
  | | 
  | +-"Для примера я взял один из своих шаблонов HTML-документа ..."
  | | 
  | +-">"
  | | 
  | +-"": <тип_токена"
  | | 
  | +-">"
  | | 
  | +-" "
  | | 
  | +-"]"
  | | 
  | +-"". Вот что получилось:"
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<mark>
  | | | 
  | | +-"Сам документ"
  | | | 
  | | +-<pre>
  | |   | 
  | |   +-"stub"
  | | 
  | +-"\n"
  | | 
  | +-<mark>
  |   | 
  |   +-"Список токенов"
  |   | 
  |   +-<pre>
  |     | 
  |     +-"stub"
  | 
  +-<p>
  | | 
  | +-"Теперь мы готовы приступить ко второй части — построе�..."
  | 
  +-<p>
  | | 
  | +-"Сколько нужно классов для реализации всех свойств HTML-э..."
  | 
  +-<p>
  | | 
  | +-"В идеале — по одному классу для каждого элемента, чтоб�..."
  | | 
  | +-">"
  | | 
  | +-", <li"
  | | 
  | +-">"
  | | 
  | +-", <strong"
  | | 
  | +-">"
  | | 
  | +-" и др, чтобы отсеять токены с неразмеченным текстом. Те�..."
  | | 
  | +-<i>
  | | | 
  | | +-"нисходящим синтаксическим разбором"
  | | 
  | +-"."
  | 
  +-<p>
  | | 
  | +-"Процедура парсинга:"
  | | 
  | +-"\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Вот и всё! Если вы всё сделали правильно, полученное де�..."
  | | 
  | +-"\n"
  | | 
  | +-<pre>
  | | | 
  | | +-"| "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"+--<ROOT"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"  | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"  +--<!DOCTYPE"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"  | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"  +--<html"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    +--<head"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<meta"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<title"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<link"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<link"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | +--<COMMENT"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"    +--<body"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      +--<header"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | +--<div"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      +--<nav"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | +--<ul"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   +--<li"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | +--<a"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   +--<li"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | +--<a"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |   +--<li"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |     | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      |     +--<a"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      +--<main"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | +--<MACRO"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"      +--<footer"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"        | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"        +--<hr"
  | | | 
  | | +-">"
  | | | 
  | | +-"\n"
  | | | 
  | | +-"        | "
  | | | 
  | | +-"\n"
  | | | 
  | | +-"        +--<small"
  | | | 
  | | +-">"
  | | 
  | +-"\n"
  | | 
  | +-"        "
  | | 
  | +-"\n"
  | | 
  | +-"Однако, хотя полученное дерево действительно можно на�..."
  | | 
  | +-">"
  | | 
  | +-" и <script"
  | | 
  | +-">"
  | | 
  | +-", а потому исходников пока не привожу. Но обязательно д�..."
  | 
  +-<p>
    | 
    +-"P.S. Залил в публичный доступ "
    | 
    +-<a>
    | | 
    | +-"исходники"
    | 
    +-". Имхо, сыроватые, поэтому буду обстругивать до полноце..."
    | 
    +-"\n"
</pre>

Всё здорово, но текстовых нод, идущих цепочкой друг за другом, слишком много. К тому же, я бы хотел, чтобы цитаты, размещённые подряд, соединялись в одну. Для этого нам нужно пройти по дереву в глубину ещё раз и выполнить конкатенацию, т.е., сцепление однородных элементов друг с другом. Детали этого процесса объяснять не буду, прикреплю исходники, а пока просто посмотрите, как изменилось наше

Дерево после конкатенации:
<pre><article>
| 
+-<section>
  | 
  +-<p>
  | | 
  | +-@2che
  | | 
  | +-"\n"
  | 
  +->>442964
  | 
  +-<h1>
  | | 
  | +-"Искусство парсинга или DOM своими руками"
  | 
  +-<p>
  | | 
  | +-"Привет, Хабр! Недавно я задался идеей создать простой я..."
  | | 
  | +-<i>
  | | | 
  | | +-"синтаксический анализатор"
  | | 
  | +-", проще говоря — "
  | | 
  | +-<i>
  | | | 
  | | +-"парсер"
  | | 
  | +-". Поскольку я привык делать велосипеды, то направился в..."
  | 
  +-<p>
  | | 
  | +-"Сразу оговорюсь, — если ваша цель — свой скриптовый яз..."
  | 
  +-<p>
  | | 
  | +-"Прежде всего, парсинг, или "
  | | 
  | +-<i>
  | | | 
  | | +-"синтаксический разбор"
  | | 
  | +-" — не синоним полного процесса превращения текста в об..."
  | | 
  | +-<b>
  | | | 
  | | +-"Лексический разбор"
  | | 
  | +-" текста на токены — небольшие куски этого текста, имею�..."
  | | 
  | +-<b>
  | | | 
  | | +-"Синтаксический разбор"
  | | 
  | +-" — построение из токенов на основе их значений "
  | | 
  | +-<i>
  | | | 
  | | +-"абстрактного синтаксического дерева"
  | | 
  | +-" (AST — abstract syntax tree), или "
  | | 
  | +-<i>
  | | | 
  | | +-"объектной модели документа"
  | | 
  | +-" (DOM — document object model)."
  | 
  +-<p>
  | | 
  | +-"Но давайте по порядку. Перед тем, как открывать свою лю�..."
  | | 
  | +-<i>
  | | | 
  | | +-"форма Бэкуса-Наура (БНФ)"
  | | 
  | +-" и "
  | | 
  | +-<i>
  | | | 
  | | +-"расширенная форма Бэкуса-Наура"
  | | 
  | +-". Я использовал их симбиоз, взяв лучшее от обеих форм. Л�..."
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"<сумма> = <выражение_1> <знак_плюс> <выражение_2>"
  | 
  +-<p>
  | | 
  | +-"Здесь одно выражение определено через три других, след..."
  | 
  +-<p>
  | | 
  | +-"Когда же остановиться?"
  | 
  +-<p>
  | | 
  | +-"Описание синтаксиса любого языка в формальных граммат..."
  | | 
  | +-<i>
  | | | 
  | | +-"терминалов"
  | | 
  | +-" и "
  | | 
  | +-<i>
  | | | 
  | | +-"нетерминалов"
  | | 
  | +-". "
  | | 
  | +-<b>
  | | | 
  | | +-"Нетерминалы"
  | | 
  | +-" — выражения, требующие определения:\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"<выражение_1> = <число> (<знак_умножения> | <знак_деления>) <�..."
  | 
  +-<p>
  | | 
  | +-<b>
  | | | 
  | | +-"Терминалы"
  | | 
  | +-" самодостаточны, их не нужно определять. Выше приведён�..."
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"<сумма> = <выражение_1> "+" <выражение_2>\n<выражение_1> = <числ..."
  | 
  +-<p>
  | | 
  | +-"где "+", "*", "/" — терминалы.\nВыделить из грамматики терми�..."
  | 
  +-<p>
  | | 
  | +-"Полное описание БНФ доступно в Википедии "
  | | 
  | +-<a>
  | | | 
  | | +-"здесь"
  | | 
  | +-" и "
  | | 
  | +-<a>
  | | | 
  | | +-"здесь"
  | | 
  | +-". Составление грамматики языка — важная стадия создан�..."
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Когда грамматика готова, можно приступать к лексическ�..."
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"enum Token_type {\n    END = 1, TEXT = 2,\n    OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = ..."
  | 
  +-<p>
  | | 
  | +-"Урезанная процедура process:\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Проверяем с помощью switch тип ожидаемого токена (или ток�..."
  | 
  +-<p>
  | | 
  | +-<img />
  | 
  +-<p>
  | | 
  | +-"Вначале ориентироваться в грамматике сложно, но со вре..."
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Первому ожидаемому токену очевидно необходимо задать ..."
  | 
  +-<p>
  | | 
  | +-"Для примера я взял один из своих шаблонов HTML-документа ..."
  | 
  +-<blockquote>
  | | 
  | +-<mark>
  | | | 
  | | +-"Сам документ"
  | | | 
  | | +-<pre>
  | |   | 
  | |   +-"stub"
  | | 
  | +-"\n"
  | | 
  | +-<mark>
  |   | 
  |   +-"Список токенов"
  |   | 
  |   +-<pre>
  |     | 
  |     +-"stub"
  | 
  +-<p>
  | | 
  | +-"Теперь мы готовы приступить ко второй части — построе�..."
  | 
  +-<p>
  | | 
  | +-"Сколько нужно классов для реализации всех свойств HTML-э..."
  | 
  +-<p>
  | | 
  | +-"В идеале — по одному классу для каждого элемента, чтоб�..."
  | | 
  | +-<i>
  | | | 
  | | +-"нисходящим синтаксическим разбором"
  | | 
  | +-"."
  | 
  +-<p>
  | | 
  | +-"Процедура парсинга:\n"
  | 
  +-<blockquote>
  | | 
  | +-<pre>
  |   | 
  |   +-"stub"
  | 
  +-<p>
  | | 
  | +-"Вот и всё! Если вы всё сделали правильно, полученное де�..."
  | | 
  | +-<pre>
  | | | 
  | | +-"| \n+--<ROOT>\n  | \n  +--<!DOCTYPE>\n  | \n  +--<html>\n    | \n    +--<head>\n    | | \n    | +--<..."
  | | 
  | +-"\n        \nОднако, хотя полученное дерево действительно мо..."
  | 
  +-<p>
    | 
    +-"P.S. Залил в публичный доступ "
    | 
    +-<a>
    | | 
    | +-"исходники"
    | 
    +-". Имхо, сыроватые, поэтому буду обстругивать до полноце..."
</pre>

Остался последний шаг — представление этого дерева в HTML-форме. Здесь всё просто: Создаём строку в методе корня с началом первичной разметки (открывающие элементы html и body, блок head) и начинаем присоединять возвращённые строки от аналогичных элементов детей. Тут мы снова имеем дело с рекурсивным спуском: каждый класс при вызове виртуального метода to_HTML() создаёт строку, помещает в неё свою первичную разметку, затем вызывает тот же метод у каждого своего потомка, соединяет строки, дополняет первичную разметку и возвращает вызвавшему родителю. Вот, например, как выглядит данный метод для класса Inline (сочетающего в себе форматированные встроенные элементы):

string Inline::to_HTML (const unsigned int &level) {
    string HTML;

// ****** НАЧАЛО ПЕРВИЧНОЙ РАЗМЕТКИ - ОТКРЫВАЮЩИЙ ТЕГ ******
    switch (type) {
    case BOLD: {
        HTML.append("<b>");
    break; }
    case ITALIC: {
        HTML.append("<i>");
    break; }
    case UNDERLINED: {
        HTML.append("<ins>");
    break; }
    case OVERLINED: {
        HTML.append("<span class=\"overlined\">");
    break; }
    case THROWLINED: {
        HTML.append("<del>");
    break; }
    case SUBSCRIPT: {
        HTML.append("<sub>");
    break; }
    case SUPERSCRIPT: {
        HTML.append("<sup>");
    break; }
    case MARKED: {
        HTML.append("<mark>");
    break; }
    case MONOSPACE: {
        HTML.append("<pre>");
    break; }
    default:
        throw string("invalid inline type: " + type_str() + "!");
    }
// ***   ***   ***   ***

// ****** РЕКУРСИВНЫЙ СПУСК - КОНТЕНТ МЕЖДУ ТЕГАМИ ******
    for (unsigned long i(0); i < children_count; i++)
        HTML.append(children[i]->to_HTML(level+1));
// ***   ***   ***   ***

// ****** КОНЕЦ ПЕРВИЧНОЙ РАЗМЕТКИ - ЗАКРЫВАЮЩИЙ ТЕГ ******
    switch (type) {
    case BOLD: {
        HTML.append("</b>");
    break; }
    case ITALIC: {
        HTML.append("</i>");
    break; }
    case UNDERLINED: {
        HTML.append("</ins>");
    break; }
    case OVERLINED: {
        HTML.append("</span>");
    break; }
    case THROWLINED: {
        HTML.append("</del>");
    break; }
    case SUBSCRIPT: {
        HTML.append("</sub>");
    break; }
    case SUPERSCRIPT: {
        HTML.append("</sup>");
    break; }
    case MARKED: {
        HTML.append("</mark>");
    break; }
    case MONOSPACE: {
        HTML.append("</pre>");
    break; }
    default:
        throw string("invalid inline type: " + type_str() + "!");
    }
// ***   ***   ***   ***

    return HTML;
}

На этом всё. Надеюсь, теперь, прочитав обе статьи, вы запросто реализуете транслятор для вашего языка разметки или программирования. Если остались вопросы — задавайте в комментариях. А вот исходники. Успехов.

P. S. Забыл упомянуть про экранирование. Оно реализуется просто: если очередной символ в процедуре лексического разбора — обратный слэш ("\"), он игнорируется и обрабатывается следующий символ, но кроме него в функцию обработки символа посылается булево значение true, дающее команду экранировать. Тогда, если этот символ, например, "[", его особое значение игнорируется, и он просто присоединяется к строящемуся токену как текст. В ином случае в функцию подаётся значение false и символ обрабатывается как обычно.
Источник: https://habr.com/ru/post/444876/#habracut

Интересные статьи

Интересные статьи

В Челябинске проходят митапы системных администраторов Sysadminka, и на последнем из них я делал доклад о нашем решении для работы приложений на 1С-Битрикс в Kubernetes. Битрикс, Kubernetes, Сep...
Автокэширование в 1с-Битрикс — хорошо развитая и довольно сложная система, позволяющая в разы уменьшить число обращений к базе данных и ускорить выполнение страниц.
Одной из «киллер-фич» 12й версии Битрикса была объявлена возможность отдавать статические файлы из CDN, тем самым увеличивая скорость работы сайта. Попробуем оценить практический выигрыш от использова...
Мы публикуем видео с прошедшего мероприятия. Приятного просмотра.
Согласно многочисленным исследованиям поведения пользователей на сайте, порядка 25% посетителей покидают ресурс, если страница грузится более 4 секунд.