Konpiladore

eskuinera|thumb|400px
**Konpiladorea** programak itzultzeko programa informatiko bat da. Honekin, programazio lengoaia batean idatzita dagoena beste programazio lengoaia batera pasatzen da, ordenagailua interpretatzeko gai den beste programa bat sortuz. Aipatutako bigarren lengoaia normalean makina kodea izaten da, baino, testua ere izan daiteke. Prozesu hori **konpilazioa** bezala ezagutzen da.

Konpiladoreak programa baten iturburu-kodea itzultzea ahalbidetzen du, goiko edo beheko mailako beste lengoaia batera (makina-lengoaia, normalean). Honela, programatzaile batek gizakiek erabiltzen duten lengoaian diseina dezake berak nahi duen programa. Ondoren, beste programa batera konpilatuko da ordenagailuan erabiltzeko.

XIX. mendean, Charles Babbage matematikari britainiarrak, ordenagailu digital modernoaren printzipioak sortu zituen. Makina batzuk asmatu zituen: makina diferentziala, problema matematiko konplexuak konpontzeko. Historialari askok, Babbage eta Augusta Ada Byron (1815-1852) hartzen dituzte ordenagailu digital modernoaren asmatzaile bezala. Garai hartako teknologia ez zen gai bere kontzeptuak praktikara eramateko, baina, bere asmakizunetako batek, makina analitikoak, bazituen ordenagailu modernoaren hainbat ezaugarri.

Konpilazioa egiteko momentuan, datu egiturak konpiladorearen toki desberdinetan gorde egiten dira ondoren errazago erabiltzeko. Horrela, optimizazioa egiteko orduan zailtasun gutxiago egongo dira eta, horrela, prozesua hobetuko da.

## Konpiladore baten zatiak 
Normalean konpiladoreak bi zati dituzte:
* *Front End*: iturburu kodea analizatzen duen zatia da, bere balioa egiaztatzen du, honela deribazio arbola sortu eta sinbolo taulako balioak betetzeko. Zati hau plataforma edo konpilatu behar den sistemarekiko independentea da
* *Back End*: makina kodea sortzen duen zatia da, plataforma berezi batekoa, analisi fasean lortutako emaitzekin, Front End-en bitartez egindakoa.
Zatiketa honek berak ahalbidetzen du Back End erabiltzea makina kodea sortzeko programazio lengoaia ezberdinetatik. Gainera, Front End bera ere zenbait plataforma ezberdinetan ere makina kodea sortzeko erabiltzen da.
Back End-ek sortzen duen kodea ez da zuzenean exekutatzen, beste programa bati lotu behar baitzaio.

## Historia 
1946an sortu zen lehen ordenagailu digitala. Hasiera batean, makina hauek zenbakizko kodea exekutatzen zuten makinaren zirkuitura eragiketa bakoitzeko egoera eramanez, makina lengoaia deitzen dena.

Lehen erabiltzaileak berehala ohartu ziren ordenagailu hauen abantailaz, hau da, programak gako errazagoen bidez idatz zitezkeela. Azken batean, gako guzti horiek eskuz itzultzen ziren makina lengoaiara. Gako hauek osatzen dute mihiztadura lengoaia.

Dena dela, mihiztadura-lengoaia makina baten lengoaia izaten jarraitzen zuen, baino erabil errazagoa. Ikerketa lanak beste lengoaia batera bideratu ziren, pertsonarentzat errazago izango zen batera, alegia. Lehen konpiladorea Grace Hopper-ek idatzi zuen 1952an programazio lengoaiarako A-0. 1950an John Backus-ek IBM ikerketa bat bideratu zuen lengoaia aljebraikoari buruz. 1954an formula matematikoak idaztea posible zen lengoaia bat sortu zuten eta FORTRAN (FORmulae TRANslator) izena eman zioten. Maila altuko lehen lengoaia izan zen eta 1957an ordenagailuan erabil zitekeen IBM modelo 704 bezala.

Honela sortu zen lehen aldiz lengoaia bat beste batera itzultzen zuen programaren kontzeptua. Itzulitakoa maila altuko lengoaiatik maila baxuko lengoaiara denean konpiladorea erabiltzen da
Bere iturburu kode propioa konpilatzeko gai zen konpiladorea Hart eta Levin-ek sortutakoa da MIT-en 1962an. 1970etik aurrera normaltzat jo da konpilatzen den lengoaia berberean idaztea, ordezko bezala Pascal oso erabilia izan den arren.

## Konpiladore motak 
* **Konpiladore gurutzatuak**: funtzionamenduan dagoen sistema ezberdin batentzat sortzen dute kodea.
* **Konpiladore optimizatuak**: kodean aldaketan egiten dituzte efizientzia hobetzeko, baina beti ere funtzionamenduan dagoen jatorrizko programa errespetatuz
* **Pasada bateko konpiladoreak**: iturburu kodea behin bakarrik irakurrita sortzen dute makina lengoaia
* **Pasada bat baino gehiagoko konpiladoreak**: behin baina gehiagotan irakurtzen dute iturburu kodea makina lengoaia sortu baino lehen
* **JIT konpiladoreak**: interprete baten zati dira eta behar den neurrian konpilatzen dituzte kode zatiak

Konpiladore bat sortzerako garaian: informatikaren lehen urratsetan, konpiladorearen softwarea konplexuenetakotzat zuten
Lehen konpiladoreak makina lengoaian programatzen ziren zuzenean. Konpiladorea sortuz geroztik, konpiladorearen bertsio ezberdinak sortu daitezke konpiladore horrek konpilatzen duen lengoaia berberera.
Gaur egun, badaude tresnak konpiladoreak idazterako garaian gauzak errazten dituztenak. Tresna hauek, sintaxi-analizatzailearen eskeletoa egina dute, programatzailearen esku ekintza semantikoak soilik utziz.

= Konpilazio-prozesua =
**Konpilazioa** goi mailako programazio-lengoaia jakin bateko aginduak makina-lengoaiara itzultzen dituen prozesua da. Horretarako, programa exekutagarri bat sortu behar da, adibidez, .exe luzapeneko programa bat.

Normalean, programa exekutagarria sortzeko bi pauso jarraitu behar dira. Lehenengo pausoari *konpilazio* deritzo, eta fase honetan goi-mailako programazio-lengoaia batean idatzitako iturburu-kodea behe-mailako kodera itzultzen du (ez makina-lengoaiara). Bigarren pausoari *kateatzea* deritzo, eta fase honetan aurrekoan sortutako behe-mailako kode guztiak konpiladorearen liburutegietako funtzio guztiekin kateatzen dira, horrela, exekutagarria zuzenean sistema eragilearekin komunikatu ahal da. Pauso hau bukatzeko, kode guztia makina-kodera itzultzen da, eta modulu guztiz exekutagarria lortzen da.

Posible da programa batek programazio-lengoaia desberdinetan idatzitako zatiak izatea, adibidez: C, C++, Asm... Kasu honetan, zati horiek era independentean konpilatzen dira eta ondoren, kateatze fasean, zati guztiak kateatzen dira modulu exekutagarri bakarrean.

= Prozesuaren etapak =
Itzulpen prozesu honetan hainbat fase daude, eta bakoitzean eragiketa logiko batzuk gauzatzen dira.

## Analisi-fasea 
Konpilazio-prozesuaren lehenengo fasea analisi-fasea da. Analisi fase honek bere barruan hiru azpi-fase ditu, eta horietako bakoitzean analisi mota desberdin bat egiten da.

