Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 8

Для работы алгоритма используется МПА, построенный на основе исходной КС-грамматики G(VT,VN,P,S). Все правила из множества P представим в виде A ® a₁½a₂½…½a_k, т.е. для каждого нетерминального символа AÎVN перенумеруем все возможные альтернативы. Входная цепочка имеет вид a=a₁a₂…a_n, ½a½= n, a_iÎVT "i. В алгоритме используется ещё одно дополнительное состояние b для обратного хода (back – возврат). Для хранения уже выбранных альтернатив используется дополнительный стек L₂, который может содержать символы входного языка автомата aÎVT и символы вида A_j, где AÎVN – это будет означать, что среди всех возможных правил для символа A была выбрана альтернатива с номером j.

Итак, алгоритм работает с двумя стеками: L₁ – стек МПА и L₂ – стек возвратов, причём в цепочку стека L₁ символы помещаются слева, а в цепочку стека L₂ – справа.

Состояние алгоритма на каждом шаге определяется четырьмя параметрами: (Q,i,L₁,L₂), где Q – текущее состояние автомата (q или b), i – положение считывающей головки во входной цепочке (1 < i £ n+1), L₁ и L₂ – содержимое стеков.

Начальным состоянием алгоритма является (q,1,S,l), где S – целевой символ грамматики. Алгоритм начинает работу с начального состояния и циклически выполняет 6 шагов до тех пор, пока не перейдёт в конечное состояние или не обнаружит ошибку.

Алгоритм выполняет циклически следующие шаги:

Шаг 1 («Разрастание»):(q, i, Ab, m) ® (q, i, g₁b, mA₁), где bÎ(VNÈVT)^*, m – содержимое стека возвратов L₂, если A ® g₁ – первая из всех альтернатив для символа A (заменяем нетерминал в стеке МПА по правилу вывода, а в стек возврата записываем выбранную альтернативу).

Шаг 2 («Успешное сравнение»): (q, i, ab, m) ® (q, i+1, b, ma), если a = a_i, aÎVT (текущий символ стека МПА совпадает с i-м во входной цепочке – тогда переписываем этот терминальный символ a в стек возвратов и переходим к рассмотрению следующего (i+1) символа).

Шаг 3 («Завершение»): Если в стеке МПА пусто, то: (q, i, l, m) ® (b, i, l, m), если i ¹ n+1, и разбор завершён, если i =n+1.

Шаг 4 («Неуспешное сравнение»): (q, i, ab, m) ® (b, i, ab, m), если a ¹ a_i, aÎVT (текущий символ стека МПА отличен от i-го во входной цепочке – тогда переходим в состояние возврата).

Шаг 5 («Возврат по входу»): (b, i, b, ma) ® (b, i–1, ab, m) "aÎVT (возвращаемся к предыдущему символу входной цепочки, переписав терминальный символ из стека возврата в стек МПА).

Шаг 6 («Другая альтернатива»): Состояние алгоритма (b, i, g_jb, mA_j).

§  Если существует другая альтернатива для символа AÎVN: A ® g_j+1, то перейти (b, i, g_jb, mA_j) ® (q, i, g_j+1b, mA_j+1) (переходим к рассмотрению другой альтернативы для последнего примененного правила для нетерминала A – записываем номер очередной альтернативы в стек возврата вместо предыдущего и заменяем цепочку в стеке).

§  Если A º S, i = 1 и нет больше неиспользованных альтернатив для символа S, то сигнализировать об ошибке и прекратить выполнение.

§  Если нет больше неиспользованных альтернатив для символа A, но A ¹ S, то перейти (b, i, g_jb, mA_j) ® (, i, Ab, m) (возвращаем последний нетерминал из стека возврата в стек МПА, заменив им выведенную ранее из него цепочку).

В случае успешного завершения алгоритма на основе содержимого стека возврата можно построить цепочку вывода. Если в стеке содержится символ A_j, то в цепочку вывода помещают номер правила, соответствующего альтернативе A ® g_j; при этом игнорируются все терминальные символы, находящиеся в стеке возврата.

Заметим, что в состоянии прямого хода алгоритма (q) его поведение на очередном шаге определяется содержимым стека L₁, а в состоянии обратного хода (b) – содержимым стека L₂.