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

Существует масса способов реализации алгоритма, моделирующего работу этого МП-автомата. Рассмотрим один из примеров реализации алгоритма нисходяще­го распознавателя с возвратом.

Для работы алгоритма используется МП-автомат, построенный на основе исход­ной грамматики G(VT,VN,P,S). Для удобства работы все правила из множест­ва Р в грамматике G представим в виде A->a₁|a₂|…|a_n, то есть пронумеруем все возможные альтернативы для каждого нетерминального символа AÎVN. Вход­ная цепочка символов имеет вид a=a₁a_2…a_n, |a| = n. В алгоритме используется также еще дополнительное состояние автомата b (от «back» — «назад»), которое сигнализирует о выполнении возврата к уже прочитанной части входной цепоч­ки. Для хранения уже выбранных альтернатив используется дополнительный стек L₂, который может содержать следующую информацию:

символы aÎVT входного языка автомата;

символы вида A_j, где A ÎVN — это означает, что среди всех возможных правил для символа А была выбрана альтернатива с номером j.

В итоге алгоритм работает с двумя стеками: l₁ — стек МП-автомата и L₂ — стек возвратов. Оба они представлены в виде цепочек символов. Символы в цепочку стека l₁ помещаются слева, а в цепочку стека L₂ — справа. В целом состояние ал­горитма на каждом шаге определяется четырьмя параметрами: (Q, i, L₁, L₂), где Q — текущее состояние автомата (q или b); i — положение считывающей голов­ки во входной цепочке символов a (1 < i <= n+1); L₁ — содержимое стека МП-ав­томата; L₂ — содержимое дополнительного стека.

Начальным состоянием алгоритма является состояние (q, 1, S, l), где S — целе­вой символ грамматики. Алгоритм начинает свою работу с начального состояния и циклически выполняет шесть шагов до тех пор, пока не перейдет в конечное состояние или не обнаружит ошибку. На каждом шаге алгоритма проверяется, соответствует ли текущее состояние алгоритма заданному для данного шага ис­ходному состоянию, и выполняются ли заданные дополнительные условия. Если это требование выполняется, алгоритм переходит в следующее состояние, уста­новленное для этого шага, если нет — шаг пропускается, алгоритм переходит к следующему шагу.

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

Шаг 1 (Разрастание), (q, i, Аb, a) —> (q, i, g₁b, aA₁), если A->g₁ — это первая из всех возможных альтернатив для символа А.

Шаг 2 (Успешное сравнение), (q, i, ab, a) -> (q, i+1, b, aа), если а = а_i, aÎVT.

Шаг 3 (Завершение). Если состояние соответствует (q, n+1, l, a), то разбор завер­шен, алгоритм заканчивает работу, иначе (q, i, l, a) -> (b, i, l, a), когда i¹n+1.

Шаг 4 (Неуспешное сравнение), (q, i, аb, a) —> (b, i, аb, a), если а ¹a_i, aÎVT.

Шаг 5 (Возврат по входу), (b, i, b, aа) —> (q, i-1, ab, a)), "aÎVT.

Шаг 6 (Другая альтернатива). Исходное состояние (b, i, g_jb, aA_j), действия:

· перейти в состояние (q, i, g_j+1b, aA_j+1), если еще существует альтернатива A—>g_j+1 для символа A ÎVN;

· сигнализировать об ошибке и прекратить выполнение алгоритма, если AºS и не существует больше альтернатив для символа S;

· иначе перейти в состояние (q, i, Аb, a).

В случае успешного завершения алгоритма цепочку вывода можно построить на основе содержимого стека L₂, полученного в результате выполнения алгоритма. Цепочка вывода строится следующим образом: поместить в цепочку номер пра­вила m, соответствующий альтернативе А—>g_j, если в стеке содержится символ A_j; все символы aÎVT, содержащиеся в стеке L₂, игнорируются.

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

Рассмотрим в качестве примера грамматику G ({+.-,/,*, a, b}, {S, R, T, F, E}, P, S) с правилами (это нелеворекурсивная грамматика):

Р:

S -> Т | TR

R -> +T | -Т | +TR | -TR

Т -> Е | EF

F -> *Е | /Е | *EF | /EF

Е -> (S) | а | b

Проследим разбор цепочки а+(а*b) из языка этой грамматики с помощью алго­ритма нисходящего распознавателя с возвратами. Работу алгоритма будем пред­ставлять в виде последовательности его состояний, взятых в скобки {} (фигурные скобки используются, чтобы не путать их с круглыми скобками, предусмотрен­ными в правилах грамматики). Альтернативы будем нумеровать слева направо, правила — слева направо и сверху вниз. Для пояснения каждый шаг работы со­провождается номером шага алгоритма, который был применен для перехода в очередное состояние (записывается перед состоянием через символ «:» — двое­точие).

Алгоритм работы нисходящего распознавателя с возвратами при разборе цепоч­ки а+(а*b) будет выполнять следующие шаги:

