Задача разбора, для чего она нужна? Или что такое parsing?⁠⁠

Предыдущая статья: Дерево вывода предложения (сентенции) грамматики. Синтаксическое дерево. в vk.com

Ответ, по поводу к какому языку относилась грамматика из прошлой статьи: Барабанная дробь!!!! Языку идентификаторов. Вместо a подставляйте любой символ из алфавита {A, … Z, a, … z, А … Я, а, …, я} и вместо b из алфавита
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. Таким образом вы получите типичный синтаксис любого языка программирования относящееся к названию переменных.

Собственно таким образом грамматика задает синтаксис языка, порядок языка, место каждого вашего символа, а если этот порядок нарушается, то значит данная цепочка (предложение, сентенция) , не относится к вашему языку. Вот над выяснением принадлежит ли некая цепочка символов к языку заданной грамматики и отвечает решенная задача разбора, но так же преследует цель выявлении структуры цепочки, семантики языка.

Так что же такое задача разбора? Очевидно, если вы прочли прошлую статью:
Задачей разбора является восстановление дерева вывода для заданной цепочки символов.

Повторюсь, ничто иное как построение вывода для заранее заданной цепочки, и чтобы наглядно вам продемонстрировать разбор сыграем в домино Де Ремера. За основу правил возьмём всю ту же грамматику G = ({a, b}, {S, A, B}, {S → AB, A → aA | a, B → bB | b}, S), создадим кости соответствующие правилам вывода:

Кости правил

Возьмем всю ту же самую цепочку aaabb и добавим в нашу игру ещё костей с этими символами и разложим их:

Начало игры

Вы обратили внимание на формы костей? Да, верно, наша цель, собрать дерево так чтобы подошли к нашим половинкам нужные кости правил, вот так:

Конец игры

Каким образом мы можем восстановить дерево? Ну первое что бросается в глаза, это в каком направлении мы будем подбирать кости правил. Подход решения от стартового вспомогательного символа к основным называется нисходящим разбором, в обратном же направлении восходящим разбором. И так же от левых символов левосторонним, а от правых правосторонним. Примеры:

Левосторонний нисходящий разбор.

Правосторонний восходящий разбор.

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

Значение слова детерминация происходит от лат. determinatio — предел, заключение, определение, что означает определенность, однозначность, в нашем случае мы говорим о завершённых ходах, о том что всякое поставление кости на своём месте.

На этом тема закрыта, в следующий раз расскажу почему же бывает так, что 2+2*2 = 8?