Нисходящий разбор с возвратами

Принципы нисходящего разбора можно применить и в «первозданном» виде, не используя каких-либо дополнительных свойств и соотношений, выводимых из грамматики. Если считать что данная грамматика является LL(1)-грамматикой, то можно сконструировать простой алгоритм, основанный на подборе для очередного нетерминала правой части правила по принципу «первого подходящего». Зная принципы рекурсивного программирования, можно легко сформулировать «правила жизни» такого алгоритма, который будет довольно изящным и компактным, но неэффективным (см. исходный текст программы в SynDownFull.cpp):

· шаг рекурсивного алгоритма заключается в выводе всех возможных цепочек из очередного нетерминала sym и выборе первой подходящей, покрывающей начало незакрытой части входного предложения, начиная с символа с позицией (индексом) s:

int Step(char sym, int s)

· в качестве результата рекурсивная функция возвращает индекс k – части строки, закрытой цепочкой, выведенной из соответствующего нетерминала, либо –1, если цепочку вывести не удается;

· рекурсивная функция просматривает все множество правил (заданных массивом указателей на строки) и выбирает те, у которых в левой части стоит закрываемый символ sym:

char *GR[]={ " Z: U", " U: SU", " U: ", " S: aRa", " R: b", " R: aRa", NULL};

…

for (i=0; GR[i]! =NULL; i++)

if (GR[i][0]==sym) {…

· просматривая правую часть выбранного правила, программа выполняет различные действия в зависимости от того, является ли он терминалом или нетерминалом:

· для терминального символа производится сравнение его с очередным символом строки, при совпадении они оба пропускаются, при несовпадении – правая часть считается неподходящей;

· для нетерминального символа функция вызывает сама себя рекурсивно по отношению к этому нетерминалу и очередному символу строки. Если вызов неудачен, то вся правая часть является неподходящей, если удачен – то «закрывается» часть входной строки, просмотренная рекурсивным вызовом

for (j=2, k=s; GR[i][j]! =0; j++){ // просмотр правой части i-го правила

if (isNT(GR[i][j])! =-1) // для очередного нетерминала

{

int l=Step(GR[i][j], k); // рекурсивный вызов для нетерминала

if (l==-1) break; // результат отрицательный – отклонить правило

k=l; // иначе – продолжить просмотр после закрытой части

}

else { // для очередного терминала – при совпадении

if (GR[i][j]==str[k]) k++; // с символом строки – пропустить оба, иначе

else break; // отклонить правило

}}

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

Замечание: Требование однозначности выбора предполагает, что в каждом случае будет найдена только одна подходящая правая часть правила. Отсутствие таковой представляет тот случай в работе алгоритма, когда вышележащий вызов «идет не по тому пути» и просматривает «не ту» правую часть. Поэтому возвраты с отрицательным результатом вполне обоснованы. Особый вопрос – аннулирующие правила с пустой правой частью – они подходят всегда. Логично предположить, что их применение должно иметь более низкий приоритет, когда другие правила с непустой правой частью дали отрицательный результат. В приведенном примере программы этого можно достигнуть, помещая аннулирующие правила в конец группы правил с одинаковой левой частью.

//-------------------------------------------------------------------------SynDownFull.cpp

char str[100];

char *GR[]={ " Z: U", " U: SU", " U: ", " S: aRa", " R: b", " R: aRa", NULL };

int isNT(char c) { // Функция проверки на нетерминал – встречается в левой части

for (int i=0; GR[i]! =NULL; i++) if (GR[i][0]==c) return i;

return -1; }

int cnt=0; // Счетчик подстановок правил

int Step(char sym, int s) { // Для нетерминала sym и части строки, начиная с s

int i, j, k;

for (i=0; GR[i]! =NULL; i++) // Просмотр всех правил

if (GR[i][0]==sym) { // Выбор правил для заданного нетерминала

if (str[s]==0 & & GR[i][2]! =0) continue; // Если строка закончилась – применять только

cnt++; // аннулирующие правила

printf(" s=%d Rule: %s\n", s, GR[i]); getch();

for (j=2, k=s; GR[i][j]! =0; j++) { // Просмотр правой части

if (isNT(GR[i][j])! =-1) // Очередной символ - нетерминал

{

int l=Step(GR[i][j], k); // Рекурсивный вызов для текущего нетерминала

if (l==-1) break; // Неудача – пропустить правило

printf(" success: %d-%d NT=%c\n", k, l, GR[i][j]); getch();

k=l; // Удачно – закрыть просмотренную часть строки

}

else { // Очередной символ - терминальный

if (GR[i][j]==str[k]) k++; // Совпадает с текущим в строке – пропустить оба

else break; // Не совпадает – пропустить правило

}

}

if (GR[i][j]==0) { // Дошли до конца правила – правило подходит

printf(" sucess: %s %s\n", GR[i], & str[k]); getch();

return k; // Возвратить индекс незакрытой части строки

}}

return -1; }

void main() {

int k;

printf(" String: "); gets(str);

if (str[Step('Z', 0)]==0) puts(" SUCESS");

printf(" Rules applied: %d\n", cnt); }

Естественным ограничением для полного перебора вариантов является исключение прямой или косвенной левосторонней рекурсии. То есть в грамматике принципиально недопустимы правила или сочетания правил вида

E:: E + T или

E:: X…

X:: E…

которые приводят к “зацикливанию” алгоритма. В данном случае такое правило применяется само к себе бесконечное число раз.