Информатика и выч. техника \ Информатика

Реализация синтаксического блока. Применение конечного автомата. Головная функция для проверки работы автомата

Страницы работы

23 страницы (Word-файл)
Скачать файл

Фрагмент текста работы

Реализация синтаксического блока

Применение конечного автомата

Пусть нам надо построить распознаватель объявлений переменных с фиксированной точкой.

Грамматика:

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 – целое без знака

}

Автомат:

M=(K, T, d, S, F)

T={I, ,, ), ), U, ;}

Рассмотрим пример объявления вида:

DECLARE  A12 ( 5  ,  2 ) ,  B3 (  5 , 3  )  ;   Можно и:DCL  A12 ( 5  ,  2 ) ,  B3 (  5 , 3  )  ;

Прямоугольная выноска: Маркер конца строки            1         2   3 4 5 6 7 8   2  3 4 5 6 7 9   -  номера состояний

T = {1, 2, 3, 4, 5, 6, 7, 8, 9}   F = {9}

d:

I

U

,

(

)

;

΄\0΄

1

2

0

2

3

0

3

4

0

4

5

0

5

6

0

6

7

0

7

8

9

0

8

2

0

9

1

Рассмотрим примеры программной реализации этого автомата, предполагая, что имеются автоматы для распознавания понятий I (идентификатор), U(целое без знака), скобок и т.д. Также пусть в Edit1 находится распознаваемая строка, в Edit2 будет результат проверки, а в Edit3  - ошибочное сообщение.

. . .

#include <string.h>

#include <stdio.h>

. . .

char *DclOp(char *),

*DclRecogn(char *),

*LbrRecogn(char *),

*RbrRecogn(char *),

*UnsgnRecogn(char *),

*CommaRecogn(char *),

*ScolRecogn(char *),

*IdentRecogn(char *);

char buf[80], InfMes[100], ErrMes[100];

. . .

. . .

Головная функция для проверки работы автомата

. . .

strcpy(buf,Edit1->Text.c_str());

if (DclOp(buf)!=NULL)

sprintf(InfMes,"Да, это оператор DCL");

else sprintf(InfMes,"Нет, это не оператор DCL");

Edit2->Text=InfMes;

Edit2->Show();

Edit3->Text=ErrMes;

Edit3->Show();

*ErrMes='\0';

*InfMes='\0';

. .

Функциии для автоматов:

char *DclOp (char *s){

char *ps;

if ((s = DclRecogn(s)) != NULL)

do{

if ((s = IdentRecogn(s)) != NULL)

if ((s = LbrRecogn(s)) != NULL)

if ((s = UnsgnRecogn(s)) != NULL)

if ((s = CommaRecogn(s)) != NULL)

if ((s = UnsgnRecogn(s)) != NULL)

if ((s = RbrRecogn(s)) != NULL)

if ((ps = ScolRecogn(s)) != NULL) return(ps);

} while (s!=NULL && (s = CommaRecogn(s)) != NULL);

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 *IdentRecogn (char *s){

while ( *s = = ' ' || *s = = '\t' ) s++;

if ( !isalpha ( *s++ ) ) return ( NULL );

while ( isdigit ( *s ) || isalpha ( *s ) ) s++;

return (s);

}

char *UnsgnRecogn (char *s){

while ( *s = = ' ' || *s = = '\t' ) s++;

if ( !isdigit ( *s++ ) ) return(NULL);

while ( isdigit ( *s ) ) s++;

return (s);

}

char *DclRecogn (char *s){

while ( *s = = ' ' || *s = = '\t' ) s++;

/*      if ( *s++= = 'D' && *s++ = = 'E' && *s++= = 'C' && *s++ = = 'L' &&

*s++= = 'A' && *s++ = = 'R' && *s++ = = 'E') return (s);*/

if(!strncmp("DECLARE",s,7)) return (s+7);

if(!strncmp("DCL",s,3)) return (s+3);

return(NULL);

}

char *CommaRecogn (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);

}

Автомат магазинного типа (МП-автомат)

