Universitatea "politehnica" din Bucuresti

Universitatea "POLITEHNICA" din Bucuresti

Facultatea de Electronica, Telecomunicatii si Tehnologia Informatiei

Compilatoare

= Sisteme de operare =

Văleanu Andrei Gabriel

Bumb Tudor

Grupa 432 A, ETTI

Cuprins:

Capitolul I – Bumb Tudor 432A

1. 
   Introducere
   
   1. 
      Ce este un compilator?
      
   2. 
      Clasificarea compilatoarelor.
      
2. 
   Etapele compilării
   
   1. 
      Analiză lexicală
      
   2. 
      Preprocesarea
      
   3. 
      Analiză sintactică
      

• 
  Analiza Sintactică Predictivă
  

4. 
   Analiză semantică
   
5. 
   Optimizare cod
   
6. 
   Generarea codului final
   
7. 
   Detectarea erorilor
   

Capitolul II - Văleanu Andrei 432A

1. 
   Principiile compilării
   
2. 
   Structura compilatorului
   
3. 
   Reprezentări intermediare
   
   1. 
      Codul Stack-Machine
      
   2. 
      Codul Three-Address
      
4. 
   Abstractizarea procedurilor
   
5. 
   Compilarea pentru Mașina Virtuală Java (JVM) - Java Virtual Machine
   

Bibliografie

Capitolul I

1.1Introducere:

• 
  Ce este un compilator?
  

În 1954, compania IBM scoate pe piață primul calculator cu producție de serie, 704. Problema, la acea vreme, era că dezvoltarea oricarui program nou trebuia să se facă în limbajul de asamblare, ridicând astfel costurile software-ului peste cel al hardware-ului.

John Backus a fost primul care a reușit să facă o conversie a codului de nivel înalt, în limbaj de asamblare, proiectul numindu-se FORTRAN I, având un impact enorm în stiința calculatoarelor. Compilatoarele moderne păstrează structura generală a acestui proiect.

Un compilator traduce un program scris într-un limbaj de nivel înalt de programare potrivit oamenilor, într-un limbaj de nivel scăzut, cod mașină.

Inițial compilatoarele erau scrise în limbaj de asamblare. Primul compilator care a fost capabil sa-și compileze propriul cod sursă scris într-un limbaj de nivel înalt a fost creat pentru LISP( o familie de limbaje de programare) de catre Hart și Levin de la MIT în 1962.

După 1970, compilatoarele au început să fie scrise chiar în limbajul pe care urmau să-l compileze.

Trecerea de la scrierea programelor în limbajul de asamblare, la scrierea lor în limbaje de nivel înalt a avut un impact imens asupra vitezei de dezvoltare a programelor.

Principalele avantaje ale folosirii unui compilator sunt:

• 
  Notațiile folosite de către limbajele de nivel înalt sunt mult mai apropiate de modul în care oamenii gândesc rezolvarea unei probleme.
  
• 
  Compilatorul poate detecta greșeli de limbaj.
  
• 
  Programele scrise într-un limbaj de nivel înalt sunt mai scurte decât cele scrise în limbaj de asamblare.
  
• 
  Folosirea unui limbaj de nivel înalt aduce avantajul că unu program poate fi compilat pentru mai multe limbaje de asamblare, putând fi portat pe mai multe sisteme.
  

Deși scrierea programelor într-un limbaj de nivel înalt aduce multe avantaje, folosirea compilatorului pentru a-l traduce în limbaj de asamblare necesită mai mult timp, ducând la o rulare mai înceată a programului. [1.3]

• 
  Clasificarea compilatoarelor
  

1. După platforma pe care va fi executat codul obiect produs de către compilator:

- Compilatoare native (Native/Hosted compilers): codul obiect va fi rulat pe acelaşi tip de calculator şi pe acelaşi tip de sistem de operare ca şi cele pe care a fost rulat compilatorul(Ex: compilatoarele din BorlandC, Microsoft Visual Studio 6).

- Cross Compiler: codul obiect generat de către compilator va fi rulat pe un alt tip de platformă. Acest tip de compilatoare se utilizează în special pentru dezvoltarea de programe pentru sistemele embedded, care nu au fost proiectate astfel încât să suporte un mediu de dezvoltare(Ex: Programele pentru microprocesoare).

Un compilator care produce cod obiect pentru o mașină virtuală poate fi executat atât pe același tip de platformă ca și cea pe care a rulat compilatorul, cât și pe un alt tip. De aceea, aceste compilatoare nu sunt clasificate ca și native sau cross.[1.6][1.7]
1.2 Etapele Compilarii

Etapele compilării exemplificate pentru o propoziție în limbaj natural: [1.1]

		Propoziţia este validă din punct de vedere lexical? (atomii lexicali care compun propoziţia aparţin vocabularului limbajului?)	Propoziţia este validă din punct de vedere lexical? (atomii lexicali care compun propoziţia aparţin vocabularului limbajului?)	Propoziţia este validă din punct de vedere semantic? (Propoziţia are înţeles?)
