+БОНУС: как включать классы друг в друга в 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", "nn", "> ", ">>...", "###...[", "*[", "%[", "_[", "^[", "~[", "&[", "+[", "=[", "`[", "]", "<<", "[<", ">", " @... ", "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 и символ обрабатывается как обычно.
Автор: James Soifer
