Распознаватели КС-языков с возвратом

Распознаватели КС-языков с возвратом представляют собой самый простой тип распознавателей, основанный на модели недетерминированного МП-автомата. Как известно, при работе такого автомата возможны альтернативные варианты его поведения. Существуют два варианта реализации алгоритма работы недетерминированного МПА.

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

Во втором варианте алгоритм моделирования МПА на каждом шаге работы при возникновении неоднозначности с несколькими возможными следующими состояниями должен запускать свою новую копию для обработки каждого из этих состояний. Если хотя бы одна из копий приводит в заключительную конфигурацию, то цепочка распознана и работа всех остальных копий также завершается. Если ни одна из копий не достигнет конечной конфигурации, алгоритм завершается с ошибкой и цепочка не принимается.

Во втором варианте различные копии алгоритма должны выполняться параллельно, следовательно, необходимо наличие механизма управления параллельными процессами. Кроме того, количество копий алгоритма заранее неизвестно, их может быть много, в то время как количество одновременно выполняющихся процессов ограничено. Этим объясняется то, что большее распространение получил первый вариант алгоритма, который называется «разбором с возвратами».

Хотя МПА представляет собой односторонний распознаватель, алгоритм моделирования его работы предусматривает возврат к уже прочитанной цепочке символов.

Кроме того, любой практический алгоритм должен завершаться за конечное время. Алгоритм моделирования работы произвольного МПА в общем случае не удовлетворяет такому условию. Например, после считывания всей входной цепочки МПА может совершить произвольное число (может быть, и бесконечное) e-переходов. В таком случае, если входная цепочка не принята, алгоритм может никогда не завершиться.

Для того чтобы избежать таких ситуаций, алгоритм работы МПА с возвратами строят не для произвольных автоматов, а для автоматов, удовлетворяющих некоторым заданным условиям. Обычно грамматику исходного языка подвергают сначала некоторым эквивалентным преобразованиям, приводя её к заранее заданному виду.

Вычислительная сложность алгоритмов:

Алгоритмы разбора с возвратами имеют экспоненциальную сложность, т.е. их вычислительные затраты экспоненциально зависят от длины входной цепочки символов. Обозначим эту цепочку a½aÎV_T^*, её длина ½a½= n. Конкретный характер зависимости определяется вариантом реализации алгоритма.

В общем случае при первом варианте реализации время выполнения алгоритма для произвольной КС-грамматики имеет экспоненциальную, а необходимый объём памяти – линейную зависимость от длины входной цепочки: T=O(eⁿ), M=O(n). При втором варианте ситуация обратная – время имеет линейную зависимость, а требуемый объём памяти – экспоненциальную: T=O(n), M=O(eⁿ). В любом случае, непомерно большие вычислительные затраты на реализацию алгоритма существенно ограничивают возможности его применения. Для конкретных классов КС-языков существуют более эффективные алгоритмы распознавания.

Основные варианты разбора с возвратом – это нисходящий распознаватель и распознаватель на основе алгоритма «сдвиг-свёртка».

4.3.1.1. Нисходящий распознаватель с возвратом (с подбором альтернатив)

Этот распознаватель моделирует работу МПА с одним состоянием q: R({q}, V, Z, d, q, S, {q}). Автомат распознаёт цепочки КС-языка, задаваемого грамматикой G(V_T,V_N,P,S). Входной алфавит автомата содержит терминальные символы грамматики V=V_T, а алфавит магазинных символов Z=V_TÈV_N.

Начальная конфигурация автомата (q,a,S), где входная цепочка aÎV_T^*, а в стеке находится целевой символ грамматики. Конечная (заключительная) конфигурация автомата (q, e,e).

Функция перехода строится на основе правил грамматики следующим образом:

1. Если правило (A ® m)ÎP, то (q,m)Îd(q, e,A), AÎV_N, mÎ(V_TÈV_N)^*.