Creangă este un sriicotr.	NU
Creangă scriitor un este.	DA		NU
Scriitor este un Creangă	DA		DA	NU
Creangă este un scriitor	DA		DA	DA

[1.1]Etapele compilării exemplificate pentru o propoziție în limbaj de programare:

1. 
   Analiza Lexicală[1.3]
   

Scopul analizei lexicale este transformarea şirului de caractere care formează codul sursă, într-o secvenţă de grupuri sintactice numite atomi lexicali.

Un atom lexical(token) este o componentă singulară și indivizibilă a unui limbaj. Fiecare atom lexical poate fi reprezentat prin două elemente: tipul şi valoarea.

Exemplu:

- cuvinte cheie în C: while, for, if, else;

- identificatori: nume de variabile, nume de funcții, nume de constante;

- nume simbolice: #define PI 3.14;

În etapa de analiză lexicală se generează şi se completează tabela de simboli; aceasta se bazează pe următoarele structuri:

• 
  Tabela de identificatori: cuprinde numele identificatorului, tipul acestuia, şi în funcţie de tip, o serie de informaţii semantice.
  
• 
  Tabela de constante: cuprinde tipul constantei şi valoarea acesteia.
  
• 
  Tabela de cuvinte rezervate.
  

Sintaxa atomilor lexicali este definită de către o gramatică regulată. De aceea, pentru recunoașterea lor se poate utiliza un automat finit determinist construit pe baza unei expresii regulate.

Etapa se mai numește și „lexing” sau „scanning”, iar programul desemnat să o realizeze se numește „analizator lexical” sau „scanner”.

În tabela de simboli fiecare atom lexical este reprezentat printr-un cod numeric care specifică clasa acestuia și o serie de informații specifice clasei din care face parte.

Ex:

◦Pentru un atom lexical de tip număr trebuie să se memoreze atât tipul numărului, cât și valoarea acestuia.

◦Pentru un atom lexical de tip nume de variabilă trebuie să se memoreze tipul, domeniul de valabilitate (scope) și valoarea.

◦Pentru un atom lexical de tip nume de funcție trebuie să se memoreze numărul de parametrii, tipul fiecărui parametru și modul de transfer al acestora.

Analizorul lexical este de obicei implementat printr-o funcție care, ori de câte ori este apelată (de către analizorul sintactic), întoarce atomul lexical următor.

Analiza lexicală este partea critică pentru un compilator, din punct de vedere al performanţelor. Dacă analizorul lexical este implementat în forma comandată de către analizorul sintactic, atunci el va fi apelat pentru fiecare atom lexical din codul sursă. Rezultă deci că această componentă trebuie să fie foarte eficientă.

2. 
   Preprocesarea[1.3]
   

Este necesară în cazul limbajelor care utilizează macrourile (pentru înlocuirea acestora) sau care permit compilarea condiţională și pentru eliminarea comentariilor. Este realizată prin manipularea simbolilor lexicali.

Ex: macrourile din limbajul C

#define min(X, Y) ((X) < (Y) ? (X) : (Y))

x = min(a, b); ==> x = ((a) < (b) ? (a) : (b));

y = min(1, 2); ==> y = ((1) < (2) ? (1) : (2));

z = min(a + 28, *p); ==> z = ((a + 28) < (*p) ? (a + 28) : (*p));

3. 
   Analiza Sintactică[1.3]
   

Verifică dacă codul sursă este scris potrivit regulilor gramaticii care defineşte limbajul sursă. Implică analiza gramaticală a secvenţei de atomi lexicali pentru a identifica structura sintactică a programului.

În această fază se construieşte arborele de derivare: secvenţa liniară a atomilor lexicali este înlocuită cu o structură arborescentă, pe baza regulilor gramaticii formale care defineşte sintaxa limbajului.

Având în vedere cele două modalităţi de construire a unui arbore de derivare, analiza sintactică poate fi abordată în două feluri:

1. ascendent (bottom-up)

2. descendent (top-down)

• 
  Analiza Sintactică Ascendentă
  

• 
  Analiza Sintactică Descendentă
  

Analiza Sintactică Predictivă[1.5]
Analiza sintactică predictivă poate fi modelată prin intermediul unui automat finit cu stivă care lucrează asupra unui şir de intrare.

Si – şirul de intrare (conţine atomii lexicali obţinuţi în urma etapei de analiză lexicală);

isi – indice pentru Si;

St – stiva (acces LIFO);

ist – vârful stivei;

Analiza sintactică predictivă pleacă de la notiunea de derivare stânga:

S => w1 => … => wn, unde wi = xiAαI, wi+1 = xiβiαI, cu proprietatea A -> βi P, iar xi  * şi αI  (VN)*

Algoritmul analizei sintactice predictive pentru un limbaj definit printr-o gramatică generatoare este:

1. Analiza sintactică porneşte de la simbolul de start S, care este introdus în stivă.

2. Se face expandarea vârfului stivei, alegând convenabil o regulă de producţie.