### Analisi lexikoa 
Lehen azpi-fasean analisi lexikoa egiten da. Bertan, iturburu-kodea irakurtzen da ezkerretik eskumara, eta irakurritakoa *token* izeneko osagai lexiko batzuetan taldekatzen da. Horretarako, konpiladoreak hiztegi moduan ezagutzen dituen karaktere-kate bakoitzarekin *token* bat osatzen du. Horrez gain, zuriuneak, lerro zuriak eta iruzkinak ezabatzen dira iturburu-kodetik. Bukatzeko, lengoaiaren sinbolo guztiak (hitz-gakoak, eragileak, etab.) era egokian idatzi direla konprobatzen da.

Adibidez, idatzitako iturburu-kodean "x = 12*(3+4)^2" espresioa agertzen bada, analisi lexikoaren prozesuan sortzen diren *token*ak hurrengoak dira: x, =, 12, *, (, 3, +, 4, ), ^ eta 2.

Analisi lexikoaren helbururik garrantzitsuena hurrengo fasearentzat irakurterraza izango den egitura bat sortzea da. Fase honetan onargarria ez den edozein hitz aurkituz gero, konpiladoreak errore mezu bat sortuko du eta ez du hurrengo faseekin jarraituko.

### Analisi sintaktikoa 
Bigarren azpi-fasean analisi sintaktikoa gauzatzen da. Fase honetan aurretik sortutako *token*ak irakurtzen dira, eta osagai lexiko hauek egitura hierarkiko bat jarraituz antolatzen dira, esaldi gramatikalak osatuz. Ondoren, talde bakoitzaren sintaktika egokia dela konprobatzen da, hau da, programazio-lengoaiaren gramatika betetzen duela. Orokorrean, programaren esaldi gramatikalak analisi sintaktikoaren zuhaitzaren bitartez adierazten dira.

Programa baten egitura hierarkikoa adierazteko, arau desberdinak definitzen dira. Adibidez, espresioen definiziorako hurrengo arauak jarrai daitezke:

# Edozein identifikatzaile espresioa da
# Edozein zenbaki espresioa da
# Espresioa1 eta Espresioa2 espresioak badira, orduan:
#* Espresioa1 + Espresioa2 ere espresioa da
#* Espresioa1 * Espresioa2 ere espresioa da
#* (Espresioa1) ere espresioa da

Analisi sintaktikoan zehar akatsen bat aurkituz gero, konpiladoreak errore mezu bat sortuko du eta ez du hurrengo faseekin jarraituko.

### Analisi semantikoa 
Analisi-etaparen azken azpi-fasean analisi semantikoa gauzatzen da. Fase honetan, iturburu-programa berrikusten da akats semantikoak detektatzeko asmoarekin. Akats semantikoaren adibide bat hurrengoa izan daiteke: deklaratutako aldagai baten mota eta ondoren aldagai horri esleitutako balioaren mota bat ez etortzea. Adibidez, *int kontagailua=a* espresioan "a" balioa karaktere bat da, eta *int* motak zenbaki oso bat espero du. Beraz, kasu honetan konpiladoreak akats semantiko bat dagoela adierazten du.

Akats semantikoak aurkitzeaz gain, konpiladoreak aldagai bakoitzaren motei buruzko informazioa biltzen du, ondorengo faseetan erabili ahal izateko. Analisi semantikoa egiterakoan, aurreko fasean gertatzen zen bezala, lortutako informazioa egitura hierarkiko baten bidez adierazten da. Egitura honi esker espresio desberdinen eragingaiak eta eragileak identifika daitezke.

Fase honetako atalik garrantzitsuenetariko bat moten egiaztapena da. Bertan, eragile bakoitzak baimendutako eragingaiak dituela egiaztatu behar da, iturburu-lengoaia bakoitzak duen espezifikazioen arabera. Adibidez, programazio-lengoaia batzuek definitzen dute matrize baten indize bezala ezin dela zenbaki erreal bat jarri, beraz, konpiladoreak semantika-akats bat adieraziko du hori gertatzen den bakoitzean. Programazio-lengoaia bakoitzak arau semantiko desberdinak izan ditzake.

