Universitatea Tehnica a MoldoveiFiliera Francofona Informatica

Catedra ATILimbaje Formale shi Proiectarea Compilatorului

Tema : Analizatorul lexical.Varianta 8

A efectuat: studentul grupei FI-071: Negrivoda Serghei

A verificat : lector superior: Marusic Galina

Chisinau 2009

Cuprinsul proiectului:Varianta 8

1

1. Foaia de titlu

2. Scopul lucrării

3. Descrierea limbajului dat

4. Notiuni teoretice.

5. Rezolvarea sarcinii

6. Listingul programului

7. Concluzie

Scopul lucrarii:

2

1. În descrierea neformală a unui limbaj dat să se evidenţieze lexemele. Pentru fiecare tip de lexemă să se construiască un automat finit, care acceptă lexeme corecte.

2. Determinaţi dacă automatele construite sunt deterministe.3. Dacă automatul finit nu este detrminist, să se construiască pentru el un

automat finit determinist echivalent.4. Construiţi schema analizatorului lexical pentru limbajul dat.5. Testaţi lucrul analizatorului lexical pe 5 şiruri de intrare corecte şi 3

şiruri, care conţin lexeme incorecte sau simboluri neacceptate de limbaj, construind pentru aceste şiruri:

Vectorul sintactic;Vectorul semantic;Completarea tabelului pentru fiecare tip de lexemă.

6. Elaboraţi un program pentru analizatorul lexical şi demonstraţi lucrul programului pentru şirurile de intrare construite.

Descrierea limbajului dat:

3

Identificatorul in limbajul FORTRAN se defineşte ca o secvenţă din litere şi cifre, care începe în mod obligatoriu cu o literă. Lungimea identificatorului nu trebuie să depăşească 6 simboluri. Constantele sunt numere întregi, reale şi cu precizie dublă. Numerele reale se scriu în forma obişnuită cu punct zecimal. Aceste numere pot fi urmate de un exponent care are forma E <semn>< număr întreg>. Semnul poate fi omis. Numărul de precizie dublă se deosebeşte de cel real doar prin prezenţa obligatorie a exponentului, indicat prin litera D în loc de E. Textele propuse spre analizare se definesc cu ajutorul producţiilor:

<program> → <listă de instrucţiuni><listă de instrucţiuni> → <instrucţiune><listă de instrucţiuni> → <instrucţiune> <listă de instrucţiuni><instrucţiune> → <identificator> = <expresie><instrucţiune> → <etichetă>:<identificator>= <expresie><etichetă> → <număr întreg><expresie> →<număr><expresie> →(<expresie>)<expresie> →<identificator><expresie> →<expresie> <operaţie> <expresie> <operaţie> → + <operaţie> → <operaţie> → / <operaţie> → * <operaţie> → **De menţionat că eticheta poate ocupa poziţiile 1-5 în rînd, iar instrucţiunia 7-72, rîndurile avînd lungimea maximă 80 de simboluri. Spaţiile libere se ignorează.

4

Notiuni teoretice:

Limbajul Fortran este decanul de varsta al limbajelor de larga folosinta . A aparut in 1956 si isi datoreaza numele prescurtarii cuvintelor : FORmula TRANslation ( Traducere de formule ). Initial reprezenta un limbaj orientat pe calcule stiintifice avand definite concepte precum : matrice , functii trigonometrice , numere reale in dubla precizie . Versiunile ulterioare care au cunoscut o mare popularitate au extins posibilitatile limbajului trasformandu-l intr-un limbaj eficient , de uz general .In prezent exista pentru IBM-PC doua implementari mai importante ale limbajului : Microsoft Fortran , Fortran for Windows .

Desi nu poate fi considerat „ depasit „ din punct de vedere conceptual ( este un limbaj algoritmic – structurat ) este neindicata folosirea lui datorita absentei unor medii de programare performante si pentru ca tendinta actuala ii este defavorabila .

