Compilador

Diagrama de blocs de l'operació d'un bon compilador.

Un compilador és un programa informàtic que tradueix un programa escrit en un llenguatge de programació a un altre llenguatge de programació, generant un programa equivalent que la màquina serà capaç d'interpretar. Usualment el segon llenguatge és llenguatge de màquina, però també pot ser un codi intermedi (bytecode), o simplement text. Aquest procés de traducció es coneix com a compilació.

Un compilador és un programa que permet traduir el codi font d'un programa en llenguatge d'alt nivell, a un altre llenguatge de nivell inferior (típicament llenguatge de màquina). D'aquesta manera un programador pot dissenyar un programa en un llenguatge molt més proper a com pensa un ésser humà, per després compilar-ho a un programa més manejable per un ordinador.

Com a part important d'aquest procés de traducció, el compilador informa al seu usuari de la presència d'errors en el programa font.

Parts d'un compilador

La construcció d'un compilador involucra la divisió del procés en una sèrie de fases que variarà segons la seva complexitat. Generalment aquestes fases s'agrupen en dues tasques: l'anàlisi del programa font i la síntesi del programa objecte.

• Anàlisi : Es tracta de la comprovació de la correcció del programa font, i inclou les fases corresponents a l'Anàlisi lèxica (que consisteix en la descomposició del programa font en components lèxics), l'Anàlisi sintàctica (agrupació dels components lèxics en frases gramaticals) i l'Anàlisi semàntica (comprovació de la validesa semàntica de les sentències acceptades a la fase d'Anàlisi sintàctica).
• Síntesi: El seu objectiu és la generació de la sortida expressada en el llenguatge objecte i sol estar formada per una o diverses combinacions de fases de Generació de Codi (normalment es tracta de codi intermedi o de codi objecte) i d'optimització de codi (en què es busca obtenir un codi el més eficient possible).

Alternativament, les fases descrites per a les tasques d'anàlisi i síntesi es poden agrupar en Front-end i Back-end:

• Front-end: és la part que analitza el codi font, comprova la seva validesa, genera l'arbre de derivació i omple els valors de la taula de símbols. Aquesta part sol ser independent de la plataforma o sistema per al qual es vagi a compilar, i està composta per les fases compreses entre l'Anàlisi lèxica i la Generació de Codi Intermedi.
• Back- end: és la part que genera el codi màquina, específic d'una plataforma, a partir dels resultats de la fase d'anàlisi, realitzada pel Front End.

Aquesta divisió permet que el mateix Back End s'utilitzi per generar el codi màquina de diversos llenguatges de programació diferents i que el mateix Front End que serveix per analitzar el codi font d'un llenguatge de programació concret serveixi per generar codi màquina en diverses plataformes diferents. Sol incloure la generació i optimització del codi dependent de la màquina.

El codi que genera el Back End normalment no es pot executar directament, sinó que necessita ser enllaçat per un programa enllaçador ( linker )

Història

El 1946 es va desenvolupar la primera computadora digital. Al principi, aquestes màquines executaven instruccions consistents en codis numèrics que assenyalaven als circuits de la màquina els estats corresponents a cada operació, el que es va denominar llenguatge màquina.

Aviat els primers usuaris d'aquests ordinadors van descobrir l'avantatge d'escriure els seus programes mitjançant claus més fàcils de recordar que aquests codis, al final, totes aquestes claus juntes es traduïen manualment a llenguatge màquina. Aquestes claus constitueixen els anomenats llenguatges assembladors.

Malgrat tot, el llenguatge d'assemblador seguia sent el d'una màquina, però més fàcil de manejar. Els treballs de recerca es van orientar cap a la creació d'un llenguatge que expressés les diferents accions a realitzar d'una manera el més senzilla possible per a una persona. El primer compilador va ser escrit per Grace Hopper, el 1952 per al llenguatge de programació A-0. El 1950 John Backus va dirigir una investigació a IBM sobre un llenguatge algebraic. El 1954 es va començar a desenvolupar un llenguatge que permetia escriure fórmules matemàtiques de manera traduïble per un ordinador, va ser anomenat FORTRAN (Formulae translator). Va ser el primer llenguatge d'alt nivell i es va introduir el 1957 per a l'ús de l'ordinador IBM model 704.

