Разбор КС-языка по табелю, часть вторая, итоговая: Провидец⁠⁠

Предыдущая статья:Разбор КС-языка по табелю, часть первая: Создание табеля в vk.com

Статья для повторения: Автомат с магазинной памятью (стог-памятью) и КС-языки

На прошлом уроке мы создали табель разбора для грамматики:

Давайте этот табель поместим в общее представление разборщика КС-языков в начальном состоянии, который назовём «Провидец»:

Я надеюсь вы повторили статью, которая указана выше? Да? Замечательно. Мы видим контуром обведено внутренне устройство провидца, он состоит из:
1. Табеля разбора, в котором ранее пустые ячейки помечены словом «Ошибка». Это значит, что данная пара конечного и неконечного приводит к ошибке.
2. Стога в который вложен # - правый ограничитель потока, который является подом (далее будем говорить просто грань, имея в виду грань строки). А так же вложен стартовый неконечный символ В, что говорит нам, что разбор является нисходящим.
3. Движка который читает принимаемое выражение и делает вывод. В ходе разбора он управляет стог-памятью, обращаясь к табелю для принятия решения, какую цепь поместить следующей взамен верхнего неконечного. Если встречается продукция вида П → ε или конечный символ, то просто снимаем символ с верха. Если на верху оказывается символ не равнозначный рассматриваемому или мы не находим в табеле продукцию сообщаем об ошибке. Останавливается когда верх будет равен грани.

Работа провидца напоминает повторение левостороннего вывода рассматриваемого выражения. Рассмотрим выражение «ч+ч*ч»:
В => ДС => РПС => чПС => чС => ч+ДС => ч+РПС => ч+чПС => ч+ч*РПС =>
ч+ч*чПС => ч+ч*чС => ч+ч*ч

Ниже показана работа совершённая движком, для распознавания этого выражения:

Так как в табеле однозначно определенна применяемая продукция, то мы знаем, что может нас ожидать впереди, поэтому мы и назвали разборщика провидцем. Ниже приложен его псевдокод. Здесь и здесь, вы можете посмотреть полный псевдокод и реализацию на С# от получения табеля, до разбора выражения.

В следующей статье мы рассмотрим включения действий в рекурсивный спуск и немного подытожим цикл статей. Подписывайтесь, чтобы не пропустить.