НИСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ

В алгоритме используется два магазина L1 и L2 и счетчик с текущей позицией входного указателя. Для описания алгоритма воспользуемся стилизованными обозначениями, похожими на описания конфигурации МП-автомата.

Алгоритм 4.1. Алгоритм нисходящего разбора с возвратами.

Вход. Не леворекурсивная КС-грамматика G = (N, S, P, S) и входная цепочка w = a₁, a₂, ¼, a_n (n ³ 0). Предполагается что правила из P пронумерованы числами 1, 2, ¼, p.

Выход. Левый разбор цепочки w, если он существует, или слово “ошибка” в противном случае.

Метод.

(1) Для каждого нетерминала А Î N упорядочить его альтернативы. Пусть А _j - индекс j -ой альтернативы нетерминала А.

(2) Четверкой (q, i, a, b) будем обозначать конфигурацию алгоритма, где:

(а) q - состояние алгоритма;

(б) i - позиция входного указателя (предполагается, что (n+1) -ым “входным символом” служит правый концевой маркер $);

(в) a - содержимое первого магазина (L1);

(г) b - содержимое второго магазина (L2).

Будем считать, что верх первого магазина расположен справа, а второго - слева.

Магазин L2 служит для представления “текущей” левовыводимой цепочки, то есть той сентенциальной формы, которая получилась к данному моменту разбора в результате развертки нетерминалов. Верхний символ в L2 будет символом, помечающим активную вершину порожденного к данному моменту частично дерева левого выхода. В L1 представлена текущая история проделанных выборов альтернатив и входные символы, по которым прошла входная головка. Алгоритм имеет три состояния: q - нормальной деятельности, b - возврата, t – заключительное состояние.

(3) Начальная конфигурация алгоритма: (q, 1, e, S$).

(4) Существует шесть типов шагов. Эти шаги будут описаны в терминах их воздействия на конфигурацию алгоритма. Запись (q, i, a, b)÷¾ (q¢, i¢, a¢, b¢) означает что если (q, i, a, b) -текущая конфигурация, то нужно перейти в следующую конфигурацию (q¢, i¢, a¢, b¢). Если не оговорено противное, то и i - число от 1 до (n+1), aÎ(SÈI)^*, где I - множество индексов альтернатив, bÎ(SÈN)^*.

Шесть шагов определяется так:

(а) Разрастание дерева

(q, i, a, Ab)÷¾ (q, i, aA₁, g₁b), где A®g₁ правило из P и g₁ - перваяальтернативанетерминала A, а A₁ – ее индекс. Этот шаг соответствует разрастанию частичного дерева вывода, при котором применяется первая альтернатива самого левого нетерминала дерева.

(б) Успешное сравнение входного символа с порожденным символом

(q, i, a, ab)÷¾ (q, i+1, aа, b), при условии, что а _i= а (i £ n). Если i -ый входной символ совпадает с очередным порожденным терминалом, то терминал передается из L2 в L1, а позиция указателя увеличивается на единицу.

(в) Успешное завершение

(q, n+1, a, $)÷¾ (t, n+1, a, e). Достигнут конец входной цепочки и найдена левовыводимая цепочка, совпадающая с входной. Левый разбор входной цепочки восстанавливается по цепочке a с помощью гомоморфизма h, где h(a)=e, для всех а Î S и h(A _j)=p, где p - номер правила А ® g и g - j -ая альтернатива нетерминала А.

(г) Неудачное сравнение входного символа с порожденным символом

(q, i, a, аb)÷¾ (b, i, a, ab), при условии, что а _i ¹ а. Надо перейти в состояние возврата b, как только обнаружится, что порожденная левовыводимая цепочка не совпадает с входной цепочкой.

(д) Возврат по входу

(b, i, aa, b)÷¾ (b, i-1, a, ab) для всех аÎS. В состоянии возврата входные символы переносятся назад из L1 в L2.

(е) Испытание очередной альтернативы

(b, i, aA_j, g_jb)÷¾

(е1) (q, i, aA_j+1, g_j+1b), если g_j+1 - (j+1) -ая альтернатива нетерминала А. (g_j в L2 заменяется на g_j+1).

(е2) Следующая конфигурация невозможна, если i=1, A=S и S имеет только j альтернатив. (Это условие указывает, что все возможные левовыводимые цепочки, совместимые с входной цепочкой w, уже исчерпаны, а ее разбор не найден).

(е3) (b, i, a, Ab) в оставшихся случаях. (Здесь исчерпаны все альтернативы нетерминала A и дальнейший возврат происходит путем удаления A_j из L1 и замены в L2 цепочки g_j на A).

Алгоритм выполняется следующим образом:

Шаг 1: Исходя из начальной конфигурации, вычислить последующие конфигурации C₀÷¾ C₁÷¾¼÷¾ C_i ÷¾ ¼, пока их можно вычислить.

Шаг 2: Если последняя конфигурация (t, n+1, g, e), - выдать h(g) и остановиться, иначе выдать сообщение об ошибке. „

Поиск по сайту: