Информатика и выч. техника \ Лингвистическое обеспечение информационных систем

Реализация компилятора. Организация лексического блока, страница 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, U_1, U₂} T={ d,.}

	d	.	\0
S	U₁		0
U₁	U₁	U₂	0
U₂	U₂		1

d =

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

IsReal (char *s){

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

s++;

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

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

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	U₁	U₁	U₂			U₁	U₁	0
U₁			U₂			U₁	U₁	0
U₂				U₃	U₃	U₂	U₂	1
U₃	U₄	U₄				U₄		0
U₄						U₄		1

Здесь:

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

U₁– целая часть числа

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

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

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

Ниже представлен пример программной реализации этого автомата в предположении, что распознаваемая цепочка символов представлена отдельной строкой. В дальнейшем также будем предполагать, что на вход конечного автомата подается строка литер, полученная выделением из входной строки всех литер до первого символа-разделителя (см. лабораторную работу 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;

1 2

Скачать файл