VERIFICAREA TIPURILOR

VERIFICAREA TIPURILOR

Un compilator trebuie sa asigure verificarea completa a programului sursa, adica atat respectarea conventiilor sintactice cat si a celor semantice specifice limbajului respectiv. Verificarile sintactice se face exclusiv si complet la compilare. Cele semantice sint facute de obiceim partial la compilare, partial la executie. Verificarile semantice din timpul copilarii se numesc statice.

Categorii de verificari statice:

verificari de tip: se verifica compatibilitatea intre operatori si operanzi, intre parametrii formali si actuali

verificari privind fluxul de control al programului: instructiunilor care determina ca fluxul de control al programului sa paraseasca o anumita constructie trebuie sa li se poata asocia o locatie la care sa se transfere controlul

verificari de unicitate: daca un obiect trebuie definit sau declarat o singura data

verificari legate de nume: exista limbaje de programare in care acelasi nume trebuie sa apara de 2 sau mai multe ori in situatii bine precizate (Ada: loop, bloc)

Unele din aceste verificari pot fi incluse in alte activitati ale compilatorului sau se pot realiza concomitent cu ele (unicitatea unui identificator va fi detectata folosind tabela de simboluri). In majoritatea compilatoarelor verificarile statice se combina intr-o singura trecere cu generarea de cod intermediar si cu analiza sintactica. In cazul unor limbaje de programare mai complexe (ex. Ada) s-a preferat ca verificarile de tip sa fie tratate intr-o trecere separata, situata intre analiza sintactica si generarea de cod intermediar.

Un verificator de tip (VT) verifica daca tipul unei constructii de limbaj corespunde celui asteptat din context. Informatia de tip culese de un verificator de tip este utila atat pentru verificari cat si pentru generarea de cod. Ex: pentru operatorul '+' trebuie analizat contextul in care apare (adunare de intregi, reale, siruri, multimi) si se va genera codul corespunzator fiecarei situatii.

Un operator care in diverse contexte are semnificatii diferite este supraincarcat. Dpdv. Al compilarii, supraincarcarea poate fi insotita de constrangeri de tip (ex. Cu operanzi micsti, caz in care trebuie generat un operator special de conversie a unuia din cei 2 operanzi la tipul rezultat din context).

O notiune inrudita cu supraincarcarea operatorilor dar totusi distincta este polimorfismul aplicat functiilor. Corpul unei functii polimorfice poate fi executat cu argumente de tipuri diferite.

Sisteme de tipuri.

Proiectarea unui VT pentru un anumit limbaj se bazeaza pe informatii despre unele constructii sintactice ale limbajului respectiv: definitii de tipuri si reguli pentru asignarea de tipuri unor constructii de limbaj.

Exemple:

Pascal: daca avem 2 operanzi de tip intreg corespunzatori operatorilor aritmetici de adunare, scadere, inmultire, atunci rezultatul este de tip intreg

C: rezultatul operatorului unor referentieri este un pointer la obiectul referit de operand; daca tipul operatorului este t, atunci tipul rezultatului este &t.

In ambele exemple este implicita ideea ca fiecare expresie are un tip asociat cu aceasta.

Tipurile unui limbaj pot fi simple, atomice, fara structura interna din punct de vedere al utilizatorului sau compuse. De exemplu tipurile enumerare si subdomeniu desi sunt definite intern ca fiind compuse, se trateaza ca tipuri atomice.

Tipurile compuse se pot construi pronind de la tipuri atomice si/sau tipuri definite anterior. In aceeasi categorie se include si pointerii si functiile (de ex &t este construit pe baza tipului lui t).

Expresii de tip

Printr-o expresie de tip se indica tipul unei constructii de limbaj. Ea poate sa reprezinte un tip de baza, fie se poate obtine prin aplicarea unui operator numit constructor de tip asupra altor expresii de tip.Multimea tipurilor de baza si a constructiilor de tip este specifica limbajului respectiv. Se va construi o definitie pentru expresiide tip pentru limbajul Pascal (in 4 puncte):

Un tip de baza este o expresie de tip. Se admit ca tipuri de baza: boolean, char, integer, real. Se introduce un tip de baza special notat tip eroare prin care se va semnala aparitia unei erori la veirificarea de tip si un alt tip de baza vid semnificand absenta tipului, care va permite extinderea verificarilor de tip in mod uniform asupra instructionuilor in ansamblu.

Deoarece tipurile pot avea nume, rezulta ca un nume de tip poate fi de asemenea o expresie de tip

Un constructor de tip aplicat unor expresii de tip este de asemenea o expresie de tip. Ca si constructori se admit:

1. tablouri: se caracterizeaza astfel: daca T este o expresie de tip si I este o multime de indici atunci array(I,T) este o expresie de tip reprezentand un tip tablou cu elemente de tipul T si cu multimea de indici I.