2. "aÎV_T (q, e)Îd(q,a,a).

Работу автомата можно описать следующим образом. Если на верхушке стека находится нетерминальный символ A, то его можно заменить на цепочку символов m, если (A ® m)ÎP, не сдвигая при этом считывающую головку автомата. Этот шаг работы алгоритма называется «подбор альтернативы». Если на верхушке стека находится терминальный символ, совпадающий с текущим входным символом, то его можно выбросить из стека, а считывающую головку передвинуть на один символ вправо. Данный шаг называется «выброс». Если в грамматике окажется более одного правила вида (A ® m)ÎP с различными m, то функция будет содержать более одного следующего состояния, следовательно, у автомата будет несколько альтернатив.

Рассмотренный автомат строит левосторонние выводы для грамматики G, следовательно, эта грамматика не должна быть леворекурсивной. Ранее было показано, что к нелеворекурсивному виду может быть приведена произвольная грамматика, следовательно, алгоритм является универсальным. Поскольку цепочка входных символов считывается слева направо, а вывод является левосторонним, дерево строится сверху вниз. Такой распознаватель называется нисходящим.

На каждом шаге работы МП-автомата необходимо принимать решение о том, выполнять выброс или подбор альтернативы. Алгоритм должен иметь возможность выбирать поочерёдно все альтернативы, следовательно, необходимо хранить информацию о том, какие варианты уже использованы, чтобы вернуться к этому шагу и подобрать другие альтернативы. Такой алгоритм разбора называется алгоритмом с подбором альтернатив.

Существует множество способов моделирования работы данного МП-автомата. Рассмотрим один из примеров его реализации.

Алгоритм распознавателя с подбором альтернатив.

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

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

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

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

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

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

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

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

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

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

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

§ Если существует другая альтернатива для символа AÎV_N: 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₂.

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

S ® T [ S ₁ ] ½TR [ S ₂ ], 

R ® +T [ R ₁ ] ½–T [ R ₂ ] ½+TR [ R ₃ ] ½–TR [ R ₄ ].

T ® E [ T ₁ ] ½EF [ T ₂ ], 

F ® *E [ F ₁ ] ½/E [ F ₂ ] ½*EF [ F ₃ ] ½/EF [ F ₄ ].

E ® (S) [ E ₁ ] ½a [ E ₂ ] ½b [ E ₃ ].

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

