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

WHILE( ) [];

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

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

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

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

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

WHILE(A>4444 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 ( g{g|f}
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 ( g{g|f}
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(13t*(ewqw++()*we) rscr(456,345,rtgrt,345444rtr,,,)

Отсутствует (
Отсутствует )
Предупреждение: Отсутствует условие ()
Отсутствует ; после функции
Параметр функции не может начинатся с цифры
Неизвестный идентификатор(ы) —

435, 4,
Не найден идентификатор или ЦБЗ
Идентификатор не может начинаться с цифры
Не найден или не верный параметр
Неизвестная знаковая конструкция
_____________________________________________________________________
Обрабатываем строчку — whiLE(43-(sss(5445344>(5445r+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

Отсутствует (
Предупреждение: Отсутствует условие ()
_____________________________________________________________________
Обрабатываем строчку — whilertt3432*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 Б{Б|Ц}rrrrn»); cprintf(» 6. -> Ц{Ц}rn»); cprintf(» 7. -> ([{,}])rn»); cprintf(» 8. -> | rn»);

} if(n == 3)

{ cprintf(«n ЯЗЫК ОПЕРАТОРАnnnrr»); cprintf(» WHILE(AB) [FUNCTION([PAR,PAR,…])];rnn»); cprintf(» AB — Выражение rn»); cprintf(» FUNCTION — функцияrn»); cprintf(» PAR — параметры функции, могут быть цифры или текст rn»); cprintf(» количество их не ограниченоrnn»); cprintf(» Пробелы между символами недопустимыrnnn»);

} 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