# Подходы к определению парсинга

Говоря о разборе каких-либо данных в соответствии с каким-либо форматом, необходимо понимать, что именно имеется в виду под разбором: что мы имеем и что хотим получить.

Ниже предлагается способ формализации этих понятий и их связь с различными математическими теориями.

## Теоретико-множественная формулировка

***Буфер*** $M$ — массив элеметов: $M = [b_1, b_2, ..., b_n]$

*Часто элементами являются байты, однако это не требуется, разбор можно проводить хоть для последовательности табуреток.*

***Сегмент*** $s(i, j)$ буфера $M$ — непрерывное непустое подмножество (отрезок) $M$: $s = [b_i, ..., b_j], \quad 1 \le i \le j \le n$


Т.о. сегмент определяется двумя индексами в буфере. Одновременно с этим сегменты можно определять и другой парой чисел:
$$
\mathbf{offset}(s) := i - 1 \quad(0 \le \mathbf{offset}(s) \le n-1) \\
\mathbf{size}(s) := j - i +1 \quad (1 \le \mathbf{size}(s) \le n) \\
\mathbf{offset}(s) + \mathbf{size}(s) \le n
$$

* $S(M)$ — множество всех возможных сегментов буфера $M$
* $|S(M)| = \frac{n(n^2+3n-2)}{2}$, где $n$ — размер буфера
* Сегменты, как подмножества $M$, могут *пересекаться* и *вкладываться*:

$$
s_1 \cap s_2, \quad s_3 \subset s_4
$$

***Разбор*** буфера $P$ — непустое множество сегментов $P \subset S(M)$

***Покрытие разбора*** $c(P)$ — объединение сегментов разбора

$$
c(P) = \bigcup_{s \in P} s
$$

*Пример разбора:*

Но нас будут интересовать не просто разборы, а *правильные* разборы!

***Множество правильных разборов*** — такие разборы, что:
1. Разбор из одного сегмента $P = \{s\}$ — правильный
2. Если $P$ — правильный, то $P' = P \cup\{s\}$ — тоже правильный, где $s$ — сегмент, содержащий покрытие $P$: $c(P) \subset s$
3. Если $P_1$ и $P_2$ — два правильных разбора, покрытия которых не пересекаются ($c(P_1) \cap c(P_2) = \emptyset$), то $P = P_1 \cup P_2$ — тоже правильный разбор.

Такое оределение очень похоже на определение *правильных скобочных последовательностей*, и это не случайно. Можно рассматривать сегмент как пару "скобок", стоящих в определенном месте между элементами буфера, тогда разбор — это некая скобочная последовательность, "привязанная" к буферу, а правильный разбор — правильная скобочная последовательность.

***Полный разбор*** — разбор, в котором для каждого элемента буфера существует сегмент, содержащий его и при этом не содержащий других сегментов.

***Корневой разбор*** — разбор, содержащий сегмент $s(1, n)$, т.е. весь буфер.

Все приведенные понятия никак не опираются на свойства элементов буфера и по сути воспринимают буфер как абстрактное множество. Это значит, что свойства правильности, полноты и т.д. никак не связаны со *значениями* элементов буфера (значениями байтов). Буфер с точки зрения этих понятий определяется только размером $n$.

На данном этапе можно сказать, что задача парсинга включает в себя отыскание некоторого **полного правильного корневого разбора** буфера:

***Разборщик*** — это алгоритм, который на вход получает буфер и либо завершается успешно и возвращает полный правильный корневой разбор буфера, либо завершается неуспешно (ошибка разбора).

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

***Язык разборщика*** — множество буферов, принимаемых данным разборщиком без ошибки.

В данном разделе мы не затронем вопроса, как именно определяется язык разборщика. Здесь мы лишь предъявили требования к результату разбора, определили структуру, которую хотим видеть на выходе алгоритма. Разговор о языках разборщиков пойдет ниже.

## Формулировка в терминах грамматик

В рамках теории формальных языков, формат данных — это некий язык. В качестве алфавита логично выбрать двоичный алфавит: $A = \{0, 1\}$. Соответственно буферы (бинарные файлы) — это слова, которые могут принадлежать языку, или не принадлежать.

## Связь формулировок, дерево разбора

У правильных разборов есть удобное представление в виде **дерева**. Действительно, в правильном разборе сегменты не могут пересекаться, они могут только *вкладываться* друг в друга. Это дает возможность говорить о том, что один сегмент является *дочерним* для другого, а тот — *родительским*. Такое дерево называется **деревом разбора**.

*Пример представления разбора в виде дерева разбора:*


В данном примере в дереве 13 узлов — в разборе 13 сегментов:
ROOT, MAGIC, HEADERS, BODY, HDR1-2, CHUNK1-3, K, V (две пары).
У каждой вершины есть соответствующий ей сегмент. У некоторых сегментов есть дочерние сегменты, которые вкладываются в него.