Primul compilator FORTRAN a fost dezvoltat pentru IBM 704 în 1954–57 de o echipă IBM condusă de John W. Backus. Acesta a fost un compilator de optimizare, deoarece autorii considerau că nimeni nu ar fi folosit limbajul dacă performanţele sale nu ar fi fost comparabile cu Assemblerul.

Limbajul a fost adoptat pe scară largă de către oamenii de ştiinţă pentru scrierea programelor ce foloseau numere în mod intensiv, fapt ce a încurajat autorii de compilatoare să producă soft-ul lor în aşa fel încât să genereze cod mai rapid. În special includerea unui tip de date numeric complex în limbajul FORTRAN l-a făcut potrivit pentru folosirea în ştiinţa computaţională.

Numeroase standarde ale limbajului au apărut: FORTRAN II în 1958, FORTRAN IV în 1961, FORTRAN 66 în 1966, FORTRAN 77 în 1977 , Fortran 90 în 1990, Fortran 95 în 1995, şi Fortran 2003 în 2003. Fortran III a fost creat în 1958, lăsând posibilitatea includerii de cod asamblare de tip Inline în programele sale; dar nu a fost niciodată dat spre folosinţă deoarece conceptul de portabilitate al unui limbaj de nivel înalt ar fi fost pierdut.

5

Interfaţa analizorului lexicalDupa cum se ştie analizorul lexical funcţioneză ca un modul in cadrul unui compilator sau a oricărui program care realizează prelucrări ce necesită identificarea unor şiruri ce pot fi descrise de o gramatică regulată. In funcţionarea sa analizorul lexical interacţionează cu celelalte componenteale compilatorului prin intermediul unei interfeţe specifice :

Rolul analizei lexicale este de a traduce textul programului intr-o secvenţă de atomi lexicali. In acest mod se obţine un "text" mai uşor de prelucrat de către celelalte componente ale compilatorului, deoarece se realizează o abstractizare a unei infinităţi de şiruri de intrare in atomi de tip - identificatori, constante, etc. De asemenea prin eliminarea blancurilor şi a altor separatori irelevanţi (ca de exemplu comentarii), textul prelucrat se poate reduce drastic. De cele mai multe ori analiza lexicală realizează şi alte activitati auxiliare ca de exemplu păstrarea evidenţei numărului de linii citite. O astfel de informaţie este foarte utilă pentru construirea mesajelor de eroare. Cand se proiectează un analizor lexical se pune in general problema

6

care este nivelul de complexitate al atomilor lexicali consideraţi. De exemplu in cazul in care un limbaj utilizează numere complexe, se pune problema dacă analizorul lexical va fi cel care va recunoaşte o constantă de forma:

(<real>, <real>)producand un atom lexical corespunzător sau recunoaşterea unei astfel de constante ramane in sarcina nivelului analizei sintactice. In general un analizor lexical este specificat sub forma :

p1 {actiune 1}p2 {actiune 2}

...pn {actiune n}

unde pi este o expresie regulata, iar actiune i este o secvenţă de operaţii care se execută pentru fiecare subşir care corespunde modelului oferit de pi.Dacă in tabela nu există şirul căutat rezultatul este 0.Pentru cuvintele cheie de obicei se face o tratare speciala, de exemplu se poate initializa tabela de simboli cu intrari corespunzătoare tuturor cuvintelor cheie din limbajul respective executand apeluri de forma : insert_s("if", cod_if);

insert_s("else", cod_else);etc. inainte de a se incepe execuţia efectivă a compilatorului. In acest caz recunoaşterea cuvintelor cheie se va face apoi intr-un mod similar cu a oricarui alt identificator. Se observă deci de ce in majoritatea limbajelor de programare cuvintele cheie nu pot să fie utilizate ca nume cu altă semnificaţie. O astfel de tratare are avantajul ca in cazul in care se face o declaraţie de tip de forma:

