+БОНУС: взаимное включение классов друг в друга в C++
Привет, Хабр! Эта статья — прямое продолжение статьи Искусство парсинга или DOM собственными руками, где мы разобрали HTML-документ и построили на его основе абстрактное синтаксическое дерево (AST) с доступом к любому элементу через индексацию при помощи лишь стандартной библиотеки C++, проще говоря, научились самостоятельно парсить XML-подобные штуки. Напомню, что процесс парсинга, или синтаксического анализа/разбора состоит из двух этапов: лексического разбора (разбора текста на токены) и построения AST. Если первый мы рассмотрели очень подробно, с примерами и исходниками, то описание второго похоже на пустую куколку бабочки, у которой есть только оболочка, а прекрасное содержимое автор извлёк перед публикацией. На то была причина, для HTML построить дерево действительно просто, нужно всего 4 класса: пустой тег, блок, текстовый узел и корень документа, наследуемый от блока. Сегодня мы оставим такую простоту позади и построим дерево, где свойства элементов, и пустых, и блочных, будут содержаться не в атрибутах тегов, а непосредственно в классах, а для этого классов придётся создать много. Действительно много. Строить будем не из простых известных языков разметки, а создадим свой, с правилами, показанными на изображении под катом. Плюс в конце ещё переведём, или, говоря правильнее, транслитируем документ с предыдущей статьёй, размеченной нашим языком, в HTML, а в качестве бонуса я отвечу начинающим программистам C++ на тривиальный, но труднонаходимый вопрос: как включать классы «друг в друга»?
![](https://habrastorage.org/webt/gp/bv/er/gpbverq2xlourlzxmmmhghayhem.png)
Примечания в грамматике
Прежде чем мы перейдём непосредственно к построению дерева, давайте освежим память и уясним некоторые детали предварительной работы. Вы ещё помните, что весь синтаксис языка нужно прописать в форме одной из контекстно-свободных формальных грамматик, например, БНФ? Вот только начинающим программистам трудно сразу их освоить, да и к тому же, не все возможные правила этими грамматиками можно описать. В таких случаях, если вы зашли в тупик и никак не сформулируете определённое правила в правильной форме, можно записать его как замечания на естественном человеческом языке, например, так:
...
<ordered_list_item> = <number_marker> <div>
<number_marker> = <number> "." {<number> "."} " "
<number> = <digit> {<digit>}
!! link ending ">" and image/span ending "]" can't follow "\n" or document start
Перевод: окончания ссылки ">" и изображения/встроенного элемента "]" не могут следовать сразу за началом строки или документа.
То есть, если в начале строки лексер встретит "]" или ">", мы должны дать ему установку проигнорировать особое значение этих символов и работать с ними как с обычным текстом. Такой способ добавления замечаний в грамматику не единственный, вы можете делать это по своему. В конце концов, файл с описанием синтаксиса — не курсовая работа, никто не заставляет соблюдать все правила и важно только, чтобы именно вам было удобно с ним работать. Главное, не забывать о сделанных замечаниях и отразить их в нужных участках кода.
Давайте рассмотрим полное описание данного языка:
<article> = {<article_item>}
<article_item> = <underline> | <section>
(* ARTICLE ITEMS *)
<underline> = "___" {"_"} "\n"
<section> = <div> {<div>}
<div> = <paragraphs> | <title> | <quote> | <cite> | <unordered_list> | <ordered_list>
(* SECTION ITEMS *)
<paragraphs> = <paragraph> {"\n" <paragraph>}
<paragraph> = <span> {<span>} ("\n" | <END>)
<span> = <bold> | <italic> | <underlined> | <overlined> | <throwlined> | <subscript> | <superscript> | <marked> | <monospace> | <text> | <image> | <link> | <notification>
<title> = <number signs> <left_angle_bracket> {<span>} <right_angle_bracket> ("\n" | <END>)
<number signs> "######" | "#####" | "####" | "###" | "##" | "#"
<quote> = "> " {<span>} ("\n" | <END>)
<cite> = ">>" <number> ("\n" | <END>)
<number> = <digit> {<digit>}
(* PARAGRAPH ITEMS *)
<bold> = "*[" {<span>} "]"
<italic> = "%[" {<span>} "]"
<underlined> = "_[" {<span>} "]"
<overlined> = "^[" {<span>} "]"
<throwlined> = "~[" {<span>} "]"
<subscript> = "&[" {<span>} "]"
<superscript> = "+[" {<span>} "]"
<marked> = "=[" {<span>} "]"
<monospace> = "`[" {<span>} "]"
<text> = <textline> "\n" {<textline> "\n"}
<textline> = <symbol> {<symbol>}
<symbol> = /^[\n]/
<link> = "<<" <text> ">" {<span>} ">"
<image> = "[<" <text> ">" [<text>] "]"
<notification> = (" " | "\n") "@" <word> (" " | "\n" | <END>)
<word> = (<letter> | <digit>) {<letter> | <digit>}
<letter> = "a" | "b" | "c" | "d" | ... | "_" | "-"
<digit> = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
(* LISTS *)
<unordered_list> = <unordered_list_item> {<unordered_list_item>}
<ordered_list> = <ordered_list_item> {<ordered_list_item>}
<unordered_list_item> = <marker> <div>
<marker> = ("*" {"*"}) | ("+" {"+"}) " "
<ordered_list_item> = <number_marker> <div>
<number_marker> = <number> "." {<number> "."} " "
<number> = <digit> {<digit>}
!! link ending ">" and image/span ending "]" can't follow "\n" or document start
В прошлый раз нужно было выписать терминалы и проверять каждый входящий символ на соответствие одному из них. Но тогда терминалы были односимвольные! Теперь необходимо кроме выделения терминалов разделить их самих на ключи — то есть, символы. Почему «ключи»? Они имеют ключевое значение для лексера. В результате всех действий у нас в файле с грамматикой появятся строчки:
(* TERMINALS *)
"___...", "\n", "\n\n", "> ", ">>...", "###...[", "*[", "%[", "_[", "^[", "~[", "&[", "+[", "=[", "`[", "]", "<<", "[<", ">", " @... ", "\n@...\n", " @...\n", "\n@... ", "***... ", "+++... ", "123.56. "
(* KEYS *)
"_", "\n" ">", "#", "*", "%", "^", "~", "&", "+", "=", "`", "<", "[", "]", " ", "@", "1..9", ".", <END>
Стек ожидаемых типов токенов
В прошлый раз, опять же, всё было проще, у нас было всего 10 типов токенов, не считая конца, и было меньше шансов запутаться в этом зоопарке лексем. Теперь типов, очевидно, больше. Напомню, что задача лексера — оставить парсеру как можно меньше работы, в идеале, лишь построение дерева. Поэтому набор типов токенов должен как можно точнее отражать их сущность. В первой статье я привёл пример хорошего набора, в этой приведу его вместе с «антипримером». Видите терминалы, начинающие встроенные текстовые элементы (полужирный — bold, курсив — italic и т.д.)? Мы могли бы разобрать их на пару токенов: ведущий ("*", "%" и др.) и ведомый ("[") и в такой форме передать парсеру. Легко догадаться, что лучше сделать точное определение текстового элемента на уровне лексера, т.е. определить "*[" как «bold_start», "%[" как «italic_start» и и.д. Чем больше типов и чем точнее они отражают самих себя — тем лучше. При этом второе важнее первого. Например, мы могли бы разобрать нотификацию на символ "@" и имя пользователя, но, очевидно, лучше оставить их совмещёнными в одной лексеме.
Ну вот мы определились с типами. С чего начать процедуру разбора текста на токены? Как и тогда, начните с начала. Что может следовать сразу за началом разбираемого документа? Не спешите загибать пальцы. В отличие от HTML, все 22 типа здесь могут дать старт. Ничего страшного, вооружившись битовой унификацией, так и пишем:
curr_token_type = TEXT | UNDERLINE | TITLE_START | QUOTE_START | CITE | BOLD_START | ...
а в функции обработки символа:
case TEXT | UNDERLINE | TITLE_START | QUOTE_START | CITE | ...
Если не понимаете, о чём идёт речь, прочитайте первую статью.
Не бойтесь длинного обобщённого типа ожидаемого токена. Первый символ строки сразу сократит его длину до 2-4 типов. Так как наши терминалы многосимвольны, определение идёт по ключам.
Всё просто, посмотрите сами:
if (c == '_') {
buffer.push_back('_');
curr_token_type = TEXT | UNDERLINE | UNDERLINED_START;
Нижнее подчёркивание сразу определило строящийся токен к одному из трёх типов: простого текста, горизонтальной черте или начало подчёркнутого текста ("_[").
Возвращаясь к проблеме, как уследить за всеми обобщёнными типами и не забыть обработать их все? Заведите стек… в блокноте! Именно так, записывайте все обобщённые типы, появляющиеся после «curr_token_type = ...» в список, и после обработки одного берите из этого списка другой с конца. Можно организовать работу со списком и как с очередью, это большого значения не имеет. Главное, что так вы не забудете, какие типы уже обработаны, а какие ещё предстоит обработать.
Дерево классов
Наконец, мы добрались до синтаксического разбора. Здесь нужно определиться с классами нод (узлов) будущего дерева точно так же, как мы определялись с типами токенов. Для этого снова откройте блокнот и напишите следущее:
Node { Node * parent, Node_type type } #-
Root { Root_item[] children, ulong children_count }
Так мы определили будущий базовый класс всех нод и его производный — корень дерева, то есть, сам документ. Документ (см. БНФ выше) состоит из двух типов нод: раздела (section) и горизонтальной линии (underline). Определим для них базовый класс Root_item и опишем каждый так же, как мы описали корень. Кроме того, здесь же, в блокноте, сразу указываем все другие поля классов, если они есть. Для корня это число «детей» — т.е. внутренних разделов и горизонтальных линий. Раздел состоит из элементов, для которых мы определим базовый класс Div и так далее, двигаясь рекурсивно по грамматике, определим все нужные классы. Перед тем, как писать код, определим здесь же все включения заголовков. Это просто: все прямые наследники базовых обобщённых классов должны включаться в содержащие их классы.
Обозначим эти зависимости в виде списков после решётки, и у нас получится такой документ:
Node { Node * parent, Node_type type } #-
Root { Root_item[] children, ulong children_count } #Underline, #Section
Root_item {} #-
Underline {}
Section { Div[] children, ulong children_count } #Paragraph, #Title, #Quote, #Cite, #Unordered_list, #Ordered_list
Div {} #-
Paragraph { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Title { char level, Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Quote { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Cite { ulong number } #-
Unordered_list { Div } #Paragraph, #Title, #Quote, #Cite, #Ordered_list
Ordered_list { Div } #Paragraph, #Title, #Quote, #Cite, Unordered list
Span {} #-
Bold { Span[] children, ulong children_count } #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Italic { Span[] children, ulong children_count } #Bold, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Underlined { Span[] children, ulong children_count } #Bold, #Italic, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Overlined { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Throwlined { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Subscript { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Superscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Superscript { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Marked, #Monospace, #Text, #Image, #Link, #Notification
Marked { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Monospace, #Text, #Image, #Link, #Notification
Monospace { Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Text, #Image, #Link, #Notification
Text { string text } #-
Image { string src, string alt } #-
Link { string URL, Span[] children, ulong children_count } #Bold, #Italic, #Underlined, #Overlined, #Throwlined, #Subscript, #Superscript, #Marked, #Monospace, #Text, #Image, #Notification
Notification { string user } #-
Здесь я пометил "#-" отсутствие зависимостей и убрал включения классов в самих себя.
Замечаем, что все классы встроенного форматирования (Bold, Italic, ...) зависимы друг от друга и, кроме того, от класса Link, который так же зависим от них! В похожем положении находятся Unordered_list и Ordered_list. Включение заголовков друг в друга не просто приведёт к игнорированию одного из них, как ожидалось бы, но и не пройдёт валидацию препроцессором, а одностороннее включение не позволит нам объявить внутри включаемого класса функцию открытия элемента класса включающего и возвращения ссылки на оный. Как быть? Есть два способа.
Включение классов друг в друга
Сначала посмотрим на классы Bold, Italic и так до Monospace. Они похожи. Настолько, что могут быть объединены в один класс «Inline». Возможно, такое решение вызовет сомнения. У меня тоже вызывало, но на практике различие между ними влияло лишь на форму представления в виде дерева в терминале и на теги в HTML. Если вы видите, что некоторые классы содержат одинаковые поля, имеют одинаковые зависимости и вообще схожее описание в формальной грамматике, смело объединяйте их. Так вы облегчите работу себе и процессору.
Но такой трюк не пройдёт с классом Link, ведь он содержит дополнительное поле — строку URL. Воспользуемся вторым способом.
Все знают, что хорошим тоном в программировании на C++ является разделение классов на объявление и определение? В заголовке с расширением .h или .hpp — объявление, в исходнике с расширением .cpp — определение, так? А теперь обращаюсь к новичкам в программировании: сядьте и пристегните ремни безопасности, потому что будет неприятно. Ведь то, что мы прописываем в файле с расширением .h — не что иное, как определение класса. А в файле .cpp — уже реализация методов этого класса. Не понятно? В школе нас обманывали. Класс объявляется так же, как функция, одной строкой, если не содержит шаблонов.
Даже проще функции, ведь у него нет аргументов. Вот типичное объявление класса:
class MyClass;
И всё! А объявления полей и методов — уже его определение.
Этим мы и воспользуемся. Включим заголовок класса Inline в заголовок класса Link, а в нём самом объявим класс Link перед определением класса Inline. Выглядеть файл inline.h должен так:
#ifndef INLINE_H
#define INLINE_H
#include "AST/span.h"
#include "AST/text.h"
#include "AST/image.h"
#include "AST/notification.h"
class Link;
class Inline : public Span {
public:
static const unsigned long MAX_CHILDREN_COUNT = 0xFFFFFF;
private:
Span ** children;
unsigned long children_count;
unsigned long extended;
void extend();
public:
Inline(const Node * parent, const Node_type &type);
Inline(const Span * span);
~Inline();
Inline * add_text(const string &text);
Inline * add_image(const string &src, const string &alt);
Inline * add_notification(const string &user);
Link * open_link(const string &URL);
...
Класс Inline ещё ничего не знает о классе Link, о его полях и методах, но точно знает о его существовании. Поэтому мы можем объявлять методы, возвращающие указатель на объект класса Link, либо принимающие его в качестве аргумента. Слово указатель выделено не случайно, класс Inline ещё не умеет строить объекты типа Link, так как не имеет доступа к его конструктору, зато может работать со всеми указателями, т.к. у них у всех одинаковый интерфейс. Но нам здесь объекты и не нужны. А вот в реализации метода open_link создаётся объект типа Link и возвращается указатель на него, а значит, к моменту вхождения препроцессора в этот метод конструктор и остальные методы Link, которые могут понадобиться методу open_link, должны быть объявлены. Здесь воспользуемся преимуществом разделения исходного кода на отдельные файлы с заголовками и реализацией. В файл inline.cpp включён («подинклюден») файл inline.h, но файл link.h не включён в inline.h. Значит, включение его в inline.cpp будет первым включением для препроцессора. Тогда файл inline.cpp будет начинаться так:
#include "inline.h"
#include "link.h"
...
Повторю всё вышесказанное. Заголовок класса A.h включаем в заголовок класса B.h как обычно, а класс B объявляем перед классом A и включаем его заголовок в исходник A.cpp. Данный способ не единственный, но самый простой, по моему мнению.
Замечу, что такое взаимное включение классов не мешает наследовать класс B от класса A, если именно его объявление мы записали перед определением класса A. Именно так я и сделал, унаследовав Ordered_list от Unordered_list.
Построение дерева
Итак, мы добрались до построения абстрактного синтаксического дерева. В прошлой статье функция уместилась в 50 строк. Спойлер: на этот раз она выросла почти до 1400. Принцип работы тот же: проверяем тип каждого токена и в зависимости от него выполняем определённый участок кода, храня в памяти открытый узел дерева. Вот только если для разбора HTML почти все участки содержали одну и только одну из трёх команд: добавить пустой узел внутрь открытого, открыть новый узел в открытом и закрыть открытый узел, вернув его родителя, то здесь нужное действие ещё зависит от типа открытого узла. Например, если на обработку поступил токен «горизонтальная линия», а открытый узел — корень документа, то всё, что нужно, — добавить в этот открытый узел с помощью кастования и функции с условным названием add_line() линию, примерно так:
if (type == Node::ROOT)
static_case<Root*>(open_node)->add_line();
Но если открытый узел — абзац (Paragraph), то сначала нужно закрыть его и всех возможных предков (маркированные и нумерованные списки), пока открытый узел не станет иметь тип «раздел», а затем закрыть и его:
else if (type == Node::PARAGRAPH) {
open_node = static_cast<Paragraph*>(open_node)->close();
while (open_node->get_type() != Node::SECTION) {
if (open_node->get_type() == Node::UNORDERED_LIST)
open_node = static_cast<Unordered_list*>(open_node)->close();
else if (open_node->get_type() == Node::UNORDERED_LIST)
open_node = static_cast<Unordered_list*>(open_node)->close();
else if (open_node->get_type() == Node::PARAGRAPH)
open_node = static_cast<Paragraph*>(open_node)->close();
}
open_node = static_cast<Section*>(open_node)->close();
open_node = tree->add_line();
}
Если открытый узел — подпись к изображению, то горизонтальная линия вообще нарушает грамматику, и необходимо выбросить исключение, а если открытый узел — не ссылка, а входящий токен ">" имеет тип «LINK_FINISH», его следует обработать не как конец ссылки, а как текст и т.д.
Таким образом, дерево switch/case, проверяющее тип входящего токена, должно содержать ещё одно дерево switch/case, проверяющее тип открытого узла. Вначале за такую конструкцию сложно взяться, но не обязательно начинать с начала, с первого условия. Можно создать типовый документ, размеченный вашим языком / содержащий сценарий на вашем языке и реализовывать условия по ходу документа, проверяя результат выводом псевдографического дерева в терминал. Я в качестве такого документа взял предыдущую статью, самый первый поступивший токен — начало заголовка. Значит, обрабатываем токен с типом TITLE_START. Следом идут текст заголовка и закрывающая квадратная скобка, обрабатываем токены типов TEXT и SPAN_OR_IMAGE_FINISH.
После этого у нас уже получится такое мини-деревце:
<article>
|
+-<section>
|
+-<h1>
|
+-"Искусство парсинга или DOM своими руками"
По ходу дела вы заметите, что некоторые классы включают в себя одинаковые методы с одинаковыми алгоритмами. Например, классы абзаца Paragraph и цитаты Quote одинаково открывают ссылки и добавляют в себя текст. В таких случаях лучшим решением будет при рефакторинге создать один класс с данными методами и унаследовать от него нужные ноды. Я попытался такое реализовать, но моих навыков не хватило, и я запутался в неоднозначности при кастовании, поэтому просто привожу результаты работы лексера и парсера:
Сама статья
@2che
>>442964
#[Искусство парсинга или DOM своими руками]
Привет, Хабр! Недавно я задался идеей создать простой язык разметки наподобие markdown, который отлично подходил бы для моих задач, а именно — быстрого написания лекций с форматированием и возможностью вставки математических формул «на лету», с применением одной лишь клавиатуры. Чтобы перевести текст, написанный в таком формате, в более понятную форму, например, документ LibreOffice Writer, нужен %[синтаксический анализатор], проще говоря — %[парсер]. Поскольку я привык делать велосипеды, то направился в поисковые системы с запросами «parser example», «html to DOM», «how to parse html» и др. К моему разочарованию, на всех найденных ресурсах либо приводились элементарные примеры типа калькулятора Страуструпа с рекурсивным спуском, либо использовались готовые решения, такие как flex, bison, llvm и yacc. Библиотек, предназначенных для парсинга строго определённых языков, нашлось ещё больше (gumbo, jsoup, rapidjson, инструменты Qt и др.) Ни то, ни другое не входило в мои планы по написанию парсера своей разметки на C++ с использованием лишь стандартной библиотеки, поэтому моим источником знаний об искусстве парсинга вместо электронных ресурсов стали методички технических институтов. О том, как взять текст и построить из него AST (абстрактное синтаксическое дерево), о некоторых подводных камнях, на которые я натыкался в процессе, о возможных ошибках я сегодня и расскажу.
Сразу оговорюсь, — если ваша цель — свой скриптовый язык или что ещё сложнее, этой статьи будет недостаточно для его реализации. В идеале нужно на отлично знать теорию автоматов и дискретные структуры. Но в качестве отправной точки можно пока ограничиться и моим опытом, которым я щедро поделюсь под катом. Это не совсем то, что я задумывал изначально, зато идеально подходит для примера. Парсить мы будем HTML, как простой и всем знакомый язык.
Прежде всего, парсинг, или %[синтаксический разбор] — не синоним полного процесса превращения текста в объектную модель. Сам процесс состоит из двух этапов:
1. *[Лексический разбор] текста на токены — небольшие куски этого текста, имеющие определённое синтаксическое значение.
2. *[Синтаксический разбор] — построение из токенов на основе их значений %[абстрактного синтаксического дерева] (AST — abstract syntax tree), или %[объектной модели документа] (DOM — document object model).
Но давайте по порядку. Перед тем, как открывать свою любимую IDE и писать код, нужно разработать грамматику будущего языка. Из формальных контекстно-свободных грамматик самые известные — %[форма Бэкуса-Наура (БНФ)] и %[расширенная форма Бэкуса-Наура]. Я использовал их симбиоз, взяв лучшее от обеих форм. Любое выражение можно определить через другие выражения так:
> `[<сумма> = <выражение_1> <знак_плюс> <выражение_2>]
Здесь одно выражение определено через три других, следующих одно за другим. Их, в свою очередь, тоже необходимо представить через «третьи» выражения и т.д.
Когда же остановиться?
Описание синтаксиса любого языка в формальных грамматиках состоит из двух типов лексем: %[терминалов] и %[нетерминалов]. *[Нетерминалы] — выражения, требующие определения:
> `[<выражение_1> = <число> (<знак_умножения> | <знак_деления>) <число>]
*[Терминалы] самодостаточны, их не нужно определять. Выше приведённые примеры можно записать так:
> `[<сумма> = <выражение_1> "+" <выражение_2>
<выражение_1> = <число> ("*" | "/") <число>]
где "+", "*", "/" — терминалы.
Выделить из грамматики терминалы нужно сразу, можно даже выписать их в отдельный список внизу основных определений, — они пригодятся позже.
Полное описание БНФ доступно в Википедии <<https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0>здесь> и <<https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0>здесь>. Составление грамматики языка — важная стадия создания языка, не терпящая легкомыслия. Одна ошибка в ней может привести к полностью нерабочему коду, который придётся переписывать с нуля. Поэтому, прежде чем делать следующий шаг, убедитесь, что в составленной грамматике не осталось спорных моментов. Если у вас два монитора, будет удобно на всё оставшееся время работы занять документом с грамматикой один монитор, чтобы иметь возможность быстро перемещаться глазами на него, когда будете кодить. Поверьте, так придётся делать постоянно. Вот составленная мной грамматика HTML5 в форме БНФ:
> `[stub]
Когда грамматика готова, можно приступать к лексическому анализатору (другое название лексического разборщика, т.к. помимо разбора, он выявляет в документе лексические ошибки). На первый взгляд всё просто: поглощать символы, записывать в буфер и при обнаружении ключевого терминала определять полученную лексему как токен с определённым типом, так? Да, только тип токена здесь имеет большее значение, чем символ. Сейчас поясню. Само собой, процедура disassemble(ifsteam &file) должна содержать цикл, читающий по одному символу из входного потока и отправляющий его в процедуру process(const char &c), где этот символ обрабатывается. Кажется, что процедуре process нужно содержать switch, где на каждый ключевой символ определены свои функции в зависимости от текущего типа токена. На самом деле всё наоборот: лучше с помощью switch проверять именно тип токена, а функции определять для символов. Более того, текущий токен чаще всего имеет неопределённый тип, один из многих. Например, после открытия угловой скобки может идти: открывающий, закрывающий, пустой теги, а также комментарий в стиле HTML или макро тег (сценарий PHP, заключённый в "<?… ?>". И для всех таких объединений нужен свой case. Как такое реализовать? С помощью битовых флагов. Пусть задано конечное число типов токена (чем больше — тем лучше, так как задача лексического анализатора — оставить как можно меньше работы синтаксическому). Для каждого типа задано уникальное число степени двойки (1, 2, 4, 8 и т.д). Тогда в двоичном формате они будут выглядеть так: 0001, 0010, 0100 и т.д., и при побитовом сложении любого числа любых типов получится уникальное число. Если текстовое описание сложно для понимания, приведу код. Вот определение типов:
> `[enum Token_type {
END = 1, TEXT = 2,
OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO_TAG = 64,
ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBLE_QUOTED_ATTRIBUTE_VALUE = 1024
};]
Урезанная процедура process:
> `[stub]
Проверяем с помощью switch тип ожидаемого токена (или токенов), а внутри каждого case определяем процедуры для каждого из ключевых терминалов. Функций не так много, все выполняют простые действия: либо добавление символа к буферу, либо слив буфера в очередной токен, либо смену ожидаемого типа токена (токенов), либо выброс исключения. Определить нужную процедуру легко по написанной выше грамматике при помощи текстового редактора с возможностью поиска. Просто ищем все включения ожидаемого токена (токенов) в определения других выражений, затем включения этих выражений в «третьи» и т.д. Вот пример для открывающего тега в текстовом редакторе gedit:
[<https://hsto.org/webt/72/fw/tw/72fwtwt_waeie4ulzftkxua356w.png>]
Вначале ориентироваться в грамматике сложно, но со временем и опытом она становится не сложнее деления столбиком. А вот и процедура disassemble:
> `[stub]
Первому ожидаемому токену очевидно необходимо задать тип TEXT, а в конце добавить токен типа END с любым текстом (или пустой, как здесь).
Для примера я взял один из своих шаблонов HTML-документа с комментарием, добавил к нему псевдо-скрипт PHP, обработал лексером и вывел список токенов в формате "[ "<текст_токена>": <тип_токена> ]". Вот что получилось:
> =[Сам документ`[stub]]
=[Список токенов`[stub]]
Теперь мы готовы приступить ко второй части — построению синтаксического дерева. Поскольку наши теги имеют аттрибуты, то узлы дерева кроме связи с другими узлами будут содержать массивы пар ключ-значение. Получившаяся конструкция сможет полноправно называться объектной моделью документа DOM, упомянутой в заголовке статьи.
Сколько нужно классов для реализации всех свойств HTML-элементов?
В идеале — по одному классу для каждого элемента, чтобы можно было определять для них каскадные таблицы стилей, но мы ограничимся тремя — пустым тегом «Node», унаследованным от него блоком «Block» (контент, заключённый между двумя парными тегами) и унаследованным от него корнем дерева «Root». Также определим в парсере массив тегов, которые могут содержать текст, такие, как <p>, <li>, <strong> и др, чтобы отсеять токены с неразмеченным текстом. Теперь дело за малым. Если вы хорошо проработали лексический анализатор, то задача синтаксического — просто поглощать токены и выполнять в открытом узле одну из трёх операций: добавить в него пустой узел, открыть новый или закрыть самого, вернув указатель на родителя. Для последней потребуется, чтобы все классы, начиная с базового Node, содержали такой указатель, получаемый при создании элемента. Этот процесс называется %[нисходящим синтаксическим разбором].
Процедура парсинга:
> `[stub]
Вот и всё! Если вы всё сделали правильно, полученное дерево можно вывести на экран:
`[|
+--<ROOT>
|
+--<!DOCTYPE>
|
+--<html>
|
+--<head>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<meta>
| |
| +--<title>
| |
| +--<link>
| |
| +--<link>
| |
| +--<COMMENT>
|
+--<body>
|
+--<header>
| |
| +--<div>
|
+--<nav>
| |
| +--<ul>
| |
| +--<li>
| | |
| | +--<a>
| |
| +--<li>
| | |
| | +--<a>
| |
| +--<li>
| |
| +--<a>
|
+--<main>
| |
| +--<MACRO>
|
+--<footer>
|
+--<hr>
|
+--<small>]
Однако, хотя полученное дерево действительно можно назвать DOM, до полноценных jQuery, Jsoup, beautifulsoup или Gumbo нашему парсеру далеко, в частности потому, что он не может правильно обрабатывать текст, расположенный между парными тегами <style> и <script>, а потому исходников пока не привожу. Но обязательно добавлю, если хабровчане изъявят такое желание. Успехов.
P.S. Залил в публичный доступ <<https://gitlab.com/2che/nyHTML>исходники>. Имхо, сыроватые, поэтому буду обстругивать до полноценной библиотеки.
Токены от лексера
0: [ "2che" : NOTIFICATION ] 1: [ " " : NEWLINE ] 2: [ "442964" : CITE ] 3: [ "#[" : TITLE_START ] 4: [ "Искусство парсинга или DOM своими руками" : TEXT ] 5: [ "]" : SPAN_OR_IMAGE_FINISH ] 6: [ " " : DOUBLE_NEWLINE ] 7: [ "Привет, Хабр! Недавно я задался идеей создать простой язык разметки наподобие markdown, который отлично подходил бы для моих задач, а именно — быстрого написания лекций с форматированием и возможностью вставки математических формул «на лету», с применением одной лишь клавиатуры. Чтобы перевести текст, написанный в таком формате, в более понятную форму, например, документ LibreOffice Writer, нужен " : TEXT ] 8: [ "%[" : ITALIC_START ] 9: [ "синтаксический анализатор" : TEXT ] 10: [ "]" : SPAN_OR_IMAGE_FINISH ] 11: [ ", проще говоря — " : TEXT ] 12: [ "%[" : ITALIC_START ] 13: [ "парсер" : TEXT ] 14: [ "]" : SPAN_OR_IMAGE_FINISH ] 15: [ ". Поскольку я привык делать велосипеды, то направился в поисковые системы с запросами «parser example», «html to DOM», «how to parse html» и др. К моему разочарованию, на всех найденных ресурсах либо приводились элементарные примеры типа калькулятора Страуструпа с рекурсивным спуском, либо использовались готовые решения, такие как flex, bison, llvm и yacc. Библиотек, предназначенных для парсинга строго определённых языков, нашлось ещё больше (gumbo, jsoup, rapidjson, инструменты Qt и др.) Ни то, ни другое не входило в мои планы по написанию парсера своей разметки на C++ с использованием лишь стандартной библиотеки, поэтому моим источником знаний об искусстве парсинга вместо электронных ресурсов стали методички технических институтов. О том, как взять текст и построить из него AST (абстрактное синтаксическое дерево), о некоторых подводных камнях, на которые я натыкался в процессе, о возможных ошибках я сегодня и расскажу." : TEXT ] 16: [ " " : DOUBLE_NEWLINE ] 17: [ "Сразу оговорюсь, — если ваша цель — свой скриптовый язык или что ещё сложнее, этой статьи будет недостаточно для его реализации. В идеале нужно на отлично знать теорию автоматов и дискретные структуры. Но в качестве отправной точки можно пока ограничиться и моим опытом, которым я щедро поделюсь под катом. Это не совсем то, что я задумывал изначально, зато идеально подходит для примера. Парсить мы будем HTML, как простой и всем знакомый язык." : TEXT ] 18: [ " " : DOUBLE_NEWLINE ] 19: [ "Прежде всего, парсинг, или " : TEXT ] 20: [ "%[" : ITALIC_START ] 21: [ "синтаксический разбор" : TEXT ] 22: [ "]" : SPAN_OR_IMAGE_FINISH ] 23: [ " — не синоним полного процесса превращения текста в объектную модель. Сам процесс состоит из двух этапов:" : TEXT ] 24: [ " " : NEWLINE ] 25: [ "1. " : ORDERED_LIST_ITEM_MARKER ] 26: [ "*[" : BOLD_START ] 27: [ "Лексический разбор" : TEXT ] 28: [ "]" : SPAN_OR_IMAGE_FINISH ] 29: [ " текста на токены — небольшие куски этого текста, имеющие определённое синтаксическое значение." : TEXT ] 30: [ " " : NEWLINE ] 31: [ "2. " : ORDERED_LIST_ITEM_MARKER ] 32: [ "*[" : BOLD_START ] 33: [ "Синтаксический разбор" : TEXT ] 34: [ "]" : SPAN_OR_IMAGE_FINISH ] 35: [ " — построение из токенов на основе их значений " : TEXT ] 36: [ "%[" : ITALIC_START ] 37: [ "абстрактного синтаксического дерева" : TEXT ] 38: [ "]" : SPAN_OR_IMAGE_FINISH ] 39: [ " (AST — abstract syntax tree), или " : TEXT ] 40: [ "%[" : ITALIC_START ] 41: [ "объектной модели документа" : TEXT ] 42: [ "]" : SPAN_OR_IMAGE_FINISH ] 43: [ " (DOM — document object model)." : TEXT ] 44: [ " " : DOUBLE_NEWLINE ] 45: [ "Но давайте по порядку. Перед тем, как открывать свою любимую IDE и писать код, нужно разработать грамматику будущего языка. Из формальных контекстно-свободных грамматик самые известные — " : TEXT ] 46: [ "%[" : ITALIC_START ] 47: [ "форма Бэкуса-Наура (БНФ)" : TEXT ] 48: [ "]" : SPAN_OR_IMAGE_FINISH ] 49: [ " и " : TEXT ] 50: [ "%[" : ITALIC_START ] 51: [ "расширенная форма Бэкуса-Наура" : TEXT ] 52: [ "]" : SPAN_OR_IMAGE_FINISH ] 53: [ ". Я использовал их симбиоз, взяв лучшее от обеих форм. Любое выражение можно определить через другие выражения так:" : TEXT ] 54: [ " " : NEWLINE ] 55: [ "> " : QUOTE_START ] 56: [ "`[" : MONOSPACE_START ] 57: [ "<сумма" : TEXT ] 58: [ ">" : LINK_FINISH ] 59: [ " = <выражение_1" : TEXT ] 60: [ ">" : LINK_FINISH ] 61: [ " <знак_плюс" : TEXT ] 62: [ ">" : LINK_FINISH ] 63: [ " <выражение_2" : TEXT ] 64: [ ">" : LINK_FINISH ] 65: [ "]" : SPAN_OR_IMAGE_FINISH ] 66: [ " " : DOUBLE_NEWLINE ] 67: [ "Здесь одно выражение определено через три других, следующих одно за другим. Их, в свою очередь, тоже необходимо представить через «третьи» выражения и т.д." : TEXT ] 68: [ " " : DOUBLE_NEWLINE ] 69: [ "Когда же остановиться?" : TEXT ] 70: [ " " : DOUBLE_NEWLINE ] 71: [ "Описание синтаксиса любого языка в формальных грамматиках состоит из двух типов лексем: " : TEXT ] 72: [ "%[" : ITALIC_START ] 73: [ "терминалов" : TEXT ] 74: [ "]" : SPAN_OR_IMAGE_FINISH ] 75: [ " и " : TEXT ] 76: [ "%[" : ITALIC_START ] 77: [ "нетерминалов" : TEXT ] 78: [ "]" : SPAN_OR_IMAGE_FINISH ] 79: [ ". " : TEXT ] 80: [ "*[" : BOLD_START ] 81: [ "Нетерминалы" : TEXT ] 82: [ "]" : SPAN_OR_IMAGE_FINISH ] 83: [ " — выражения, требующие определения:" : TEXT ] 84: [ " " : NEWLINE ] 85: [ "> " : QUOTE_START ] 86: [ "`[" : MONOSPACE_START ] 87: [ "<выражение_1" : TEXT ] 88: [ ">" : LINK_FINISH ] 89: [ " = <число" : TEXT ] 90: [ ">" : LINK_FINISH ] 91: [ " (<знак_умножения" : TEXT ] 92: [ ">" : LINK_FINISH ] 93: [ " | <знак_деления" : TEXT ] 94: [ ">" : LINK_FINISH ] 95: [ ") <число" : TEXT ] 96: [ ">" : LINK_FINISH ] 97: [ "]" : SPAN_OR_IMAGE_FINISH ] 98: [ " " : DOUBLE_NEWLINE ] 99: [ "*[" : BOLD_START ] 100: [ "Терминалы" : TEXT ] 101: [ "]" : SPAN_OR_IMAGE_FINISH ] 102: [ " самодостаточны, их не нужно определять. Выше приведённые примеры можно записать так:" : TEXT ] 103: [ " " : NEWLINE ] 104: [ "> " : QUOTE_START ] 105: [ "`[" : MONOSPACE_START ] 106: [ "<сумма" : TEXT ] 107: [ ">" : LINK_FINISH ] 108: [ " = <выражение_1" : TEXT ] 109: [ ">" : LINK_FINISH ] 110: [ " "+" <выражение_2" : TEXT ] 111: [ ">" : LINK_FINISH ] 112: [ " " : NEWLINE ] 113: [ "<выражение_1" : TEXT ] 114: [ ">" : LINK_FINISH ] 115: [ " = <число" : TEXT ] 116: [ ">" : LINK_FINISH ] 117: [ " ("*" | "/") <число" : TEXT ] 118: [ ">" : LINK_FINISH ] 119: [ "]" : SPAN_OR_IMAGE_FINISH ] 120: [ " " : DOUBLE_NEWLINE ] 121: [ "где "+", "*", "/" — терминалы." : TEXT ] 122: [ " " : NEWLINE ] 123: [ "Выделить из грамматики терминалы нужно сразу, можно даже выписать их в отдельный список внизу основных определений, — они пригодятся позже." : TEXT ] 124: [ " " : DOUBLE_NEWLINE ] 125: [ "Полное описание БНФ доступно в Википедии " : TEXT ] 126: [ "<<" : LINK_START ] 127: [ "https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0" : TEXT ] 128: [ ">" : LINK_FINISH ] 129: [ "здесь" : TEXT ] 130: [ ">" : LINK_FINISH ] 131: [ " и " : TEXT ] 132: [ "<<" : LINK_START ] 133: [ "https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0" : TEXT ] 134: [ ">" : LINK_FINISH ] 135: [ "здесь" : TEXT ] 136: [ ">" : LINK_FINISH ] 137: [ ". Составление грамматики языка — важная стадия создания языка, не терпящая легкомыслия. Одна ошибка в ней может привести к полностью нерабочему коду, который придётся переписывать с нуля. Поэтому, прежде чем делать следующий шаг, убедитесь, что в составленной грамматике не осталось спорных моментов. Если у вас два монитора, будет удобно на всё оставшееся время работы занять документом с грамматикой один монитор, чтобы иметь возможность быстро перемещаться глазами на него, когда будете кодить. Поверьте, так придётся делать постоянно. Вот составленная мной грамматика HTML5 в форме БНФ:" : TEXT ] 138: [ " " : NEWLINE ] 139: [ "> " : QUOTE_START ] 140: [ "`[" : MONOSPACE_START ] 141: [ "stub" : TEXT ] 142: [ "]" : SPAN_OR_IMAGE_FINISH ] 143: [ " " : DOUBLE_NEWLINE ] 144: [ "Когда грамматика готова, можно приступать к лексическому анализатору (другое название лексического разборщика, т.к. помимо разбора, он выявляет в документе лексические ошибки). На первый взгляд всё просто: поглощать символы, записывать в буфер и при обнаружении ключевого терминала определять полученную лексему как токен с определённым типом, так? Да, только тип токена здесь имеет большее значение, чем символ. Сейчас поясню. Само собой, процедура disassemble(ifsteam &file) должна содержать цикл, читающий по одному символу из входного потока и отправляющий его в процедуру process(const char &c), где этот символ обрабатывается. Кажется, что процедуре process нужно содержать switch, где на каждый ключевой символ определены свои функции в зависимости от текущего типа токена. На самом деле всё наоборот: лучше с помощью switch проверять именно тип токена, а функции определять для символов. Более того, текущий токен чаще всего имеет неопределённый тип, один из многих. Например, после открытия угловой скобки может идти: открывающий, закрывающий, пустой теги, а также комментарий в стиле HTML или макро тег (сценарий PHP, заключённый в "<?… ?" : TEXT ] 145: [ ">" : LINK_FINISH ] 146: [ "". И для всех таких объединений нужен свой case. Как такое реализовать? С помощью битовых флагов. Пусть задано конечное число типов токена (чем больше — тем лучше, так как задача лексического анализатора — оставить как можно меньше работы синтаксическому). Для каждого типа задано уникальное число степени двойки (1, 2, 4, 8 и т.д). Тогда в двоичном формате они будут выглядеть так: 0001, 0010, 0100 и т.д., и при побитовом сложении любого числа любых типов получится уникальное число. Если текстовое описание сложно для понимания, приведу код. Вот определение типов:" : TEXT ] 147: [ " " : NEWLINE ] 148: [ "> " : QUOTE_START ] 149: [ "`[" : MONOSPACE_START ] 150: [ "enum Token_type {" : TEXT ] 151: [ " " : NEWLINE ] 152: [ " END = 1, TEXT = 2," : TEXT ] 153: [ " " : NEWLINE ] 154: [ " OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO_TAG = 64," : TEXT ] 155: [ " " : NEWLINE ] 156: [ " ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBLE_QUOTED_ATTRIBUTE_VALUE = 1024" : TEXT ] 157: [ " " : NEWLINE ] 158: [ "};" : TEXT ] 159: [ "]" : SPAN_OR_IMAGE_FINISH ] 160: [ " " : DOUBLE_NEWLINE ] 161: [ "Урезанная процедура process:" : TEXT ] 162: [ " " : NEWLINE ] 163: [ "> " : QUOTE_START ] 164: [ "`[" : MONOSPACE_START ] 165: [ "stub" : TEXT ] 166: [ "]" : SPAN_OR_IMAGE_FINISH ] 167: [ " " : DOUBLE_NEWLINE ] 168: [ "Проверяем с помощью switch тип ожидаемого токена (или токенов), а внутри каждого case определяем процедуры для каждого из ключевых терминалов. Функций не так много, все выполняют простые действия: либо добавление символа к буферу, либо слив буфера в очередной токен, либо смену ожидаемого типа токена (токенов), либо выброс исключения. Определить нужную процедуру легко по написанной выше грамматике при помощи текстового редактора с возможностью поиска. Просто ищем все включения ожидаемого токена (токенов) в определения других выражений, затем включения этих выражений в «третьи» и т.д. Вот пример для открывающего тега в текстовом редакторе gedit:" : TEXT ] 169: [ " " : NEWLINE ] 170: [ "[<" : IMAGE_START ] 171: [ "https://hsto.org/webt/72/fw/tw/72fwtwt_waeie4ulzftkxua356w.png" : TEXT ] 172: [ ">" : LINK_FINISH ] 173: [ "]" : SPAN_OR_IMAGE_FINISH ] 174: [ " " : DOUBLE_NEWLINE ] 175: [ "Вначале ориентироваться в грамматике сложно, но со временем и опытом она становится не сложнее деления столбиком. А вот и процедура disassemble:" : TEXT ] 176: [ " " : NEWLINE ] 177: [ "> " : QUOTE_START ] 178: [ "`[" : MONOSPACE_START ] 179: [ "stub" : TEXT ] 180: [ "]" : SPAN_OR_IMAGE_FINISH ] 181: [ " " : DOUBLE_NEWLINE ] 182: [ "Первому ожидаемому токену очевидно необходимо задать тип TEXT, а в конце добавить токен типа END с любым текстом (или пустой, как здесь)." : TEXT ] 183: [ " " : DOUBLE_NEWLINE ] 184: [ "Для примера я взял один из своих шаблонов HTML-документа с комментарием, добавил к нему псевдо-скрипт PHP, обработал лексером и вывел список токенов в формате "[ "<текст_токена" : TEXT ] 185: [ ">" : LINK_FINISH ] 186: [ "": <тип_токена" : TEXT ] 187: [ ">" : LINK_FINISH ] 188: [ " " : TEXT ] 189: [ "]" : SPAN_OR_IMAGE_FINISH ] 190: [ "". Вот что получилось:" : TEXT ] 191: [ " " : NEWLINE ] 192: [ "> " : QUOTE_START ] 193: [ "=[" : MARKED_START ] 194: [ "Сам документ" : TEXT ] 195: [ "`[" : MONOSPACE_START ] 196: [ "stub" : TEXT ] 197: [ "]" : SPAN_OR_IMAGE_FINISH ] 198: [ "]" : SPAN_OR_IMAGE_FINISH ] 199: [ " " : NEWLINE ] 200: [ "=[" : MARKED_START ] 201: [ "Список токенов" : TEXT ] 202: [ "`[" : MONOSPACE_START ] 203: [ "stub" : TEXT ] 204: [ "]" : SPAN_OR_IMAGE_FINISH ] 205: [ "]" : SPAN_OR_IMAGE_FINISH ] 206: [ " " : DOUBLE_NEWLINE ] 207: [ "Теперь мы готовы приступить ко второй части — построению синтаксического дерева. Поскольку наши теги имеют аттрибуты, то узлы дерева кроме связи с другими узлами будут содержать массивы пар ключ-значение. Получившаяся конструкция сможет полноправно называться объектной моделью документа DOM, упомянутой в заголовке статьи." : TEXT ] 208: [ " " : DOUBLE_NEWLINE ] 209: [ "Сколько нужно классов для реализации всех свойств HTML-элементов?" : TEXT ] 210: [ " " : DOUBLE_NEWLINE ] 211: [ "В идеале — по одному классу для каждого элемента, чтобы можно было определять для них каскадные таблицы стилей, но мы ограничимся тремя — пустым тегом «Node», унаследованным от него блоком «Block» (контент, заключённый между двумя парными тегами) и унаследованным от него корнем дерева «Root». Также определим в парсере массив тегов, которые могут содержать текст, такие, как <p" : TEXT ] 212: [ ">" : LINK_FINISH ] 213: [ ", <li" : TEXT ] 214: [ ">" : LINK_FINISH ] 215: [ ", <strong" : TEXT ] 216: [ ">" : LINK_FINISH ] 217: [ " и др, чтобы отсеять токены с неразмеченным текстом. Теперь дело за малым. Если вы хорошо проработали лексический анализатор, то задача синтаксического — просто поглощать токены и выполнять в открытом узле одну из трёх операций: добавить в него пустой узел, открыть новый или закрыть самого, вернув указатель на родителя. Для последней потребуется, чтобы все классы, начиная с базового Node, содержали такой указатель, получаемый при создании элемента. Этот процесс называется " : TEXT ] 218: [ "%[" : ITALIC_START ] 219: [ "нисходящим синтаксическим разбором" : TEXT ] 220: [ "]" : SPAN_OR_IMAGE_FINISH ] 221: [ "." : TEXT ] 222: [ " " : DOUBLE_NEWLINE ] 223: [ "Процедура парсинга:" : TEXT ]https://gitlab.com/2che/markedit 224: [ " " : NEWLINE ] 225: [ "> " : QUOTE_START ] 226: [ "`[" : MONOSPACE_START ] 227: [ "stub" : TEXT ] 228: [ "]" : SPAN_OR_IMAGE_FINISH ] 229: [ " " : DOUBLE_NEWLINE ] 230: [ "Вот и всё! Если вы всё сделали правильно, полученное дерево можно вывести на экран:" : TEXT ] 231: [ " " : NEWLINE ] 232: [ "`[" : MONOSPACE_START ] 233: [ "| " : TEXT ] 234: [ " " : NEWLINE ] 235: [ "+--<ROOT" : TEXT ] 236: [ ">" : LINK_FINISH ] 237: [ " " : NEWLINE ] 238: [ " | " : TEXT ] 239: [ " " : NEWLINE ] 240: [ " +--<!DOCTYPE" : TEXT ] 241: [ ">" : LINK_FINISH ] 242: [ " " : NEWLINE ] 243: [ " | " : TEXT ] 244: [ " " : NEWLINE ] 245: [ " +--<html" : TEXT ] 246: [ ">" : LINK_FINISH ] 247: [ " " : NEWLINE ] 248: [ " | " : TEXT ] 249: [ " " : NEWLINE ] 250: [ " +--<head" : TEXT ] 251: [ ">" : LINK_FINISH ] 252: [ " " : NEWLINE ] 253: [ " | | " : TEXT ] 254: [ " " : NEWLINE ] 255: [ " | +--<meta" : TEXT ] 256: [ ">" : LINK_FINISH ] 257: [ " " : NEWLINE ] 258: [ " | | " : TEXT ] 259: [ " " : NEWLINE ] 260: [ " | +--<meta" : TEXT ] 261: [ ">" : LINK_FINISH ] 262: [ " " : NEWLINE ] 263: [ " | | " : TEXT ] 264: [ " " : NEWLINE ] 265: [ " | +--<meta" : TEXT ] 266: [ ">" : LINK_FINISH ] 267: [ " " : NEWLINE ] 268: [ " | | " : TEXT ] 269: [ " " : NEWLINE ] 270: [ " | +--<meta" : TEXT ] 271: [ ">" : LINK_FINISH ] 272: [ " " : NEWLINE ] 273: [ " | | " : TEXT ] 274: [ " " : NEWLINE ] 275: [ " | +--<meta" : TEXT ] 276: [ ">" : LINK_FINISH ] 277: [ " " : NEWLINE ] 278: [ " | | " : TEXT ] 279: [ " " : NEWLINE ] 280: [ " | +--<meta" : TEXT ] 281: [ ">" : LINK_FINISH ] 282: [ " " : NEWLINE ] 283: [ " | | " : TEXT ] 284: [ " " : NEWLINE ] 285: [ " | +--<meta" : TEXT ] 286: [ ">" : LINK_FINISH ] 287: [ " " : NEWLINE ] 288: [ " | | " : TEXT ] 289: [ " " : NEWLINE ] 290: [ " | +--<meta" : TEXT ] 291: [ ">" : LINK_FINISH ] 292: [ " " : NEWLINE ] 293: [ " | | " : TEXT ] 294: [ " " : NEWLINE ] 295: [ " | +--<meta" : TEXT ] 296: [ ">" : LINK_FINISH ] 297: [ " " : NEWLINE ] 298: [ " | | " : TEXT ] 299: [ " " : NEWLINE ] 300: [ " | +--<title" : TEXT ] 301: [ ">" : LINK_FINISH ] 302: [ " " : NEWLINE ] 303: [ " | | " : TEXT ] 304: [ " " : NEWLINE ] 305: [ " | +--<link" : TEXT ] 306: [ ">" : LINK_FINISH ] 307: [ " " : NEWLINE ] 308: [ " | | " : TEXT ] 309: [ " " : NEWLINE ] 310: [ " | +--<link" : TEXT ] 311: [ ">" : LINK_FINISH ] 312: [ " " : NEWLINE ] 313: [ " | | " : TEXT ] 314: [ " " : NEWLINE ] 315: [ " | +--<COMMENT" : TEXT ] 316: [ ">" : LINK_FINISH ] 317: [ " " : NEWLINE ] 318: [ " | " : TEXT ] 319: [ " " : NEWLINE ] 320: [ " +--<body" : TEXT ] 321: [ ">" : LINK_FINISH ] 322: [ " " : NEWLINE ] 323: [ " | " : TEXT ] 324: [ " " : NEWLINE ] 325: [ " +--<header" : TEXT ] 326: [ ">" : LINK_FINISH ] 327: [ " " : NEWLINE ] 328: [ " | | " : TEXT ] 329: [ " " : NEWLINE ] 330: [ " | +--<div" : TEXT ] 331: [ ">" : LINK_FINISH ] 332: [ " " : NEWLINE ] 333: [ " | " : TEXT ] 334: [ " " : NEWLINE ] 335: [ " +--<nav" : TEXT ] 336: [ ">" : LINK_FINISH ] 337: [ " " : NEWLINE ] 338: [ " | | " : TEXT ] 339: [ " " : NEWLINE ] 340: [ " | +--<ul" : TEXT ] 341: [ ">" : LINK_FINISH ] 342: [ " " : NEWLINE ] 343: [ " | | " : TEXT ] 344: [ " " : NEWLINE ] 345: [ " | +--<li" : TEXT ] 346: [ ">" : LINK_FINISH ] 347: [ " " : NEWLINE ] 348: [ " | | | " : TEXT ] 349: [ " " : NEWLINE ] 350: [ " | | +--<a" : TEXT ] 351: [ ">" : LINK_FINISH ] 352: [ " " : NEWLINE ] 353: [ " | | " : TEXT ] 354: [ " " : NEWLINE ] 355: [ " | +--<li" : TEXT ] 356: [ ">" : LINK_FINISH ] 357: [ " " : NEWLINE ] 358: [ " | | | " : TEXT ] 359: [ " " : NEWLINE ] 360: [ " | | +--<a" : TEXT ] 361: [ ">" : LINK_FINISH ] 362: [ " " : NEWLINE ] 363: [ " | | " : TEXT ] 364: [ " " : NEWLINE ] 365: [ " | +--<li" : TEXT ] 366: [ ">" : LINK_FINISH ] 367: [ " " : NEWLINE ] 368: [ " | | " : TEXT ] 369: [ " " : NEWLINE ] 370: [ " | +--<a" : TEXT ] 371: [ ">" : LINK_FINISH ] 372: [ " " : NEWLINE ] 373: [ " | " : TEXT ] 374: [ " " : NEWLINE ] 375: [ " +--<main" : TEXT ] 376: [ ">" : LINK_FINISH ] 377: [ " " : NEWLINE ] 378: [ " | | " : TEXT ] 379: [ " " : NEWLINE ] 380: [ " | +--<MACRO" : TEXT ] 381: [ ">" : LINK_FINISH ] 382: [ " " : NEWLINE ] 383: [ " | " : TEXT ] 384: [ " " : NEWLINE ] 385: [ " +--<footer" : TEXT ] 386: [ ">" : LINK_FINISH ] 387: [ " " : NEWLINE ] 388: [ " | " : TEXT ] 389: [ " " : NEWLINE ] 390: [ " +--<hr" : TEXT ] 391: [ ">" : LINK_FINISH ] 392: [ " " : NEWLINE ] 393: [ " | " : TEXT ] 394: [ " " : NEWLINE ] 395: [ " +--<small" : TEXT ] 396: [ ">" : LINK_FINISH ] 397: [ "]" : SPAN_OR_IMAGE_FINISH ] 398: [ " " : NEWLINE ] 399: [ " " : TEXT ] 400: [ " " : NEWLINE ] 401: [ "Однако, хотя полученное дерево действительно можно назвать DOM, до полноценных jQuery, Jsoup, beautifulsoup или Gumbo нашему парсеру далеко, в частности потому, что он не может правильно обрабатывать текст, расположенный между парными тегами <style" : TEXT ] 402: [ ">" : LINK_FINISH ] 403: [ " и <script" : TEXT ] 404: [ ">" : LINK_FINISH ] 405: [ ", а потому исходников пока не привожу. Но обязательно добавлю, если хабровчане изъявят такое желание. Успехов." : TEXT ] 406: [ " " : DOUBLE_NEWLINE ] 407: [ "P.S. Залил в публичный доступ " : TEXT ] 408: [ "<<" : LINK_START ] 409: [ "https://gitlab.com/2che/nyHTML" : TEXT ] 410: [ ">" : LINK_FINISH ] 411: [ "исходники" : TEXT ] 412: [ ">" : LINK_FINISH ] 413: [ ". Имхо, сыроватые, поэтому буду обстругивать до полноценной библиотеки." : TEXT ] 414: [ " " : NEWLINE ] 415: [ "" : END ]
Синтаксическое дерево
<pre><article>
|
+-<section>
|
+-<p>
| |
| +-@2che
| |
| +-"\n"
|
+->>442964
|
+-<h1>
| |
| +-"Искусство парсинга или DOM своими руками"
|
+-<p>
| |
| +-"Привет, Хабр! Недавно я задался идеей создать простой я..."
| |
| +-<i>
| | |
| | +-"синтаксический анализатор"
| |
| +-", проще говоря — "
| |
| +-<i>
| | |
| | +-"парсер"
| |
| +-". Поскольку я привык делать велосипеды, то направился в..."
|
+-<p>
| |
| +-"Сразу оговорюсь, — если ваша цель — свой скриптовый яз..."
|
+-<p>
| |
| +-"Прежде всего, парсинг, или "
| |
| +-<i>
| | |
| | +-"синтаксический разбор"
| |
| +-" — не синоним полного процесса превращения текста в об..."
| |
| +-"\n"
| |
| +-<b>
| | |
| | +-"Лексический разбор"
| |
| +-" текста на токены — небольшие куски этого текста, имею�..."
| |
| +-"\n"
| |
| +-<b>
| | |
| | +-"Синтаксический разбор"
| |
| +-" — построение из токенов на основе их значений "
| |
| +-<i>
| | |
| | +-"абстрактного синтаксического дерева"
| |
| +-" (AST — abstract syntax tree), или "
| |
| +-<i>
| | |
| | +-"объектной модели документа"
| |
| +-" (DOM — document object model)."
|
+-<p>
| |
| +-"Но давайте по порядку. Перед тем, как открывать свою лю�..."
| |
| +-<i>
| | |
| | +-"форма Бэкуса-Наура (БНФ)"
| |
| +-" и "
| |
| +-<i>
| | |
| | +-"расширенная форма Бэкуса-Наура"
| |
| +-". Я использовал их симбиоз, взяв лучшее от обеих форм. Л�..."
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"<сумма"
| |
| +-">"
| |
| +-" = <выражение_1"
| |
| +-">"
| |
| +-" <знак_плюс"
| |
| +-">"
| |
| +-" <выражение_2"
| |
| +-">"
|
+-<p>
| |
| +-"Здесь одно выражение определено через три других, след..."
|
+-<p>
| |
| +-"Когда же остановиться?"
|
+-<p>
| |
| +-"Описание синтаксиса любого языка в формальных граммат..."
| |
| +-<i>
| | |
| | +-"терминалов"
| |
| +-" и "
| |
| +-<i>
| | |
| | +-"нетерминалов"
| |
| +-". "
| |
| +-<b>
| | |
| | +-"Нетерминалы"
| |
| +-" — выражения, требующие определения:"
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"<выражение_1"
| |
| +-">"
| |
| +-" = <число"
| |
| +-">"
| |
| +-" (<знак_умножения"
| |
| +-">"
| |
| +-" | <знак_деления"
| |
| +-">"
| |
| +-") <число"
| |
| +-">"
|
+-<p>
| |
| +-<b>
| | |
| | +-"Терминалы"
| |
| +-" самодостаточны, их не нужно определять. Выше приведён�..."
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"<сумма"
| |
| +-">"
| |
| +-" = <выражение_1"
| |
| +-">"
| |
| +-" "+" <выражение_2"
| |
| +-">"
| |
| +-"\n"
| |
| +-"<выражение_1"
| |
| +-">"
| |
| +-" = <число"
| |
| +-">"
| |
| +-" ("*" | "/") <число"
| |
| +-">"
|
+-<p>
| |
| +-"где "+", "*", "/" — терминалы."
| |
| +-"\n"
| |
| +-"Выделить из грамматики терминалы нужно сразу, можно да..."
|
+-<p>
| |
| +-"Полное описание БНФ доступно в Википедии "
| |
| +-<a>
| | |
| | +-"здесь"
| |
| +-" и "
| |
| +-<a>
| | |
| | +-"здесь"
| |
| +-". Составление грамматики языка — важная стадия создан�..."
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Когда грамматика готова, можно приступать к лексическ�..."
| |
| +-">"
| |
| +-"". И для всех таких объединений нужен свой case. Как такое ..."
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"enum Token_type {"
| |
| +-"\n"
| |
| +-" END = 1, TEXT = 2,"
| |
| +-"\n"
| |
| +-" OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO..."
| |
| +-"\n"
| |
| +-" ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBL..."
| |
| +-"\n"
| |
| +-"};"
|
+-<p>
| |
| +-"Урезанная процедура process:"
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Проверяем с помощью switch тип ожидаемого токена (или ток�..."
| |
| +-"\n"
|
+-<p>
| |
| +-<img />
|
+-<p>
| |
| +-"Вначале ориентироваться в грамматике сложно, но со вре..."
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Первому ожидаемому токену очевидно необходимо задать ..."
|
+-<p>
| |
| +-"Для примера я взял один из своих шаблонов HTML-документа ..."
| |
| +-">"
| |
| +-"": <тип_токена"
| |
| +-">"
| |
| +-" "
| |
| +-"]"
| |
| +-"". Вот что получилось:"
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<mark>
| | |
| | +-"Сам документ"
| | |
| | +-<pre>
| | |
| | +-"stub"
| |
| +-"\n"
| |
| +-<mark>
| |
| +-"Список токенов"
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Теперь мы готовы приступить ко второй части — построе�..."
|
+-<p>
| |
| +-"Сколько нужно классов для реализации всех свойств HTML-э..."
|
+-<p>
| |
| +-"В идеале — по одному классу для каждого элемента, чтоб�..."
| |
| +-">"
| |
| +-", <li"
| |
| +-">"
| |
| +-", <strong"
| |
| +-">"
| |
| +-" и др, чтобы отсеять токены с неразмеченным текстом. Те�..."
| |
| +-<i>
| | |
| | +-"нисходящим синтаксическим разбором"
| |
| +-"."
|
+-<p>
| |
| +-"Процедура парсинга:"
| |
| +-"\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Вот и всё! Если вы всё сделали правильно, полученное де�..."
| |
| +-"\n"
| |
| +-<pre>
| | |
| | +-"| "
| | |
| | +-"\n"
| | |
| | +-"+--<ROOT"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<!DOCTYPE"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<html"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<head"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<meta"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<title"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<link"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<link"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<COMMENT"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<body"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<header"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<div"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<nav"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<ul"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<li"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | | "
| | |
| | +-"\n"
| | |
| | +-" | | +--<a"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<li"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | | "
| | |
| | +-"\n"
| | |
| | +-" | | +--<a"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<li"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<a"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<main"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | | "
| | |
| | +-"\n"
| | |
| | +-" | +--<MACRO"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<footer"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<hr"
| | |
| | +-">"
| | |
| | +-"\n"
| | |
| | +-" | "
| | |
| | +-"\n"
| | |
| | +-" +--<small"
| | |
| | +-">"
| |
| +-"\n"
| |
| +-" "
| |
| +-"\n"
| |
| +-"Однако, хотя полученное дерево действительно можно на�..."
| |
| +-">"
| |
| +-" и <script"
| |
| +-">"
| |
| +-", а потому исходников пока не привожу. Но обязательно д�..."
|
+-<p>
|
+-"P.S. Залил в публичный доступ "
|
+-<a>
| |
| +-"исходники"
|
+-". Имхо, сыроватые, поэтому буду обстругивать до полноце..."
|
+-"\n"
</pre>
Всё здорово, но текстовых нод, идущих цепочкой друг за другом, слишком много. К тому же, я бы хотел, чтобы цитаты, размещённые подряд, соединялись в одну. Для этого нам нужно пройти по дереву в глубину ещё раз и выполнить конкатенацию, т.е., сцепление однородных элементов друг с другом. Детали этого процесса объяснять не буду, прикреплю исходники, а пока просто посмотрите, как изменилось наше
Дерево после конкатенации:
<pre><article>
|
+-<section>
|
+-<p>
| |
| +-@2che
| |
| +-"\n"
|
+->>442964
|
+-<h1>
| |
| +-"Искусство парсинга или DOM своими руками"
|
+-<p>
| |
| +-"Привет, Хабр! Недавно я задался идеей создать простой я..."
| |
| +-<i>
| | |
| | +-"синтаксический анализатор"
| |
| +-", проще говоря — "
| |
| +-<i>
| | |
| | +-"парсер"
| |
| +-". Поскольку я привык делать велосипеды, то направился в..."
|
+-<p>
| |
| +-"Сразу оговорюсь, — если ваша цель — свой скриптовый яз..."
|
+-<p>
| |
| +-"Прежде всего, парсинг, или "
| |
| +-<i>
| | |
| | +-"синтаксический разбор"
| |
| +-" — не синоним полного процесса превращения текста в об..."
| |
| +-<b>
| | |
| | +-"Лексический разбор"
| |
| +-" текста на токены — небольшие куски этого текста, имею�..."
| |
| +-<b>
| | |
| | +-"Синтаксический разбор"
| |
| +-" — построение из токенов на основе их значений "
| |
| +-<i>
| | |
| | +-"абстрактного синтаксического дерева"
| |
| +-" (AST — abstract syntax tree), или "
| |
| +-<i>
| | |
| | +-"объектной модели документа"
| |
| +-" (DOM — document object model)."
|
+-<p>
| |
| +-"Но давайте по порядку. Перед тем, как открывать свою лю�..."
| |
| +-<i>
| | |
| | +-"форма Бэкуса-Наура (БНФ)"
| |
| +-" и "
| |
| +-<i>
| | |
| | +-"расширенная форма Бэкуса-Наура"
| |
| +-". Я использовал их симбиоз, взяв лучшее от обеих форм. Л�..."
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"<сумма> = <выражение_1> <знак_плюс> <выражение_2>"
|
+-<p>
| |
| +-"Здесь одно выражение определено через три других, след..."
|
+-<p>
| |
| +-"Когда же остановиться?"
|
+-<p>
| |
| +-"Описание синтаксиса любого языка в формальных граммат..."
| |
| +-<i>
| | |
| | +-"терминалов"
| |
| +-" и "
| |
| +-<i>
| | |
| | +-"нетерминалов"
| |
| +-". "
| |
| +-<b>
| | |
| | +-"Нетерминалы"
| |
| +-" — выражения, требующие определения:\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"<выражение_1> = <число> (<знак_умножения> | <знак_деления>) <�..."
|
+-<p>
| |
| +-<b>
| | |
| | +-"Терминалы"
| |
| +-" самодостаточны, их не нужно определять. Выше приведён�..."
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"<сумма> = <выражение_1> "+" <выражение_2>\n<выражение_1> = <числ..."
|
+-<p>
| |
| +-"где "+", "*", "/" — терминалы.\nВыделить из грамматики терми�..."
|
+-<p>
| |
| +-"Полное описание БНФ доступно в Википедии "
| |
| +-<a>
| | |
| | +-"здесь"
| |
| +-" и "
| |
| +-<a>
| | |
| | +-"здесь"
| |
| +-". Составление грамматики языка — важная стадия создан�..."
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Когда грамматика готова, можно приступать к лексическ�..."
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"enum Token_type {\n END = 1, TEXT = 2,\n OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = ..."
|
+-<p>
| |
| +-"Урезанная процедура process:\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Проверяем с помощью switch тип ожидаемого токена (или ток�..."
|
+-<p>
| |
| +-<img />
|
+-<p>
| |
| +-"Вначале ориентироваться в грамматике сложно, но со вре..."
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Первому ожидаемому токену очевидно необходимо задать ..."
|
+-<p>
| |
| +-"Для примера я взял один из своих шаблонов HTML-документа ..."
|
+-<blockquote>
| |
| +-<mark>
| | |
| | +-"Сам документ"
| | |
| | +-<pre>
| | |
| | +-"stub"
| |
| +-"\n"
| |
| +-<mark>
| |
| +-"Список токенов"
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Теперь мы готовы приступить ко второй части — построе�..."
|
+-<p>
| |
| +-"Сколько нужно классов для реализации всех свойств HTML-э..."
|
+-<p>
| |
| +-"В идеале — по одному классу для каждого элемента, чтоб�..."
| |
| +-<i>
| | |
| | +-"нисходящим синтаксическим разбором"
| |
| +-"."
|
+-<p>
| |
| +-"Процедура парсинга:\n"
|
+-<blockquote>
| |
| +-<pre>
| |
| +-"stub"
|
+-<p>
| |
| +-"Вот и всё! Если вы всё сделали правильно, полученное де�..."
| |
| +-<pre>
| | |
| | +-"| \n+--<ROOT>\n | \n +--<!DOCTYPE>\n | \n +--<html>\n | \n +--<head>\n | | \n | +--<..."
| |
| +-"\n \nОднако, хотя полученное дерево действительно мо..."
|
+-<p>
|
+-"P.S. Залил в публичный доступ "
|
+-<a>
| |
| +-"исходники"
|
+-". Имхо, сыроватые, поэтому буду обстругивать до полноце..."
</pre>
Остался последний шаг — представление этого дерева в HTML-форме. Здесь всё просто: Создаём строку в методе корня с началом первичной разметки (открывающие элементы html и body, блок head) и начинаем присоединять возвращённые строки от аналогичных элементов детей. Тут мы снова имеем дело с рекурсивным спуском: каждый класс при вызове виртуального метода to_HTML() создаёт строку, помещает в неё свою первичную разметку, затем вызывает тот же метод у каждого своего потомка, соединяет строки, дополняет первичную разметку и возвращает вызвавшему родителю. Вот, например, как выглядит данный метод для класса Inline (сочетающего в себе форматированные встроенные элементы):
string Inline::to_HTML (const unsigned int &level) {
string HTML;
// ****** НАЧАЛО ПЕРВИЧНОЙ РАЗМЕТКИ - ОТКРЫВАЮЩИЙ ТЕГ ******
switch (type) {
case BOLD: {
HTML.append("<b>");
break; }
case ITALIC: {
HTML.append("<i>");
break; }
case UNDERLINED: {
HTML.append("<ins>");
break; }
case OVERLINED: {
HTML.append("<span class=\"overlined\">");
break; }
case THROWLINED: {
HTML.append("<del>");
break; }
case SUBSCRIPT: {
HTML.append("<sub>");
break; }
case SUPERSCRIPT: {
HTML.append("<sup>");
break; }
case MARKED: {
HTML.append("<mark>");
break; }
case MONOSPACE: {
HTML.append("<pre>");
break; }
default:
throw string("invalid inline type: " + type_str() + "!");
}
// *** *** *** ***
// ****** РЕКУРСИВНЫЙ СПУСК - КОНТЕНТ МЕЖДУ ТЕГАМИ ******
for (unsigned long i(0); i < children_count; i++)
HTML.append(children[i]->to_HTML(level+1));
// *** *** *** ***
// ****** КОНЕЦ ПЕРВИЧНОЙ РАЗМЕТКИ - ЗАКРЫВАЮЩИЙ ТЕГ ******
switch (type) {
case BOLD: {
HTML.append("</b>");
break; }
case ITALIC: {
HTML.append("</i>");
break; }
case UNDERLINED: {
HTML.append("</ins>");
break; }
case OVERLINED: {
HTML.append("</span>");
break; }
case THROWLINED: {
HTML.append("</del>");
break; }
case SUBSCRIPT: {
HTML.append("</sub>");
break; }
case SUPERSCRIPT: {
HTML.append("</sup>");
break; }
case MARKED: {
HTML.append("</mark>");
break; }
case MONOSPACE: {
HTML.append("</pre>");
break; }
default:
throw string("invalid inline type: " + type_str() + "!");
}
// *** *** *** ***
return HTML;
}
На этом всё. Надеюсь, теперь, прочитав обе статьи, вы запросто реализуете транслятор для вашего языка разметки или программирования. Если остались вопросы — задавайте в комментариях. А вот исходники. Успехов.
P. S. Забыл упомянуть про экранирование. Оно реализуется просто: если очередной символ в процедуре лексического разбора — обратный слэш ("\"), он игнорируется и обрабатывается следующий символ, но кроме него в функцию обработки символа посылается булево значение true, дающее команду экранировать. Тогда, если этот символ, например, "[", его особое значение игнорируется, и он просто присоединяется к строящемуся токену как текст. В ином случае в функцию подаётся значение false и символ обрабатывается как обычно.