var A: array [1..10] of integer;

tipul lui A : array (1..10, integer).

2. produse : daca T1 si T2 sunt expresii de tip, atunci produsul lor cartezian T1*T2 este de asemenea expresie de tip. In plus, operatorul "*" este asociativ la stanga
3. articole - tipul unui articol poate fi considerat ca produsul tipurilor campurilor sale. In plus, se poate tine cont si de faptul ca pe langa tip, campurile au si nume, care pot si ele sa fie incluse in expresii de tip. Rezulta ca expresia de tip pentru un articol se poate obtine prin aplicarea constructorului record unui produs ai carui factori sint produse intre numerele campurilor si tipurile corespunzatoare

type tipsir = record

adresa: integer;

sir : array [1..15] of char;

end;

var tablou: array[1..100] of tipsir;

Pentru numele de tip notat tipsir se construieste urmatoarea expresie de tip:

Tipsir =record((adresa*integer)*(sir8array(1..15,char)))

Variabila trablou fiind tablou de inregistrari, I se asociaza expresia de tip array(1..100, tipsir).

4. pointeri - daca T este o expresie de tip atunci pointer (T) reprezinta de asemenea o expresie de tip semnificand pointer la obiectul de tipul T
5. functii - din punct de vedere matematic, o functie pune in corespondenta elementele unei multimi reprezentand domeniul, cu elementele altei multimi (codomeniul). Similar, in limbajele de programare, functiile pot fi privite ca punand in corespondenta un tip domeniu D cu un tip codomeniu D. Tipul unei astfel de functii poate fi reprezentat formal prin urmatoarea expresie de tip: D→C.

expresiile de tip pot contine variabile ale caror valori sint de asemenea expresii de tip (tipul articol de exemplu)

O expresie de tip poate fi reprezentata printr-un graf. Pornind de la abordarea dirijata de sintaxa din capitolul precedent, se poate construi un arbore cat si un graf orientat aciclic pentru aceeasi expresie de tip. Nodurile interioare corespund constructiilor de tip sint pentru tipuri de baza.

Exemplu: char * char → pointer (integer)

Arbore graf orientat aciclic

1.2 Definitia unui sistem de tipuri

Un sistem de tipuri este o colectioe de reguli care permit asignarea de expresii de tip diferitelor patri ale unui program. Un verificator de tip corect implementeaza intotdeauna un anumit sistem de tipuri. In ceea ce urmeaza, un sistem de tip va fi specificat intr-o maniere dirijata de sintaxa (ca DDS sau schema de traducere), deci vor putea fi efectiv implemenate utilizand tehnicile din capitolul precedent. Sistemel de tipuri difera de la un limbaj la altul, dar pot diferi si in diferite compilatoare pentru acelasi limbaj.

Verificarea statica si dinamica a tipurilor

Orice verificare de tip poate fi facuta dinamic daca s transmite in codul obiect tipul elementelor impreuna cu valoarea acelui element. Aceasta insa conduce la performante slabe. Un sistem de tipuri este consistent daca elimina necesitatea verificarii dinamice de tip, garantand de la compilare(static) ca aceste erori nu pot sa apara la executia programului. Daca un astfel de sistem de tipuri asigneaza unei parti de program o expresie de tip diferita de tipul eroare atunci se garanteaza ca in acea parte de program, la executia ei nu pot sa apara erori de tip. Un limbaj de programare se numeste puternic tipizat daca prin compilatorul sau se poate garanta ca programele pe care le accepta se vor executa fara erori de tip. In situatii practice acest lucru nu este integral posibil(ex: incadrearea indicelui de tablou in limitele date).

2. Specificarea unui verificator de tip simplu

Se va descrie un verificator de tip pentru un limbaj simplu in care un identificator trebuie declarat inainte de a fi utilizat; prin declarare I se asociaza un tip. Verificatorul este o schema de traducere compusa din 2 parti:

a.       partea de declaratii - se stabileste tipul identificatorului conform declaratiei si se introduce in tabela de simboluri

b.      partea de instructiuni si expresii - se sintetizeaza tipul fiecarei expresii din tipul subexpresiilor componente, se executa verificarile de tip conform cu verificarile semantice ale limbajului

Se trateaza astfel :

a.       tipuri de baza, tablouri, pointeri

b.      siruri de caractere, numere si identificatori, operatorul %, expresii corespunzatoare constructorilor de tip

2.1 Prezentarea limbajului

a.       gramatica

P→ D;E

D → D ; D | id : T | є

T → char | integer | array [num] of T | ^ T

E → literal | num | id | E mod E | E[E] | E^

