Пример 4.2

Рассмотрим грамматику G = ({a,b}, {S,A}, { S ® bAa, A ® aA | e}, S)

Для данной грамматики РС-анализатор, реализованный по обычной схеме, будет таким:

void S(void)

{if (c == ‘b’) {c = fgetc(fp); A();

if (c != ‘a’) ERROR();}

else ERROR();

}

void A(void)

{if (c == ‘a’) {c = fgetc(fp); A();}

}

Тогда при анализе цепочки baaa функция A() будет вызвана три раза; она прочитает подцепочку ааа, хотя третий символ а - это часть подцепочки, выводимой из S. В результате окажется, что baaa не принадлежит языку, порождаемому грамматикой, хотя в действительности это не так.

Проблема заключается в том, что подцепочка, следующая за цепочкой, выводимой из A, начинается таким же символом, как и цепочка, выводимая из А.

Однако в грамматике G = ({a,b,с}, {S,A}, { S ® bAс , A ® aA | e }, S)

нет проблем с применением метода рекурсивного спуска.

Выпишем условие, при котором e-правило вывода делает неприменимым РС-метод.

Пусть множество FIRST(A) - это множество терминальных символов, которыми начинаются цепочки, выводимые из А в грамматике
G = (VT, VN, P, S), то есть FIRST(A) = { a Î VT | A Þ aa, A Î VN,
a Î (VT È VN)^*}.

Пустьмножество FOLLOW(A) - это множество терминальных символов, которые следуют за цепочками, выводимыми из А в грамматике
G = (VT, VN, P, S), то есть FOLLOW(A) = { a Î VT | S Þ aAb, b Þ ag, A Î VN, a, b, g Î (VT È VN)^*}.

Тогда, если FIRST(A) Ç FOLLOW(A) ¹ Æ ,то метод рекурсивного спуска неприменим к данной грамматике.

Если

A ® a₁A | ... | a_nA | b₁ | ... |b_m| e,

B ® aAb и

FIRST(A) Ç FOLLOW(A) ¹ Æ (из-за вхождения А в правила вывода для В), то можно попытаться преобразовать такую грамматику:

B ® aA’

A’ ® a₁A’ | ... | a_nA’ | b₁b | ... |b_mb| b

A ® a₁A | ... | a_nA | b₁ | ... |b_m| e

Полученная грамматика будет эквивалентна исходной, так как из B по-прежнему выводятся цепочки вида a {a_i} b_j b либо a {a_i} b.

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

Метод рекурсивного спуска применим к достаточно узкому подклассу КС-грамматик. Известны более широкие подклассы КС-грамматик, для которых существуют эффективные анализаторы, обладающие тем же свойством, что и анализатор, написанный методом рекурсивного спуска, - входная цепочка считывается один раз слева направо и процесс разбора полностью детерминирован, в результате на обработку цепочки длины n расходуется время cn. К таким грамматикам относятся LL(k)-грамматики, LR(k)-грамматики, грамматики предшествования и некоторые другие (см., например, [2], [3]).