На основании полученной цепочки номеров альтернатив S₂T₁E₂R₁T₁E₁S₁T₂E₂F₁E₃

построим последовательность номеров примененных правил: 2, 7, 14, 3, 7, 13, 1, 8, 14, 9, 15. Получаем левосторонний вывод: S => TR => ER => aR => a+T => a+E => a+(S) => a+(T) => a+(EF) => a+(aF) => a+(a*E) => a+(a*b). Соответствующее ему дерево вывода приведено на рис. 11.2.

Рис. 11.2. Дерево вывода для грамматики без левых рекурсий

Из приведенного примера очевиден недостаток алгоритма нисходящего разбора с возвратами — значительная временная емкость: для разбора достаточно корот­кой входной цепочки (всего 7 символов) потребовалось 68 шагов работы алго­ритма. Такого результата и следовало ожидать, исходя из экспоненциальной зависимости необходимых для работы алгоритма вычислительных ресурсов от длины входной цепочки. Это существенный недостаток данного алгоритма.

Преимуществом данного алгоритма можно считать простоту его реализации. Прак­тически этот алгоритм разбора можно использовать только тогда, когда извест­но, что длина исходной цепочки символов заведомо не будет большой (не боль­ше нескольких десятков символов). Для реальных компиляторов такое условие невыполнимо, но для некоторых небольших распознавателей вполне допустимо, и здесь данный алгоритм разбора может найти применение именно благодаря своей простоте.

Еще одно преимущество алгоритма — его универсальность. На его основе можно распознавать входные цепочки языка, заданного любой КС-грамматикой, доста­точно лишь привести ее к нелеворекурсивному виду (а это можно сделать с любой грамматикой, см. раздел «Преобразование КС-грамматик. Приведенные грамма­тики»). Интересно, что грамматика даже не обязательно должна быть однознач­ной — для неоднозначной грамматики алгоритм найдет один из возможных ле-носторонних выводов.

Сам по себе алгоритм разбора с подбором альтернатив, использующий возвраты, • не находит применения в реальных компиляторах. Однако его основные принци­пы лежат в основе многих нисходящих распознавателей, строящих левосторон­ние выводы и работающих без использования возвратов. Методы, позволяющие строить такие распознаватели для некоторых классов КС-языков, рассмотрены далее. Эти распознаватели будут более эффективны в смысле необходимых вы­числительных ресурсов, но алгоритмы их работы уже более сложны, кроме того, они не являются универсальными.

3.2.3 Распознаватель на основе алгоритма «сдвиг-свертка»

3.2.3.1. Принцип работы восходящего распознавателя по алгоритму «сдвиг-свертка»

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

Начальная конфигурация автомата определяется так: (q,a, l) — автомат пребыва­ет в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов aÎVT^*, стек пуст.

Конечная конфигурация автомата определяется так: (q, l, S) — автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S.

Функция переходов МП-автомата строится на основе правил грамматики:

1. (q,A) Îd(q, l, g), AÎVN, gÎ(VTÈVN)^*, если правило А->g содержится во мно­жестве правил Р грамматики G: А->gÎ Р.

2. (q, a)Îd(q, a, l) "aÎVT.

Неформально работу этого расширенного автомата можно описать так: если на верхушке стека находится цепочка символов g, то ее можно заменить на нетер­минальный символ А, если в грамматике языка существует правило вида А—>g, не сдвигая при этом считывающую головку автомата (этот шаг работы называет­ся «свертка»); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки а, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется «сдвиг» или «перенос»). Сам алгоритм, моделирующий работу такого расширенного ав­томата, называется алгоритмом «сдвиг-свертка» или «перенос-свертка» (по на­званиям основных действий алгоритма).

Данный расширенный МП-автомат строит правосторонние выводы для грамматики. Для моделирования такого автомата необходимо, чтобы грамматика G(VT, VN, P, S) не содержала l-правил и цепных правил (иначе, автомат может войти в бесконечный цикл из сверток). Поскольку произвольную КС-грамматику всегда можно преобразовать к виду без l-правил и цепных правилБ о этот алгоритм применим для любой КС-граматики, следовательно, им можно распознавать цепочки любого КС-языка.

Этот расширенный МП-автомат строит правосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода снизу вверх. Такой распознаватель называется восходящим.

Данный расширенный МП-автомат потенциально имеет больше неоднозначностей, чем рассмотренный выше МП-автомат, основанный на алгоритме подбора альтернатив. На каждом шаге работы автомата надо решать следующие вопросы:

· что необходимо выполнять: сдвиг или свертку;

· если выполнять свертку, то какую цепочку g выбрать для поиска правил (цепочка g должна встречаться в правой части правил грамматики);

· какое правило выбрать для свертки, если окажется, что существует несколько правил вида А->g (несколько правил с одинаковой правой частью).

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

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