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

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

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

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

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

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

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

Шаг 2 («Успешное сравнение»): (q, i, ab, m) ® (q, i+1, b, ma), если a = ai, 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 ¹ ai, aÎVT (текущий символ стека МПА отличен от i-го во входной цепочке – тогда переходим в состояние возврата).

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

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

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

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

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

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

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

Пример. Рассмотрим грамматику G ({+,–,/,*,a,b,(,)}, {S, R, T, F, E}, P, S), где правила P имеют вид:

S ® T [S1]½TR [S2]

R ® +T [R1]½–T [R2]½+TR [R3]½–TR [R4].

T ® E [T1]½EF [T2]

F ® *E [F1]½/E [F2]½*EF [F3]½/EF [F4].

E ® (S) [E1]½a [E2]½b [E3].

Здесь каждое правило сопровождается соответствующим символом [Ai], который будет заноситься в стек возврата. Это нелеворекурсивная грамматика для арифметических выражений, которая была построена ранее. Рассмотрим процесс выполнения разбора цепочки a/(a–b). Состояния алгоритма будем записывать в фигурных скобках. Подчеркиваем одной чертой символы, с которыми работаем в настоящий момент; двумя чертами – не совпавший терминальный символ. В круглых скобках возле знака выводимости записываем номер соответствующего шага алгоритма.