3. Dacă în vârful stivei apare un terminal, acesta este comparat cu simbolul curent din şirul de intrare. Dacă cele două simboluri sunt egale, atunci vârful stivei este scos şi se avansează în şirul de intrare. Altfel, se semnalează eroare.

4. La sfârşit, dacă stiva este goală şi s-a ajuns la sfârşitul şirului de intrare, atunci acesta este corect. Altfel nu este corect.

Procedura de analiza este:

sf = false

repeta

daca (st(ist))st(ist)=si(isi))

atunci ist <- ist - 1

isi <- isi + 1

ori st(ist) VN

atunci expandez varful stivei cu o productie

având în vedere şi simbolul curent

din şirul de intrare

ori (st(ist)=ε)  (si(isi)= ε)

atunci succes

sf <- true

altfel eroare

sf <- true

pana sf

sf
Exemplu:

Fie gramatica generatoare pentru care mulţimea regulilor de producţie este:

E->TE’ E’->+TE’ E’->ε

T->FT’ T’->*FT’ T’-> ε

F->id F->(E)
Şi fie propoziţia: id+(id*id)

Funcţionarea automatului de analiză sintactică predictivă va fi:

Modelul matematic este automatul finit cu stiva

AP = unde

Q - multimea de stari,

- alfabetul automatului,

- alfabetul stivei,

z0 - simbolul initial al stivei,

q0 - stare initiala,

F - multimea de stari finale,

f - functia de tranzitie

f : Q x ( Σ U{ ε }) x --> P (Q x *)

- unde P este o multime de perechi

Starea automatului

(q, x, ), qQ, x *, *

Tranziţie

(q1, ax, z) ├ (q2, x, ) <=> (q2, ) f(q1, a, z)

Un sir w * este acceptat de către automat

• după criteriul stării vide (q0, w, z0) ├ (q, ε, ε)

• criteriul starii finale (q0, w, z0) ├ (q, ε, ), q F
Fie gramatica :

E -> E + T | T

T -> T * F | F

F -> i | (E)

Neterminale : VN = {E, T, F}

Terminale : = {+, *, (, ), i}

Automatul de analiză sintactică predictivă:

Q = {q}

= {+, *, (, ), i}

= {E, T, F, +, *, (, ), i}

z0 = E

q0 = q

F = 

AP = < {q}, {+, *, (, ), i}, {E, T, F, +, *, (, ), i} , f , q , E , >

f(q, a, a) = (q, ε) ,

f(q, ε, A) = (q, ) , oricare A-> P

f(q, ε, E) = {(q, E+T), (q, T)}

f(q, ε, T) = {(q, T*F), (q, F)}

f(q, ε, F) = {(q,i), q, (E)}

Pentru analiza propozitiei i*i+i evolutia automatului este :

(q, i*i+i , E) ├ (q, i*i+i , E+T) ├ (q, i , T)

├ (q, i*i+i , T+T) ├ (q, i , F)

├ (q, i*i+i , T*F+T) ├ (q, i , i)

├ (q, i*i+i , F*F+T) ├ (q, ε, ε)

├ (q, i*i+i , i*F+T)

├ (q, *i+i , *F+T)

├ (q, i+i , F+T)

├ (q, i+i , i+T)

├ (q, +i , +T)
Pentru a putea utiliza analiza sintactică predictivă, gramatica generatoare a limbajului ţintă trebuie să îndeplinească condiţiile:

1. Nu se foloseşte recursivitate stânga în regulile de producţie: nu există niciun neterminal A astfel încât A=+>Aα.

Îndeplinirea acestei condiţii asigură faptul că stiva nu se va

extinde la infinit, având în vedere că se foloseşte derivarea

stânga pentru înlocuirea neterminalelor.

2. Pentru orice neterminal, părţile drepte ale producţiilor

sale încep diferit: Nu există două producţii A->αβ şi A->αγ, cu αdiferit de ε.

Această condiţie asigură identificarea uşoară a regulii de

producţie care trebuie folosită pentru a expanda un neterminal din vârful stivei, pe baza simbolului curent din şirul de intrare.

Eliminarea recursivităţii stânga:

Dacă există reguli de producţie care folosesc recursivitatea stânga, de exemplu:

A->Aα, A->β

Atunci introducem un nou neterminal A’ şi înlocuim regulile în cauză cu:

A->βA’, A’->αA’, A’->ε

Ex:

E->E+T E->TE’

E->T E’->+TE’

E’->ε
Dacă nu este îndeplinită a doua condiţie, şi gramatica conţine, de exemplu, regulile:

A->αβ, A->αγ

Atunci introducem un nou neterminal A’ şi înlocuim regulile în cauză cu:

A-> αA’, A’->β, A’->γ
Ex:

C->if t then C endif C->if t then C C’

C->if t then C else C endif C’->endif

C’->else C endif

4. 
   Analiza semantică[1.3]
   

SEMÁNTIC, -Ă, semantici, -ce, s. f., adj. I. S. f. 1. Ramură a lingvisticii care se ocupă cu studierea sensurilor cuvintelor și a evoluției acestor sensuri;

