Принцип работы нисходящего распознавателя с подбором альтернатив

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

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

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

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

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

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

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

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

Работу данного МП-автомата можно неформально описать следующим образом:

если на верхушке стека автомата находится нетерминальный символ А, то его можно заменить на цепочку символов к, если в грамматике языка есть правило А-> a, не сдвигая при этом считывающую головку автомата (этот шаг работы на­зывается «подбор альтернативы»); если же на верхушке стека находится терми­нальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется «выброс»). Данный МП-ав­томат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида А—> a, следовательно, тогда функция d(q, l,A) будет содержать более одного следующего со­стояния — у автомата будет несколько альтернатив.

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

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

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

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