## Sintesi-fasea 
Analisi-fasea bukatu denean, sintesi-fasea gauzatzen da. Bertan, iturburu-programaren baliokide izango den objektu-kode bat sortu behar da. Objektu-kodea sortzeko beharrezkoa da analisi-akatsik ez egotea, beraz, aurreko faseetako edozein puntutan akatsen bat aurkituz gero, sintesi-fasea ez da hasiko. Hala ere, analisi-akatsik ez egoteak ez du esan nahi programak ondo funtzionatuko duenik, izan ere, programak kontzeptu-erroreak edo txarto kalkulatutako espresioak izan ditzake.

Objektu-kodea normalean modulu desberdinetan banatutako eta makina-lengoaian edo mihiztadura-lengoaian idatzitako kodea izaten da. Kode horiek sortzeko, programak erabiltzen dituen aldagai bakoitzarentzat memoria-posizio bat aukeratu behar da.

### Tarteko kodearen eraketa 
Analisi sintaktikoa eta semantikoa egin ondoren, konpilatzaile batzuek tarteko kode bat eratzen dute. Kode honek ezaugarri garrantzitsu bi bete behar ditu: sortzeko erraza eta objektu-kodera itzultzeko erraza izan behar da.

Tarteko adierazpen honek forma desberdinak izan ditzake. Formarik erabilienetako bat "hiru norabideko kodea" izenekoa da, eta forma honetan memoria-posizio bakoitzak erregistro moduan egin dezake lan. Kodea agindu-sekuentzia batez osatzen da, eta bere ezaugarri orokorrak hurrengoak dira:

* Agindu bakoitzak gehienez hiru eragile ditu.
* Hiru norabideko agindu bakoitzak gehienez eragingai bakarra dauka, esleipenaz gain.
* Itzultzaileak aldi baterako izen bat sortu behar du, agindu bakoitzak kalkulatutako balioak gordetzeko.
* Hiru norabideko agindu batzuek hiru eragile baino gutxiago dituzte.

## Kodea optimizatzea 
Azken faseari kodearen optimizatzea deritzo. Fase honetan aurreko fasean sortutako tarteko kodea hobetzen da, makinak arinago exekuta dezan. Konpiladore desberdinek kodeen optimizazio-maila desberdinak gauzatzen dituzte. Optimizazio handia egiten duten konpiladoreei «konpiladore optimizatzaile» deitzen zaie, eta mota hauetako konpiladoreetan prozesu-denboraren zatirik handiena optimizazio fasean erabiltzen da. Hala ere, optimizazio sinpleagoak egiten dituzten konpilatzaileak ere badaude, objektu-programaren exekuzio-denbora nabarmenki gutxitzen dutenak baina konpilazioa asko atzeratzen ez dutenak.

## Oinarrizko datuen egitura 
Konpilatzaileak oso elkarrekintza sendoak ditu, erabilitako algoritmoen faseen eta honek jasaten dituen datuen egituren artean. Beraz, konpilatzailearen idazleak ahal duen heinean, inplementatutako algoritmoak modurik eraginkorrenean idazten ditu.

### Osagai lexiko edo tokenak 
Lexiko aztergailu batek tokenen ezaugarriak batzen dituenean, normalean tokena modu sinboliko batean irudikatzen du, hau da, iturburu lengoaian idatzitako token taldea irudikatuz zerrendatutako datuen itxuradun balio baten bezala. Batzuetan, beharrezkoa izaten da karaktere kate berdina edo katearen informazio deribatua mantentzea, besteak beste, izena, identifikazio token bati elkartua, edo zenbakizko token baten zenbakia. Lengoaia gehienetan lexiko analizatzaileak token bat sortzea bakarrik behar du. Kasu honetan, aldagai global sinple bat erabil daiteke tokenaren informazioa mantentzeko. Beste kasu batzuetan (adibiderik esanguratsuena FORTRAN da), beharrezkoa izan daiteke tokenen matrize bat erabiltzea.