Va sorgir així per primera vegada el concepte d'un traductor com un programa que traduïa un llenguatge a un altre llenguatge. En el cas particular en que el llenguatge a traduir és un llenguatge d'alt nivell i el llenguatge traduït de baix nivell, s'empra el terme compilador.

La tasca de fer un compilador no va ser fàcil. El primer compilador de FORTRAN trigar 18 anys-persona a realitzarse i era molt senzill. Aquest desenvolupament de FORTRAN estava molt influenciat per la màquina objecte on havia de ser implementat. Com a exemple d'això tenim el fet que els espais en blanc fossin ignorats, pel fet que el perifèric que s'utilitzava com a entrada de programes (una lectora de targetes perforades) no comptava correctament els espais en blanc.

El primer compilador autocontingut, és a dir, capaç de compilar el seu propi codi font va ser el creat per a Lisp per Hart i Levin al MIT el 1962. Des de 1970 s'ha convertit en una pràctica comuna escriure el compilador en el mateix llenguatge que aquest compila, encara que Pascal i C han estat alternatives molt usades.

Crear un compilador autocontingut genera un problema anomenat bootstrapping, és a dir el primer compilador creat per a un llenguatge ha de o bé ser compilat per un compilador escrit en un altre llenguatge o bé compilat en executar el compilador en un intèrpret.

Tipus de compiladors

Aquesta taxonomia dels tipus de compiladors no és excloent, pel que pot haver compiladors que s'adscriguin a diverses categories:

• Compiladors creuats: generen codi per a un sistema operatiu o arquitectura diferent del que estan funcionant.
• Compiladors optimitzadors: realitzen canvis en el codi per millorar la seva eficiència, però mantenint la funcionalitat del programa original.
• Compiladors d'una sola passada: generen el codi màquina a partir d'una única lectura del codi font.
• Compiladors de diverses passades: necessiten llegir el codi font diverses vegades abans de poder produir el codi màquina.
• Compiladors JIT (Just In Time): formen part d'un intèrpret i compilen parts del codi segons es necessiten.

Pauta de creació d'un compilador: En les primeres èpoques de la informàtica, el programari dels compiladors era considerat com un dels més complexos existents.

Els primers compiladors es van realitzar programant-los directament en llenguatge màquina o en assemblador. Un cop es disposa d'un compilador, es poden escriure noves versions del compilador (o altres compiladors diferents) en el llenguatge que compila aquest compilador.

Actualment hi ha eines que faciliten la tasca d'escriure compiladors o intèrprets informàtics. Aquestes eines permeten generar l'esquelet de l'analitzador sintàctic a partir d'una definició formal del llenguatge de partida, especificada normalment mitjançant una gramàtica formal i barata, deixant únicament al programador del compilador la tasca de programar les accions semàntiques associades.

Procés de compilació

És el procés pel qual es tradueixen les instruccions escrites en un determinat llenguatge de programació a llenguatge màquina. A més d'un traductor, es poden necessitar altres programes per crear un programa objecte executable. Un programa font es pot dividir en mòduls emmagatzemats en arxius diferents. La tasca de reunir el programa font sovint es confia a un programa diferent, anomenat preprocessador. El preprocessador també pot expandir abreviatures, crides a macros, a proposicions del llenguatge font.

Normalment la creació d'un programa executable (un típic.exe per a Microsoft Windows o DOS) comporta dos passos. El primer pas es diu compilació (pròpiament dit) i tradueix el codi font escrit en un llenguatge de programació emmagatzemat en un arxiu a codi de baix nivell (normalment en codi objecte, no directament a llenguatge màquina). El segon pas es diu enllaçat en el qual s'enllaça el codi de baix nivell generat de tots els fitxers i subprogrames que s'han enviat compilar i s'afegeix el codi de les funcions que hi ha a les biblioteques del compilador perquè l'executable pugui comunicar-se directament amb el sistema operatiu, traduint així finalment el codi objecte a codi màquina, i generant un mòdul executable.