Compilatorul adaugă informaţii semantice arborelui de derivare şi completează în mod corespunzător tabela de simboli.

1. Fiecare definiţie a unui identificator este înlocuită printr-un nume unic (atom lexical unic), iar informaţiile despre fiecare atom lexical unic sunt adăugate în tabela de simboli.

2. Fiecare apariţie a unui identificator este înlocuită cu numele (atomul lexical) unic care îi corespunde.

3. Se fac apoi o serie de verificări semantice (verificări privind înţelesul) – se verifică dacă numele (identificatorii) nu este utilizat într-un mod impropriu.

4. Verificarea tipului (type checking) – se verifică dacă există erori privind tipurile folosite.

Exemple:

◦Pentru operatorul modulo, ambii operanzi trebuie să fie de tip întreg: a % b

◦Pentru operatorii logici (ŞI, SAU, NOT) operanzii trebuie să fie de tip boolean: !a

5.Object binding – asocierea dintre definiţiile funcţiilor şi claselor şi declararea acestora.

6.Definite assigment – verificarea faptului că toate variabilele locale au fost iniţializate înainte de a fi utilizate.

5. 
   Optimizare Cod[1.3]
   

Înainte de a optimiza codul are loc o etapă de analiză ce constă în adunarea de informații despre program, pornind de la codul intermediar construit pe baza codului sursă.

Au loc:

◦Analiza fluxului de date cu scopul de a construi use-define chaines;

◦Analiza dependenţelor;

◦Analiza alias-urilor;

◦Analiza pointerilor;

◦Analiza escape;

◦Construirea grafului de apeluri;

◦Construirea grafului fluxului de control;

Optimizarea începe prin transpunerea codului intermediar într-o formă echivalentă care este mai rapidă sau de dimensiuni mai mici.

Cuprinde:

◦Inline expansion

◦Dead code elimination

◦Constant propagation

◦Loop transformation

◦Register allocation

◦Automatic parallelization

Optimizarea se poate face și direct asupra codului sursă înainte de compilare, sau asupra codului generat (în limbaj de asamblare sau în limbaj mașină). Efectuarea optimizării duce la încetinirea procesului de compilare, dar codul rezultat va rula mai rapid și/sau va necesita mai puțină memorie.

Optimizarea buclelor: optimizare globală, care necesită analiza și modificarea unor părți mari de cod. Pentru codul sursă:

for(int r = 0; r < 100; r++ )

{

// … alte calcule

float pi = 4 * arctan(1);

aria = pi * r * r;

}

Execuția este mai eficientă dacă instrucțiunea “float pi=4*arctan(1);” este mutată în afara buclei for. Mutarea ei se poate face mult în fața instrucțiunii for, de unde și clasificarea ca optimizare globală.

Optimizarea peephole (limbaj de asamblare sau limbaj mașină): optimizare locală, în care instrucțiunile sunt analizate în grupuri de câteva (de exemplu câte două), iar modificările se fac numai în interiorul unui grup.

6. 
   Generarea Codului Final[1.3]
   

Codul intermediar transformat este translatat în limbajul de ieşire, şi anume limbajul maşină a sistemului.

Exemplu:

◦Pentru un procesor care are un singur registru, din codul intermediar A:=B+C (scris ADD A,B,C în formatul codului cu trei adrese) se generează:

LOAD B

ADD C

STORE A

7. 
   Detectarea Erorilor[1.3]
   

În fiecare etapă a compilării pot fi identificate erori specifice.

Exemplu:

◦În analiza lexicală: un șir de caractere din codul sursă nu corespunde niciunui atom lexical.

◦În analiza sintactică: șirul de atomi lexicali identificați nu formează o propoziție corectă din punct de vedere sintactic.

◦În analiza semantică: se găsesc erori la verificarea tipurilor.
Raportările unei erori trebuie sortate în ordinea de apariție în cadrul codului sursă și afișate în mod corespunzător utilizatorului.

Erorile depistate în urma verificărilor efectuate pot duce la rejectarea programului (nu se poate genera cod obiect) sau la afişarea de mesaje de atenţionare (warnings), cu generarea de cod obiect.

Capitolul II


2.1 Principile Compilării:
Compilatoarele sunt programe de dimensiuni foarte mari, complexe si construite cu foarte mare atentie. In timp ce multe probleme din designul compilatoarelor au mai multe soluți si interpretări, exista două principii pe care trebuie sa le avem in minte intotdeauna:

• 
  Compilatorul trebuie să pastreze sensul programului ce este compilat.
  
• 
  Compilatorul trebuie sa imbunatatească programul sursă intr-un mod ce poate fi observat. [2.3]
  

2.2 Structura compilatorului:
Compilatorul trebuie să inteleagă programul sursă pe care il folosește ca intrare si îi mapează funcționalitatea pentru mașina țintă. Natura distincta a acestor două sarcini sugerează o divizare in procesul de compilare in doua etape mari : front-end si back-end

