Міністерство освіти та науки України Національний університет «Львівська політехніка» кафедра прикладної математики ЛАБОРАТОРНА РОБОТА №3 з системного програмування на тему: «Синтаксичний аналіз» Мета: побудувати граматику, яка породжує запропоновану підмножину мови програмування, визначити типи можливих помилок та форму відповідного повідомлення . Написати програму синтаксичного контролю методом рекурсивного спуску (низхідний аналіз), попередньо застосувавши еквівалентні перетворення граматики (якщо потрібно). При потребі внести доповнення у підпрограму лексичного аналізу. Написати програму – синтаксичний аналізатор, що отримує на вході – текст вхідної програми на запропонованій підмножині мови програмування (у вхідному файлі), а на виході – повідомлення про наявність синтаксичних помилок у вхідній програмі (можна вести контроль до першої помилки) з інформацією про тип помилки та місце її знаходження. Для виділення чергової лексеми використати підпрограму, розроблену у Лаб. Роботі №2. Варіант №9. Завдання: Розглянути підмножину мови Pascal, у якій є ідентифікатори (довжина – не більше 10 символів), цілі константи (довжина – не більше 6 символів), які використовуються у операторах опису (типи змінних – real , integer,boolean), оператори присвоєння, оператори циклу типу while (умова – логічний вираз, утворений з логічних змінних і відповідних логічних операцій). Граматика: S → Program I; [R] T R → var P P → Z: Y;{Z: Y;} Z → I {, I} Y → Real | Integer | Boolean T → begin A end. A → B {;B} B → V | W | L V → I := U W → while G do B L → begin A end U → M | M + U | M – U | M or U M → N | N * M | N / M | N and M N → I | C | (G) | not N D → = | < | > | <> | <= | >= G → U D U | (G) Де: S = <Програма> R = <Розділ описів> P = <Опис> Z = <Змінні> Y = <Тип> T = <Тіло програми> A = <Оператори> B = <Оператор> V=<Присвоєння> W = <While> L = <Блок> U = <Вираз> M = <Терм> N = <Множ> D = <Відношення> G = <Логічний вираз> Код програми: #include <fstream.h> #include <string.h> #include <stdio.h> #include <iostream.h> #include <ctype.h> #include <windows.h> //*********************Opus Global'nuh zminnuh***********************// FILE *in; char *f1 = "input.txt"; char *lex, syn, lit = ' ', ch = 0; int cl = 9, f = 0, num = 1, id_num = 0; struct st { char *id; int type; }; st M_id[100]; //************************Prototupu fynkcij**************************// int getlit(); int zarezerv(char*); void scan(); void S(); void R(); void P(); void Z(); void Y(); void T(); void A(); void B(); void V(); void W(); void L(); void U(); void M(); void N(); void G(); void D(); void Vudilutu_Lexemy(); //****************************MAIN***********************************// void main(void) { in=fopen(f1, "r"); S(); if(f) Vudilutu_Lexemy(); else cout<<"\n\nV programi nemae pomulok...\n"; for(int j = 0; j < id_num; j++) cout<<"\n"<<M_id[j].id<<"\t"<<M_id[j].type; } //*************************Opus fynkcij******************************// int getlit() { lit = fgetc(in); if(ch != 0) putchar(ch); ch = lit; if(lit >= 'A' && lit <= 'Z') lit -= 'A' - 'a'; switch (lit) { case '+': return 3; break; case '-': return 3; break; case '*': return 3; break; case '/': return 3; break; case ';': return 3; break; case '(': return 3; break; case ')': return 3; break; case ',': return 3; break; case '.': return 3; break; case '<': return 4; break; case ':': return 5; break; case '=': return 6; break; case '>': return 7; break; } if(isalpha(lit)) return 1; else if(isdigit(lit))return 2; else return 9; } int zarezerv(char* lex) { if (!stricmp(lex,"begin")) {syn ='G';return 1;} if (!stricmp(lex,"end")) {syn ='N';return 1;} if (!stricmp(lex,"integer")) {syn ='I';return 1;} if (!stricmp(lex,"real")) {syn ='R';return 1;} if (!stricmp(lex,"boolean")) {syn ='L';return 1;} if (!stricmp(lex,"do")) {syn ='T';return 1;} if (!stricmp(lex,"while")) {syn ='W';return 1;} if (!stricmp(lex,"var")) {syn ='V';return 1;} if (!stricmp(lex,"program")) {syn ='M';return 1;} if (!stricmp(lex,"or")) {syn ='O';return 1;} if (!stricmp(lex,"and")) {syn ='U';return 1;} if (!stricmp(lex,"not")) {syn ='C';return 1;} return 0; } void scan() { int i; lex=new char[30]; if(cl&&!feof(in)) { i=0; while (lit==' ' || lit=='\n' || lit=='\t') { if(lit == '\n') num++; cl=getlit(); } switch(cl) { case 1: lex[i++]=lit; cl=getlit(); while ((cl<=2)&&(cl!=0)) {lex[i++]=lit;cl=getlit();} lex[i]='\0'; if(zarezerv(lex)) { break;} else {if(i<=10) syn='A'; else {syn='E';break;}} break; case 2: lex[i++]=lit; cl=getlit(); while ((cl==2)&&(cl!=0)) {lex[i++]=lit; cl=getlit();} lex[i]='\0'; if(i<=6) syn='B';else syn='F';break; case 3: lex[0]=lit;lex[1]='\0'; syn=lit; cl=getlit();break; case 4: lex[i++]=lit; cl=getlit(); if (cl==7) {lex[i++]=lit; lex[i]='\0'; syn='D'; cl=getlit();break;} else {if (cl==6) {lex[i++]=lit; lex[i]='\0'; syn='H'; cl=getlit();break;}} lex[i]='\0';syn='J';break; case 5: lex[i++]=lit; cl=getlit(); if (cl==6) {lex[i++]=lit; lex[i]='\0'; syn='K'; cl=getlit();break;} lex[i]='\0';syn=':';break; case 6: lex[i++]=lit;lex[i]='\0'; cl=getlit(); syn='P';break; case 7: lex[i++]=lit;cl=getlit(); if (cl==6) {lex[i++]=lit; lex[i]='\0'; syn='Q'; cl=getlit();break;} lex[i]='\0';syn='R';break; case 9: lex[0]=lit;lex[1]='\0'; syn='X';cl=getlit();break; } } } void S() { scan(); if(syn != 'M'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Programa povuna po4unatus' zi slova Program!!!\n"; return;} scan(); if(syn != 'A'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Nekorektne imja programu!!!\n"; return;} scan(); if(syn != ';'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyet'sja ';'!!!\n"; return;} scan(); if(syn != 'V' && syn != 'G'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyet'sja BEGIN abo VAR!!!\n"; return;} if(syn == 'V') R(); if(f) return; T(); } void R() { if(f) return; scan(); P(); } void P() { if(f) return; Z(); if(f) return; if(syn != ':'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ':'!!!\n"; return;} scan(); Y(); if(f) return; if(syn != ';'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ';'!!!\n"; return;} scan(); while(syn != 'G') { Z(); if(f) return; if(syn != ':'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ':'!!!\n"; return;} scan(); Y(); if(f) return; if(syn != ';'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ';'!!!\n"; return;} scan(); } } void Z() { if(f) return; if(syn != 'A'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja identufikator!!!\n"; return;} M_id[id_num].id = lex; M_id[id_num++].type = 4; scan(); while(syn != ':') { if(syn != ','){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ':'!!!\n"; return;} scan(); if(syn != 'A'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja identufikator!!!\n"; return;} M_id[id_num].id = lex; M_id[id_num++].type = 4; scan(); } } void Y() { if(f) return; if(syn != 'I' && syn != 'R' && syn != 'L'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Nevidomuj typ danuh!!!\n"; return;} while(M_id[id_num].type == 4) { } scan(); } void T() { if(f) return; if(syn != 'G'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja BEGIN!!!\n"; return;} scan(); A(); if(f) return; if(syn != 'N'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja END!!!\n"; return;} scan(); if(feof(in)) {printf(" "); lex = " ";} if(syn != '.'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja '.'!!!\n"; return;} } void A() { if(f) return; if(syn != 'N') B(); if(f) return; while(syn != 'N') { if(syn != ';'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ';'!!!\n"; return;} scan(); if(syn == 'N') break; B(); if(f) return; } } void B() { if(f) return; //while(syn == ';') scan(); if(syn == 'N') return; if(syn == 'W') W(); else if(syn == 'G') L(); else if(syn == 'A') V(); else {f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Neo4ikyvani symvolu!!!\n"; return;} } void V() { if(f) return; if(syn != 'A'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja identufikator!!!\n"; return;} scan(); if(syn != 'K'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ':='!!!\n"; return;} scan(); G(); } void W() { if(f) return; scan(); G(); if(f) return; if(syn != 'T'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja DO!!!\n"; return;} scan(); B(); } void L() { if(f) return; scan(); A(); if(f) return; if(syn != 'N'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja END!!!\n"; return;} scan(); } void G() { U(); if(syn != 'P' && syn != 'J' && syn != 'R' && syn != 'D' && syn != 'H' && syn != 'Q') return; D(); U(); } void U() { if(f) return; M(); if(f) return; if(syn == '+' || syn == '-' || syn == 'O'){scan(); U();} } void M() { if(f) return; N(); if(f) return; if(syn == '*' || syn == '/' || syn == 'U'){scan(); M();} } void N() { if(f) return; if(syn == '(') { scan(); U(); if(f) return; if(syn != ')'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyjet'sja ')'!!!\n"; return;} } else if(syn == 'C'){scan(); N();} else if(syn == 'E'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Dovzhuna identufikatora <= 10!!!\n"; return;} else if(syn == 'F'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Dovzhuna ciloji konstantu <= 6!!!\n"; return;} else if(syn != 'A' && syn != 'B'){f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": Pomulka y vurazi!!!\n"; return;} scan(); } void D() { if(f) return; if(syn != 'P' && syn != 'J' && syn != 'R' && syn != 'D' && syn != 'H' && syn != 'Q') {f = 1; cout<<"\n\n!!!ERROR!!!Line "<<num<<": O4ikyet'sja logi4na operacija!!!\n"; return;} scan(); } void Vudilutu_Lexemy() { int X, Y; CONSOLE_SCREEN_BUFFER_INFO csbi; COORD coord; GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbi); X = coord.X = csbi.dwCursorPosition.X; Y = coord.Y = csbi.dwCursorPosition.Y; coord.X -= strlen(lex); SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord); SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 192); printf(lex); SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); while(!feof(in)) { lit = fgetc(in); if(ch != 0) putchar(ch); ch = lit; } } Функція Vudilutu_Lexemy() – виділяє лексему при аналізі якої виникла помилка. Спочатку курсор перемішується на довжину лексеми назад по рядку(функція SetConsoleCursorPosition), далі змінюється атрибут тексту(192 – чорний шрифт на червоному фоні), потім друкується лексема ще раз, на сам кінець атрибут повертається в стандартний(7 – стандартний атрибут) та додруковується залишок вхідної програми. Контрольний приклад: Приклад вхідного файлу: program a34; var abcd2, f: real; b, a, s: integer; se, c, d: BooLeAn; efw,dwewe,we:Real; Begin f:=(b*b)+a*s - f * s+b; while ((s>= (s*a/s)) do begin bEgin b:=165523; c:= not true; end; d:=not false or (not se or d); c := not c and se or false; se := TrUe or FaLsE and d or not c; end; end. Приклад виводу в консолі: program a34; var abcd2, f: real; b, a, s: integer; se, c, d: BooLeAn; efw,dwewe,we:Real; Begin f:=(b*b*)+a*s - f * s+b; while ((s>= (s*a/s)) do begin bEgin b:=165523; c:= not true; end; d:=not false or (not se or d); c := not c and se or false; se := TrUe or FaLsE and d or not c; end; end. !!!ERROR!!!Line 11: Pomulka y vurazi!!! Press any key to continue Висновок: На цій лабораторній я ознайомився з принципом синтаксичного аналізу – перевірки вхідної програми на належність написаній граматиці за допомогою методу рекурсивного спуску. Метод рекурсивного спуску полягає в аналізі «з гори – до низу» - ми рухаємось від початкового не терміналу граматики до вхідної стрічки(коду програми) використовуючи рекурсію – за допомогою якої легко описуються циклічні структури. Також я написав програму синтаксичного контролю вхідного тексту програми написаної на мові Pascal, яка при виявленні помилки виводить рядок програми що містить помилку та вказує тип помилки. Результати програми виводяться на екран.