Aquests dos passos es poden fer per separat, emmagatzemant el resultat de la fase de compilació en arxius objectes (un típic .obj per a Microsoft Windows, DOS o per a Unix), per a enllaçar-los en fases posteriors, o crear directament l'executable, amb la qual cosa la fase de compilació s'emmagatzema només temporalment. Un programa podria tenir parts escrites en diversos llenguatges (per exemple C, C + + i Asm), que es podrien compilar de forma independent i després enllaçar juntes per formar un únic mòdul executable.

Etapes del procés

El procés de traducció es compon internament de diverses etapes o fases, que realitzen diferents operacions lògiques. És útil pensar en aquestes fases com en peces separades dins del traductor, i poden escriure's en realitat com operacions codificades separadament encara que en la pràctica sovint s'integrin juntes.

Fase d'anàlisi

Anàlisi lèxica

Article principal: Analitzador lèxic

L'anàlisi lèxica constitueix la primera fase, aquí es llegeix el programa font d'esquerra a dreta i s'agrupa en components lèxics (tokens), que són seqüències de caràcters que tenen un significat. A més, tots els espais en blanc, línies en blanc, comentaris i altra informació innecessària s'elimina del programa font. També es comprova que els símbols del llenguatge (paraules clau, operadors, etc.) S'han escrit correctament.

Com que la tasca que realitza l'analitzador lèxic és un cas especial de coincidència de patrons, es necessiten els mètodes d'especificació i reconeixement de patrons, s'usen principalment els autòmats finits que acceptin expressions regulars. No obstant això, un analitzador lèxic també és la part del traductor que maneja l'entrada del codi font, i ja que aquesta entrada sovint involucra una important despesa de temps, l'analitzador lèxic ha de funcionar de manera tan eficient com sigui possible.

Anàlisi sintàctica

Article principal: Analitzador sintàctic

En aquesta fase els caràcters o components lèxics s'agrupen jeràrquicament en frases gramaticals que el compilador utilitza per sintetitzar la sortida. Es comprova si l'obtingut de la fase anterior és sintàcticament correcte (obeeix a la gramàtica del llenguatge). En general, les frases gramaticals del programa font es representen mitjançant un arbre d'anàlisi sintàctica.

L'estructura jeràrquica d'un programa normalment s'expressa utilitzant regles recursives. Per exemple, es poden donar les següents regles com a part de la definició d'expressions :

1. Qualsevol identificador és una expressió.
2. Qualsevol nombre és una expressió.
3. Si expressió₁ i expressió₂ són expressions, llavors també ho són:
   • expressió₁ + expressió₂
   • expressió ₁ * expressió₂
   • (expressió₁)

Les regles 1 i 2 són regles bàsiques (no recursives), mentre que la regla 3 defineix expressions en funció d'operadors aplicats a altres expressions.

La divisió entre l'anàlisi lèxica i l'anàlisi sintàctica és una mica arbitrària. Un factor per determinar la divisió és si una construcció del llenguatge font és inherentment recursiva o no. Les construccions lèxiques no requereixen recursió, mentre que les construccions sintàctiques solen requerir-la. No es requereix recursió per reconèixer els identificadors, que solen ser cadenes de lletres i dígits que comencen amb una lletra. Normalment, es reconeixen els identificadors pel simple examen del flux d'entrada, esperant fins a trobar un caràcter que no sigui ni lletra ni dígit, i agrupant després totes les lletres i dígits trobats fins a aquest punt en un component lèxic anomenat identificador. D'altra banda, aquesta classe d'anàlisi no és prou poderosa per analitzar expressions o proposicions. Per exemple, no podem aparellar de manera apropiada els parèntesis de les expressions, o les paraules begin i end en proposicions sense imposar alguna classe d'estructura jeràrquica o d'anidament a l'entrada.

