Распознаватели с возвратом – это самый примитивный тип распознавателей для КС-языков. Логика их работы основана на моделировании недетерминированного МП-автомата.
Поскольку моделируется недетерминированный МП-автомат (который в общем виде не преобразуется в детерминированный), то на некотором шаге работы моделирующего алгоритма возможно возникновение нескольких допустимых следующих состояний автомата. В таком случае существуют два варианта реализации алгоритма.
В первом варианте на каждом шаге работы алгоритм должен запоминать все возможные следующие состояния МП-автомата, выбирать одно из них, переходить в это состояние и действовать так до тех пор, пока либо не будет достигнуто конечное состояние автомата, либо автомат не перейдет в такую конфигурацию, когда следующее состояние будет не определено. Если достигнуто одно из конечных состояний – входная цепочка принята, работа алгоритма завершается. В противном случае алгоритм должен вернуть автомат на несколько шагов назад, когда еще был возможен выбор одного из набора следующих состояний, выбрать другой вариант и промоделировать поведение автомата с этим условием. Алгоритм завершается с ошибкой, когда все возможные варианты работы автомата будут перебраны и ни одно из возможных конечных состояний не было достигнуто.
Во втором варианте алгоритм моделирования МП-автомата должен на каждом шаге работы при возникновении неоднозначности с несколькими возможными следующими состояниями автомата запускать новую свою копию для обработки каждого из этих состояний. Алгоритм завершается, если хотя бы одна из выполняющихся его копий достигнет одно из конечных состояний. При этом работа всех остальных копий алгоритма прекращается. Если ни одна из копий алгоритма не достигла конечного состояния МП-автомата, то алгоритм завершается с ошибкой.
Второй вариант реализации алгоритма связан с управлением параллельными процессами в вычислительных системах, поэтому сложен в реализации. Кроме того, на каждом шаге работы МП-автомата альтернатив следующих состояний может быть много, а количество возможных параллельно выполняющихся процессов в операционных системах ограничено, поэтому применение второго варианта алгоритма осложнено. По этим причинам большее распространение получил первый вариант алгоритма, который предусматривает возврат к ранее запомненным состояниям МП-автомата – отсюда и название “разбор с возвратами”.
Следует отметить, что, хотя МП-автомат является односторонним распознавателем, алгоритм моделирования его работы предусматривает возврат назад, к уже прочитанной части цепочки символов, чтобы исключить недетерминизм в поведении автомата (который невозможно промоделировать).
Есть еще одна особенность в моделировании МП-автомата: любой практически ценный алгоритм должен завершаться за конечное число шагов (успешно или неуспешно). Алгоритм моделирования работы произвольного МП-автомата в общем случае не удовлетворяет этому условию. Например, даже после считывания всей входной цепочки символов МП-автомат может совершить произвольное (в том числе и бесконечное) число -переходов. В том случае, если цепочка не принята, это может привести к бесконечному количеству шагов моделирующего алгоритма, который по этой причине никогда не будет закончен.
Чтобы избежать таких ситуаций, алгоритмы разбора с возвратами строят не для произвольных МП-автоматов, а для МП-автоматов, удовлетворяющим некоторым заданным условиям. Как правило, эти условия связаны с тем, что МП-автомат должен строиться на основе грамматики заданного языка только после того, как она подвергнется некоторым преобразованиям. Поскольку преобразования грамматик сами по себе не накладывают каких-либо ограничений на входной класс КС-языков (в результате преобразования мы всегда получаем эквивалентную грамматику), то они и не ограничивают применимости алгоритмов разбора с возвратами – эти алгоритмы применимы для любого КС-языка, заданного произвольной КС-грамматикой или МП-автоматом.
Алгоритмы разбора с возвратами обладают экспоненциальными характеристиками. Это значит, что вычислительные затраты алгоритмов экспоненциально зависят от длины входной цепочки символов: α, αVT*, n=|α|. Конкретная зависимость определяется вариантом реализации алгоритма.
Доказано, что в общем случае при первом варианте реализации для произвольной КС-грамматики G(VT,VN,P,S) время выполнения данного алгоритма Тэбудет иметь экспоненциальную зависимость от длины входной цепочки, а необходимый объем памяти Мэ– линейную зависимость от длины входной цепочки: Тэ= О(еn) и Мэ= О(n). При втором варианте реализации, наоборот, время выполнения данного алгоритма Тэбудет иметь линейную зависимость от длины входной цепочки, а необходимый объем памяти Мэ– экспоненциальную зависимость от длины входной цепочки: Тэ= О(n) и Мэ= О(еn).
Экспоненциальная зависимость вычислительных затрат от длины входной цепочки существенно ограничивает применимость алгоритмов разбора с возвратами. Они тривиальны в реализации, но имеют неудовлетворительные характеристики, поэтому могут использоваться только для простых КС-языков с малой длиной входных предложений языка. Для многих классов КС-языков существуют более эффективные алгоритмы распознавания, поэтому алгоритмы разбора с возвратами применяются редко.
Далее рассмотрены два основных варианта таких алгоритмов.
