|
Построение формального языка 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 ( gg 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) return(1); 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) y++; 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. |
|
