возвратом. Разбор выполняет рекурсивная функция Rec(int k), параметр которой
определяет положение указателя исходной цепочки. Пусть правила грамматики за-
даются в файле по строкам. Каждая строка определяет одно правило грамматики,
причем нетерминалами являются большие латинские буквы, а терминалами — ма-
ленькие латинские буквы. Нетерминал в левой части правила отделяется от правой
части последовательностью символов − >, окруженной пробелами.
Сразу отметим, что рекурсивный алгоритм нисходящего разбора не может ра-
ботать на леворекурсивных правилах, т.к. выбор первого леворекурсивного правила
грамматики блокирует все остальные. Единственный результат, который будет до-
стигнут в этом случае — сообщение stack overflow! . Это ограничение распространя-
ется на любые нисходящие методы разбора, а не только на рекурсивные.
Левая рекурсия может быть не только явной, но и скрытой, например, при нали-
чии правил S → Ac, A → BaB, B → SaA получаем леворекурсивную зависимость
S ⇒ Ac ⇒ BaBc ⇒ SaAaBc. Скрытая рекурсия при нисходящем разборе также
приведет к сообщению о переполнении стека.
// грамматический разбор на нисходящий стратегии с возвратами
#include <stdio.h>
#include <string.h>
#include <STDLIB.H>
#define MAX_STACK 2000
#define MAXK 100 // максимальное число правил грамматики
#define MAX_LEX 500 // максимальная длина исходной цепочки
typedef char LEX[MAX_LEX];
int len[MAXK];
char a[MAXK]; //левые части
LEX fi[MAXK]; // правые части правил грамматики
int m; // фактическое число правил грамматики
LEX x; // исходная цепочка
FILE *gr = fopen("gramm.txt","r"); //файл, содержащий правила грамматики
FILE *in = fopen("input.txt","r"); // файл с исходной цепочкой
char stack[MAX_STACK]; //стек
int uk; // указатель первого свободного элемента стека
void GetData(void)
{
LEX ss; // вспомогательная строка для ввода "->"
int i;
fscanf(gr,"%d\n",&m);// число правил
for (i=0; i<m; i++)
{
fscanf(gr,"%c %s %s\n",&a[i],&ss,&fi[i]);
// правило задается в форме a -> fi
if (fi[i][0]==’e’) {len[i]=0; fi[i][0]=’\0’;}
else len[i]=strlen(fi[i]);
}
fscanf(in,"%s",&x);
239