Partea de front-end este centrată pe intelegerea programului sursă si să codeze această informație pentru a putea fi folosită ulterior de back-end. Această reprezentare intermediară a informației ( IR – intermidiate representation ) devine reprezentarea definitivă a compilatorului pentru codul pe care il traduce.

La fiecare pas in procesul de compilare , compilatorul va avea o reprezentare definitivă. In practică se folosesc mai multe IR-uri pe masură ce compilarea progresează, dar la fiecare pas o reprezentare va fi cea definitvă. Putem să ne gândim la o reprezentare definitvă ca la o versiune a unui program ce este transmis intre doua faze ale compilatorului, cum este IR transmis de la front-end la back-end in figura prezentată anterior. [2.3]
Intr- un compilator cu două faze, front-end trebuie să se asigure ca programul este construit corect, și să mapeze codul in reprezentarea intermediară. Back-endul trebuie să mapeze reprezentarea intermediară in setul de instrucțiuni și resursele finite ale mașinii țintă. Deoarece back-endul procesează doar reprezentarea intermediară putem presupune ca aceasta nu conține erori de sintaxă sau semantice.
Compilatorul poate face mai multe treceri asupra reprezentarii intermediare (IR) inainte sa obținem o variantă a codului țintă ( versiunea finală ). Acest lucru duce la un cod mai eficient, pentru că intr-o fază compilatorul poate studia si inregistra detaliile semnificative iar intr-o fază ulterioară poate folosi aceste detali pentru a imbunătăti traducerea. Această abordare necesită salvarea informațiilor salvate in prima trecere in reprezentarea intermediară ( IR ), pentru ca la treceri ulterioare aceste informații sa poată fi accesate si utilizate. [2.5]__Reprezentarea_codurilor_liniare'>[2.5]__Stack-Machine_Code'>[2.5]
O structură in două faze simplifică procesul de retargetare al compilatorului. Putem foarte ușor să construim mai multe back-enduri pentru un singur front-end pentru a produce compilatoare ce acceptă acelasi limbaj de programare dar au ca țintă mai multe mașini. Similar putem construi mai multe front-enduri pentru limbaje diferite de programare dar care produc aceeasi reprezentare intermediară , fapt ce ne permite sa folosim un singur back-end.
Introducând incă un IR putem adaugă mai multe faze procesului de compilare. Putem adaugă o a-3a fază intre front-end si back-end. Aceasta etapă intermediară, sau optimizator ( optimizer ), primește ca intrare un program IR si produce un alt program IR echivalent din punct de vedere semantic ca ieșire. Folosind IR ca interfață, putem aduce această modifcare compilatorului fară a produce erori pentru front-end si back-end. Astfel obținem un compilator in trei faze:

Optimizatorul este un transformator de tip IR-IR ce incearcă să imbunătățească programul IR . De reținut este faptul că aceste transformatoare sunt, defapt, compilatoare ). Optimizatorul poate face mai multe treceri peste IR, analiza IR-ul, si rescrie IR-ul. Optimizatorul poate rescrie IR-ul intr-un mod care produce un program țintă mai rapid sau mai redus ca dimensiune, sau poate avea alte obiective , precum un program care produce mai putine erori de pagină “page faults” sau consuma mai putină energie. [2.5]

2.3Reprezentări intermediare (IR – Intermediate Representation):
Structura de date centrală dintr-un compilator este reprezentarea intermediară (IR) a codului ce este compilat. Majoritatea trecerilor executate de un compilator citesc si manipulează reprezentarea intermediară a codului. Astfel este crucial să stim ce să reprezentăm si cum sa reprezentăm pentru a fi eficienti din punct de vedere al costului si eficiența compilări.

Reprezentările intermediare sunt clasificate in :

• 
  Reprezentări intermediare GRAFICE – reprezintă informațiile pe care compilatorul le are intr-un graf. Algoritmi sunt exprimati din perspectiva unor obiecte grafice : noduri , legaturi, liste, arbori.
  
• 
  Reprezentări intermediare LINIARE – se aseamană cu pseudo-codul pentru o mașină abstractă. Algoritmii iterează asupra unor secvente simple, liniare de operatii.
  
• 
  Reprezentări intermediare HIBRIDE – combină elemente din reprezentările intermediare grafice si cele liniare, in incercarea de a obține aspectele pozitive ale ambelor reprezentări. O reprezentare hibridă comună folosește un IR liniar de nivel scăzut pentru a reprezenta blocuri de cod si grafuri pentru a reprezenta fluxul de control al acestor blocuri. [2.6]
  

Reprezentări intermediare liniare:

Reprezentările liniare folosite in compilatoare se aseamănă cu codul de asamblare pentru o mașină abstractă.

Logica pentru folosirea unei forme liniare este urmatoarea:

