Реализация компилятора. Организация лексического блока, страница 2

    if (*s== '\0') return(1); else return 0;

}

else return(0);

}

Еще один пример реализации конечного автомата для распознавания вещественного числа.

Грамматика для этого случая имеет вид:

G=(N, T, P, S)                    N={S, U}                 T={ d, .}

P={ S àU.U

       U à d | dU

     }

Описание автомата имеет вид:

M=(K, T, d, S,F)       K={S, U1, U2}     T={ d,.}

d

.

\0

S

U1

0

U1

U1

U2

0

U2

U2

1

         d  =

Пример программной реализации этого автомата.

IsReal (char *s){

if (isdigit(*s) { //перешли в состояние U1 после появления 1-ой цифры

    s++;

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

    if(*s=='.') { //перешли в состояние U2 после появления десятичной точки

         s++;

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

        /* проверка на допускающее состояние */

        if (*s== '\0') return(1); else return 0;

    }

else return(0);

}

А что изменится, если числа станут 16-тиричными?

Еще один пример реализации конечного автомата для распознавания вещественного p-ичного числа со знаком.

Грамматика для этого случая имеет вид:

G=(N, T, P, S)                    N={S, U}                 T={d, x, +, -, ., E,e}

P={

S à ±U.UE±V  |±U.Ue±V  | ± U E± V  |± U e± V  |  ±. U E± V | ±. U e± V | ± U. E± V| ± U. e± V  |  U.UE± V  | U.Ue± V  |  U E± V  | U e± V  |  . U E± V  | . U e± V | U. E± V  | U. e± V |U.UE V  | U.Ue V  |  U E V  | U e V  |  . U E V  |. U e V  |  U. E V  | U. e V  |

± U.U  |   ± U.  |  U.U  |  . U

}

       V à d | dV

       U à x | xU

     }

Описание автомата имеет вид:

M=(K, T, d, S,F)       K={S, U, E}     T={+, -, d, x, ., E, e}

         d  =

+

-

.

E

e

d

x

\0

S

U1

U1

U2

U1

U1

0

U1

U2

U1

U1

0

U2

U3

U3

U2

U2

1

U3

U4

U4

U4

0

U4

U4

1

Здесь:

x означает понятие "16-ричная цифра".

            U1 – целая часть числа

            U2 – дробная часть числа

            U3 – появление знака экспоненты

            U4 – значение экспоненты

Ниже представлен пример программной реализации этого автомата в предположении, что распознаваемая цепочка символов представлена отдельной строкой. В дальнейшем также будем предполагать, что на вход конечного автомата подается строка литер, полученная выделением из входной строки всех литер до первого символа-разделителя (см. лабораторную работу 2).

IsReal (char *s){

    int n;

    n=0;

    if(*s=='+' || *s=='-')s++;

    while (isxdigit (*s))s++,n++; //состояние U1

    if (*s=='.'){

        s++;

        while(isxdigit(*s)) s++,n++; //состояние U2

        if (n==0) return 0; //нет ни целой ни дробной части

    }

    if (*s=='E' || *s=='e'){ //состояние U3

        s++;

        if (*s=='+' || *s=='-') s++;

        if (isdigit(*s)){ //состояние U4

           s++;

           while(isdigit(*s)++);

        } else return 0;

     }

     if(*s=='\0')return 1;else return 0;

}

Для распознавания понятия служебного символа:

TermRecogn (char *s){

    if(!strcmp(s,²TITLE²)) return(TTL);

    if(!strcmp(s,²WRITE²)) return(WRITE);

       .       .       .

    if(!strcmp(s,²END²)) return(END);

    return(0);

}

Для распознавания понятия символа-разделителя:

DlmRecogn (char *s){

    if(!strcmp(s,²+²)) return(PLUS);

    if(!strcmp(s,²-²)) return(MINUS);

    if(!strcmp(s,²<=²)) return(LE);

       .       .       .

    if(!strcmp(s,²;²)) return(SCOL);

    return(0);

}

Конечные автоматы могут применяться не только в ЛБ, но и в СБ. Здесь, главным условием является то, что грамматика для разбираемой  строки символов должна быть линейной.

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

Организация таблиц

Описание таблицы символов:

#define BEGTBL   31  /* начальное значение кода имени */

#define ENDTBL   60  /* конечное значение кода имени  */

struct tbl {

int code;                     /* код символа-идентификатора  */

char name[9];             /* имя символа-идентификатора */

int dcl;                        /* признак объявления */

int type;                      /* тип символа-идентификатора */

char inival[16];          /* начальное значение символа-идентификатора */

} TBL[31];

Инициализация таблицы:

TBL->code=-1;

Обработка символа-идентификатора:

IdRecogn (char *str){

struct tbl * ptbl;

int n;

char *s, ErrStr[100]; //можно сделать ErrStr глобальной переменной

n=1;  s=str;

/*имя идентификатора должно  начинаться с буквы */

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

while(isalpha(*s)||isdigit(*s)){ n++; s++;}

if(*s!='\0') return 0; //проверка на заключительное состояние

if(n>8){       /*длина имени не может быть больше 8 */

sprintf(ErrStr,"слишком длинное имя идентификатора %s",str);   ErrMes(str);

/* ограничиваем длину имени восемью символами */

*(str+8)='\0';

}

/*проверяем, есть ли в таблице уже это имя */

ptbl=TBL;

n=BEGTBL;

while(ptbl->code!=-1){

if(strcmp(ptbl->name,str)==0) return(ptbl->code);

n++; ptbl++;

}

if(n>=ENDTBL){

ErrMes ("переполнение таблицы идентификаторов");

return(-1);

}

ptbl->code=n;

strcpy(ptbl->name,str);

ptbl++;

ptbl->code=-1;

return(n);

}

Для описания в программе больших массивов данных, особенно для случаев, когда  при запуске программы в зависимости от реальных данных размерности этих массивов могут меняться в большом диапазоне, удобно использовать динамическое распределение памяти, например с помощью функций malloc из библиотек alloc.h или stdlib.h или оператора new.

Пример

. . .

#define BTBL 31

#define ETBL 60

#define BLIT 61

#define ELIT 99

struct tbl{

  int code;

  char name[9];

  int dcl;

} *TBL;

struct lit{

  int code;

  char val [16];

  int dcl;

} *LIT;

. . .

 TBL=(struct tbl *)malloc ((ETBL-BTBL+2)*sizeof(struct tbl));

  LIT=(struct lit * )malloc ((ELIT-BLIT+2)*sizeof(struct lit));

Для оператора new:

Оператор new требует в качестве операнда имени типа и предназначен для размещения данного указанного типа в динамической памяти, результатом его выполнения будет указатель на это данное. При невозможности выделить память оператор new возвращает значение NULL - предопределенную константу, имеющую нулевое значение практически во всех компиляторах Си и Си++. Память, выделяемую оператором new, можно инициализировать, указав за именем типа скалярного данного начальное значение в круглых скобках, задание начальных значений для агрегатов данных рассмотрим позже. Примеры применения оператора new :

int *ip = new int; /* создание объекта типа int и получение указателя на него */

int *ip2 = new int(2); // то же с установкой начального значения 2

int *intArray = new int [ 10 ]; // массив из 10 элементов типа int

double **matr = new double [ m ] [ n ]; // матрица из m строк и n столбцов

Данное, размещенное в динамической памяти оператором new, удаляется из памяти оператором delete (или delete[]) с операндом-указателем, значение которого получено оператором new, например,

delete ip;

delete[] intArray; 

Оператор delete только освобождает динамическую память, но не изменяет значение указателя-операнда. Программист должен помнить, что после освобождения памяти использовать этот указатель для обращения к данному нельзя.

  TBL = new struct tbl [ETBL-BTBL+2];

  LIT = new struct lit   [ELIT-BLIT+2];

Освобождаются динамические переменные с помощью, соответственно, функции free:

free(TBL);

или оператора delete:

delete[] TBL;