Student: Roșu Ionuț-Cosmin
Yüklə 61,62 Kb.
|
- Bu səhifədəki naviqasiya:
- Instrumente folosite în construcţia compilatoarelor...............................................12
- Instrumente folosite în construcţia compilatoarelor
|
Sisteme de Operare Compilatoare Student: Roșu Ionuț-Cosmin Universitatea Politehnica Bucuresti Facultatea de Electronica, Telecomunicatii si Tehnologia Informatiei Cuprins
Principiile si tehnicile de scriere ale unui compilator acopera o arie atât de vasta de cunotinte incât orice informatician profesionist poate participa la constructia lui. Elaborarea unui compilator necesita elemente de limbaje de programare, arhitectura a calculatorului, teoria limbajelor formale, algoritmi, baze de date, si multe alte domenii din Computing Science, la care se adauga intr-o foarte mare masura elemente de matematica superioara. Similar limbajelor naturale, limbajele intelese de calculator isi comunica informatia prin intermediul unor mesaje structurate in cuvinte si propozitii. Aceste texte, pentru a fi intelese, trebuie sa satisfaca anumite reguli deosebit de precise. Regulile se refera atât la structura sintactica a mesajelor cat si la cea semantica. La prima vedere, un compilator este deci un program care citeste un program scris intr-un anumit limbaj (numit limbaj sursa) si il translateaza intr-un program echivalent scris in alt limbaj (obiect). In acest proces, este posibil ca programul compilator sa raporteze utilizatorului prezenta anumitor erori in programul sursa. Deci, totul se petrece conform diagramei: 
Aparent, marea varietate de compilatoare pare coplesitoare. Exista foarte multe limbaje sursa, plecând de la limbajele de programare traditionale cum ar fi Pascal sau (mai vechi) Fortran, pâna la limbajele specializate caracteristice fiecarei aplicatii posibile calculatoarelor (ca un exemplu, editorul de texte LaTex este de fapt un limbaj de programare). Limbajele object sunt de asemenea variate; un limbaj obiect poate fi un alt limbaj de programare, un limbaj de asamblare sau cod -masina caracteristic unui anumit tip de calculator (plecând de la microprocesoare pânä la supercomputere). Primele compilatoare au inceput sa apara in anii ‘50. Data initiala este greu de dat, deoarece in acea vreme multe grupuri realizau experirnente si implementari diverse care pot fi considerate sau nu modele incipiente de compilator. Baza de lucru era formata din diverse tehnici de programare mai mult sau mai puin sofisticate. In acea vreme, a scrie un compilator era considerat o sarcinä extrem de dificila. Primul compilator de Fortran de exemplu, a luat 18 ani pentru a fi implementat in intregime conform definitiei teoretice data de grupul condus de Backus. De atunci au fost elaborati algoritmi de rezolvare a principalelor probleme care apar In timpul compilärii; s-a sistematizat constructia analizorilor lexicali, sintactici, de generare a codului, etc. Au fost dezvoltate limbaje de asamblare performante, medii interactive de programare, echipamente soft, care ajuta enorm in faza scrierii programului compilator. Toate acestea conduc in prezent la posibilitatea ca un compilator simplu sa poata fi realizat de un singur student ca proiect de laborator.
In cele ce urmeaza, programul scris de utilizator intr-un limbaj de programare poarta numele de program sursa. El va constitui materialul de lucru pentru calculator, in urma caruia se obtin o serie de rezultate. Dupa introducerea in calculator, programul sursa este transformat in program obiect. Acesta se poate prezenta sub forma binara sau de program scris in limbaj de asamblare. In general, prin program object se intelege programul sursa translatat de catre calculator intr-un lirnbaj de nivel 0 au 1. Compilatorul este programul care face aceasta transformare. Deci, un compilator nu este o componenta hard, ci un program scris intr-un limbaj de nivel inferior limbajului in care este scris programul sursa. Istoric, se pare ca primul compilator (in structura sa de astazi) a fost scris in 1952 de echipa condusa de Dr. Grace Hooper pentru firma Remington Rand, anume A-O System. In timp, functiile compilatorului s-au complicat si diversificat, astfel incât astazi, rolul unui compilator nu este doar acela de a genera programul object, ci mult mai vast.
Procesul de compilare a unui program are loc in mai multe faze. O faza este o operatie unitara in cadrul careia are loc transformarea programului sursa dintr-o reprezentare in alta. Principalele faze ale unei compilari sunt cele din figura de mai jos: 
In afara de actiunile enumerate mai sus, procesul de compilare mai include urmatoarele: Gestionarea tabelei de simboluri: tabela de simboluri (TS) este o structura de date destinata pastrarii de informatii despre simbolurile (numele) care apar in programul sursa; compilatorul face referire la aceasta tabela aproape in toate fazele compilarii. Tratarea erorilor: un compilator trebuie sa fie capabil sa recunoasca anumite categorii de erori care pot sa apara in programul sursa; tratarea unei erori presupune detectarea ei, emiterea unui mesaj corespunzator si revenirea din eroare, adica, pe cat posibil, continuarea procesului de compilare pana la epuizarea textului sursa, astfel incat numarul de compilari necesare eliminarii tuturor erorilor dintr-un program sa fie cat mai mic. Practic, exista erori specifice fiecarei faze de compilare. De remarcat ca au fost mentionate doar cele mai importante functii, intâlnite la aproape toate compilatoarele. De la caz la caz, in functie de complexitate, unele module pot disparea si pot apare altele noi. De asemenea ordinea lor de parcurgere poate fi diferita. La multe compilatoare, analiza lexicala este comandata de cea sintactica. O alta posibilitate este efectuarea in acelasi timp a analizei sintactice cu cea semantica si generarea codului (compilatoarele cu o singura trecere). In cazul limbajelor de programare simple, construite doar pentru un anumit tip de calculator, limbajul intermediar nu este necesar si se trece direct la codul obiect.
In sprijinul proiectantilor de compilatoare au fost create instrumente software precum generatoarele de analizoare lexicale si sintactice, generatoarele de compilatoare sau sistemele de scriere a translatoarelor. Aceste instrumente sunt programe care produc compilatoare sau parti din compilatoare, primind la intrare o specificare a limbajului sursa precum si a calculatorului tinta. Translatorul Este de obicei un program de compilare pentru limbajele specializate (de nivel 3). Aceste limbaje sunt alcatuite din macro-instrucuni ale unui limbaj de programare algoritmic. Translatorul le traduce de fapt linie cu linie in limbajul initial; se obine astfel un program de nivel 2, prelucrat de compilator. Unul din cele mai cunoscute interpretere este cel al limbajului BASIC. In acest caz insa, el face translatarea direct in limbaj de asamblare.
3.1 Planificarea unui compilator Un compilator nou poate fi necesar la definirea unui nou limbaj sursa, a unui cod intermediar nou, sau pentru ambele scopuri. Proiectarea compilatorului se poate reduce astfel intr-o faza ulterioara doar la definirea unui set de module componente, a caror realizare si implementare vor depinde in final de elemente specifice. Marimea limbajului sursa. Marimea unui limbaj afecteaza bineinteles marimea si numarul modulelor care vor compune compilatorul. Desi nu exista o definitie precisa a marimii unui limbaj, intuitiv este clar ca un compilator pentru un limbaj evoluat cum ar fi C sau Prolog, este mai mare si mai greu de realizat decât compilatoare pentru limbaje mici, cum sunt de exemplu PL1—PL9. Un alt factor important, este posibilitatea de extensie. Majoritatea limbajelor sursa se schimba de-a lungul vietii lor; au existat numeroase variante de Pascal, au fost variante de Fortran II, Fortran IV, Fortran 77. Modificãrile sunt uneori spectaculoase. De la Pascalul initial care nu prevedea nici o instrucune goto, ulterior s-au definit diverse posibi1itati de salt neconditionat. La Fortran, intre ciclurile si instructiunile conditionale definite in 1957, si cele din 1977 exista deosebiri care conduc practic la un nou limbaj. Pe de-alta parte, un limbaj de programare nou este foarte costisitor. Multe module care ar necesita doar modificari minore trebuiesc rescrise complet. Rezultã ca o modalitate de a crea un nou limbaj este de a transforma un compilator deja construit intr-unul care sä satisfacã solicitarile unui anumit grup de utilizatori. Multe limbaje mici definite pe UNIX au evoluat ulterior transformându-se in limbaje mari.
Natura si limitele impuse de codul intermediar, ca si criteriul unui timp de compilare optim trebuiesc avute de asemenea in vedere. Daca se defineste un cod intermediar nou, trebuie verificata cu mare atentie corectitudinea sa. In general primele variante de asambloare sau de computere au multe procesoare neverificate practic, pe care este preferabil ca un compilator sa le evite. Erori de programare generate de astfel de procesoare pot conduce la erori de estimare a posibilitatilor de lucru cu un compilator. Daca un limbaj sursa este folosit, atunci este preferabil ca el sa fie implementat pentru mai multe coduri intermediare. Daca el are succes la noi grupuri de utilizatori, compilatoarele sale vor trebui sa se adapteze pentru diverse tipuri de calculatoare. Computere sunt in continua evolutie, asa ca este bine ca orice compilator sa fie capabil sa se adapteze noilor limbaje de asamblare folosite de acestea. Acest fapt ridica importanta codului intermediar. 3.3 Criterii de performanta Sub acest nume pot fi tratate mai multe aspecte ale unui compilator: viteza de compilare, calitatea codului obiect optimizat, diagnosticuri de eroare, portabilitate. Ele nu pot fi indeplinite in egala masura, iar o comparatie a avantajelor unui criteriu fata de altul este greu de realizat. De exemplu, viteza de compilare are mai mare importanta decat un cod obiect mai performant? Cum poate fi apreciat din acest punct de vedere un modul cu o analiza a erorilor foarte detaliata? O buna viteza de compilare se poate obtine prin reducerea la maxim a modulelor compilatorului si a trecerilor dintre ele. Un compilator cu doua treceri este mai rapid din acest punct de vedere. Ideal ar fi ca generarea codului obiect sa se realizeze odata cu analiza sintactica si semantica. Practic insa, acest gen de compilatoare nu este adaptabil in timp la noi versiuni de limbaj si calculator, si deci are o viata scurta. In plus ele nu permit implementarea unui limbaj sursa evoluat.
Exista mai multe modalitati prin care poate fi implementat un compilator. Cea mai simpla este aceea de a reconversiona sau reinstala un compilator deja existent. Daca nu exist un compilator suficient de apropiat conceptional de limbajul pe care ne propunem sa-l implementam, exista posibilitatea de a reorganiza un compilator deja cunoscut al unui limbaj apropiat si de a-i modifica pe rand componentele pentru a obtine noul compilator. Cazul când se pleaca la scrierea completa a unui nou compilator este destul de rar. Bootstrapping Deoarece compilatorul este un program deosebit de complex, este preferabil ca el sa fie scris intr-un limbaj mai “prietenos” decât un limbaj de asamblare. In sistemul UNIX, compilatoarele sunt realizate de obicei in C; chiar si compilatoarele de C. Aceasta utilizare a facilitatilor oferite de un limbaj pentru a se autocompila formeaza ideea de baza in ceea ce numim bootstrapping. Acesta este utilizat pe scara larga in scrierea de compilatoare si deplasarea lor de la o masina la alta, modificându-le numai a doua parte. Pentru descrierea procesului de bootstrapping, un compilator este caracterizat prin trei limbaje: limbajul sursa S pe care il compileaza, limbajul intermediar T in care genereaza codul si limbajul de implementare I in care este scris compilatorul. Cele trei limbaje sunt reprezentate prin urmatoarea diagrama (numita - din cauza formei sale - T-diagrama):
Pentru usurinta descrierii, vom nota aceasta T-diagrama cu SIT. De remarcat ca cele trei limbaje S, I i T pot fi diferite intre ele, de exemplu, un compilator poate sa fie executat pe un calculator si sa produca codul intermediar corespunzator altui calculator. Un astfel de compilator este numit compilator de tranzitie. Sa presupunem ca scriem un compilator de tranzitie pentru un limbaj nou L folosind limbajul de implementare S pentru a genera codul corespunzator masinii N; deci scriem LSN. Compilatorul corespunzator lui S functioneaza pe alta masina M si genereaza codul pentru M, el este caracterizat de T-diagrama LMM. Când LSN este executat folosind SMM, se obtine forma LMN. Acest proces poate fi ilustrat prin diagrama urmatoare:
Când mai multe T-diagrame pot fi combinate ca in figura precedenta, se subintelege ca limbajul de implementare S al compilatorului LSN trebuie sa fie acelasi cu limbajul sursa al compilatorului SMM si codul intermediar M al compilatorului realizat coincide cu limbajul de implementare al formei LMN. Diagrama din figura precedenta poate fi scrisa si sub forma unei ecuatii: LSN+SMM=LMN. O utilizare a bootstrapping-uluj consta in constructia de compilatoare pentru subseturi din ce in ce mai mari (extensii) ale unui limbaj. Fie L un limbaj de programare nou care trebuie implementat pe calculatorul M. La primul pas se poate scrie un compilator mic care translateaza o submultime S a lui L intr-un cod intermediar pentru M; deci un compilator SMM. Aceasta submultime S este folosita in continuare pentru a scrie un compilator LSM pentru limbajul L. Când LSM este executat folosind SMM, se obtine LMM, adica o implementare a lui L. Nelliac a fost unul din primele limbaje implementate in acest fel. Parintele limbajului Pascal, Wirth, si-a implementat produsul scriind un compilator in Pascal. Acest compilator a fost apoi translatat - fara nici o incercare de optimizare - intr-un limbaj de nivel inferior recunoscut de un computer. Acest compilator era scris pentru un subset al limbajului Pascal. Au urmat mai multe trepte de bootstrapping pâna la obtinerea compilatorului pentru intregul limbaj. Pentru a beneficia pe deplin de avantajele oferite de bootstrapping, un compilator trebuie scris in limbajul pe care il compileaza. Sa presupunem ca scriem un compilator LLN pentru L in L, care va genera codul calculatorului N. Extensia consta in plasarea lui pe alt calculator M unde exista un compilator LMM care genereaza codul lui M. Se obtine astfel un compilator de tranzitie LMN care lucreaza pe M dar produce codul pentru N:
Compilatorul LLN este compilat a doua oara, de aceasta data folosind compilatorul de tranzitie: 
Rezultatul este un compilator LNN care este executat pe N si genereaza codul pentru N. Aceasta constructie este aplicata on numeroase cazuri; ea poate fi ilustrata prin diagrama: 
De exemplu, compilatorul pentru limbajul Fortran H a fost scris In Fortran si bootstrapped de doua ori: odata pentru convertirea de pe IBM 7094 sistemul 360, iar a doua oara pentru a se auto-optimiza prin reducerea marimii compilatorului de la 550 K Ia circa 400 K. Revizuirea limbajului de programare Pascal a condus la scrirea in 1972 a unui nou compilator pentru calculatoarele din seria CDC 6000. Obtinerea unui compilator eficient s-a obtinut printr-un procedeu similar celui descris mai sus:
S-a notat cu O “vechiul” limbaj Pascal si cu P-limbajul revizuit. 3.5 Mediul de scriere al unui compilator Dupa cum s-a mai observat, un compilator este in esenta un program. Mediul in care este scris acest program poate deci afecta performantele sale; de asemenea, limbajul in care este scris. Multe compilatoare pentru mediul DOS au fost scrise in limbaje de tip Fortran. In cazul mediului de programare UNIX, preferintele se indreapta spre limbaje de tip C. De exemplu, in scrierea compilatorului, este naturala impartirea intregului program in module; acestea pot fi prelucrate in moduri complet diferite. Deci, un program de gestiune a prelucrarii acestor module ar fi de mare ajutor la scrierea compilatorului. Mediul de programare UNIX ofera pentru aceasta diverse facilitati (cum ar fi comanda make). De asemenea, pot fi realizate diverse module speciale care, desi nu fac parte din compilatorul propriu zis, faciliteaza procesul de compilare. De exemplu, poate exista un generator automat de analizori lexicali pentru definitii ale limbajului sub forma de expresii regulate. Sau, find data o gramatica de tip LR (sau LL) ca definie a unui limbaj, se pot construi module care genereaza automat analizorii sintactici corespunzatori. In mod similar pot exista module de generare de atributari de gramatici, de generatori de cod, etc. Este ceea ce se presupune prin a fi un compilator de compilatoare (compiler compiler). De asemenea, trebuie sã ne asiguram ca un compilator genereaza un cod obiect corect. Cum el este un program, aceasta este o problema matematica de corectitudine a programelor. Practic, aceasta cerina este asigurata prin folosirea unui pachet de programe de testate (metoda numita testul de regresie). La intervale regulate de timp precum si ori de câte ori compilatorul este modificat, programele de test sunt compilate folosind atât versiunea noua cat si versiunea pastrata ca “martor” intr-un kit de instalare. Oricee diferenta in programele realizate in cod obiect sau intermediar sunt semnalate. Mediul UNIX poate fi folosit pentru a realiza automat aceste verificari. O problema dificila este alegerea programelor care compun testele. Ideal pachetul de teste ar trebui sa contina verificari ale tuturor instruciunilor in diverse situatii, trebuie un mare grad de ingeniozitate pentru a realiza acest lucru in cat mai putine teste. Se pot da ca exemple utile pachetele de teste pentru Fortran, LaTex, C. Multe echipe adauga la testele de regresie programe care au generat blocaje in versiunile vechi ale limbajului. Testele de performanta sunt de asemenea importante. De obicei autorii au grija sa verifice daca noile versiuni ale compilatorului genereaza coduri cel putin la fel de bune ca cele anterioare, introducând verificari de timp in testele de regresie. Trebuie de asemenea urmarita mentinerea performanelor unui compilator. Aceasta cerinta apare mai ales daca el este scris de un personal fluctuant al firmei si când compilatorul este pus sa lucreze in diverse medii. Elementul esential aici este un cat mai bun stil de programare insotit de documentatie detaliata. Folosind o idee a lui Knuth din 1984 pentru Pascal toate compilatoarele actuale au module “readme” care prezinta in mod automat informatii necesare pentru intelegerea lor.
Pentru că fazele apărute în construcţia compilatoarelor sunt, în esenţă, aceleaşi, au apărut o serie de instrumente soft folosibile. Aceste instrumente sunt des referite ca: compilatoare de compilator, generatoare de compilator sau sisteme de scriere a translatoarelor. 1. Generatoare de analizor lexical (scanner generators) Aceste programe generează automat un analizor lexical, pe baza unei specificaţii alcătuite din expresii regulate şi acţiuni asociate acestor expresii regulate.
2. Generatoare de analizor sintactice (parser generators) Un astfel de generator este un program a cărui intrare este o gramatică indpendentă de context iar ieşirea este un analizor sintactic.
3. Mecanisme de traducere orientate pe sintaxă (syntax-directed translation engines) Acestea sunt rutine de parcurgere a arborelui de analiză şi a codului intern. În acest domeniu sunt programe ale proiectului COCKTAIL, cum ar fi:
Yüklə 61,62 Kb. Dostları ilə paylaş:
|