typedef int intreg;după introducerea in tabela de simboli a cuvintului intreg de către analizorul lexical, analizorul sintactic va putea să completeze apoi intrarea in tabela de simboli cu informaţiile corespunzătoare numelui unui tip. In acest mod in următoarele intalniri ale acestui cuvant analizorul lexical va putea să transmită ca ieşire atomul lexical corespunzător unui nume de tip.In cazul constantelor analizorul lexical realizează recunoaşterea acestora şi memorează valorile corespunzătoare in tabela de constante pentru a permite utilizarea ulterioară in cadrul generării de cod. Analizorul sintactic apelează de obicei analizorul lexical ca pe o funcţie care are ca valoare codul atomului lexical recunoscut de către analizorul lexical. Se observă ca in

7

acest caz utilizarea unei proceduri de tip ungetc() nu este suficientă. In general o colecţie de funcţii care asigură citirea textului sursă pentru analizorul lexical trebuie să satisfacă următoarele condiţii: • funcţiile trebuie să fie cat mai rapide, realizand un număr minim de copieri pentru caracterele parcurse; • existenţa unui mecanism care să permită examinarea unor caractere in avans şi revenirea pe şirul de intrare; • să admită atomi lexicali suficient de lungi;Pentru a obţine o utilizare eficientă a operaţiilor legate de accesul la disc este necesar ca dimensiunea bufferuluisă fie adaptată modului de alocare a spatiului pe disc. Astfel, pentru sistemul de operare MS-DOS utilizarea unui buffer mai mic decat 512 octeţi nu are nici o justificare (o operaţie de citire va citii cel puţin un sector de pe disc). De preferat este ca bufferul să fie un multiplu al unităţii de alocare a spatiului pe disc.O alternativă de specificare a limbajelor constă în definirea unui algoritm care să răspundă „Da” în cazul în care un şir x aparţine limbajului şi „Nu” dacă şirul nu aparţine limbajului. Unitatea de comandă are un „program cablat" care impune o anumită funcţionare a maşinii. Funcţionarea (sau evoluţia) este o secvenţă de „mişcări". Mişcarea constă dintr-o modificare a configuraţiei maşinii de către o operaţie. Vom înţelege prin configuraţie ansamblul stărilor componentelor maşinii. Mişcarea se poate defini printr-o pereche formată din configuraţia din care pleacă maşina şi configuraţia în care ajunge in urma, mişcării. Banda de intrare

Cap de citire

Asemenea „modele fizice''sînt intuitive şi ele stau la baza interpretării relaţiilor matematice ce vor forma snbstanta acestui paragraf. Pentru a fi însa efectiv utilizabil, un algoritm de analiză trebuie riguros fundamentat.

8

Unitatea de comandă

memorie

Rezolvarea sarcinii.Gramatica:1.P→L2.L→I3.L→IL4.I→i=E5.I→e i =E

6.E→n7.E→i8.E→n*E9.E→i*E

Unde: I-instructiune i-identificator E-expresie e-eticheta n-numere intregi, reale si cu precizie dubla Tabelul şi codul lexemelor pentru limbajul dat:

AF pentru numere intregi:

AF pentru numere reale:

Lexeme CodulNumareticheta

identificator=*/+-

**()

1234567891011

0-9q0

q1

9

AF pentru numere reale cu precizie dubla:

AF pentru identificatori:

. E

Cifra

q0

q1

q2

Cifra

. D

Cifra

q0

q1

q2

Cifra

1

2

1

2

0

2

1

2

1

1

f

a

q0

q1

q2

q3

q4

q5

q10

q9

q8

q7

q6

q11

l

f

a

d

i

l

i

e

10

Next, i

Codul respectiv în

vectorul sintactic

AF pentru identificatori

simbolic

ERROR- illegal identifieridentifier

cautarea dupa TI completarea vectorului sintactic si semantic

AF pentru num.reale

ERROR- illegal identifierconstant

ERROR-unknown symbol

ieşire

AF pentru num.intregi

