О применимости метода рекурсивного спуска

Метод рекурсивного спуска применим в том случае, если каждое правило грамматики имеет вид:

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

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

Ясно, что если правила вывода имеют такой вид, то рекурсивный спуск может быть реализован по выше изложенной схеме.

Естественно, возникает вопрос: если грамматика не удовлетворяет этим условиям, то существует ли эквивалентная КС-грамматика, для которой метод рекурсивного спуска применим? К сожалению, нет алгоритма, отвечающего на поставленный вопрос, т.е. это алгоритмически неразрешимая проблема.

Изложенные выше ограничения являются достаточными, но не необходимыми. Попытаемся ослабить требования на вид правил грамматики:

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

Общий вид этих правил:

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

Формально здесь не выполняются условия применимости метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами.

Действительно, в цепочке a,a,a,a,a из нетерминала L может выводиться и подцепочка a , и подцепочка a,a , и вся цепочка a,a,a,a,a. Неясно, какую из них выбрать в качестве подцепочки, выводимой из L. Если принять решение, что в таких случаях будем выбирать самую длинную подцепочку (что и требуется при разборе реальных языков), то разбор становится детерминированным.

Тогда для метода рекурсивного спуска процедура L будет такой:

void L()

{ if (c != 'a') ERROR();

while ((c = fgetc(fp)) == ',')

if ((c = fgetc(fp)) != 'a') ERROR();

}

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

S ® LB^

L ® a {, a}

B ® ,b

Если для этой грамматики написать анализатор, действующий РС-методом, то цепочка а,а,а,b будет признана им ошибочной, хотя в действительности это не так.

Нужно отметить, что в языках программирования ограничителем подобных серий всегда является символ, отличный от разделителя, поэтому подобных проблем не возникает.

(2) если грамматика не удовлетворяет требованиям применимости метода рекурсивного спуска, то можно попытаться преобразовать ее, т.е. получить эквивалентную грамматику, пригодную для анализа этим методом.

a) если в грамматике есть нетерминалы, правила вывода которых леворекурсивны, т.е. имеют вид

A ® Aa₁ | ... | Aa_n | b₁ | ... | b_m,

где a_i Î (VT È VN)⁺, b_j Î (VT È VN)^*, i = 1, 2, ..., n; j =1, 2 ,..., m, то непосредственно применять РС-метод нельзя.

Левую рекурсию всегда можно заменить правой:

A ® b₁A’ | ... | b_mA’

A’ ® a₁A’ | ... | a_nA’ | e

Будет получена грамматика, эквивалентная данной, т.к. из нетерминала A по-прежнему выводятся цепочки вида b_j {a_i}, где i = 1,2,...,n; j = 1,2,...,m.

b) если в грамматике есть нетерминал, у которого несколько правил вывода начинаются одинаковыми терминальными символами, т.е. имеют вид

A ® aa₁ | aa₂ | ... | aa_n | b₁ | ... |b_m,

где a Î VT; a_i, b_j Î (VT È VN)^*, то непосредственно применять РС-метод нельзя. Можно преобразовать правила вывода данного нетерминала, объединив правила с общими началами в одно правило:

A ® aA’ | b₁ | ... | b_m

A’ ® a₁ | a₂ | ... | a_n

Будет получена грамматика, эквивалентная данной.

c) если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, т.е. имеют вид

A ® B₁a₁ | ... | B_na_n | a₁b₁ | ... | a_mb_m

B₁ ® g₁₁ | ... | g_1k

. . .

B_n ® g_n1 | ... | g_np,

где B_i Î VN; a_j Î VT; a_i, b_j, g_ij Î (VT È VN)^*, то можно заменить вхождения нетерминалов B_i их правилами вывода в надежде, что правило нетерминала A станет удовлетворять требованиям метода рекурсивного спуска:

A ® g₁₁a₁ | ... | g_1ka₁ | ... | g_n1a_n | ... | g_npa_n | a₁b₁ | ... | a_mb_m

d) если допустить в правилах вывода грамматики пустую альтернативу, т.е. правила вида

A ® a₁a₁ | ... | a_na_n | e ,

то метод рекурсивного спуска может оказаться неприменимым (несмотря на то, что в остальном достаточные условия применимости выполняются).

Например, для грамматики G = ({a,b}, {S,A}, P, S), где

P: S ® bAa

A ® aA | e

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

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}, P, S), где

P: S ® bAс

A ® aA | e

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

Выпишем условие, при котором 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]).