if ((ps=LbrRecogn(s))!= NULL){ s=ps;nb++; }
if ((ps=IdentRecogn(s))!= NULL)s=ps;
if ((ps=RbrRecogn(s))!= NULL){ s=ps;nb--; if(nb<0)return NULL;}
}
if(nb==0 && (ps=ScolRecogn(s))!=NULL)return ps;
return NULL;
}
char *LbrRecogn (char *s){
while ( *s = = ' ' || *s = = '\t') s++;
if ( *s = = '(') return(++s);
return (NULL);
}
char *RbrRecogn (char *s){
while ( *s = = ' ' || *s = = '\t' ) s++;
if ( *s = = ')') return(++s);
return (NULL);
}
char *SignRecogn (char *s){
while ( *s = = ' ' || *s = = '\t' ) s++;
if ( *s = = '+' || *s = = '-' || *s = = '*' || *s = = '/') return(++s);
return (NULL);
}
char *IdentRecogn (char *s){
while ( *s == ' ' || *s == '\t' ) s++;
if ( !isalpha ( *s++ ) ) return ( NULL );
while ( isdigit ( *s ) || isalpha ( *s ) ) s++;
return (s);
}
char *EqRecogn (char *s){
while ( *s = = ' ' || *s = = '\t') s++;
if ( *s = = '=') return(s);
return (NULL);
}
char *ScolRecogn (char *s){
while ( *s == ' ' || *s == '\t') s++;
if ( *s == ';') return(++s);
return (NULL);
}
Метод является одним из наиболее распространенных методов нисходящего разбора. Идея метода весьма проста: каждому нетерминальному символу грамматики соответствует процедура, распознающая любую цепочку, порожденную этим символом.
Из требований эффективности следует:
каждый очередной этап анализа должен выбираться лишь в зависимости от текущего состояния процесса и от одного следующего читаемого символа;
ни к какому уже пройденному этапу не должно быть повторного обращения.
Все это вместе определяет просмотр на один шаг вперед без возврата.
А теперь возникает вопрос: любые ли КС-грамматики можно разбирать методом рекурсивного спуска, а если нет, то каким ограничениям должна удовлетворять такая КС-грамматика?
Пример 1
S ® A | B
A ® xA | y
B ® xB | z
Необходимо проверить: а) xxxy
S ® A ® xA ®xxA ® xxxA ® xxxy все ОК
б)xxxz
S ® A ® xA ®xxA ® xxxA ® xxxy и не ОК, т.к. надо было пойти по ветке S ® B.
S ® B ® xB ®xxB ® xxxB ® xxxz и теперь все ОК.
Отсюда вытекает:
Правило 1. В грамматике начальные символы альтернативных правых частей должны быть различны.
Наш пример можно изменить
S ® C
C ® xC | y | z и теперь все в порядке.
Пример 2
S ® Ax
A ® xA | x
Необходимо проверить: x
S ® Ax ® xx и все приехали, надо было добавить правило A ® e, а вот как его потом реализовать?
Правило 2. Для любого символа, порождающего пустую строку, множество начальных символов не должно пересекаться с множеством символов, которые могут появиться в предложениях языка справа от любой последовательности, порожденной этим символом.
Оба эти правила вместе запрещают использование правил вывода с левой рекурсией вида:
A ® B
A ® AB
A ® e
и, если только возможно, надо все приводить к формам с правой рекурсией.
А теперь переходим непосредственно к рассмотрению метода рекурсивного спуска. Идея метода очень проста и заключается в замене каждого нетерминала рекурсивной процедурой, распознающей все цепочки, порожденные этим нетерминалом. Этот метод является широко известным и легко реализуемым детерминированным методом разбора сверху вниз. Используя этот метод можно очень легко и быстро писать программы синтаксического анализатора.
Пусть имеем пример грамматики:
Грамматика:
G=(N,T,P,S) N={} T={D, E, C, L, A, R, l, d, ;, ,, (, )}
P={S®DECLARE L; L – список объявленных имен
L ® O, L O – объявление имени
L ® O I – идентификатор
O ® I(U, U) U – целое без знака
}
Пусть имеется функция NextSymb(), которая возвращает значение очередного символа (лексемы) из файла, используемая как symbol = NextSymb();
#include <stdio.h>
#include <string.h>
. . .
#define BEGTBL 30
#define ENDTBL 59
#define BEGLIT 60
#define ENDLIT 99
#define DCL 10
#define COMMA 11
#define SCOL 12
#define LBR 13
#define RBR 14
#define FPRT fprintf(out,"%02d ",symbol)
. . .
int NextSymb (void);
void DclOp(void);
void List(void);
void Op(void);
FILE *in, *out;
int symbol; //для хранения кода текущей лексемы
char buf[80]; //буфер для чтения очередной строки из файла
char *pbuf; //текущая позиция очередной лексемы
FILE *in; //входной файл с кодами лексем
FILE *out; //выходной файл после синтаксического анализа
. . .
Головная функция
. . .
in=fopen(lname,"r");
out=fopen(sname,"w");
if((pbuf=fgets(buf,80,in))!=NULL) {
symbol=atoi(pbuf);
Op();
}
fclose(in); fclose(out);
. . .
void Op(void){
if (symbol==DCL){
DclOp();
Op();
}
}
NextSymb (void) {
pbuf += 3;
if ( atoi(pbuf) ) return atoi(pbuf);
else{ fprintf(out,"00\n");
if ( (pbuf = fgets(buf, 80, in) ) == NULL) return -1;
else return (atoi(pbuf));
}
}
void DclOp(void) {
if (symbol == DCL) {
FPRT;symbol=NextSymb();
List();
if (symbol==SCOL) {
FPRT;symbol=NextSymb();
} else printf("Нет точки с запятой\n");
}else printf("Нет DECLARE\n");
}
void List(void){
if(symbol>=BEGTBL && symbol<=ENDTBL){
FPRT;symbol=NextSymb();
if (symbol == LBR) {
FPRT;symbol=NextSymb();
if(symbol>=BEGLIT && symbol<=ENDLIT){
FPRT;symbol=NextSymb();
if (symbol == COMMA) {
FPRT;symbol=NextSymb();
if(symbol>=BEGLIT && symbol<=ENDLIT){
FPRT;symbol=NextSymb();
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.