Достаточные условия применимости метода рекурсивного спуска

Метод рекурсивного спуска применим к грамматике, если правила вывода грамматики имеют один из следующих видов:

1) A ® a, где a Î(T È N)^*, и это единственное правило вывода для этого нетерминала;

2) A ® a ₁ a ₁ | a ₂ a ₂ |…| a_na_n, где a_i Î T для каждого i= 1, 2,…, n; a_i¹a_j для i¹j, a_i Î(T È N)^*, т.е. если для нетерминала А несколько правил вывода, то они должны начинаться с терминалов, причем эти терминалы должны быть различными.

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

При описании синтаксиса языков программирования часто встречаются правила, которые задают последовательность однотипных конструкций, отделенных друг от друга каким-либо разделителем. Общий вид таких правил:

L ® a | a, L или в сокращенной форме L ® a {, a }.

Формально здесь не выполняются условия метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Но если принять соглашения, что в подобных ситуациях выбирается самая длинная подцепочка, выводимая из нетерминала L, то разбор становится детерминированным, и метод рекурсивного спуска будет применим к данному правилу грамматики. Соответствующая правилу процедура будет иметь вид:

procedure L;

begin

if CH <>’ a ’ then Err else gc;

while CH =’,’ do

begin

gc;

if CH <>’ a ’ then Err else gc

end

end;

Распознаватели LL(k)-грамматик