Алгоритм построения правого разбора по списку разбора

Вход: КС-грамматика без циклов, правила которой занумерованы числами от 1 до , входная цепочка и список разбора для цепочки .

Выход: Правый разбор цепочки или сообщение об ошибке.

Метод:

Если в списке нет ситуации вида , то . Поэтому надо выдать сигнал «ошибка» и остановиться. В противном случае положить и выполнить процедуру .

Процедура определяется так:

1) Если - номер правила , то пусть значением переменной будет цепочка, начинающаяся номером , за которым следует предыдущее значение , т.е. . (Предполагается, что - глобальная переменная)

2) Если , то положить и .

3)

a) Если , вычесть 1 из и из .

b) Если , найти в ситуацию для некоторого , для которого ситуация . Затем выполнить процедуру вычесть 1 из и положить .

4) Повторять шаг 3 до тех пор, пока не станет . После этого остановиться.

Пример №1

Задание.

Пусть задана грамматика с правилами

и – входная цепочка, для которой построен список разбора :

Дата добавления: 2014-01-07