Хабрахабр

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

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

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

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

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

...
<ordered_list_item> = <number_marker> <div>
<number_marker> = <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.

В заголовке с расширением .h или .hpp — объявление, в исходнике с расширением .cpp — определение, так? Все знают, что хорошим тоном в программировании на C++ является разделение классов на объявление и определение? Ведь то, что мы прописываем в файле с расширением .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. Данный способ не единственный, но самый простой, по моему мнению.

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

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

Итак, мы добрались до построения абстрактного синтаксического дерева. В прошлой статье функция уместилась в 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, проверяющее тип открытого узла. Я в качестве такого документа взял предыдущую статью, самый первый поступивший токен — начало заголовка. Можно создать типовый документ, размеченный вашим языком / содержащий сценарий на вашем языке и реализовывать условия по ходу документа, проверяя результат выводом псевдографического дерева в терминал. Следом идут текст заголовка и закрывающая квадратная скобка, обрабатываем токены типов TEXT и SPAN_OR_IMAGE_FINISH. Значит, обрабатываем токен с типом TITLE_START.

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

<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;
}

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть