Реализация синтаксического блока. Применение конечного автомата

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

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

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

Грамматика:

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, Z₀),  где

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

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

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

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

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

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

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

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

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

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

. . .

#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;