Общие правила (рекомендации) для разработки нисходящих распознавателей.

1. Во всех правилах грамматики избавиться от левосторонней рекурсии

( см. предыдущую лекцию)

2. Для каждого правила <U>::= u разработать программу, которая будет удовлетворять следующим требованиям:

А. Программа должна либо определить «u» (т .е. требуемые операции), либо сообщить о невозможности это сделать.

Б. Если при разборе «u» встречается нетерминальный символ <X> (u=…<X>…), то для анализа этого нетерминального символа <X> необходимо передать управление программе, связанной с правилом: <X>::=x.

В. При отрицательном ответе после анализа нетерминального символа <X> программа разбора цепочки «u» должна либо проанализировать альтернативный вариант(в цепочке «u» где-то встречается альтернатива u::= …<X>| альтернатива), либо выдать сообщение об ошибке.

Г. В начале управление должно быть передано программе :<Z>::=…, где <Z>- начальный символ.

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

Пример нисходящего распознавателя для грамматики описывающей арифметическое выражение.

Предположим задана грамматика арифметического выражения:

1. <Z>::=<E>
2. <E>::=<T> | <E> + <T> | <E> - <T>
3. <T>::=<F> | <T> * <F>| <T> / <F>
4. <F>::=(<E>) | i, где I либо const, либо идентификатор.

Для разработки распознавателя арифметического выражения воспользуемся приведенными выше рекомендациями.

1) правила 2 и 3 имеют левостороннюю рекурсию => избавляемся от неё:

1. <Z>::=<E>

2.<E>::=<T> | { (+|-) <T>}

3.<T>::=<F> | {( *| /) <F>}

4.<F>::=(<E>) | i

2) каждому правилу поставим в соответствие функцию fi. Каждая из этих функций имеет следующий прототип:

int fi(char **u, double *d);

*u- указатель на текущий символ разбираемого арифметического выражения.

*d- текущее значение числа рассчитанное при вызове функции.

int – каждая функция возвращает код ошибки( 0- нет ошибки; 1- ошибка, прекратить вычисления)

Схема, поясняющая необходимость использования двойного указателя **u для перемещения к следующему символу арифметического выражения в вызываемой и вызывающей программах.

1)char **u:

2)char *u:

Схема взаимодействия функций fi в соответствии со сформулированными правилами (рекомендациями).

Реализация функций f1, f2, f3, f4.

Для обработки ошибки будем использовать следующий макрос:

#define fun(a) if (a) return(1)

f1:

*u – указатель на начальный символ арифметического выражениях;

d - указатель на переменную, где будет храниться окончательное результирующее число.

int f1 (char **u, double *d)

{

return(f2(u, d)); // реализация безусловного перехода 1

}

f2:

int f2(char **u, double *d)

{

double d1;

fun (f3(u, d)); // реализация безусловного перехода 2

while (1) // реализация «хвоста»

{

*u+=strspn(*u, “ “); // продвинуть указатель за пробел

switch (**u)

{

case’+’:

(*u)++; // перейти за «+»

fun (f3(u, &d1)); // обращение к f3 если встречается «+»

*d+=d1;

break;

case’-’:

(*u)++; // перейти за «-»

fun (f3(u, &d1)); // обращение к f3 если встречается «-»

*d-=d1;

break;

defalt: // больше нет символов хвоста

return(0);

}

}

}

f3:

int f3(char **u, double *d)

{

double d1;

fun (f3(u, d));

while (1)

{

*u+=strspn(*u, “ “);

switch (**u)

{

case’*’:

(*u)++;

fun (f4(u, &d1));

*d*=d1;

break;

case’/’:

(*u)++;

fun (f4(u, &d1));

*d/=d1;

break;

defalt:

return(0);

}

}

}

f4:

int f3(char **u, double *d)

{

*u+=strspn(*u, “ ”);

if (**u==’(’)

{

(*u)++;

fun (f2(u, d ));

*u+=strspn(*u,” “);

if (**u!=”)“)

return (1);

else

{

(*u)++;

return (0);

}

}

//Разбор альтернативы (вычисление i)

разбор I (const или идентификатор)

if ( ошибка)

return(1);

else

{

*d=число, полученное после разбора

return(0);

}

}

Синтаксическое дерево строится неявно. Дерево образует последовательность вызовов функций f1-f4.

Покажем, как разработанный распознаватель строит синтаксическое дерево. Пусть задано следующее арифметическое выражение:

25 + (A+B) / C*D

2. Объединение разнородных СУБД с помощью ODBC-интерфейса.