Un compilator este un program complex care realizeaza traducerea unui program sursa intr-un program obiect. De obicei programul sursa este scris intr-un limbaj de nivel superior celui in care este scris programul obiect.

Structura generala pentru un compilator este:

 

program sursa

|

+ ----------------- +

| preprocesor | pas 1

+ ----------------- +

| pas 2

+ - - - - - - - | - - - - - - - - - - - - - - - - - - - - - - +

| | |

| | |

| + ------------------ + + -------------------- + |

| | analiza lexicala | --------- >| analiza sintactica | |

| | |< --------- | | |

| + ------------------ + + -------------------- + |

| | | | |

| + ------------------ + + -------------------- + |

| | gestiunea tabelei| | analiza semantica | |

| | de simboli |< --------- | | |

| + ------------------ + + -------------------- + |

| | | |

| | + -------------------- + |

| + ------------------- >| generarea de cod | |

| | intermediar | |

| + -------------------- + |

+ - - - - - - - - - - - - - - - - - - - - - - | - - - - - - -+

| cod intermediar

|

+ -------------------- +

pas 3 | optimizare |

| cod intermediar |

+ -------------------- +

|

| cod intermediar

+ -------------------- +

pas 4 | generarea de cod |

| obiect |

+ -------------------- +

|

| cod obiect

+ -------------------- +

pas 5 | optimizare |

| cod obiect |

+ -------------------- +

|

limbaj de asamblare

sau

cod masina

Preprocesorul realizeaza activitati de tip macro substitutie, eliminarea comentariilor, etc.

Al doilea pas reprezinta de fapt componenta principala a compilatorului (celelalte componente ar putea sa lipseasca). Efectul executiei acestui pas consta din verificarea corectitudinii formale a textului programului si traducerea acestui text intr-o forma intermediara.

Urmatorii trei pasi realizeaza prelucrari asupra programului in cod intermediar in scopul imbunatatirii performantelor acestuia (optimizarea) si generarii programului obiect.

Pasul cel mai complex dintr-un compilator ramane pasul 2 in care se realizeaza cele mai importante operatii fara de care nu poate avea loc procesul de compilare. Intr-un compilator real cele cinci componente care il formeaza: analiza lexicala, analiza sintactica, analiza semantica, gestiunea tabelei de simboli si generarea de cod nu sunt neaparat identificabile sub forma unor proceduri ori functii distincte ci

 

 

sunt realizate printr-un ansamblu de functii care coopereaza. In cele ce urmeaza aceste componente vor fi descrise separat pentru simplificarea expunerii.

1.1 Analiza lexicala

Aceasta faza a compilatorului realizeaza traducerea textului programului intr-o forma mai usor de prelucrat de catre celelalte componente. Analizorul lexical considera textul primit la intrare ca fiind format din unitati lexicale pe care le recunoaste producand atomi lexicali. Un atom lexical poate sa fie de exemplu, un cuvant cheie al limbajului (for, while, etc) dar si un numar sau un nume. Nu exista o corespondenta biunivoca intre sirurile de intrare si atomii lexicali. Adica, daca pentru atomul lexical corespunzator cuvantului cheie while exista un singur sir de intrare, pentru atomul lexical corespunzator unui numar intreg pot sa existe foarte multe siruri de intrare. Una dintre deciziile ce trebuie luate la inceputul proiectarii unui compilator consta din stabilirea atomilor lexicali. De exemplu, se pune problema daca sa existe cate un atom lexical pentru fiecare operator de comparatie (<, <=, >, >=) sau sa existe un unic atom lexical - corespunzator operatiei de comparatie. In primul caz generarea de cod poate sa fie mai simpla. Pe de alta parte existenta unui numar mare de atomi lexicali poate complica in mod exagerat analiza sintactica. In general, operatorii care au aceeasi prioritate si asociativitate pot sa fie grupati impreuna.

Rolul unui analizor lexical este de a traduce sirurile de intrare in atomi lexicali. Un atom lexical este reprezentat printr-un cod numeric care specifica clasa acestuia si o serie de atribute care sunt specifice fiecarei clase. Astfel, poate sa existe clasa operatorilor relationali pentru care un atribut trebuie sa se specifice tipul concret al operatorului. Tipul atomului lexical este necesar pentru analiza sintactica in timp ce valoarea atributului este semnificativa pentru analiza semantica si generarea de cod. Pentru un atom lexical de tip numar atributele vor descrie tipul numarului si valoarea acestuia.

Un analizor lexical apare in general ca o functie care interactioneaza cu restul compilatorului printr-o interfata simpla : ori de cate ori analizorul sintactic are nevoie de un nou atom lexical va apela analizorul lexical care ii va da atomul lexical urmator.

1.2 Analiza sintactica

Analiza sintactica descompune textul programului sursa in componentele sale "gramaticale", construind un arbore care reflecta aceasta structura. Sa consideram de exemplu expresia :

A * B + C * D

Aceasta expresie poate sa fie descrisa de urmatorul tip de arbore numit arbore sintactic:

+

/ \

/ \

/ \

* *

/ \ / \

/ \ / \

A B C D

In acest arbore au fost evidentiate relatiile (din punctul de vedere al modului de evaluare) intre componentele expresiei. Daca se doreste insa sa se evidentieze structura expresiei din punctul de vedere al unitatilor sintactice din care este formata, atunci se va utiliza pentru reprezentarea expresiei un arbore de derivare (parse tree). Pentru exemplul considerat un arbore de derivare ar putea sa fie de forma:

 

 

expresie

/ | \

expresie + expresie

/ / / \ \ \

/ / / \ \ \

/ / / \ \

expresie * expresie expresie * expresie