-Codul sursă ce servește ca intrare a compilatorului este de formă liniară, la fel cum este si codul mașină generat de compilator. Daca un IR liniar este folosit ca reprezentare definitivă intr-un compilator , trebuie sa includă un mecanism de codare al transferului de control intre puncte din program. Fluxul de excuție intr-un IR liniar este de cele mai multe ori identic cu cel de pe mașina țintă, astfel, codul liniar include de obicei ramuri condiționale si salturi in execuție. Fluxul de control marchează blocurile elementare dintr-un IR liniar ; blocurile se termină la ramuri, la salturi, sau chiar inainte de operații marcate. [2.5]

Stack-Machine Code:
Codul Stack-Machine , sau stivă-mașină, este o formă a codului “one-address” sau cu adresare simplă, si se presupune existența unei stive de operanzi. Majoritatea operațiilor își iau operanzii din stiva si pun rezultatul inapoi in stivă. De exemplu : o diferență de intregi ar scoate din stivă primele două elemente si ar pune in stivă diferența lor. Utilizarea stivei crează o nevoie pentru noi operați. Reprezentările intermediare ce folosesc stiva includ de obicei o operatie de interschimbare – swap- a primelor doua elemente din stivă.

Exemplu de cod Stack-Machine pentru expresia a-2 * b :

1. 
   Push 2
   
2. 
   Push b
   
3. 
   Multiply
   
4. 
   Push a
   
5. 
   Substract
   

Codul Stack-Machine este compact. Stiva crează un spațiu de nume implicit si elimină multe nume din IR. Acest lucru reduce din dimensiunea programului in formă IR. Folosirea stivei prezintă insă dezavantujul că toate rezultatele si argumentele sunt tranzitori, daca nu se asigură mutarea lor explicită in memorie.

Codul Stack-Machine este simplu de generat si executat. Java folosește bytecode-ul , un IR compact similar in concept cu codul Stack-Machine . Bytecode-ul este rulat fie intr-un interpretor sau este tradus in cod mașină specific fiecarei platforme chiar inainte de executie. Astfel se crează un sistem cu o forma compactă a programului pentru distribuire si portare catre noi mașini. [2.5]
Three-Address Code:

In codul three-address ( codare cu 3 adrese ) majoritatea operațiilor au forma i <- j op k , cu un operator ( op ), doi operanzi ( j si k ) si un rezultat ( I ). O parte din operatori cum ar fi load si jump , au nevoie de mai puține argumente.

Exemplu de cod Three-Address pentru expresia a – 2 * b:

1. 
   T1← 2
   
2. 
   T2← b
   
3. 
   T3← T1*T2
   
4. 
   T4← a
   
5. 
   T5← T4-T3
   

Codul Three-Address este atractiv din mai multe motive. In primul rând este compact. Majoritatea operațiilor sunt constituie din 4 obiecte: o operație si 3 nume. Atât operația cat si numele fac parte din seturi limitate. Operațiile necesită de obicei 1-2 bytes. Numele sunt reprezentate de intregi sau indici dintr-un tabel, si de obicei 4 bytes sunt suficienți. [2.5]

Reprezentarea codurilor liniare :
Multe tipuri de structure de date au fost folosite pentru a implementa IR-uri liniare. Alegerile facute de persoana care scrie compilatorul influențează costul operațiilor efectuate asupra codului IR. De vreme ce compilatorul petrece foarte mult timp manipulând forma IR a codului , aceste costuri necesită atenție.

Vom folosi ca exemplu codul Three-Address dar aceleași concluzi pot fi aplicate si pentru altfel de coduri liniare , de exemplu codul Stack-Machine.

De cele mai multe ori codurile Three-Address sunt implementate ca un set de cvadruple. Fiecare cvadruplu este reprezentat cu patru câmpuri : un operator, doi operanzi ( sau surse ), si o destinație. Pentru a forma blocuri, compilatorul are nevoie de un mechanism pentru a conecta cvadruple individuale. [2.3]

In Figura de mai sus sunt prezentate 3 moduri de a reprezenta un bloc elementar.

• 
  Vector simplu – este plasat in interiorul unui nod dintr-un graf de control al fluxului de executie.
  
• 
  Vectori de pointeri – folosiți pentru a grupa cvadruple intr-un bloc. Vectorul de pointeri poate fi in interiorul unui nod dintr-un graf de control al fluxului de executie.
  
• 
  Lista Inlanțuită – alcătuiește o listă din cvadruple. Necesită mai putina memorie in nodul dintr-un graf de control al fluxului de executie.
  

Considerând costurile rearanjări codului din acest bloc, prima operație incarcă o constantă intr-un registru ( pe cele mai multe mașini această operație se traduce direct intr- o operație de incarcare imediată ) . A doua si a patra operație (T2← b și T4← a) incarcă valori din memorie, operație ce, pe majoritatea mașinilor se executa dupa un delay de mai multe cicluri de execuție , in cazul in care nu sunt incărcate in memoria cache primară. Pentru a ascunde o parte din intarziere, organizatorul de instrucțiuni ar putea muta operațiile de incarcare a lui b si a inainte incărcării immediate a lui 2. [2.3]

