Построение формального языка L

Построение формального языка L

Построение формального языка L

WHILE( ) [, , ...])>];

WHILE - входной терминальный символ

- условное выражение

- некоторая функция, которая может отсутствовать

- параметры функции, которые тоже могут отсутствовать

Пример правильного синтаксиса:

WHILE(A>4444]:

1. ( while( ) [];

2. ( T| < T| > T| >= T | != T

3. ( O | T*O | T**O | T+O | T-O | T/O

4. ( () | |

5. ( БЦ

6. ( Ц{Ц}

7. ( ([{,}])

8. ( | | (

Классификация G[Z]

G[]:

1. ( while( ) [];

2. ( T| < T| > T| >= T | != T

3. ( O | T*O | T**O | T+O | T-O | T/O

4. ( () | |

5. ( БЦ

6. ( Ц{Ц}

7. ( ([{,}])

8. ( | | (

Сделаем замену нетерминальных символов:

( Z

( A

( B

( C

( D

( E

( F

( G

Сделаем замену терминальных символов:

WHILE ( a

( ( b

) ( c

; ( d

Ц ( f

Б ( g

, ( h

G[Z]:

1. Z ( abAc[D]d

2. A( B|A B|A = B |A != B

3. B ( C | B*C | B**C | B+C | B-C | B/C

4. C ( bAc | E | F

5. E ( gf

6. F ( f{f}

7. D ( Eb[G{hG}]c

8. G ( E | F | (

Вывод : G[Z] - контекстно-свободная грамматика.

Выбор метода анализа

Хотя однозначность в общем случае для контекстно-зависимых грамматик

не доказана, ее использование возможно для грамматик в которых

однозначность очевидна. Наиболее хорошо разработанным методом анализа, для

данного типа грамматик является, метод рекурсивного спуска.

Диагностика и нейтрализация ошибок

Разработанный алгоритм относится к общеизвестному методу

синтаксического разбора, предложенный Айронсом.

Основная идея метода состоит в том, что по контексту без возврата

отбрасываются те символы, которые привели в тупиковую ситуацию и разбор

продолжается.

Приведем пример синтаксического разбора:

While (A > ) cls();

1. Z ( abAc[D]d

2. A( B|A B|A = B |A != B

3. B ( C | B*C | B**C | B+C | B-C | B/C

4. C ( bAc | E | F

5. E ( gf

6. F ( f{f}

7. D ( Eb[G{hG}]c

8. G ( E | F | (

Z

a b A c D

B A E

C B g{g} b G c

E C (

g E

g

While ( A > ) cls ( )

;

тупиковая ситуация

Тестирование на цепочках

Протокол работы синтаксического распознавателя оператора цикла while

языка С.

_____________________________________________________________________

Обрабатываем строчку - While(a>)cls();

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - a

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - )

Проверка на ЦБЗ, текущий символ - )

Проверка на FUNC, текущий символ - c

Проверка на IDENT, текущий символ - c

Найденные ошибки в строке While(a>)cls();

Предупреждение: Отсутствует условие ()

Не найден идентификатор или ЦБЗ

_____________________________________________________________________

Обрабатываем строчку - while(1>3t*(ewqw++()*we)

rscr(456,345,rtgrt,345444rtr,,,)

Найден While проверка началась с символа - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - e

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - +

Проверка на ЦБЗ, текущий символ - +

Проверка на TERM

Проверка на O

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - w

Проверка на FUNC, текущий символ - r

Проверка на IDENT, текущий символ - r

Проверка на PAR, текущий символ - 4

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на PAR, текущий символ - 3

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на PAR, текущий символ - r

Проверка на IDENT, текущий символ - r

Проверка на PAR, текущий символ - 3

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на PAR, текущий символ - ,

Проверка на IDENT, текущий символ - ,

Проверка на ЦБЗ, текущий символ - ,

Найденные ошибки в строке 435 4 whilei>>3t*(ewqw++()*we)

rscr(456,345,rtgrt,345444rtr,,,)

Отсутствует (

Отсутствует )

Предупреждение: Отсутствует условие ()

Отсутствует ; после функции

Параметр функции не может начинатся с цифры

Неизвестный идентификатор(ы) -

435, 4,

Не найден идентификатор или ЦБЗ

Идентификатор не может начинаться с цифры

Не найден или не верный параметр

Неизвестная знаковая конструкция

_____________________________________________________________________

Обрабатываем строчку - whiLE(43-(sss344>(544523*232)

clrscr(,)

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 5

Проверка на ЦБЗ, текущий символ - 5

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 2

Проверка на ЦБЗ, текущий символ - 2

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 2

Проверка на ЦБЗ, текущий символ - 2

Проверка на TERM

Проверка на O

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - w

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 2

Проверка на ЦБЗ, текущий символ - 2

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 2

Проверка на ЦБЗ, текущий символ - 2

Проверка на FUNC, текущий символ -

Проверка на IDENT, текущий символ - c

Проверка на PAR, текущий символ - ,

Проверка на IDENT, текущий символ - ,

Проверка на ЦБЗ, текущий символ - ,

Найденные ошибки в строке while(i>344>(544523*232)

clrscr(,)

Отсутствует ; после функции

Не найден или не верный параметр

Неизвестная знаковая конструкция

_____________________________________________________________________

Обрабатываем строчку - while(u>r+erhgeerg(e>=rwe+++r+788erwe++))

scr(eee,qeer+erhgeerg(e>=rwe+++r+788erwe++))

scr(eee,qee77777u777) clrscr(,...,)

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 7

Проверка на ЦБЗ, текущий символ - 7

Проверка на FUNC, текущий символ -

Проверка на IDENT, текущий символ - c

Проверка на PAR, текущий символ - ,

Проверка на IDENT, текущий символ - ,

Проверка на ЦБЗ, текущий символ - ,

Найденные ошибки в строке while(i>77777u777) clrscr(,...,)

Отсутствует ; после функции

Идентификатор не может начинаться с цифры

Не найден или не верный параметр

_____________________________________________________________________Обрабат

ываем строчку - while(4545>>445--- ;

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 4

Проверка на ЦБЗ, текущий символ - 4

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ -

Проверка на ЦБЗ, текущий символ -

Проверка на FUNC, текущий символ - ;

Проверка на IDENT, текущий символ - ;

Найденные ошибки в строке while(4545>>445--- ;

Отсутствует )

Предупреждение: отсутствует имя функции

Не найден идентификатор или ЦБЗ

Неизвестная знаковая конструкция

_____________________________________________________________________

Обрабатываем строчку - while(i>=0);

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 0

Проверка на ЦБЗ, текущий символ - 0

Проверка на FUNC, текущий символ - ;

Проверка на IDENT, текущий символ - ;

Найденные ошибки в строке while(i>=0);

Предупреждение: отсутствует имя функции

_____________________________________________________________________

Обрабатываем строчку - while(i>=0) 544();

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 0

Проверка на ЦБЗ, текущий символ - 0

Проверка на FUNC, текущий символ -

Проверка на IDENT, текущий символ - 5

Найденные ошибки в строке while(i>=0) 544();

Отсутствует ; после функции

Предупреждение: отсутствует имя функции

_____________________________________________________________________

Обрабатываем строчку - whilei>=0) clrscr();13

Найден While проверка началась с символа - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - i

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 0

Проверка на ЦБЗ, текущий символ - 0

Проверка на FUNC, текущий символ -

Проверка на IDENT, текущий символ - c

Найденные ошибки в строке whilei>=0) clrscr();13

Отсутствует (

Предупреждение: Отсутствует условие ()

_____________________________________________________________________

Обрабатываем строчку - whilertt>3432*23432)

Найден While проверка началась с символа - (

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - d

Проверка на AB

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 3

Проверка на ЦБЗ, текущий символ - 3

Проверка на TERM

Проверка на O

Проверка на IDENT, текущий символ - 2

Проверка на ЦБЗ, текущий символ - 2

Проверка на FUNC, текущий символ -

Проверка на IDENT, текущий символ -

Найденные ошибки в строке while(dd>>3432*23432)

Отсутствует ; после функции

Предупреждение: отсутствует имя функции

Неизвестная знаковая конструкция

Листинг программы

ВАРИАHТ # 10

Синтаксический распознователь оператора цикла While

Файл программы - А513.cpp

с текстом для распознования - test.513

с протоколом работы - error.513

Кафедpа : АСУ

Гpуппа : А-513

Студент : Стариков Дмитрий Александрович

Пpеподаватели : кандидат технических наук, доцент

Шоpников Юpий Владимиpович,

ассистент Панова Веpа Боpисовна

Дата : 30 мая 1997г.

//--------------------------------------------------------------------------

--

// Заголовочные файлы.

//--------------------------------------------------------------------------

--

#include

#include

#include

#include

#include

#include

#define UP 72 // стрелка вверх

#define DOWN 80 // стрелка вниз

#define ALTX 45 // выход

#define F1 59

#define F2 60

#define F3 61

#define ESC 27

#define FL_NAME "test.513"

#define FL_TEST "error.513"

void open_fl(void); // откpыть файл

void work_space(void); // упpавляет pабочей областью

void print_page(void); // печатает текст на экpан

void help_line(void); // текст с помощью нижняя стpочка

void help(int);

int scan(); // Делает разбор строки

int my_while(); // опеpатоp

int AB(); // арифметическое выражение

int TERM(); // Терм

int O(); // Операнд

int IDENT(); // Идентификатор

int ZBZ(); // Целое без знака

int FUNC(); // Функция

int PAR(); // Параметр

char TEXT[22][80];

int position; // Номер текущей страницы

int cur_y=3; // положение куpсоpа на экpане

int x,y; // Текущая позиция при компиляции в

строчке

int f=0; // При f=1 ошибки для функции

char screen[4096]; // Сохpаняет полную копию экpана

char screen1[4096]; // Сохpаняет часть экpана

char *mistake[]={"Ошибок нет!!!", //0

"Опеpатоp while не найден", //1

"Отсутствует (", //2

"Отсутствует )", //3

"Предупреждение: Отсутствует условие ()", //4

"Отсутствует ; после функции", //5

"Предупреждение: отсутствует имя функции", //6

"Пропущено / или * или ** или + или - ", //7

"", //8

"Параметр функции не может начинатся с цифры", //9

"Неизвестный идентификатор(ы) - ", //10

"Не найден идентификатор или ЦБЗ", //11

"Идентификатор не может начинаться с цифры", //12

"Не найден или не верный параметр", //13

"Неизвестная знаковая конструкция", //14

""}; //15

FILE *fl_t;

int mistake_number[15]; //массив хранящий коды ошибок (0 или 1)

//где 1-ошибка присутсвует, 0 в противном случае

//mistake_number[i], где i номер ошибки из mistake

char strange[100]; //перечень неизвестных идентификаторов

//найденых в строке во время разбора

int s=0; //текущая позиция в strange

void main()

{

open_fl();

help_line();

print_page();

work_space();

}

//--------------------------------------------------------------------------

--

// Открытие файла

//--------------------------------------------------------------------------

--

void open_fl(void)

{

FILE *fl;

int i;

window(1,1,80,25);

textbackground(BLACK);

textcolor(WHITE);

clrscr();

_setcursortype(_NOCURSOR);

if((fl_t= fopen(FL_TEST,"w"))== NULL) exit(1);

if ((fl = fopen(FL_NAME,"r"))==NULL)

{

window(18,10,60,16);

textbackground(GREEN);

textcolor(BLACK);

clrscr();

gotoxy(5,2);cprintf(" Немогу найти файл test.513");

gotoxy(5,3);cprintf("Проверте его наличие на диске");

gotoxy(5,4);cprintf(" или создайте новый");

gotoxy(3,6);cprintf("Для продолжения нажмите любую

клавишу");

getch();

exit(0);

}

for(i=0;i -> WHILE

()[];\n\r\r");

cprintf(" 2. -> T| >T | >=T

| !=T\n\r\r\r");

cprintf(" 3. T -> O | T+O | T-O | T*O | T/O |

T**O\n\r\r\r");

cprintf(" 4. O ->() | | \n\r\r\r");

cprintf(" 5. -> БЦ\r\r\r\r\n");

cprintf(" 6. -> Ц{Ц}\r\n");

cprintf(" 7. -> ([{,}])\r\n");

cprintf(" 8. -> | \r\n");

}

if(n == 3)

{

cprintf("\n ЯЗЫК ОПЕРАТОРА\n\n\n\r\r");

cprintf(" WHILE(AB) [FUNCTION([PAR,PAR,...])];\r\n\n");

cprintf(" AB - Выражение \r\n");

cprintf(" FUNCTION - функция\r\n");

cprintf(" PAR - параметры функции, могут быть цифры

или текст \r\n");

cprintf(" количество их не ограничено\r\n\n");

cprintf(" Пробелы между символами недопустимы\r\n\n\n");

}

getch();

puttext(1,8,80,22,string);

window(1,1,80,25);

}

//--------------------------------------------------------------------------

--

// Сканирует до появления While

//--------------------------------------------------------------------------

--

int scan()

{

int k,j,w; //счетчики

mistake_number[1]=1;

for(j=0;;j++)

{

if(TEXT[x][j] == NULL) break;

if(TEXT[x][j] == 'W')

{

y=j; //если нашли W или w

if(my_while() == 1) break; //то вызываем

} //my_while

if(TEXT[x][j] == 'w')

{

y=j;

if(my_while() == 1) break;

}

if(TEXT[x][j] != ' ')

{

strange[s++]=TEXT[x][j];

mistake_number[10]=1;

}

if(TEXT[x][j] == ' ')

{

strange[s++]=',';

strange[s++]=' ';

}

}

strange[s]=NULL;

return(1);

}

//--------------------------------------------------------------------------

--

// Обрабатывает While и вызывает обработку функций

//--------------------------------------------------------------------------

--

int my_while()

{

char str[10];

int k,j,w; //счетчики

for(w=0;w')

{

y++;

if(TEXT[x][y] == '=') y++;

for(z=0;z' && TEXT[x][y]!='!' && TEXT[x][y]!=' '&& TEXT[x][y]!='=')

{

mistake_number[7]=1;

AB();

}

return(1);

}

//--------------------------------------------------------------------------

--

// Обработка операнда

//--------------------------------------------------------------------------

--

int O()

{

fprintf(fl_t,"Проверка на O\n");

if(TEXT[x][y] == '(')

{

y++;

if(TEXT[x][y] == ')')

{

mistake_number[4]=1;

y++;

}

else

{

AB();

if(TEXT[x][y] == '(')

{

AB();

}

if(TEXT[x][y] != ')')

{

mistake_number[3]=1;

y++;

}

else y++;

}

}

else

{

if(IDENT() == 0)

if(ZBZ() == 0)

if(f==0) mistake_number[11]=1;

return(0);

}

return(0);

}

//--------------------------------------------------------------------------

--

// Обработка идентификатора

//--------------------------------------------------------------------------

--

int IDENT()

{

fprintf(fl_t,"Проверка на IDENT, текущий символ -

%c\n",TEXT[x][y]);

if((isalpha(TEXT[x][y])) != NULL)

isdigit(TEXT[x][y]))

else return(0);

}

//--------------------------------------------------------------------------

--

// Целое без знака

//--------------------------------------------------------------------------

--

int ZBZ()

{

fprintf(fl_t,"Проверка на ЦБЗ, текущий символ -

%c\n",TEXT[x][y]);

if((isdigit(TEXT[x][y])) != NULL)

{

y++;

while(1)

{

if((isalpha(TEXT[x][y])) != NULL)

/* функции */

if((isdigit(TEXT[x][y])) == NULL) break;

y++;

}

return(1);

}

else return(0);

}

//--------------------------------------------------------------------------

--

// Обработка функции

//--------------------------------------------------------------------------

--

int FUNC()

{

f=1;

fprintf(fl_t,"Проверка на FUNC, текущий символ -

%c\n",TEXT[x][y]);

for(;;y++)

if(TEXT[x][y] != ' ') break;

if(IDENT()==0)

if(mistake_number[6] ==0)

if(TEXT[x][y] =='(')

{

y++;

if(TEXT[x][y] == ')')

{

mistake_number[4]=1;

y++;

}

else while(6)

{

if(PAR() != 0)

{

if(TEXT[x][y] == ')')

{

y++;

break;

}

if(TEXT[x][y] == ';') break;

if(TEXT[x][y] == ',') y++;

}

else

{

mistake_number[13]=1;

break;

}

}

}

else

{

mistake_number[2]=1;

mistake_number[13]=1;

}

if(mistake_number[13]==1)

{

for(;;y++)

{

if(TEXT[x][y] == NULL)

{

mistake_number[5]=1;

mistake_number[3]=1;

break;

}

if(TEXT[x][y] == ';')

{

mistake_number[3]=1;

break;

}

if(TEXT[x][y] == ')')

{

y++;

break;

}

}

}

if(TEXT[x][y] != ';') mistake_number[5]=1;

return(1);

}

//--------------------------------------------------------------------------

--

// Обработка параметров функции

//--------------------------------------------------------------------------

--

int PAR()

{

fprintf(fl_t,"Проверка на PAR, текущий символ -

%c\n",TEXT[x][y]);

if(IDENT() == 0)

if(ZBZ() == 0)

{

mistake_number[13]=1;

return(0);

}

return(1);

}

Список литературы:

1. Д. Грис Конструирование компиляторов для цифровых вычислительных машин.

М., Мир, 1975.

2. Лебедев В.Н. Введение в системы программирования. М., «Статистика»,

1975.

3. Шорников Ю.В., Шегал Б.Р. Методическое пособие для выполнения курсовой

работы по системному программированию. Новосибирск, 1992.