Первый вариант предполагает запоминание на каждом шаге работы всех возможных следующих состояний. Алгоритм моделирует работу автомата по одному из возможных переходов до тех пор, пока либо не будет достигнута конечная конфигурация автомата, либо возникнет ситуация, когда следующая конфигурация не определена. В последнем случае происходит возврат на несколько шагов назад в ту конфигурацию, из которой был возможен альтернативный вариант, и моделирование продолжается. Если какая-то из последовательностей шагов приводит к заключительной конфигурации, то цепочка считается принятой, а автомат заканчивает работу. Если все варианты работы перебраны, а конечная конфигурация не достигнута, то алгоритм завершается с ошибкой.
Во втором варианте алгоритм моделирования МПА на каждом шаге работы при возникновении неоднозначности с несколькими возможными следующими состояниями должен запускать свою новую копию для обработки каждого из этих состояний. Если хотя бы одна из копий приводит в заключительную конфигурацию, то цепочка распознана и работа всех остальных копий также завершается. Если ни одна из копий не достигнет конечной конфигурации, алгоритм завершается с ошибкой и цепочка не принимается.
Во втором варианте различные копии алгоритма должны выполняться параллельно, следовательно, необходимо наличие механизма управления параллельными процессами. Кроме того, количество копий алгоритма заранее неизвестно, их может быть много, в то время как количество одновременно выполняющихся процессов ограничено. Этим объясняется то, что большее распространение получил первый вариант алгоритма, который называется «разбором с возвратами».
Хотя МПА представляет собой односторонний распознаватель, алгоритм моделирования его работы предусматривает возврат к уже прочитанной цепочке символов.
Кроме того, любой практический алгоритм должен завершаться за конечное время. Алгоритм моделирования работы произвольного МПА в общем случае не удовлетворяет такому условию. Например, после считывания всей входной цепочки МПА может совершить произвольное число (может быть, и бесконечное) l-переходов. В таком случае, если входная цепочка не принята, алгоритм может никогда не завершиться.
Для того чтобы избежать таких ситуаций, алгоритм работы МПА с возвратами строят не для произвольных автоматов, а для автоматов, удовлетворяющих некоторым заданным условиям. Обычно грамматику исходного языка подвергают сначала некоторым эквивалентным преобразованиям, приводя её к заранее заданному виду.
Вычислительная сложность алгоритмов:
Алгоритмы разбора с возвратами имеют экспоненциальную сложность, т.е. их вычислительные затраты экспоненциально зависят от длины входной цепочки символов. Обозначим эту цепочку a½aÎVT*, её длина ½a½= n. Конкретный характер зависимости определяется вариантом реализации алгоритма.
В общем случае при первом варианте реализации время выполнения алгоритма для произвольной КС-грамматики имеет экспоненциальную, а необходимый объём памяти – линейную зависимость от длины входной цепочки: T=O(en), M=O(n). При втором варианте ситуация обратная – время имеет линейную зависимость, а требуемый объём памяти – экспоненциальную: T=O(n), M=O(en). В любом случае, непомерно большие вычислительные затраты на реализацию алгоритма существенно ограничивают возможности его применения. Для конкретных классов КС-языков существуют более эффективные алгоритмы распознавания.
Основные варианты разбора с возвратом – это нисходящий распознаватель и распознаватель на основе алгоритма «сдвиг-свёртка».
3.4.1.1 Нисходящий распознаватель с возвратом
Этот распознаватель моделирует работу МПА с одним состоянием q: R({q}, V, Z, d, q, S, {q}). Автомат распознаёт цепочки КС-языка, задаваемого грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит терминальные символы грамматики V=VT, а алфавит магазинных символов Z=VTÈVN.
Начальная конфигурация автомата (q,a,S), где входная цепочка aÎVT*, а в стеке находится целевой символ грамматики. Конечная (заключительная) конфигурация автомата (q,l,l).
Функция перехода строится на основе правил грамматики следующим образом:
1. Если правило (A ® m)ÎP, то (q,m)Îd(q,l,A), AÎVN, mÎ(VTÈVN)*.
2. "aÎVT (q,l)Îd(q,a,a).
Работу автомата можно описать следующим образом. Если на верхушке стека находится нетерминальный символ A, то его можно заменить на цепочку символов m, если (A ® m)ÎP, не сдвигая при этом считывающую головку автомата. Этот шаг работы алгоритма называется «подбор альтернативы». Если на верхушке стека находится терминальный символ, совпадающий с текущим входным символом, то его можно выбросить из стека, а считывающую головку передвинуть на один символ вправо. Данный шаг называется «выброс». Если в грамматике окажется более одного правила вида (A ® m)ÎP с различными m, то функция будет содержать более одного следующего состояния, следовательно, у автомата будет несколько альтернатив.
Рассмотренный автомат строит левосторонние выводы для грамматики G, следовательно, эта грамматика не должна быть леворекурсивной. Ранее было показано, что к нелеворекурсивному виду может быть приведена произвольная грамматика, следовательно, алгоритм является универсальным. Поскольку цепочка входных символов считывается слева направо, а вывод является левосторонним, дерево строится сверху вниз. Такой распознаватель называется нисходящим.
На каждом шаге работы МП-автомата необходимо принимать решение о том, выполнять выброс или подбор альтернативы. Алгоритм должен иметь возможность выбирать поочерёдно все альтернативы, следовательно, необходимо хранить информацию о том, какие варианты уже использованы, чтобы вернуться к этому шагу и подобрать другие альтернативы. Такой алгоритм разбора называется алгоритмом с подбором альтернатив.
Существует множество способов моделирования работы данного МП-автомата. Рассмотрим один из примеров его реализации.
Алгоритм распознавателя с подбором альтернатив.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.