Anàlisi semàntica

La fase d'anàlisi semàntica revisa el programa font per tractar de trobar errors semàntics i reuneix la informació sobre els tipus per a la fase posterior de generació de codi. S'hi fa servir l'estructura jeràrquica determinada per la fase d'anàlisi sintàctica per identificar els operadors i operands d'expressions i proposicions.

Un component important de l'anàlisi semàntica és la verificació de tipus. Aquí, el compilador verifica si cada operador té operands permesos per l'especificació del llenguatge font. Per exemple, les definicions de molts llenguatges de programació requereixen que el compilador indiqui un error cada vegada que s'usi un nombre real com a índex d'una matriu. No obstant això, l'especificació del llenguatge pot imposar restriccions als operands, per exemple, quan un operador aritmètic binari s'aplica a un nombre enter i a un nombre real. Revisa que les matrius tinguin definida la mida correcta.

Fase de síntesi

Consisteix a generar el codi objecte equivalent al programa font. Només es genera codi objecte quan el programa font està lliure d'errors d'anàlisi, la qual cosa no vol dir que el programa s'executi correctament, ja que un programa pot tenir errors de concepte o expressions mal calculades. En general el codi objecte és codi de màquina relocalitzable o codi assemblador. Les posicions de memòria es seleccionen per a cadascuna de les variables usades pel programa. Després, cadascuna de les instruccions intermèdies es tradueix a una seqüència d'instruccions de màquina que executa la mateixa tasca. Un aspecte decisiu és l'assignació de variables a registres.

Generació de codi intermedi

Després de les anàlisis sintàctica i semàntica, alguns compiladors generen una representació intermèdia explícita del programa font. Es pot considerar aquesta representació intermèdia com un programa per a una màquina abstracta. Aquesta representació intermèdia ha de tenir dues propietats importants; ha de ser fàcil de produir i fàcil de traduir al programa objecte.

La representació intermèdia pot tenir diverses formes. Existeix una forma intermèdia anomenada «codi de tres adreces» que és com el llenguatge d'assemblador d'una màquina en la qual cada posició de memòria pot actuar com un registre. El codi de tres adreces consisteix en una seqüència d'instruccions, cadascuna de les quals té com a màxim tres operands. Aquesta representació intermèdia té diverses propietats:

• Primera. - Cada instrucció de tres adreces té com a màxim un operador, a més de l'assignació, per tant, quan es generen aquestes instruccions, el traductor ha de decidir l'ordre en què s'han d'efectuar les operacions.
• Segona. - El traductor ha de generar un nom temporal per desar els valors calculats per cada instrucció.
• Tercera. - Algunes instruccions de «tres direccions» tenen menys de tres operands, per exemple, l'assignació.

Optimització de codi

La fase d'optimització de codi consisteix a millorar el codi intermedi, de manera que resulti un codi màquina més ràpid d'executar. Aquesta fase de l'etapa de síntesi és possible sobretot si el traductor és un compilador (difícilment un intèrpret pot optimitzar el codi objecte). Hi ha molta variació en la quantitat d'optimització de codi que executen els diferents compiladors. En els que fan molta optimització, anomenats « compiladors optimitzadors », una part significativa del temps del compilador s'ocupa en aquesta fase. Cal, però, optimitzacions senzilles que milloren sensiblement el temps d'execució del programa objecte sense retardar massa la compilació.

Estructura de dades principals

La interacció entre els algoritmes utilitzats per les fases del compilador i les estructures de dades que suporten aquestes fases és, naturalment, molt forta. L'escriptor del compilador s'esforça per implementar aquests algoritme d'una manera tan eficaç com sigui possible, sense augmentar massa la complexitat. De manera ideal, un compilador hauria de poder compilar un programa en un temps proporcional a la grandària d'aquest.

Components lèxics o tokens

Quan un analitzador lèxic reuneix els caràcters en un token, generalment representa el token de manera simbòlica, és a dir, com un valor d'un tipus de dades enumerat que representa el conjunt de tokens del llenguatge font. De vegades també és necessari mantenir la cadena de caràcters mateixa o una altra informació derivada d'ella, tal com el nom associat a un token identificador o el valor d'un token de nombre.

En la majoria dels llenguatges l'analitzador lèxic només necessita generar un token alhora. En aquest cas es pot utilitzar una variable global simple per mantenir la informació del token. En altres casos (l'exemple més notable és FORTRAN), pot ser necessària una matriu (o vector) de tokens.

Arbre sintàctic

Si l'analitzador sintàctic genera un arbre sintàctic, regularment es construeix com una estructura estàndard basada en un punter que s'assigna de manera dinàmica a mesura que s'efectua l'anàlisi sintàctica. L'arbre sencer pot llavors conservar-se com una variable simple que apunta al node arrel. Cada node en l'estructura és un registre els camps del qual representen la informació recollida tant per l'analitzador sintàctic com, posteriorment, per l'analitzador semàntic. Per exemple, el tipus de dades d'una expressió pot conservar-se com un camp en el node de l'arbre sintàctic per a l'expressió.

De vegades, per estalviar espai, aquests camps s'assignen de manera dinàmica, o s'emmagatzemen en altres estructures de dades, com ara la taula de símbols, que permeten una assignació i desassignació selectives. En realitat, cada node de l'arbre sintàctic per si mateix pot requerir atributs diferents per a ser emmagatzemat, d'acord amb la classe d'estructura del llenguatge que representi. En aquest cas, cada node a l'arbre sintàctic pot estar representat per un registre variable, amb cada classe de node contenint només la informació necessària per a aquest cas.

Taula de símbols

Aquesta estructura de dades manté la informació associada amb els identificadors: funcions, variables, constants i tipus de dades. La taula de símbols interacciona amb gairebé totes les fases del compilador: l'analitzador lèxic, l'analitzador sintàctic o l'analitzador semàntic poden introduir identificadors dins la taula, l'analitzador semàntic afegirà tipus de dades i altra informació, i les fases d'optimització i generació de codi utilitzaran la informació proporcionada per la taula de símbols per efectuar seleccions apropiades de codi objecte.

Donat que la taula de símbols tindrà sol·licituds d'accés amb tanta freqüència, les operacions d'inserció, eliminació i accés necessiten ser eficients, preferiblement operacions de temps constant. Una estructura de dades estàndard per a aquest propòsit és la taula de dispersió o de càlcul de direcció, tot i que també es poden utilitzar diverses estructures d'arbre. De vegades s'utilitzen diverses taules i es mantenen en una llista o pila.

Taula de literals

La cerca i la inserció ràpida són essencials també per a la taula de literals, que conté constants i cadenes utilitzades en el programa. Però, una taula de literals necessita impedir les eliminacions perquè les seves dades s'apliquen globalment al programa i una constant o cadena apareixerà només una vegada en aquesta taula. La taula de literals és important en la reducció de la mida d'un programa a la memòria al permetre la reutilització de constants i cadenes. També és necessària perquè el generador de codi construeixi adreces simbòliques per a les literals i per introduir definicions de dades a l'arxiu de codi objecte.

Codi intermedi

D'acord amb la classe de codi intermedi (per exemple, codi de tres adreces o codi P) i de les classes d'optimitzacions realitzades, aquest codi pot conservar-se com una matriu de cadenes de text, un arxiu de text temporal o bé una llista d'estructures lligades. En els compiladors que realitzen optimitzacions complexes s'ha de posar particular atenció a la selecció de representacions que permetin una fàcil reorganització.

Generació de codi intermedi

Després de les anàlisis sintàctica i semàntica, alguns compiladors generen una representació intermèdia explícita del programa font. Es pot considerar aquesta representació intermèdia com un programa per a una màquina abstracta. Aquesta representació intermèdia ha de tenir dues propietats importants; ha de ser fàcil de produir i fàcil de traduir al programa objecte.

La representació intermèdia pot tenir diverses formes. Hi ha una forma intermèdia anomenada «codi de tres adreces», que és com el llenguatge d'assemblador per a una màquina en la qual cada posició de memòria pot actuar com un registre. El codi de tres adreces consisteix en una seqüència d'instruccions, cadascuna de les quals té com a màxim tres operands. El programa font d'(1) pot aparèixer en codi de tres adreces com

temp1 := entareal(60)
temp2 := id3 * temp1 (2)
temp3 := ID2 + temp2
ID1 : = temp3

Aquesta representació intermèdia té diverses propietats. Primera, cada instrucció de tres adreces té com a màxim un operador, a més de l'assignació. Per tant, quan es generen aquestes instruccions el compilador ha de decidir l'ordre en què s'han d'efectuar les operacions, la multiplicació precedeix l'addició al programa font. Segona, el compilador ha de generar un nom temporal per desar els paràmetres calculats per cada instrucció. Tercera, algunes instruccions de «tres adreces» tenen menys de tres operadors, per exemple la primera i l'última instruccions.

Optimització de codi

La fase d'optimització de codi tracta de millorar el codi intermedi de manera que resulti un codi de màquina més ràpid d'executar. Algunes optimitzacions són trivials. Per exemple, un algorisme natural genera el codi intermedi (2) utilitzant una instrucció per a cada operador de la representació de l'arbre després de l'anàlisi semàntica, encara que hi ha una forma millor de fer els mateixos càlculs usant les dues instruccions

temp1 := id3 * 60.0 (3)
ID1 := ID2 + temp1

Aquest senzill algorisme no té res de dolent, ja que el problema es pot solucionar en la fase d'optimització de codi. És a dir, el compilador pot deduir que la conversió de 60 de sencer a real es pot fer d'una vegada per totes en el moment de la compilació, de manera que l'operació entreal es pot eliminar. A més, temp3 s'usa només una vegada, per transmetre el seu valor a ID1. Llavors resulta segur substituir ID1 per temp3, a partir de la qual cosa l'última proposició de (2) no es necessita i s'obté el codi de (3).   Hi ha moltes variacions en la quantitat d'optimització de codi que executen els diferents compiladors. Els que fan molta optimització s'anomenen «compiladors optimitzadors», ja que una part significativa del temps del compilador s'ocupa en aquesta fase. No obstant això, hi ha optimitzacions senzilles que milloren sensiblement el temps d'execució del programa objecte sense retardar massa la compilació.

Arxius temporals

Al principi els ordinadors no tenien la suficient memòria per guardar un programa complet durant la compilació. Aquest problema es va resoldre mitjançant l'ús d'arxius temporals per mantenir els productes dels passos intermedis durant la traducció o bé al compilar «al vol», és a dir, mantenint només la informació suficient de les parts anteriors del programa font que permeti procedir a la traducció.

Les limitacions de memòria són ara un problema molt menor, i és possible requerir que una unitat de compilació sencera es mantingui en memòria, especialment si es disposa de la compilació per separat en el llenguatge. Amb tot, els compiladors ocasionalment troben útil generar arxius intermedis durant alguna de les etapes del processament. Una cosa típica d'aquests és la necessitat d'adreces de correcció cap enrere durant la generació de codi.

Vegeu també

• Generació de codi
• FlagShip
• Llenguatge d'assemblador
• Assemblador
• Depurador
• Llenguatge de baix nivell
• LLVM Compilació a codi intermedi de nivell baix, posposant l'optimització a processos especialitzats segons l'arquitectura.

Enllaços externs

• Pàgina web del GCC - GNU Compiler Collection
• Let's Build a Compiler - Tutorial de Jack W. Crenshaw: Com es fa un compilador
• Java al màxim : Traductors i Compiladors amb Lex / Yacc,JFlex / Cup i JavaCC.

Viccionari