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