Этот распознаватель моделирует работу МП-автомата с одним состоянием q: R({q}, V,Z,,q,S,{q}). Автомат распознает цепочки КС-языка, заданного КС-грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит терминальные символы грамматики: V=VT, а алфавит магазинных символов строится из терминальных и нетерминальных символов грамматики: Z = VTVN.
Начальная конфигурация автомата определяется так: (q,α,S) – автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов αVT*, в стеке лежит символ, соответствующий целевому символу грамматики S.
Конечная конфигурация автомата определяется так: (q,,) – автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, стек пуст.
Функция переходов МП-автомата строится на основе правил грамматики:
1. (q,α)(q,,A), AVN, α(VTVN)*, если правило Aα содержится во множестве правил Р грамматики G: Aα Р.
2. (q,)(q,a,a) aVT.
Этот МП-автомат уже был рассмотрен выше.
Работу данного МП-автомата можно неформально описать следующим образом: если на верхушке стека автомата находится нетерминальный символ А, то его можно заменить на цепочку символов α, если в грамматике языка есть правило Аα, не сдвигая при этом считывающую головку автомата (этот шаг работы называется “подбор альтернативы”); если же на верхушке стека находится терминальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется “выброс”). Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида Аα, следовательно, тогда функция (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=VTVN.
Начальная конфигурация автомата определяется так: (q,α,) – автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов αVT*, стек пуст.
Конечная конфигурация автомата определяется так: (q,,S) – автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S.
Функция переходов МП-автомата строится на основе правил грамматики:
1. (q,A)(q,,γ), АVN, γ(VTVN)*, если правило Аγ содержится во множестве правил Р грамматики G: Аγ Р.
2. (q,a)(q,a,) aVT.
Неформально работу этого расширенного автомата можно описать так: если на верхушке стека находится цепочка символов γ, то ее можно заменить на нетерминальный символ А, если в грамматике языка существует правило вида Аγ, не сдвигая при этом считывающую головку автомата (этот шаг работы называется “свертка”); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки а, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется “сдвиг” или “перенос”). Сам алгоритм, моделирующий работу такого расширенного автомата, называется алгоритмом “сдвиг-свертка” или “перенос-свертка” (по названиям основных действий алгоритма).
Данный расширенный МП-автомат строит правосторонние выводы для грамматики G(VT,VN,P,S). Для моделирования такого автомата необходимо, чтобы грамматика G(VT,VN,P,S) не содержала -правил и цепных правил (в противном случае, очевидно, автомат может войти в бесконечный цикл из сверток). Поскольку, как было доказано выше, произвольную КС-грамматику всегда можно преобразовать к виду без -правил и цепных правил, то этот алгоритм применим для любой КС-грамматики, следовательно, им можно распознавать цепочки любого КС-языка.
Этот расширенный МП-автомат строит правосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода снизу вверх. Такой распознаватель называется восходящим.
Данный расширенный МП-автомат потенциально имеет больше неоднозначностей, чем рассмотренный ваше МП-автомат, основанный на алгоритме подбора альтернатив. На каждом шаге работы автомата надо решать следующие вопросы:
что необходимо выполнять: сдвиг или свертку;
если выполнять свертку, то какую цепочку γ выбрать для поиска правил (цепочка должна встречаться в правой части правил грамматики);
какое правило выбрать для свертки, если окажется, что существует несколько правил вида Аγ (несколько правил с одинаковой правой частью).
Чтобы промоделировать работу этого расширенного МП-автомата, надо на каждом шаге запоминать все предпринятые действия, чтобы иметь возможность вернуться к уже сделанному шагу и выполнить эти же действия по-другому. Этот процесс должен повторяться до тех пор, пока не будут перебраны все возможные варианты.