1,2 {q,1, S, e} |¾(1) {q,1, T,S1}		раскроем нетерминал T
3 |¾(1) {q,1, E,S1T1}		раскроем нетерминал E
4 |¾(1) {q,1, ( S),S1T1E1}		первый символ – не “(”
5 |¾(4) {b,1, (S),S1T1 E1 }		выберем след. альтернативу для E
6 |¾(6,1) {q,1, a,S1T1E2}		первый символ совпал, сдвиг головки
7 |¾(2) {q,2, e,S1T1E2a}		в стеке пусто, но i¹n+1 – возврат
8 |¾(3) {b,2, e,S1T1E2a}		возвращаем “a” из стека возврата в L1
9 |¾(5) {b,1, a,S1T1 E2 }		выберем след. альтернативу для E
10 |¾(6,1) {q,1, b,S1T1E3}		первый символ – не “b”
11 |¾(4) {b,1, b,S1T1 E3 }		вернем E из L2 в L1
12 |¾(6,3) {b,1, E,S1 T1 }		выберем след. альтернативу для T
13 |¾(6,1) {q,1, E F,S1T2}		раскроем нетерминал E
14 |¾(1) {q,1, ( S)F,S1T2E1}		первый символ – не “(”
15 |¾(4) {b,1, (S) F,S1T2 E1 }		выберем след. альтернативу для E
16 |¾(6,1) {q,1, a F,S1T2E2}		первый символ совпал, сдвиг головки
17 |¾(2) {q,2, F,S1T2E2a}		раскроем нетерминал F
18 |¾(1) {q,2, * E,S1T2E2aF1}		второй символ – не “*”
19 |¾(4) {b,2, *E,S1T2E2a F1 }		выберем след. альтернативу для F
20 |¾(6,1) {q,2, / E,S1T2E2aF2}		второй символ совпал, перепишем в L2
21 |¾(2) {q,3, E,S1T2E2aF2/}		раскроем нетерминал E
22 |¾(1) {q,3, ( S),S1T2E2aF2/E1}		третий символ совпал, перепишем в L2
23 |¾(2) {q,4, S),S1T2E2aF2/E1(}		раскроем нетерминал S
24 |¾(1) {q,4, T),S1T2E2aF2/E1(S1}		раскроем нетерминал T
25 |¾(1) {q,4, E),S1T2E2aF2/E1(S1T1}	раскроем нетерминал E
26 |¾(1) {q,4, ( S)),S1T2E2aF2/E1(S1T1E1}	4-й символ – не “(”
27 |¾(4) {b,4, (S)),S1T2E2aF2/E1(S1T1 E1 }	выберем след. альтернативу для E
28 |¾(6,1) {q,4, a),S1T2E2aF2/E1(S1T1E2}	4-й символ совпал, переносим в L2
29 |¾(2) {q,5, ),S1T2E2aF2/E1(S1T1E2a}	5-й символ не совпал
30 |¾(4) {b,5,),S1T2E2aF2/E1(S1T1E2a}	в стеке L2 – терминал, вернём его
31 |¾(5) {b,4, a),S1T2E2aF2/E1(S1T1 E2 }	выберем след. альтернативу для E
32 |¾(6,1) {q,4, b),S1T2E2aF2/E1(S1T1E3}	4-й символ не совпал
33 |¾(4) {b,4, b),S1T2E2aF2/E1(S1T1 E3 }				нет альтернатив для E
34 |¾(6,3) {b,4, E),S1T2E2aF2/E1(S1 T1 }				выберем след. альтернативу для T
35 |¾(6,1) {q,4, E F),S1T2E2aF2/E1(S1T2}				раскроем нетерминал E
36 |¾(1) {q,4, ( S)F),S1T2E2aF2/E1(S1T2E1}				4-й символ не совпал
37 |¾(4) {b,4, (S) F),S1T2E2aF2/E1(S1T2 E1 }				выберем след. альтернативу для E
38 |¾(6,1) {q,4, a F),S1T2E2aF2/E1(S1T2E2}				4-й символ совпал
39 |¾(2) {q,5, F),S1T2E2aF2/E1(S1T2E2a}				раскроем нетерминал F
40 |¾(1) {q,5, * E),S1T2E2aF2/E1(S1T2E2aF1}				5-й символ не совпал
41 |¾(4) {b,5, *E),S1T2E2aF2/E1(S1T2E2a F1 }				выберем след. альтернативу для F
42 |¾(6,1) {q,5, / E),S1T2E2aF2/E1(S1T2E2aF2}				5-й символ не совпал
43 |¾(4) {b,5, /E),S1T2E2aF2/E1(S1T2E2a F2 }			выберем след. альтерн. для F
44 |¾(6,1) {q,5, * EF),S1T2E2aF2/E1(S1T2E2aF3}			5-й символ не совпал
45 |¾(4) {b,5, *EF),S1T2E2aF2/E1(S1T2E2a F3 }			выберем след. альтерн. для F
46 |¾(6,1) {q,5, / EF),S1T2E2aF2/E1(S1T2E2aF4}			5-й символ не совпал
47 |¾(4) {b,5, /EF),S1T2E2aF2/E1(S1T2E2a F4 }			для F нет альтернативы
48 |¾(6,3) {b,5,F),S1T2E2aF2/E1(S1T2E2 a }				возврат по символу
49 |¾(5) {b,4, a F),S1T2E2aF2/E1(S1T2 E2 }				выберем след. альтернативу для E
50 |¾(6,1) {q,4, b F),S1T2E2aF2/E1(S1T2E3}				4-й символ не совпал
51 |¾(4) {b,4, b F),S1T2E2aF2/E1(S1T2 E3 }				вернем E из L2 в L1
52 |¾(6,3) {b,4, EF),S1T2E2aF2/E1(S1 T2 }				вернем T из L2 в L1
53 |¾(6,3) {b,4, T),S1T2E2aF2/E1(S1 }				выберем след. альтернативу для S
54 |¾(6,1) {q,4, T R),S1T2E2aF2/E1(S2}				раскроем нетерминал T
55 |¾(1) {q,4, E R),S1T2E2aF2/E1(S2T1}				раскроем нетерминал E
56 |¾(1) {q,4, ( S)R),S1T2E2aF2/E1(S2T1E1}				4-й символ не совпал
57 |¾(4) {b,4, (S) R),S1T2E2aF2/E1(S2T1 E1 }				выберем след. альтернативу для E
58 |¾(6,1) {q,4, a R),S1T2E2aF2/E1(S2T1E2}				4-й символ совпал, переносим в L2
59 |¾(2) {q,5, R),S1T2E2aF2/E1(S2T1E2a}				раскроем нетерминал R
60 |¾(1) {q,5, + T),S1T2E2aF2/E1(S2T1E2aR1}				5-й символ не совпал
61 |¾(4) {b,5, +T),S1T2E2aF2/E1(S2T1E2a R1 }				выберем след. альтернативу для R
62 |¾(6,1) {q,5, – T),S1T2E2aF2/E1(S2T1E2aR2}				5-й символ совпал, переносим в L2
63 |¾(2) {q,6, T),S1T2E2aF2/E1(S2T1E2aR2–}				раскроем нетерминал T
64 |¾(1) {q,6, E),S1T2E2aF2/E1(S2T1E2aR2–T1}			раскроем нетерминал E
65 |¾(1) {q,6, ( S)),S1T2E2aF2/E1(S2T1E2aR2–T1E1}				6-й символ не совпал
66 |¾(4) {b,6, (S)),S1T2E2aF2/E1(S2T1E2aR2–T1 E1 }				выберем след. альтер. для E
67 |¾(6,1) {q,6, a),S1T2E2aF2/E1(S2T1E2aR2–T1E2}				6-й символ не совпал
68 |¾(4) {b,6, a),S1T2E2aF2/E1(S2T1E2aR2–T1 E2 }				выберем след. альтер. для E
69 |¾(6,1) {q,6, b),S1T2E2aF2/E1(S2T1E2aR2–T1E3}				6-й символ совпал
70 |¾(2) {q,7, ),S1T2E2aF2/E1(S2T1E2aR2–T1E3b}				7-й символ совпал
71 |¾(2) {q,8, e,S1T2E2aF2/E1(S2T1E2aR2–T1E3b)}|¾(3)					Разбор закончен stop(+)

Разбор закончен, стек МПА пуст. Если взять последовательность нетерминальных символов из стека возвратов, получим цепочку номеров альтернатив и можем построить дерево вывода.

В стеке возврата цепочка S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₃b. Удалив терминальные символы, получим S₁T₂E₂F₂E₁S₂T₁E₂R₂T₁E₃. Тогда цепочка вывода будет иметь вид: SÞTÞEFÞaFÞa/EÞa/(S)Þa/(TR)Þa/(ER)Þa/(aR)Þa/(a–T)Þa/(a–E)Þa/(a–b). Дерево вывода показано на рисунке справа.

Из рассмотренного примера видно, что недостатком алгоритма нисходящего разбора с возвратами является большое время работы. Для разбора достаточно короткой цепочки из 7 символов потребовалось выполнить 70 шагов.

Преимуществом алгоритма является его простота реализации и универсальность.

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