In implementarea ce folosește un vector simplu, mutarea operației de incarcare a lui b inaintea operației de incărcare imediată implică: salvarea celor 4 câmpuri ale primei operați, copierea campurilor corespunzatoare din al-2lea slot de câmpuri in primul slot, si apoi suprascrierea câmpurilor din slotul 2 cu valorile salvate ale operației de incărcare imediată.

In implementarea cu ajutorul vectorului de pointeri se execută aceleasi 3 operații ( salvare, mutare , si suprascriere ) dar doar pentru valoarea pointerilor, astfel compilatorul salveaza pointerul catre operația de incărcare imediată, copiază pointerul catre operația de incărcare a variabile b in primul slot al vectorului de pointeri, si apoi suprascrie slotul al-2lea al vectorului cu valoarea salvată la primul pas. [2.4]

Considerând ce se intâmplă in etapa de front-end când este generată prima formă a codului IR, atunci cand este folosit un vector simplu sau un vector de pointeri, compilatorul trebuie sa aleagă p dimensiune pentru vector-numărul efectiv de cvadrupli ce vor popula blocul elementar. Pe măsură ce cvadrupli sunt generați si introduși in vector, dacă vectorul este prea mare se irosește memorie, dacă vectorul este prea mic , compilatorul trebuie să realoce alt spațiu pentru vector pentru a obține un vector cu dimensiune mai mare, sa copieze continutul din vector mai mic in vectorul nou, si să dezaloce spațiul folosit de vectorul prea mic. Aceste probleme se pot evita folosind liste inlăntuite, mărirea dimensiuni unei liste făcându-se in mode dinamic, alocând spațiu pentru un nou cvadruplu si apoi setând pointerul corespunzător din listă. [2.5]

2.4 Abstractizarea Procedurilor:
Procedurile joacă un rol vital in dezvoltarea de sisteme software. Ele asigură o abstractizare a fluxului de control al execuției si a numelor. Tot ele asigură si încapsularea informației. Limbajele obiect-orientate se bazează pe proceduri pentru a implementa metode.

Procedura este una dintre abstractizările centrale pe care se bazează majoritatea limbajelor de programare moderne. Procedurile crează un mediu de execuție controlat, fiecare procedură având spațiul ei privat. Procedurile ajută la crearea de interfețe intre componentele sistemului; interactiunile intre component sunt realizate deseori prin apeluri de procedure. [2.4]

Procedurile sunt unitatea elementară de lucru a majorității compilatoarelor. Un compilator tipic procesează o colecție de proceduri si produce cod pentru ele ce se va lega si se va executa corect cu alte colecții de proceduri compilate.

Această carcateristică ulterioară, numită si compilare separată, ne permite sa construim sistem software de dimensiuni foarte mari. Dacă compilatorul ar avea nevoie de intregul text al unui program pentru fiecare compilare, software-rile de dimensiuni mari ar fi imposibil de realizat. Ne putem imagina o recompilare a unei aplicații ce contine mai multe milioane de lini de cod pentru fiecare schimbare făcută in cadrul procesului de dezvoltare.

In continuare este prezentată procedura ca o abstractizare si mecanismele pe care compilatorul le folosește pentru a stabili abstractizarea controlului , a spațiului de nume, si a interfațării cu lumea exeterioară. [2.4]
În limbaje algoritmice, procedurile au o disciplină de apelare/returnare simplă. Un apel de procedură transferă controlul de la locația din care se face apelul la inceputul locației apelate; La ieșire/returnare, controlul se intoarce in punctul imediat urmator celui din care s-a facut apelul inițial.

Atunci când compilatorul generează cod pentru apeluri si returnări, acel cod trebuie sa păstreze suficiente informații pentru ca apelurile/returnarile sa functioneze corect. De exemplu la apelul unei funcți din funcția main a unui program, compilatorul trebuie sa salveze adresa de unde s-a făcut apelul din functia main pentru ca funcția apelată sa poată returna controlul către main. Funcția apelată poate diverge ( Computația nu s-a terminat in mod normal ), sau nu returnează, din cauza unei erori la runtime, a unei bucle infinite, sau a unui apel la o altă procedură care nu returnează. Cu toate acestea mecanismul de apelare trebuie sa păstreze suficiente informații astfel incât sa se permită reluarea execuției in funcția principală. [2.3]

2.5Compilarea pentru Mașina Virtuală Java (JVM) -

Java Virtual Machine
Mașina Virtuală Java este construită special pentru a suporta limbajul de programare Java. Kit-ul de dezvoltare oferit de Oracle ( JDK – Java Development Kit ) conține un compilator ( javac ) scris in limbajul Java, conceput special pentru setul de instrucțiuni al Mașinii Virtuale Java, si un sistem de tip runtime ce implementeaza chiar Mașina Virtuală Java.

Termenul de compilator este folosit uneori si pentru a face referire la un translator din setul de instrucțiuni ale Mașinii Virtuale Java la setul de instrucțiuni al unui CPU ( Central Processing Unit ). Un exemplu de astfel de translator este un generator de cod just-in-time ( JIT ), ce genereaza instrucțiuni specifice fiecarei platforme doar dupa ce codul Mașini Virtuale Java a fost incărcat.