### Zuhaitz sintaktikoa 
Sintaxi-analizatzaileak zuhaitz sintaktiko bat sortzen badu, normalean egitura estandar bat eratzen da. Zuhaitz osoa gorde daiteke aldagai sinple baten bezala, jatorrizko adabegirekin erlazionaturik. Egiturako adabegi bakoitza informazioa gordetzeko erregistro bat da. Informazioa, bai sintagma aztergailuarekin bai ondoren aztergailu semantikoarekin lortu egiten da. Esate baterako, adierazpen baten datuak zuhaitz sintaktikoaren adabegiaren adierazpen bezala kontserba daitezke.

Noizean behin, memorian tokia aurrezteko, eremu honek era dinamiko batean ezartzen dira edo beste datu egitura batzuetan gorde egiten dira. Hala nola, ikurren taulak, esleipena egitea eta desegitea ahalbidetzen du. Egia esan, zuhaitz sintaktikoko adabegi batek ezaugarri desberdinak behar izan dezake gorde ahal izateko; hizkuntza egituraren irudikapenaren arabera. Kasu honetan, zuhaitz sintaktikoko adabegietako bakoitza irudikaturik egon daiteke erregistro aldakor batekin.

### Ikurren taula 
Datu egitura hauek informazioa identifikadoreei erlazionatuta mantentzen dituzte: funtzioak, aldagaiak, konstanteak eta datu-motak. Ikurren taulak, konpiladorearen faseen gehiengoarekin elkar eragina du. Besteak beste, lexiko, sintagma edo semantika aztertzaileek identifikatzaileak sar dezakete taularen barnean. Semantika analizatzaileak datu-motak eta informazioa gainera dezake. Azkenik, optimizazio eta kode sorkuntza faseek ikurren taulako informazioa erabil dezakete, aukeraketa egokiak eginez objektu kodean.

Ikurren taulak sarrera eskaerak maiztasun handiz izango dituenez; txertatze, ezabatze eta sarrera eragiketak eraginkorrak izan behar dira. Ahal izanez gero, eragiketak denbora konstanteak izatea hobea izango da. Gainera, helburu horiek dituzten datu-egitura estandar bat dispertsio edo kalkulu-helbide taula da, nahiz eta zenbait zuhaitz egitura ere erabil daitekeen. Batzuetan, taula ugarietan eta zerrenda edo pila batean mantendu egiten dira.

### Literalen taula 
Literalen taulan, konstanteak eta programarentzako erabilitako kateak gorde egiten dira. Horretaz gain, bilaketa eta txertaketa azkarra izatea garrantzitsua da. Gainera, literalen taulak, ezabaketak galarazi egin behar ditu bere datuak programa guztian erabiltzen direlako. Halaber, literalen taula garrantzitsua da programak memorian izango duen tokia murriztea ahalbidetzen duelako, honi esker, konstanteak eta kateak berrerabil daitezkeelako. Bestalde, garrantzitsua da kode sorgailuak helbide sinbolikoak literalentzako sortzea datu definizioak objektu kodearen fitxategian sartzeko.

### Bitarteko kodea 
Barne kodea testu kateen konponketa behin behineko testu fitxategi edo lotutako egitura zerrenda bezala mantendu daiteke; barne kode motaren (hiru norabidedun kodea edo P kodea) eta egindako optimizazio moten arabera. Gainera, optimizazio konplexuak burutzen dituzten konpiladoreetan, arreta berezia jarri beharra dago berrantolaketa erraz bat baimentzen duten irudikapenen aukeretan.

#### Bitarteko kodeen sorkuntza 
Konpiladore batzuek bitarteko iturburu programaren irudikapen bat sortzen dute, azterketa sintaktiko eta semantikoa egin ondoren. Sortutako bitarteko iturburu programa, makina abstraktu batentzako programa bezala kontsidera daiteke. Beraz, programak bi propietate garrantzitsu izan behar ditu: produzitzeko erraza eta helburu programara itzulerraza izan behar da.

Bitarteko irudipenak forma desberdinak izan ditzake. Forma horretako bat hiru noranzko kodea da. Hori, memoriako toki bakoitza erregistro bezala jarduten duen makina baten hizkuntza mihiztatzailearen bezalakoa da. Kodea aginduen segidan oinarritzen da. Agindu bakoitzak gehienez hiru eragingai izanik. Hasierako datua beste kode batzuk erabiliz molda daiteke bukaerako datua lortzeko. Horrela, iturburu programa (1) hiru noranzkodun kode bezala aurki daiteke.
```c++
temp1 := entreal(60)
temp2 := id3 * temp1 ===> (2)
temp3 := id2 + temp2
id1 := temp3
```
Bitarteko irudikapen honek propietate ezberdinak ditu. Lehengoak, hiru noranzkoko instrukzio bakoitzak, esleipenaz gain, eragile bat du. Beraz, konpiladoreak aginduak exekutatzeko ordena aukeratu behar du. Kasu honetan, biderketak lehentasuna izango du batuketarekiko. Bigarrena konpiladoreak behin behineko izen batekin gorde beharko du instrukzio bakoitzean lortutako balio desberdinak. Azkena agindu batzuek hiru operadore baino gutxiago dituzte, adibidez lehenengo eta azken aginduek.

#### Kodearen optimizazioa 
Kodearen optimizazio faseak, bitarteko kodearen hobekuntza du helburu. Horrela, makinak bizkorrago exekutatuko duen kodea lortuz. Kasu batzuetan, optimizazio batzuk garrantzirik gabekoak izaten dira, hau da, bitarteko kodea sinplea izaten denez, optimizazioak ez du eragin esanguratsurik kodearen exekuzioan. Lehenago aipatutako adibidean, bitarteko kodea (2) algoritmo natural batek sortua da. Azterketa semantikoaren ondoren zuhaitzaren irudikapena egiteko, instrukzio bat eragile bakoitzeko erabiltzen du. Orokorrean, kalkulu berak egiteko beste modu bat dago, bi instrukzio erabiliz.
```c++
temp1 := id3 * 60.0 ===> (3)
id1 := id2 + temp1
```
Algoritmo erraz honek ez du ezer txarrik, duen arazoa kodearen optimizazio fasean konpon daitekeelako. Hots, konpiladoreak bakarrik ondoriozta dezake 60a zenbaki osotik naturalera bihurketa egitea konpilazio momentuan. Beraz, "entreal( )" agindua ken daiteke. Gainera, temp3 aldagaia, bere balorea id3 baloreari transmititzeko bakarrik erabiltzen da. Ondorioz, temp3 balorea id3 baloreagatik alda daiteke. Hortaz, (2)ren azken proposamena ez da beharrezkoa eta (3)ren kodea lortu egiten da.

Konpiladoreen artean, aldakuntza asko daude optimizatzen duten kode kantitatearen arabera. Hau da, optimizazio asko egiten dituzten konpiladoreak daude, "optimizazio konpiladore" izenekoak. Horiek, konpilatzailearen denbora gehiena fase honetan xahutzen dute. Bestalde, optimizazio sinpleak daude, non, programaren exekuzio denbora hobetu egiten duten.

### Behin behineko fitxategiak 
Hasieran konputagailuek ez zuten memoria nahikoa programa oso bat gordetzeko konpilatzen zen bitartean. Arazo hori konpontzeko, behin behineko fitxategiak sortu ziren. Horrela, behin behineko fitxategiak erabiliz bihurketa gauzatzeko bitarteko pausoetan, produktuak mantenduz. Hau da, iturri programaren bihurketan informazio baliagarria mantenduz. 

## Ikus, gainera 
* Interpretatzailea
* Araztailea
* Programazio lengoaia

## Kanpo estekak 
* ​http://libroweb.alfaomega.com.mx/book/477/free/ovas_statics/lec_adicionales/Compiladores.pdf

​