Этот автомат эквивалентен конечному автомату, к которому добавлена память магазинного типа  или стек. Помимо изменения состояний, как в конечном автомате, МП-автомат, в зависимости от значения входного символа, добавляет или удаляет верхний символ стека.

Автомат магазинного типа описывается:

M=(K, T, G, d, S, Z0),  где

K - конечное множество состояний;

T - конечный входной алфавит;

G - магазинный алфавит;

d- множество переходов;

S - начальное состояние (S Î K);

Z0 – символ магазина, первоначально находившийся в стеке.

Рассмотрим пример реализации МП-автомата для проверки баланса скобок. Пусть, например, мы описали понятие оператора присваивания в виде:

<оп_присв> ® <идент> = <выражение >;

<выражение> ®  <операнд> <знак_оп> < операнд > | < операнд >

<операнд> ® <идент> | (<выражение > )

. . .

#include <stdio.h>

. . .

char *AsgnOp(char *),

*LbrRecogn(char *),

*RbrRecogn(char *),

*EqRecogn(char *),

*SignRecogn(char *),

*ScolRecogn(char *),

*IdentRecogn(char *);

char buf[80];

int nskb=0;

. . .

strcpy(buf,Edit1->Text.c_str());

if (AsgnOp(buf)!=NULL)   sprintf(InfMes,"Yes, It's assigment operator!");

else sprintf(InfMes,"No, It's not assigment operator!");

Edit2->Text=InfMes;

Edit2->Show();

Edit3->Text=ErrMes;

Edit3->Show();

*ErrMes='\0';

*InfMes='\0';

. . .

char *AsgnOp (char *s){

char *ps;

if ((s=IdentRecogn(s))!= NULL)

if ((s=EqRecogn(s))!= NULL)

while(*s!='\0'&& ScolRecogn(s)==NULL){

if ((ps=LbrRecogn(s))!= NULL){ s=ps;nb++; }

if ((ps=IdentRecogn(s))!= NULL)s=ps;

if ((ps=SignRecogn(s))!= NULL)s=ps;

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,  а вот как его потом реализовать?

Правило 1. Для любого символа, порождающего пустую строку, множество начальных символов не должно пересекаться с множеством символов, которые могут появиться в предложениях языка справа от любой последовательности, порожденной этим символом.

Оба эти правила вместе запрещают использование правил вывода с левой рекурсией вида:

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();

if (symbol == RBR) {

FPRT;symbol=NextSymb();

if (symbol == COMMA) {

FPRT;symbol=NextSymb();

List();

}

} else printf("Нет закрывающей скобки\n");

} else printf("Нет количества дробных разрядов\n");

} else printf("Нет запятой\n");

} else printf("Нет длины числа\n");

} else printf("Нет открывающей скобки\n");                    

}

}

Еще один пример для грамматики из лабораторной работы 5

#include <stdio.h>

#include <string.h>

. . .

enum Term {TTL=1,END,Int,REAL,Input,OUTPUT};

enum Delim {COMMA=10,SCOL,COLON,EQ,ASGN,LBR,RBR }; //символы , ; : = ( )

#define BEGTBL 31

#define ENDTBL 59

#define BEGLIT  60

#define ENDLIT  99

#define FPRT fprintf(out,"%02d ",symbol)

#define FPRT1(x) fprintf(out,"%02d ",x)

#define NS symbol=NextSymb()

. . .

void Lex(void);

int NextSymb (void);

void DclOp(void);

void Title(void);

void End(void);

void List(void);

void ListIO (void);

void ExeOp(void);

void End(void);

void Expr(void);

FILE *in, *out;

struct tbl {

int code;

char name[9];

int dcl;

} TBL[]= {

31, "a", 0,

32, "b", 0,

33, "c", 0,

34, "d", 0,

35, "e", 0,

-1

}; //имитируем заполнение таблицы 5-ю именами в ЛБ

int symbol;     //для хранения кода текущей лексемы

char buf[80];  //буфер для чтения очередной строки из файла

char *pbuf;     //текущая позиция очередной лексемы

int serr=0;   //количество ошибок синт. блока