ERROR- illegal identifierconstant

AF pentru num. reale cu precizie dubla

Schema analizatorului lexical pentru limbajul dat:

nu

da

EOF

(, )

E

cautarea dupa TI completarea vectorului sintactic si semantic

ERROR- illegal identifier

cautarea dupa TI completarea vectorului sintactic si semantic0-9

da

da

nua,f,l,di,e,r0,1,2

cautarea dupa TI completarea vectorului sintactic si semantic

D

da

Analizatorului lexical pe 5 şiruri de intrare corecte şi 3 incorecte:Sirul de intrare corecta 1: a1 * 3 al1 7.5E - / fil2 + 6

Vect.sintactic 3 5 1 3 1 8 6 3 7 1Vect.semantic 1 1 2 2 3 3

TI: 1→a1 TN: 1→3 2→al1 2→7.5E 3→fil2 3→6 Sirul de intrare corecta 2: 9.6D + - fi1 ( 3 * alfa1 ) / 4

Vect.sintactic 1 7 8 3 10 1 5 3 11 6 1Vect.semantic 1 1 2 2 3

TI: 1→fi2 TN: 1→9.6D 2→alfa1 2→3 3→4 Sirul de intrare corecta 3: ( alf2 ** ( 6.2E – f0 / 9 ) + ) =

Vect.sintactic 10 3 9 10 1 8 3 6 1 11 7 11 4Vect.semantic 1 1 2 2

TI: 1→alf2 TN: 1→6.2E 2→f0 2→9Sirul de intrare corecta 4: 0 – file2 + ** ( a1 / 9 )

Vect.sintactic 1 8 3 7 9 10 3 6 1 11Vect.semantic 1 1 2 2

TI: 1→file2 TN: 1→0 2→a1 2→9Sirul de intrare corecta 5: ( alfad2 – al1 + 9.3E / 5 * filer1 ** 7.7D )

Vect.sintactic 10 3 8 3 7 1 6 1 5 3 9 1 11Vect.semantic 1 2 1 2 3 3

TI: 1→alfad2 TN: 1→9.3E 2→al1 2→5 3→filer1 3→7.7D Sirul de intrare incorecta 1: 3 + end * a1 – a2 / 2.5E * 3.3

Vect.sintactic 1 7 -1 5 3 8 -1 6 1 5 -1Vect.semantic 1 1 2

TI: 1→a1 TN: 1→3 2→2.5E ERROR(1)-illegal constant(‘end’) ERROR(2)-illegal identifier(‘a2’) ERROR(3)-unknown symbol(‘3.3’)

Sirul de intrare incorecta 2: 76 + 2 – al1 // 3.2 * + alf2 ++ 53Vect.sintactic -1 7 1 8 3 -1 -1 5 7 3 -1 -1Vect.semantic 1 1 2

