Для каждого нетерминального символа A исходной грамматики строится процедура разбора, на вход которой подается цепочка символов a.
В процессе разбора процедура считывает все символы входной цепочки, относящийся к данному нетерминалу (выводимые из него) или сообщает об ошибке. Если для символа AÎN в грамматике задано несколько правил, то при разборе выбирается то правило, в котором первые символы правой части совпадает с текущими входными символами. Если правила для данного нетерминала содержат в правой части другие нетерминалы, то процедура обращается к процедурам разбора этих нетерминалов. Если искомые символы не получены, то сообщается об ошибке.
По окончании работы процедуры текущим становится первый символ, следующий во входной цепочке за символами, выводимыми их данного нетерминала. Для начала разбора входной цепочки необходимо вызвать процедуру разбора для символа S.
Чтобы данный метод работал как метод без возвратов, необходимы жесткие ограничения на правила задающей язык грамматики. В методе подходящие правила ищутся на основе некоторого терминального символа, входящего в правую часть правила. Выбор в таком случае должен осуществляться однозначно, т.е. для каждого нетерминального символа левой части необходимо, чтобы в правой части разных правил не встречалось двух одинаковых терминальных символов.
Если в методе рекурсивного спуска анализируются только один входной символ, то для каждого нетерминального символа A грамматики G разрешаются только два вида правил:
- (A®b)ÎP, bÎ(NÈT)*, и это единственное правило для A;
- A®a1b1½a2b2½…½anbn, "i aiÎT, bÎ(NÈT)*, и ai¹aj, если i¹j, т.е. все ai различны.
Еще раз подчеркнем, сложность применения метода заключается в том, что несколько соседних символов цепочки могут быть получены с применением не одного, а нескольких правил. Поэтому в общем случае рекурсивный спуск – это метод разбора с возвратами. Поэтому данный метод хотя и нагляден, но при наличии большого количества правил в общем случае слабо применим. Поэтому данный алгоритм применяют для определенного типа грамматик.
