Дана грамматика G =({a,b,c, ^}, {S,A,B}, P, S), где
P: {S ® AB^, A ® a | cA, B ® bA}
Требуется определить, принадлежит ли цепочка caba языку L(G).
Построим вывод этой цепочки:
S ® AB^ ® cAB^ ® caB^ ® cabA^ ® caba^
Следовательно, цепочка принадлежит языку L(G). Последовательность применений правил вывода эквивалентна построению дерева разбора методом "сверху вниз" (рис.4.1):
Рис. 4.1. Последовательность построения дерева разбора
Метод рекурсивного спуска (РС-метод) реализует этот способ следующим образом: для каждого нетерминала грамматики создается своя процедура, носящая его имя. Задача этой процедуры заключается в том чтобы, начиная с указанного места исходной цепочки, найти подцепочку, которая выводится из данного нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибки, которая выдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор. Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочки, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.
Для грамматики G, приведенной выше, совокупность процедур рекурсивного спуска будет следующей:
#include <stdio.h>
int c;
FILE *fp; /* указатель на файл, в котором находится
анализируемая цепочка */
void A();
void B();
void ERROR(); /* функция обработки ошибок */
void S() {A(); B();
if (c != '^') ERROR();
}
void A() {if (c=='a') c = fgetc(fp);
else if (c == 'c') {c = fgetc(fp); A();}
else ERROR();
}
void B() {if (c == 'b') {c = fgetc(fp); A();}
else ERROR();
}
void ERROR() {printf("ERROR !!!"); exit(1);}
main() {fp = fopen("data","r");
c = fgetc(fp);
S();
printf("SUCCESS !!!"); exit(0);
}
Метод рекурсивного спуска применим в том случае, если каждое правило грамматики имеет вид:
- либо A ® a, где a Î (VT È VN)* и это единственное правило вывода для этого нетерминала;
- либо A ® a1a1 | a2a2 | ... | anan, где ai Î VT для всех i = 1,2,...,n; ai ¹ aj для i ¹ j; ai Î (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 ® Aa1 | ... | Aan | b1 | ... | bm,
где ai Î (VT È VN)+, bj Î (VT È VN)*, i = 1,2,...,n; j =1,2,...,m, то непосредственно применять РС-метод нельзя.
Левую рекурсию всегда можно заменить правой:
A ® b1A’ | ... | bmA’
A’ ® a1A’ | ... | anA’ | e
Будет получена грамматика, эквивалентная данной, так как из нетерминала A по-прежнему выводятся цепочки вида bj {ai}, где i = 1,2,...,n; j = 1,2,...,m.
b) если в грамматике есть нетерминал, у которого несколько правил вывода начинаются одинаковыми терминальными символами, то есть имеют вид
A ® aa1 | aa2 | ... | aan | b1 | ... |bm,
где a Î VT; ai,bj Î (VT È VN)*, то непосредственно применять РС-метод нельзя. Можно преобразовать правила вывода данного нетерминала, объединив правила с общими началами в одно правило:
A ® aA’ | b1 | ... | bm
A’ ® a1 | a2 | ... | an
Будет получена грамматика, эквивалентная данной.
c) если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, то есть имеют вид
A ® B1a1 | ... | Bnan | a1b1 | ... | ambm
B1 ® g11 | ... | g1k
. . .
Bn ® gn1 | ... | gnp,
где Bi Î VN; aj Î VT; ai, bj, gij Î (VT È VN)*, то можно заменить вхождения нетерминалов Bi их правилами вывода в надежде, что правило нетерминала A станет удовлетворять требованиям метода рекурсивного спуска:
