Принципы работы распознавателей с возвратом

Распознаватели с возвратом – это самый примитивный тип распознавателей для КС-языков. Логика их работы основана на моделировании недетерминированно­го МП-автомата.

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

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

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

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

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

Есть еще одна особенность в моделировании МП-автомата: любой практически ценный алгоритм должен завершаться за конечное число шагов (успешно или неуспешно). Алгоритм моделирования работы произвольного МП-автомата в об­щем случае не удовлетворяет этому условию. Например, даже после считывания всей входной цепочки символов МП-автомат может совершить произвольное (в том числе и бесконечное) число -переходов. В том случае, если цепочка не принята, это может привести к бесконечному количеству шагов моделирующего алгоритма, который по этой причине никогда не будет закончен.

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

Алгоритмы разбора с возвратами обладают экспоненциальными характеристика­ми. Это значит, что вычислительные затраты алгоритмов экспоненциально зави­сят от длины входной цепочки символов: α, αVT*, n=|α|. Конкретная зависи­мость определяется вариантом реализации алгоритма.

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

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

Далее рассмотрены два основных варианта таких алгоритмов.