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

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

Начальная конфигурация автомата определяется так: (q,α,S) – автомат пребы­вает в своем единственном состоянии q, считывающая головка находится в нача­ле входной цепочки символов αVT*, в стеке лежит символ, соответствующий целевому символу грамматики S.

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

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

1. (q,α)(q,,A), AVN, α(VTVN)*, если правило Aα содержится во мно­жестве правил Р грамматики G: Aα  Р.

2. (q,)(q,a,a) aVT.

Этот МП-автомат уже был рассмотрен выше.

Работу данного МП-автомата можно неформально описать следующим образом: если на верхушке стека автомата находится нетерминальный символ А, то его можно заменить на цепочку символов α, если в грамматике языка есть правило Аα, не сдвигая при этом считывающую головку автомата (этот шаг работы на­зывается “подбор альтернативы”); если же на верхушке стека находится терми­нальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется “выброс”). Данный МП-ав­томат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида Аα, следовательно, тогда функция (q,,A) будет содержать более одного следующего со­стояния – у автомата будет несколько альтернатив.

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

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

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

3.5.3. Распознаватель на основе алгоритма “сдвиг-свертка”

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

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

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

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

1. (q,A)(q,,γ), АVN, γ(VTVN)*, если правило Аγ содержится во мно­жестве правил Р грамматики G: Аγ  Р.

2. (q,a)(q,a,) aVT.

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

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

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

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

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

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

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

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