TI: 1→al1 TN: 1→2 2→alf2 ERROR(1)- unknown symbol(‘76’) ERROR(2)- unknown symbol(‘//’) ERROR(3)- unknown symbol(‘3.2’) ERROR(4)- unknown symbol(‘++’) ERROR(5)- unknown symbol(‘53’)Sirul de intrare incorecta 3: a0 *- + begin 2.3A ( +/ 12 fa )

Vect.sintactic -1 -1 7 -1 -1 10 -1 -1 -1 11Vect.semantic

ERROR(1)-illegal identifier(‘a0’) ERROR(2)-unknown symbol(‘*-’) ERROR(3)-illegal constant(‘begin’) ERROR(4)-illegal identifier(‘2.3A’) ERROR(5)-unknown symbol(‘+/’) ERROR(6)-unknown symbol(‘12’) ERROR(7)-illegal identifier(‘fa’)

Listingul programului:#include<stdio.h>#include <conio.h>#include <stdlib.h>#include <string.h>#include <iostream.h>char sir[100];int sintactic[50],semantic[50];char ti[10][30],te[10][30];int i=0,sin=0,identif=0,expr=0;void completaresin(int k){sintactic[sin]=k; sin++;}void completaresemi(int j,int l, int k){int y=0; char b[10];for(int m=0;m<k-l;m++) b[m]=sir[l+m];b[m]=NULL; //cout<<b; getch();for(m=0;m<identif;m++) if(strcmp(ti[m],b)==0) y=1;if(y==0&&j==3){ for(m=0;m<k-l;m++) ti[identif][m]=sir[l+m];identif++; semantic[sin-1]=identif;}}void completareseme(int j,int l, int k){int y=0; char b[30];for(int m=0;m<k-l;m++) b[m]=sir[l+m];b[m]=NULL; //cout<<b; getch();for(m=0;m<expr;m++)if(strcmp(te[m],b)==0) y=1;if(y==0&&j==1){ for(m=0;m<k-l;m++) te[expr][m]=sir[l+m];expr++;semantic[sin-1]=expr;}if(y==0&&j==2){ for(m=0;m<k-l;m++) te[expr][m]=sir[l+m];expr++;semantic[sin-1]=expr;}}void afisaresin(){cout<<"vectorul sintactic: "<<endl; for(int j=0;j<sin;j++) cout<<sintactic[j]<<" ";}void afisaresem(){cout<<endl<<"vectorul semantic: "<<endl;for(int j=0;j<sin;j++)if(semantic[j]!=0) {if(sintactic[j]==14||

sintactic[j]==15)cout<<semantic[j]<<" ";else cout<<" ";}else cout<<" ";}void eroare(int j,int l, int k){int a;cout<<endl;if(j==1){ cout<<"illegal number ("; for(a=l;a<k;a++) cout<<sir[a]; cout<<")"<<endl;}if(j==2){ cout<<"illegal symbol of assignment (";for(a=l;a<k;a++) cout<<sir[a]; cout<<")"<<endl;}if(j==3) {cout<<"illegal identifier (";for(a=l;a<k;a++) cout<<sir[a]; cout<<")"<<endl;}if(j==4){ cout<<"unknown symbol (";for(a=l;a<k;a++) cout<<sir[a]; cout<<")"<<endl;}if(j==5){cout<<"incorect expression (";for(a=l;a<k;a++) cout<<sir[a]; cout<<")"<<endl;}}void afnumere(int j){int k=j,q=0,x=j,incorect=0;do {j++;} while(sir[j]!=' '&& sir[j]!=NULL&&sir[j]!=','&&sir[j]!='='&&sir[j]!=':'&&sir[j]!=')'); //k-jq=0;while(x<j){switch(q){case 0:{ if(sir[x]=='0'||sir[x]=='1'||sir[x]=='2'||sir[x]=='3'||sir[x]=='4'||sir[x]=='5'||sir[x]=='6'||sir[x]=='7'||sir[x]=='8'||sir[x]=='9') q=0;elseif(sir[x]=='.') q=1;else incorect=1; break;}case 1:{if(sir[x]=='E') q=2; else if(sir[x]=='D') q=3;else incorect=1; break;}case 2:{ if(sir[x]=='0'||sir[x]=='1'||sir[x]=='2'||sir[x]=='3'||sir[x]=='4'||sir[x]=='5'||sir[x]=='6'||sir[x]=='7'||sir[x]=='8'||sir[x]=='9') q=2;else incorect=1; break;}case 3:{ if(sir[x]=='0'||sir[x]=='1'||sir[x]=='2'||sir[x]=='3'||sir[x]=='4'||sir[x]=='5'||sir[x]=='6'||sir[x]=='7'||

sir[x]=='8'||sir[x]=='9') q=3;else incorect=1; break;}default: break;}x++;}if(q==0&&incorect==0){completaresin(1); completareseme(1,k,j);}if(q==2&&incorect==0){completaresin(2); completareseme(2,k,j);}if(q==3&&incorect==0){completaresin(2); completareseme(2,k,j);}if(incorect==1){eroare(1,k,j);}i=j;}void afidentificator(int j){int k=j,x=j,q=0,incorect=0;do {j++;} while(sir[j]!=' '&& sir[j]!=NULL&&sir[j]!=','&&sir[j]!='='&&sir[j]!=':'&&sir[j]!=')'); //k-jif(sir[x]=='a') q=1; if(sir[x]=='f') q=6; x++;while(x<=j){switch(q){case 1:{ if(sir[x]=='1') q=11; else if(sir[x]=='l') q=2; else incorect=1; break;}case 2:{ if(sir[x]=='1') q=11; else if(sir[x]=='f') q=3; else incorect=1; break;}case 3:{ if(sir[x]=='2') q=11; else if(sir[x]=='a') q=4; else incorect=1; break;}case 4:{ if(sir[x]=='1') q=11; else if(sir[x]=='d') q=5; else incorect=1; break;}case 5:{ if(sir[x]=='2') q=11; else incorect=1; break;}case 6:{ if(sir[x]=='0') q=11; else if(sir[x]=='i') q=7; else incorect=1; break;}case 7:{ if(sir[x]=='2') q=11; else if(sir[x]=='l') q=8; else incorect=1; break;}

case 8:{ if(sir[x]=='1') q=11; else if(sir[x]=='i') q=9; else incorect=1; break;}case 9:{ if(sir[x]=='2') q=11; else if(sir[x]=='e') q=10; else incorect=1; break;}case 10:{ if(sir[x]=='1') q=11; else incorect=1; break;}case 11:{incorect=0; break;}default :{incorect=1; break;}}x++;}if(incorect==0){completaresin(3); completaresemi(3,k,j);} else { completaresin(-1); eroare(3,k,j);}i=j;}void unknown(int j){int k=j;do {j++;} while(sir[j]!=' '&& sir[j]!=NULL&&sir[j]!=','&&sir[j]!=';'&&sir[j]!=':');eroare(4,k,j);completaresin(-1);i=j;}void main(){clrscr();cout<<"Introduceti sirul: ";gets(sir);while(sir[i]){switch(sir[i]){case '0':{afnumere(i); break;}case '1':{afnumere(i); break;}case '2': {afnumere(i); break;}case '3':{afnumere(i); break;}case '4': {afnumere(i); break;}case '5': {afnumere(i); break;}case '6': {afnumere(i); break;}case '7': {afnumere(i); break;}case '8': {afnumere(i); break;}case '9': {afnumere(i); break;}case 'a':{afidentificator(i); break;}case 'f':{afidentificator(i); break;}case '=':{completaresin(4);i++; break;}case'*':{if(sir[i+1]=='*') completaresin(9); else completaresin(5);i++; break;}case '/':{completaresin(6);i++; break;}case '+':{completaresin(7);i++; break;}case '-':{completaresin(8);i++; break;}

case '(': {completaresin(10); i++; break;}case ')': {completaresin(11); i++; break;}case' ':{i++; break;}default:{ unknown(i); break;}} }cout<<endl;afisaresin();afisaresem();cout<<endl<<"Tidentif: ";

for(int v=0;v<identif;v++) {cout<<v+1<<")"<<ti[v]; cout<<", ";}cout<<endl<<"Tnumere: ";for(v=0;v<expr;v++) {cout<<v+1<<")"<<te[v]; cout<<", ";}getch();}

Rezultatul programului:

Concluzii:Efectuind lucrarea de curs, am facut cunostinta cu metodele de executare a unui analizator lexiacal, si cu princiipile de baza a unui analizator lexical.In lucrarea data eu am lucrat cu identificatorii, numerele intregi, reale shi cu precizie dubla. Am invatat sa facem sirurile corecte si incorecte shi cum sa le exprimam printr-un program efectuat cu ajutorul limbajului Fortran. In finele lucrarii am executat un program ce calculeaza shi executa ceia ce am facut noi singuri.