Skip to content

Compilatoare 101

8 March 2008

Dacă tot m-am apucat să scriu despre compilatoare, voi scrie câte ceva şi despre lucrurile de bază. Începând cu începutul, compilatorul este un program care “traduce” un limbaj într-un alt limbaj. Asta presupune, în primul rând, analiza unui text (set de comenzi, instrucţiuni etc.) scrise în limbajului sursă şi, în al doilea rând, emiterea textului echivalent în limbajul destinaţie.

De fapt, privit la un nivel înalt, compilatorul este format din două părţi: front-end şi back-end. Front-end-ul se ocupă cu procesarea input-ului, back-end-ul cu emiterea output-ului. Există şi o reprezentare intermediară, independentă de limbajele de intrare şi ieşire, care păstrează doar semantica (înţelesul) input-ului şi din care se generează output-ul.

Concret, front-end-ul analizează input-ul din punct de vedere lexical, sintactic şi semantic. Analiza lexicală presupune descompunerea textului sursă în unităţi atomice numite tokens. Pentru snippet-ul de cod

public class Program { }

token-ii sunt “public”, “class”, “Program”, “{” şi “}”. Totuşi, analiza lexicală nu înseamnă doar “spargerea” textului după spaţii. De exemplu în textul

Console.WriteLine("Hello World!");

“Hello World!” este un singur token. Treburile se complică dacă luăm un string care conţine în caracterul “, cum ar fi "Let's start with \"Hello World!\"", care este, de fapt, tot un singur token. În plus, tot analizatorul lexical “aruncă” comentariile din cod, care nu necesită o procesare ulterioară. Token-ii aceptaţi sunt definiţi riguros, (de obicei cu ajutorul expressilor regulate). Dacă întâlnim un caracter ilegal în codul sursă, de exemplu §, analizatorul lexical semnalizează o eroare. Analizatorul lexical se mai numeşte şi lexer. De fapt, ne putem gândi la procesul efectuat ca la identificarea tuturor cuvintelor dintr-o propoziţie şi verificarea că aceste cuvinte sunt corecte.

Problema este că, din punct de vedere al lexer-ului, următorul snippet este perfect corect:

class } Program public {

Acesta poate fi spart în tokens, chiar dacă nu exprimă o construcţie validă a limbajului. Cuvintele există, chiar dacă formează o propoziţie fără subiect şi fără predicat. Aici vine rândul analizatorului sintactic, care se mai numeşte şi parser. Limbajele de intrare au întotdeauna o gramatică, adică diferite construcţii specifice care sunt acceptate, restul fiind identificate ca greşite. Parserul ştie că “public” este un modificator de vizibilitate care poate să apară doar înaintea anumitor construcţii (declaraţii de clase, de metode etc.) şi nu oriunde (de exemplu în corpul unei metode). Despre cum funcţionează exact un parser nu voi vorbi aici deoarece sunt foarte multe de spus, destul de reţinut că, după analiza sintactică, ajungem la reprezentarea intermediară. Construcţia

public class Program { }

va fi reprezentată intern ca “Declaraţie de clasă, cu numele Program, vizibilitate publică şi fără conţinut“, deci se păstrează sensul, dar token-ii nu mai sunt relevanţi. “{” de exemplu ajută parserul să înţeleagă unde începe conţinutul clasei dar nu are nici un înţeles semantic. Ultima analiză efectuată este cea semantică. De exemplu construcţia

public class A : A { }

este formulată corect din punct de vedere sintactic, doar că nu are sens din punct de vedere logic. O analogie ar fi o propoziţie formulată corect, cu subiect şi predicat, dar care nu are sens. Analiza semantică asigură că input-ul este bun şi din acest punct de vedere, deci se poate traduce în limbajul de output. Aici intră o mulţime de verificări, de exemplu dacă se execută operaţii doar între tipuri compatibile de date, dacă funcţiile întorc întotdeauna un rezultat, dacă nu se folosesc variabile înainte de a fi iniţializate etc. După analiza semantică avem o reprezentare internă a input-ului validat şi aici se încheie treaba front-end-ului.

Back-end-ul preia forma internă şi o transformă în limbajul destinaţie. Mai mult, optimizează codul rezultat. Optimizările sunt de două feluri – independente de limbaj şi dependente de limbaj. Un exemplu de optimizare ar fi constant folding. De exemplu expresia

a = 2 * 3.14 * r

care presupune două operaţii de înmulţire poate fi transformată în

a = 6.28 * r

care presupune o singură operaţie de înmulţire. Compilatorul determină care expresii pot fi calculate static (adică nu depind de variabile a căror valoare este necunoscută în momentul respectiv) şi le înlocuieşte cu rezultatul expresiei. Un alt exemplu ar fi înlocuirea subexpressilor comune. De exemplu

c = a + b * x
d = a + b * y

se poate înlocui cu

t = a + b
c = t * x
d = t * y

reducând din nou numărul de operaţii necesare. Problema optimizării este NP-Completă, adică nu se poate dezvolta un algoritm (deocamdată :P) care să garanteze că pentru orice input, output-ul rezultat este optim. După efectuarea acestor optimizări, se emite codul şi se aplică optimizările dependente de limbaj. Un exemplu, în CIL, ar fi instrucţiunea

ldc_i4 0

ldc_i4 pune pe stivă întregul (pe 32 de biţi) specificat. Instrucţiunea în sine are 8 biţi plus întregul specificat 32 de biţi (chiar dacă este 0), deci 40 de biţi. Aceasta poate fi înlocuită cu

ldc_i4_0

instrucţiune care pune întregul 0 pe stivă, aceasta din urmă ocupând doar 8 biţi. Într-adevăr, pe platforma .NET nu sunt necesare multe optimizări dependente de cod deoarece runtime-ul are grijă de asta în momentul rulării.

Aceştia sunt paşii făcuţi de un compilator pentru generarea codului şi, de fiecare dată când apelaţi “build” sau “run”, codul sursă trece prin toate aceste transformări până se transformă în executabil.

One Comment
  1. George Florentin permalink

    Tot ce ai mentionat tu aici invat eu acum la master. Problema e ca 98% din termeni sunt tradusi in spaniola. Doamne ajuta!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: