Міністерство освіти і науки України Національний університет «Львівська політехніка» ЛАБОРАТОРНА РОБОТА №3. Синтаксичний аналіз Львів – 2007 Мета: виконати синтаксичний аналіз вхідного файлу використовуючи результат лексичного аналізу. Вхідні дані – текст вхідної програми підмножині мови програмування С. В-19 Розглянути підмножину мови C, у якій є ідентифікатори (довжина – не більше 10 символів), цілі константи (довжина – не більше 6 символів), дійсні константи з фіксованою крапкою, які використовуються у операторах опису (типи змінних – float , int), оператори присвоєння, оператори циклу типу for. 1. Вхідний файл: (один з можливих варіантів, без помилок) void main( ) {int i,j , k = -10; //int ident10k ; int id40 ; i = 2567; j =-3239 ; float fiden = - 22.38; float abcd123ef ; avcd1dd2 = 1259.38 ; for (id40 = 0; id40< i ; i++) {j = j;dfd=43;}; for (ident10k = 200; ident10k >= 100; ident10k--) {abcd123ef= abcd123ef; }; for(uhuh=2;j==-1;j++){j=fdj;int df=34;}; } 2. Потік лексем: z void z main o ( o ) o { t int i i o , i j o , i k = = - - c 10 o ; t int i id40 o ; i i = = c 2567 o ; i j = = - - c 3239 o ; a float i fiden = = - - d 22.38 o ; a float i abcd123ef o ; i avcd1dd2 = = d 1259.38 o ; f for o ( i id40 = = c 0 o ; i id40 s < i i o ; i i p ++ o ) o { i j = = i j o ; i dfd = = c 43 o ; o } o ; f for o ( i ident10k = = c 200 o ; i ident10k n >= c 100 o ; i ident10k m -- o ) o { i abcd123ef = = i abcd123ef o ; o } o ; f for o ( i uhuh = = c 2 o ; i j t == - - c 1 o ; i j p ++ o ) o { i j = = i fdj o ; t int i df = = c 34 o ; o } o ; o } Всі символи були розбиті на класи: букви – для ідентифікаторів цифри – для цифр та ідентифікаторів лексеми одиничної довжини ( , ; { } * ) ( ) – для знаків одиничної довжини знак + - для виділення знаку + та інкременту ++ знак – - для виділення знаку – та декременту -- знак / - для виділення знаку / та коментарів знак < > - для виділення знаків <, > та <=, >= знак . – для визначення дійсного числа решта знаків які не ввійшли до класів 1-8, 10 знак = - для виділення знаку = та порівняння = = Дескриптори лексем: z – визначає службове (зарезервоване) слово: main, void f - визначає for a - визначає float t - визначає int i – ідентифікатор c – ціле число d – дійсне число o – одно символьна лексема: , ; { } * ) ( + - операцію + p - інкремент - - операція - m - декремент / - операцію / s – строга нерівність <, > n – нестрога нерівність <=, >= = - операція присвоєння = t – операція порівняння = = 3. Граматика: Примітка1. Крапка після «відкриваючого» символу і крапка до «закриваючого» символу вказує на те що ці символи не належать до термінальних символів Не термінальні символи: M T F P O I D N M – заголовок основної програми – main T – тіло програми або циклу F – оператор for P – операція присвоєння O – опис змінних I – ініціалізація оператора for D – інкремент або декремент ідентифікатора. Використовується в 3тій складовій ініціалізації for ( I ) N – порівняння в другій складовій ініціалізації for ( I ) Термінальні символи: z f a t i c d , ; { } ) ( p m s n t = Аксіома: M Правила виводу: M => [. z .] z ( [. z .] ) { T } T => F | P | O F => f ( I ) { T } ; P => i = (. i | d | c .) ; O => t i [. = (. i | c .) .] {. , i [. = (. i | c .) .] .} ; | a i [. = (. i | d .) .] {. , i [. = (. i | d .) .] .} ; I => (. O | P .) N D D => i (. p | m .) N => i (. s | n | t .) (. i | d | c .) ; 4. Реалізація виводу про помилки: Всі помилки розбиті на такі класи: 0 – Помилки в main (при наявності такої помилки подальший аналіз може не відбутись – для тіла T) 1 – Помилки в операторі for ( в тому числі і і його ініціалізації I ) 2 – Помилки в операторі присвоєння 3 – Помилки в описі змінних 4 – Помилки лексичного аналізу, що стосуються перевищення довжини ідентифікаторів, цілих і дійсних чисел. Примітка2. При виконанні лексичного аналізу дескриптору лексеми надається значення «е»(при наявності помилки 4). В подальшому, при синтаксичному аналізі це ствоює незручності. Тому при роботі синтаксичного аналізатора, при зчитуванні рядка в якому дескриптор лексеми має значення «е», читається наступний рядок. Тобто дана лексема не розглядається. Це приводить до виникнення ряду помилок після цієї лексеми. Тому при виправленні помилок необхідно враховувати цю особливість. 5 – Помилки в тілі циклу або main Інформація про виведені помилки включає в себе тип помилки та кількість помилок певного типу. 5. Контрольний приклад: Варіант вхідного файлу: void main( ) {int i,j , k = -10; //int ident10k ; int d id40 ; i = 4 2567; j =-3239 ; float fiden = - 22.38; float abcd123ef ; avcd1dd2 = 1259.38 ; for (id40 = 0; id40<> i ; i+++) {j = j;dfd=43;}; for (ident10k = 200; ident10k >= 100; ident10k--) {abcd123ef= abcd123ef; }; for(uhuh=2;j==-1;j++){j=fdj;int ddffgfsdqqw=34;}; } Результат виконання:
Висновок: Реалізована програма яка на основі результатів лексичного аналізу, виконує синтаксичний аналіз вхідного файлу. Спочатку відбувається лексичний прохід а потім синтаксичний. Після цього виконується вивід помилок. 6. Код програми: #include <stdio.h> #include <conio.h> #include <iostream.h> #include <string.h> #define path1 "c:/workpol/3kurs/sysprog/lab303/vhid.txt" #define path2 "c:/workpol/3kurs/sysprog/lab303/leksemy.txt" //#define path1 "p:/lab303/vhid.txt" //#define path2 "p:/lab303/leksemy.txt" //--------------------------FUNCTION PROTOTIPES-------------------------- void analize(FILE*fw,char *str); int setclas(char sym); void getlit(char *str,int* i,int* clasnum); void write(FILE*fw,char lekstype,int p,int q,char*str); void leksyka(void); //--------------------- void errors(void); void syntax(void); char getsym(void); //-------------------- void M(void); void T(void); void F(void); void P(void); void O(void); void I(void); void N(void); void D(void); //-----------------------GLOBAL VARIABLES----------------------------- char str[200]; //strichka. z vhidnogo faila zchytuem po strichci char sym; FILE *fr; //vhidny fail int maserror[6]; //masyv pomylok //------------------------------MAIN------------------------------------- void main(void) { clrscr(); leksyka(); syntax(); errors(); getch(); } //---------------------FUNCTION BODIES------------------------------------- void syntax(void) { fr=fopen(path2,"r"); sym=getsym(); M(); //provirka main fclose(fr); cout<<"\nSytaxsychny analiz vhidnogo potoku leksem ("<<path2<<")uspishno vykonanyy.\n"; } //------------------------------------------------------------------------- void errors(void) { if(maserror[0]>=1)cout<<"\nDopushceni pomylky v Main. Kilkist - "<<maserror[0]; if(maserror[1]>=1)cout<<"\nDopushceni pomylky v For. Kilkist - "<<maserror[1]; if(maserror[2]>=1)cout<<"\nDopushceni pomylky v Operacii prysvoennya. Kilkist - "<<maserror[2]; if(maserror[3]>=1)cout<<"\nDopushceni pomylky v Opysi zminnyh. Kilkist - "<<maserror[3]; if(maserror[4]>=1)cout<<"\nNa etapi syntaxsychnogo analizu vyyavleno pervyschenyya rozmiru identyfikatoriv abo cilyh chysel. Kilkist - "<<maserror[4]; if(maserror[5]>=1)cout<<"\nDopushceni pomylky v Tili main abo for. Kilkist - "<<maserror[5]; } //---------------------------------------------------------------------- void M(void) { int e; e=0; //pomylok nemae if((sym=='z')&&(str[2]=='v')) { sym=getsym(); if((sym=='z')&&(str[2]=='m')) { sym=getsym(); if((sym=='o')&&(str[2]=='(')) { sym=getsym(); if((sym=='z')&&(str[2]=='v')) { sym=getsym(); if((sym=='o')&&(str[2]==')')) { sym=getsym(); if((sym=='o')&&(str[2]=='{')) { sym=getsym(); T(); if((sym=='o')&&(str[2]=='}')) { //sym=getsym(); }else e=1; }else e=1; }else e=1; } else { if((sym=='o')&&(str[2]==')')) { sym=getsym(); if((sym=='o')&&(str[2]=='{')) { sym=getsym(); T(); if((sym=='o')&&(str[2]=='}')) { //sym=getsym(); }else e=1; }else e=1; }else e=1; }; }else e=1; }else e=1; }else { if((sym=='z')&&(str[2]=='m')) { sym=getsym(); if((sym=='o')&&(str[2]=='(')) { sym=getsym(); if((sym=='z')&&(str[2]=='v')) { sym=getsym(); if((sym=='o')&&(str[2]==')')) { sym=getsym(); if((sym=='o')&&(str[2]=='{')) { sym=getsym(); T(); if((sym=='o')&&(str[2]=='}')) { //sym=getsym(); }else e=1; }else e=1; }else e=1; } else { if((sym=='o')&&(str[2]==')')) { sym=getsym(); if((sym=='o')&&(str[2]=='{')) { sym=getsym(); T(); if((sym=='o')&&(str[2]=='}')) { //sym=getsym(); }else e=1; }else e=1; }else e=1; }; }else e=1; }else e=1; }; sym=getsym(); maserror[0]+=e; } //---------------------------------------------------------------------- void T()//tilo obovyazkovo v {} { while( (!feof(fr)) && (str[2]!='}') ) { if(maserror[5]>10000){cout<<"\nPomylka programy abo nadto velyka kilkist pomylok...";break;}; if((sym!='f')&&(sym!='i')&&(sym!='t')&&(sym!='a')){maserror[5]+=1;sym=getsym();}; if(sym=='f') { F(); }; if(sym=='i') { P(); }; if((sym=='t')||(sym=='a')) { O(); }; } } //------------------------------------------------------------------------ void F(void) { int e; e=0; if(sym=='f') { sym=getsym(); if((sym=='o')&&(str[2]=='(')) { sym=getsym(); I(); if((sym=='o')&&(str[2]==')')) { sym=getsym(); if((sym=='o')&&(str[2]=='{')) { sym=getsym(); T(); if((sym=='o')&&(str[2]=='}')) { sym=getsym(); if((sym=='o')&&(str[2]==';')) {} else e=1; } else e=1; } else { e=1; } } else e=1; } else e=1; } else e=1; if(e==0){sym=getsym();}; maserror[1]+=e; } //----------------------------------------------------------------------- void P(void) { int e=0; if(sym=='i') { sym=getsym(); if(sym=='=') { sym=getsym(); if(sym=='-'){sym=getsym();}; //neobhidno shob obiyty - sho stoit pered cilym chyslom if((sym=='i')||(sym=='d')||(sym=='c')) { sym=getsym(); if((sym=='o')&&(str[2]==';')){} else e=1; } else e=1; } else e=1; } else e=1; maserror[2]+=e; while(str[2]!=';'){sym=getsym();};//vse sho do ; ye pomylkove sym=getsym(); } //------------------------------------------------------------------------ void O(void) { int e=0; if((sym!='t')&&(sym!='a'))e=1; else { if(sym=='t') { sym=getsym(); if(sym=='i') { sym=getsym(); if(sym=='=') { sym=getsym(); if(sym=='-'){sym=getsym();}; //neobhidno shob obiyty - sho stoit pered cilym chyslom if((sym=='i')||(sym=='c')) { sym=getsym(); } else e=1; } else { while((sym=='o')&&(str[2]==',')) { e=1; sym=getsym(); if(sym=='i') { sym=getsym(); if(sym=='=') { sym=getsym(); if(sym=='-'){sym=getsym();}; //neobhidno shob obiyty - sho stoit pered cilym chyslom if((sym=='i')||(sym=='c')) { sym=getsym(); if((sym=='o')&&(str[2]==';')) { e=0; break; }; } else e=1; } else { if((sym=='o')&&(str[2]==';')) { e=0; break; }; }; } else e=1; }//while }; if(str[2]!=';')e=1; } else e=1;//yaksho ne identyf }; if(sym=='a') { sym=getsym(); if(sym=='i') { sym=getsym(); if(sym=='=') { sym=getsym(); if(sym=='-'){sym=getsym();}; //neobhidno shob obiyty - sho stoit pered cilym chyslom if((sym=='i')||(sym=='d')) { sym=getsym(); } else e=1; } else { while((sym=='o')&&(str[2]==',')) { e=1; sym=getsym(); if(sym=='i') { sym=getsym(); if(sym=='=') { sym=getsym(); if(sym=='-'){sym=getsym();}; //neobhidno shob obiyty - sho stoit pered cilym chyslom if((sym=='i')||(sym=='d')) { sym=getsym(); if((sym=='o')&&(str[2]==';')) { e=0; break; }; } else e=1; } else { if((sym=='o')&&(str[2]==';')) { e=0; break; }; }; } else e=1; }//while }; if(str[2]!=';')e=1; } else e=1; }; };//else maserror[3]+=e; while(str[2]!=';'){sym=getsym();};//vse sho do ; ye pomylkove sym=getsym(); } //------------------------------------------------------------------------ void I(void) { int e=1; if((sym=='t')||(sym=='a')) { e=0; O(); N(); D(); if((sym=='p')||(sym=='m'))sym=getsym(); }; if(sym=='i') {e=0; P(); N(); D(); if((sym=='p')||(sym=='m'))sym=getsym(); }; if(str[2]==')'){e=0;} else {e=1;while(str[2]!=')'){sym=getsym();};}; //shob mogna bulo dali prodovguvaty maserror[1]+=e; } //------------------------------------------------------------------------ void N(void) { int e=0; if(sym=='i') { sym=getsym(); if((sym=='s')||(sym=='n')||(sym=='t')) { sym=getsym(); if(sym=='-'){sym=getsym();}; if((sym=='i')||(sym=='d')||(sym=='c')) { sym=getsym(); if((sym=='o')&&(str[2]==';')){} else e=1; } else e=1; } else e=1; } else e=1; maserror[1]+=e; sym=getsym(); } //------------------------------------------------------------------------- void D(void) { int e=0; if(sym=='i') { sym=getsym(); if((sym=='p')||(sym=='m')){} else e=1; } else e=1; maserror[1]+=e; } //----------------------------------------------------------------------- char getsym(void) { char sym; fgets(str,200,fr); //chytaem strichku sym=str[0]; //chytaem leksemu if(sym=='e'){fgets(str,200,fr);sym=str[0];}; return sym; } //-------------------------------------------------------------------------- void leksyka (void) { FILE *fr; //vhidny fail FILE *fw; //vyhidny fail char str[200]; //strichka. z vhidnogo faila zchytuem po strichci fr=fopen(path1,"r"); fw=fopen(path2,"w"); while(!feof(fr)) //poky ne kinec vhidnogo faila { fgets(str,200,fr); //chytaem strichku analize(fw,str); //analizuem ii. fw peredaem dlya zapysu v vyhidny fail } fclose(fr); fclose(fw); cout<<"Leksychny analiz vhidnogo faylu ("<<path1<<")uspishno vykonanyy.\nResultat u faili("<<path2<<")\n"; } //---------------------------------------------------------------------- void analize(FILE*fw,char *str) //analiz strichky str. zapys u fail fw leksem { char lekstype; //typ leksemy char leksvalue[20]; int p,q; //pozyciya pochatku i kincya leksemy int clasnum; char sym; //symvol yaky zchytaly p=0; //nomer pozycii - pochatku leksemy int i=0; //lichylnyk - probig po strichci while(str[i]!='\0') //poky ne kinec ryadka { if((str[i]==' ')||(str[i]=='\t')){i++;}; //probil i tab propuskaem getlit(str,&i,&clasnum); //berem i-tyy symvol.daem yomu nomer klasu. i++ switch (clasnum) //cey symvol vyznachae: { case 1: {lekstype='i';p=i;q=i; //identyficator do //poky bukva,cyfra to ce identyf. { getlit(str,&i,&clasnum); q++; //naroschuvannya dovgyny } while((clasnum==1)||(clasnum==2)); i--; write(fw,lekstype,p,q,str);break; //zapys v fw leksemy typu lekstype, }; //dovgynou q-p pochynayuchy z p-yi case 2: {lekstype='c';p=i;q=i+1; //cile chyslo //pozycii strichky str, shco analizuetsya getlit(str,&i,&clasnum); if(clasnum==8){lekstype='d';getlit(str,&i,&clasnum);}; //yakshco . to diysne while(clasnum==2) { getlit(str,&i,&clasnum); if(clasnum==8){lekstype='d';q++;getlit(str,&i,&clasnum);}; //yakshco . to diysne q++; }; i--; write(fw,lekstype,p,q,str);break; //zapys v fw leksemy typu lekstype, }; case 3: {lekstype='o';p=i;q=i+1;write(fw,lekstype,p,q,str);break;}; //odnosymvolni leksemy case 4: { //znak + odnosym leksem abo p-dvosymvolna increment int pr=0; lekstype='+';p=i;q=i+1; getlit(str,&i,&clasnum); if(clasnum==4){lekstype='p';pr=1;q++;write(fw,lekstype,p,q,str);}; if(pr==0){write(fw,lekstype,p,q,str);i--;}; break; }; case 5: { //znak - odnosym leksem abo m-dvosymvolna decrement int pr=0; lekstype='-';p=i;q=i+1; getlit(str,&i,&clasnum); if(clasnum==5){lekstype='m';pr=1;q++;write(fw,lekstype,p,q,str);}; if(pr==0){write(fw,lekstype,p,q,str);i--;}; break; }; case 6: { //znak / odnosym leksem abo propuskaem komentar int pr=0; lekstype='/';p=i;q=i+1; getlit(str,&i,&clasnum); if(clasnum==6) { while(str[i]!='\n'){i++;}; pr=1; }; if(pr==0){write(fw,lekstype,p,q,str);i--;}; break; }; case 7: { //znak <,> strogoi(s) abo <=,>= nestrogoi(n) nerivnosti int pr=0; lekstype='s';p=i;q=i+1; getlit(str,&i,&clasnum); if(clasnum==10){lekstype='n';pr=1;q++;write(fw,lekstype,p,q,str);}; if(pr==0){write(fw,lekstype,p,q,str);i--;}; break; }; case 8: { //krapka ne vvagaem shcho e chysla vydu .4598 i=strlen(str);puts("zustrilas krapka yaka ne ye oznakoyu diysnogo chysla. ignoruem ii");getch(); }; case 9: {break; }; case 10:{//lekstype='=';p=i;q=i+1;write(fw,lekstype,p,q,str);break;}; int pr=0; lekstype='=';p=i;q=i+1; getlit(str,&i,&clasnum); if(clasnum==10){lekstype='t';pr=1;q++;write(fw,lekstype,p,q,str);}; if(pr==0){write(fw,lekstype,p,q,str);i--;}; break; }; } } } //------------------------------------------------------------------------ void getlit(char *str,int* i,int* clasnum) //daem i-tu pozyciyu //i-tomu symvolu strichky str nadaem nomer yog klasu clasnum { char sym=str[*i]; *clasnum=setclas(sym); //vstanovluem klas symvolu sym=str[i] *i=*i+1; //nastupny budem chytaty } int setclas(char sym) //vstanovlennya do yakogo klasu nalegyt sym {int r=9; //inshi symvoly if((sym>='a')&&(sym<='z')||(sym>='A')&&(sym<='Z'))r=1; //bukvy if((sym>='0')&&(sym<='9'))r=2; //cyfry if((sym=='(')||(sym==')')||(sym==';')||(sym==',')||(sym=='{')||(sym=='}')||(sym=='*'))r=3; if(sym=='+')r=4; //odynychni leksemy if(sym=='-')r=5; if(sym=='/')r=6; if((sym=='<')||(sym=='>'))r=7; //znaky porivnyannya if(sym=='.')r=8; //des krapka. dlya float if(sym=='=')r=10; return r; } //-------------------------------------------------------------------- void write(FILE*fw,char lekstype,int p,int q,char*str) //zapys u file fw { //typ leksemy lekstype i ii znachennya yake pochynaetsya v p i mae //dovgynu q-p v strichci str char value[30]=""; //znachennya leksemy int k=q-p-1; //dovgyna leksemy for (int i=0;i<=k;i++,p++){value[i]=str[p-1];}; //formuem znachennya leksemy if(lekstype=='i'){ if(strcmp(value,"for")==0)lekstype='f'; if(strcmp(value,"main")==0)lekstype='z'; if(strcmp(value,"float")==0)lekstype='a'; if(strcmp(value,"int")==0)lekstype='t'; if(strcmp(value,"void")==0)lekstype='z'; } if(lekstype=='i'){ if(k>=9){lekstype='e';maserror[4]+=1;}; }; if(lekstype=='c'){ if(k>=5){lekstype='e';maserror[4]+=1;}; }; fprintf(fw,"%c\t%s\n",lekstype,value); //zapys u fail }