| | | |

nume nume nume nume

| | | |

A B C D

Orice analizor sintactic realizeaza traducerea unui sir de atomi lexicali intr-un astfel de arbore de derivare care descrie relatia ierarhica intre o descriere generala a propozitiei analizate (radacina arborelui) si sirul de atomi lexicali din care este format (frunzele). Un analizor sintactic poate sa construiasca efectiv o structura de date de tip arbore (cu pointeri si inregistrari) sau poate sa sintetizeze informatiile din care se poate face constructia acestuia.

1.3 Analiza semantica

Aceasta faza este de obicei incorporata in faza de analiza sintactica. Rolul acestei faze consta din verificarea din punct de vedere semantic a structurilor recunoscute drept corecte din punct de vedere sintactic. Majoritatea verificarilor realizate de catre aceasta faza se refera la tipurile constructiilor. De asemenea aceasta faza completeaza arborele de derivare cu o serie de informatii necesare generarii de cod.

1.4 Generarea de cod intermediar

Nici aceasta faza nu este intotdeauna separata de analiza sintactica, exista compilatoare care genereaza cod chiar in timpul analizei sintactice. Generarea de cod se face prin parcurgerea arborelui de derivare. Forma intermediara care se genereaza reprezinta codul obiect pentru o masina virtuala. Utilizarea formelor intermediare se justifica prin cateva argumente. In primul rand anumite optimizari nu se pot face in timpul analizei sintactice si sunt dificil de realizat pe un text de program intr-un limbaj de programare de nivel foarte scazut. De exemplu scoaterea expresiilor constante in afara ciclurilor. Alt motiv este utilizarea aceleasi faze de optimizare si generare de cod masina pentru diferite limbaje de programare, respectiv utilizarea aceleasi faze de analiza sintactica, semantica si generare de cod intermediar pentru a implementa acelasi compilator (limbaj) pe masini diferite. Cu alte cuvinte pentru a realiza implementari portabile pentru compilatoare. De asemenea utilizarea unei masini virtuale permite realizarea mai simpla de compilatoare incrementale sau interpretoare performante. Acest tip de translatoare executa direct (interpreteaza) codul intermediar fara a mai trece prin fazele urmatoare - editare de legaturi, incarcare, etc., dar si fara a recunoaste de fiecare data o instructiune care a fost deja tratata, cum s-ar intampla daca interpretarea s-ar face la nivel de limbaj sursa.

Dezavantajul utilizarii unei forme intermediare consta in mod evident din marirea timpului necesar pentru executia unei compilari.

1.5 Optimizarea codului intermediar

Aceasta faza identifica optimizarile posibile asupra codului in limbaj intermediar. De exemplu pentru o secventa ca:

 

for( )A

aai * ci = bai * di + e + f; ... ....

S

Se observa ca o parte din calcule se pot efectua o singura data inainte de ciclul for, rezultatele respective se pot memora in variabile temporare, etc. Desigur astfel de optimizari pot sa fie facute si de catre programator. Este de preferat insa sa se pastreze claritatea programului, iar acest tip de transformari sa fie realizate de catre compilator.

1.6 Generarea codului obiect

Aceasta faza depinde de masina pentru care compilatorul trebuie sa genereze cod si care poate sa fie diferita de masina pe care se executa compilatorul (cazul cross compilatoarelor). Aceasta faza depinde de arhitectura masinii tinta. Ideea este ca pentru fiecare instructiune in limbaj intermediar se va alege o secventa echivalenta de instructiuni obiect.

1.7 Optimizarea codului obiect

Si aceasta faza depinde de masina pentru care se genereaza cod. Si anume se identifica secvente de cod masina care pot sa fie inlocuite cu instructiuni mai rapide.

1.8 Gestiunea tabelei de simboluri

In tabela de simboluri se inregistreaza identificatorii utilizati in program si informatii asupra acestora. Aceste informatii pot sa se refere la tip, domeniu de valabilitate; daca este vorba de identificatori de tip nume de functie la aceste informatii se adauga si signatura functiei (numarul si tipul argumentelor, modul de transfer si eventual tipul rezultatului). In general o tabela de simboluri este o structura de date care contine cate o inregistrare pentru fiecare identificator avand campuri pentru atributele posibile. Introducerea simbolurilor in tabela se face de catre analizorul lexical. Atributele acestora sunt completate in tabela de catre analizoarele sintactic si semantic.

1.9 Detectarea erorilor

Fiecare faza a unui compilator poate sa identifice prezenta unei erori specifice. De exemplu, in analiza lexicala intalnirea unui sir care nu corespunde unui atom lexical; in analiza sintactica se identifica erori legate de structura instructiunilor. Ca de exemplu pentru sirul:

int real alfa;

fiecare atom lexical in parte este corect dar nu formeaza impreuna o propozitie corecta din punct de vedere sintactic. In faza de analiza semantica se verifica daca constructiile corecte din punct de vedere sintactic sunt corecte si din punct de vedere semantic. De exemplu daca la nivelul sintaxei poate sa apara ca fiind corecta o expresie de forma: nume + nume, fara nici o restrictie asupra tipului identificatorilor corespunzatori, este rolul analizei semantice sa identifice ca eronata o expresie in care primul nume este al unui vector iar al doilea nume este al unei proceduri.

Problema cea mai dificila legata de tratarea erorilor consta din modul in care se continua analiza dupa identificarea unei erori, pentru ca un compilator care se opreste la prima eroare intalnita nu este prea comod de utilizat. Exceptie face modul de abordare utilizat in primele versiuni ale compilatorului pentru TURBO Pascal pentru care la intalnirea unei erori se revine in regim de editare pentru corectarea acesteia.