Programele generate sint reprezentate de neterminalul P si constau dintr-o lista de declaratii urmata de o singura expresie.

Exemplu: I: integer;

I mod 7.

Observatie: tip_eroare se considera tot tip de baza!

Pentru simplitate indicii tabloului incep implicitde la 1.

array [255] of char se va traduce array (1..255, char)

^ integer se traduce cu poniter (integer)

Pe baza gramaticii de mai sus, partea din schema de traducere care indica modul de stabilire a tipului unui identificator conform declaratiei sale este urmatoarea:

P→ D;E

D → D ; D

D → id : T

D →| є

T → char

T → integer

T → array [num] of T1

T → ^ T1

Nefiind decat atribute sintetizate, actiunile semantice sint la sfarsitul productiilor. Actiunea asociata cu D → id: T introduce un tip in tabela de simboluri in intrarea corespunzatoare identificatorului respectiv, definit prin atributul sintetizat intrare. Expresia de tip ce defineste tipul identificatorului respectiv a fost sintetizata in prealabil ca valoare a atribututlui tip corespunzator neterminalului T. Cerinta ca identificatorul sa fie declarat inainte de utilizare se rezolva automat prin faprul ca in prima productie neterminalul D apare inainte de E. Tot de aici rezulta ca se pot aplica ambele metode de analiza sintactica, cu modificari corespunzatoare in gramatica data.

2.2. Verificarea tipului expresiilor

Se considera productia ce neterminalul E in partea stanga. E va avea corespondent un atribut sintetizat tip care va furniza expresia de tip asignata de sistemul de tipuri, expresiei generate de E. Constanta desemnata prin literal are tipul char, iar cea desemnata prin atomul num este intreg.

E → literal

E → num

E → id

Se considera ca avem la dispozitie o functie extr_tip(i) care returneaza din tabela de simboluri tipul inregistrat de intrarea i.

E → E1 mod E2

E → E1[E2]

Expresia indiciala E2 trebuie sa fie de tip intreg iar E1 de tip tablou, caz in care rezultatul este de tip t, extras din tipul lui E1, s nu s-a utilizat in verificare, in concluzie verificarea incadrarii indicelui in aceasta multime nu s-a lasat pentru executie.

E → E1 ^

Pentru alte tipuri si operatii se pot adauga productii noi, de exemplu daca introducem boolean.

T → boolean

Le expresii se pot adauga productii corespunzatoare operatorilor relationali si logici.

2.3. Verificarea tipurlui instructiunilor

In general instructiunilor privite ca si constructii de limbaj nu le corespund valori care pot fi de un anumit tip; pentru a uniformiza tratarea verificarii tipurilor, unei intrsuctiuni corecte din acest punct de vedere I se va asigura tipul notat cu vid (absenta tipului). Daca in schimb, in cadrul instructiunilor se detecteaza o eroare de tip, tipul asociat va fi tot tip _eroare. In continuare se va considera instructiunea de atribuire, instructiunea if, while, precum si sirul de instructiuni separate prin ;. Pentrua include si instructiuni in limbajul luat in considerare, initial facem modificarea:

P → D ; I

I → id := E | if E then I } while E do I | I ; I

Productiile si regulile semantice asociate pentru expresii raman in continuare valabile deoarece instructiunile contin expresii. La productiile corespunzatoare instructiunilor trebuie sa li se adauge actiuni semantice specifice pentru verificarea fiecarei instructiuni in parte.

I → id := E

Regula semantica considerata este aceea ca partea stanga si partea dreapta a instructiunii are acelasi tip. Constructia de limbaj este puternic tipizata si nu contine constrangeri de tip(nu se fac conversii de tip).

I → if E then I1

I → while E do I1

I → I1 ; I2

Actiunea semantica asociata rezolva propagarea erorilor, doearece intreaga secventa va avea tipul vid doar daca fiecare instructiune in parte este corecta. Un verificator de tip realizat practic si corect trebuie sa compelteze aceste probleme de principiu astfel incat sa poata raporta atat natura cat si locul erorilor de tip.

2.4. Verificarile de tip in cadrul functiilor

Pentru a realiza verificarea de tip, declararea functiilor se ca asimila cu un tip, iar apeulu functiilor reprezinta evident o expresie, care poate fi redata prin E → E(E). S-au luat in considerare doar functii cu un singur argument. Pentru a permite si declarari de functii in partea de declaratii din gramatica, la productiile pentru neterminalul T se va adauga urmatoarea productieL

T I → T1 '→' T2

E I → E1(E2)

Actiunea semantica specifica si verificarea argumentului; generalizarea la functii cu mai multe argumente se poate face construind un tip produs intre argumentele respective care sa poata fi tratata unitar ca un singur argument:

Function f (function g (real): real; x:real): real;

(real → real) * real → real