In continuare sunt prezentate doar problemele asociate cu compilarea codului sursă scris in limbajul Java in instrucțiuni pentru Mașina Virtuală Java.
Codul Mașini Virtuale Java este scris informal in limbajul de asamblare al mașinii virtuale – “virtual machine assembly language” – obținut cu ajutorul utilitarului “javap” distribuit in kit-ul de dezvoltare JDK. [2.1]

• 
  Constante , Variabile locale și Structuri de control:
  

Metoda exec() cicleaza intr-o buclă for de 100 de ori :

Rezultatul compilării poate fi :

Mașina Virtuală Java este orientată pe stivă, majoritatea operațiilor folosind unul sau mai mulți operanzi din stiva operanzilor ai cadrului curent din Mașina Virtuala Java ( JVM ) sau punând inapoi in stiva rezultatele ( prin operația PUSH ) .

Un cadru nou este creat de fiecare data cand o metodă este invocată, si odată cu acest cadru este creată si o nouă stivă pentru operanzi si un set de variabile locale pentru a fi folosite de metodă. La orice moment din executie este foarte probabil sa existe mai multe cadre si la fel de multe stive pentru operanzi pe fiecare fir de control ( În cod este echivalent cu apelurile imbricate ale metodelor ). Doar stiva operanzilor din cadrul curent este activă. [2.2]
Setul de instrucțiuni din Masina Virtuală Java face diferența intre tipuri de operanzi folosind bytecode-uri diferite pentru operații ce folosesc anumite tipuri de operanzi. Metoda exec() operează doar pe valori de tip int. Instrucțiunile din codul compilat sunt alese special pentru operațile cu intregi. (iconst_0, istore_1, iinc , iload_1, if_icmplt ) sunt specializate pentru tipul de date int. [2.2]

Cele două constante din funcția exec(), 0 și 100, sunt puse in stiva operanzilor folosind două instrucțiuni diferite. Constanta 0 este pusă in stivă folosing instrucțiunea iconst_0. Constanta 100 este pusa in stivă folosind instrucțiunea bipush, folosind valoarea ca un operand imediat. [2.2]

Intregul i este stocat ca variabila locală 1 din Mașina Virtuală. Pentru că majoritatea instrucțiunilor Mașinilor Virtuale Java operează pe valori din stiva de operanzi , și nu direct pe variabile locale, instrucțiunile care transferă valori intre variabile si stiva de operanzi sunt comune in codul compilat pentru Mașina Virtuală Java. Aceste instrucțiuni au si suport special in setul de instrucțiuni. In funcția exec() valorile sunt transferate către variabile sau din variabile folosind istore_1 si iload_1 , aceste instrucțiuni operând implicit pe variabila locală 1. [2.2]

Folosirea si refolosirea variabilelor locale este responsabilitatea persoanei care creează compilatorul. Funcțiile specializate pentru incarcare si salvare fac codul mai rapid, mai compact, si mai redus ca dimensiune in cadrul curent de execuție.

Dacă functia exec() ar folosi un alt tip de date decât int pentru contorul din bucla for, codul compilat se va schimba pentru a reflecta tipul de date folosit. De exemplu pentru tipul double :
Codul compilat :
Instrucțiunile care sunt specializate pe tipuri de date sunt pentru tipul de date double. Știm ca tipul de dată double ocupă doua variabile locale, deși este accesat doar prin cea cu indexul mai mic. Acest lucru este valabil si pentru tipul de date long. [2.2]

double doubleLocals(double d1, double d2) {

return d1 + d2;

}

Bibliografie

[1.1] http://academic.udayton.edu/saverioperugini/courses/cps343/lecture_notes/grammars.html

[1.2]

http://homedir.jct.ac.il/~rafi/formcomp.pdf

[1.3]

http://www.diku.dk/~torbenm/Basics/basics_lulu2.pdf

[1.4]

http://www.georgehernandez.com/h/aablog/2005/04.asp

[1.5]

http://homedir.jct.ac.il/~rafi/formcomp.pdf

[1.6]

http://en.wikipedia.org/wiki/Lisp_(programming_language)

[1.7]

https://en.wikipedia.org/wiki/Compiler
Capitolul 2:

[2.1] - https://docs.oracle.com/javase/specs/index.html - Java Language and Virtual Machine Specs

[2.2] - https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-3.html - Java Language Compiling for the Java Machine

[2.3] - Engineering a compiler – 2^nd Edition – Keith D. Cooper & Linda Torczon

[2.4] - Modern Compiler implementation in JAVA – 2^nd Edition – Andrew W. Appel – Editura Cambridge

[2.5] - Compilers: Principles, Techniques, and Tools (2nd Edition) - Alfred V. Aho

[2.6] - Writing Compilers and Interpreters: A Software Engineering Approach - Ronald Mak