int ilst, nlst; //номер и число строк файла с лексемами

char ostr[80], *postr; //буфер для выходной строки в Form4

int pos; //конечная позиция в выходной строки в Form4

//Головная процедура

. . .

in=fopen(lname,"r");

out=fopen(sname,"w");

if((pbuf=fgets(buf,80,in))!=NULL){

symbol=atoi(pbuf); Snt();

}

fclose(in); fclose(out);

. . .

NextSymb (void) {

pbuf += 3;

if ( atoi(pbuf) ) return atoi(pbuf);

fprintf(out,"00\n");

if ( (pbuf = fgets(buf, 80, in) ) == NULL) return -1;

return (atoi(pbuf));

}

void ErrMes(char *s){

serr++;

Form1->Memo2->Lines->Add(s);

}

void Snt(void){

Title();

DclOp();

ExeOp();

End();

}

void Title(void){

if (symbol==TTL){

FPRT; NS;

} else ErrMes("Нет заголовка программы");

}

void DclOp(void){

if (symbol >= BEGTBL && symbol <= ENDTBL ){

List();

if (symbol==COLON){

FPRT; NS;

if (symbol == Int ||symbol == REAL ){

FPRT; NS;

if (symbol == SCOL){

FPRT; NS;

}else ErrMes("Нет точки с запятой в операторе объявления");

}else ErrMes("Нет задания типа в операторе объявления");

}else ErrMes("Нет двоеточия в операторе объявления");

DclOp();

}

}

void List(void){

if(symbol>=BEGTBL && symbol<=ENDTBL){

FPRT; NS;

if (symbol == COMMA) {

FPRT; NS();

List();

}

}

}

void ExeOp(void){

if (symbol == Input){

FPRT; NS;

if (symbol == LBR){

FPRT; NS;

ListIO();

if (symbol == RBR){

FPRT; NS;

if (symbol == SCOL){

FPRT; NS;

}else ErrMes("Нет ; в операторе INPUT");

} else ErrMes("Нет закр.скобки в операторе INPUT");

} else ErrMes("Нет открыв.скобки в операторе INPUT");

ExeOp();

}else

if (symbol == OUTPUT){

FPRT;NS;

if (symbol == LBR){

FPRT;NS;

ListIO();

if (symbol == RBR){

FPRT; NS;

if (symbol == SCOL){

FPRT; NS;

}else ErrMes("Нет ; в операторе OUTPUT");

}else ErrMes("Нет закр.скобки в операторе OUTPUT");

} else ErrMes("Нет открыв.скобки в операторе OUTPUT");

ExeOp();

}else

if(symbol>=BEGTBL && symbol<=ENDTBL){

FPRT;NS;

if (symbol == EQ) {

FPRT1(ASGN); NS;

Expr();

if (symbol == SCOL){

FPRT; NS;

}else ErrMes("Нет ; в операторе присваивания");

} else ErrMes("Нет знака = в операторе присваивания");

ExeOp();

}

}

void ListIO(void){

if(symbol>=BEGTBL && symbol<=ENDTBL){

FPRT;NS;

if (symbol == COMMA) {

FPRT;NS;

ListIO();

}

} 

}

void Expr(void){

}

void End(void){

if (symbol == END) {

FPRT;NS;

} else ErrMes("Нет оператора END");

}

А теперь более общий случай с дополнительными проверочными действиями

//

#include <stdio.h>

#include <string.h>

. . .

enum Term {TTL=1,END,Int,REAL,Input,OUTPUT};

enum Delim {COMMA=10,SCOL,COLON,EQ,ASGN,LBR,RBR};

#define BEGTBL 30

#define ENDTBL 59

#define FPRT  fprintf(out,"%02d ",symbol);pos=sprintf(postr,"%02d ",symbol

Похожие материалы

Информация о работе

ВУЗ:
Новосибирский государственный технический университет (НГТУ)
Предмет:
Информатика
Тип:
Конспекты лекций
Категория:
Информатика и выч. техника (Технические предметы)
Размер файла:
160 Kb
Скачали:
0
Скачать файл