Compiler

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een compiler (letterlijk samensteller of opbouwer) is een computerprogramma dat een in een brontaal geschreven programma vertaalt in een semantisch equivalent programma in een doeltaal. Het vertalen of omzetten wordt compilatie of compileren genoemd. Met compiler wordt voornamelijk een programma bedoeld dat een programma in een hogere programmeertaal vertaalt naar een lagere programmeertaal, meestal assembleertaal of machinecode. De voornaamste reden om broncode te compileren is dan ook het maken van uitvoerbare code.

Als het gecompileerde programma uitgevoerd kan worden op een computer met een andere CPU of een ander besturingssysteem dan de computer waarop de compiler zelf draait, spreekt men van een crosscompiler. Een programma dat een vertaling uitvoert tussen hogere programmeertalen wordt meestal niet compiler genoemd, maar vertaler. Vertaalt een programma van een lagere programmeertaal naar een hogere, dan spreekt men van een decompiler.

Formeel is compilatie het vertalen van expressies uit een formele invoertaal naar expressies uit een formele uitvoertaal (of doeltaal).

De compiler controleert ook of de invoer welgevormd is en of er een correcte vertaling gemaakt kan worden, zo niet dan worden er foutmeldingen gegeven. Tegenwoordig werkt men meestal interactief en stopt de compiler doorgaans bij de eerste foutmelding. Bij de klassieke batchverwerking (de programmeur stuurt zijn programma naar het computercentrum en ontvangt de uitvoer uren later of de volgende dag) onderzoekt de compiler het hele programma op fouten.

Structuur[bewerken]

Compilatie gebeurt in verschillende fases, waarvan sommige parallel lopen. De eerste fases zijn verantwoordelijk voor het analyseren van de broncode die gecompileerd wordt. Deze fases worden samen de frontend (voorkant) van de compiler genoemd. De latere fases zijn verantwoordelijk voor het synthetiseren van het resultaat en houden zich bezig met het genereren en optimaliseren van het resultaat van de compilatie. Deze fases vormen samen de backend (achterkant) van de compiler. De frontend levert zijn resultaten af aan de backend in de vorm van een interne representatie en een symbol table.

De frontend van een compiler is specifiek voor een bepaalde programmeertaal. Voor de compilatie van programma's in verschillende programmeertalen zijn verschillende frontends nodig. De backend is (tot op zekere hoogte) onafhankelijk van de programmeertaal, maar is specifiek voor het doel waarvoor gecompileerd wordt. Dit doel kan een bepaalde processor zijn of een virtuele machine. Voor iedere processor of virtuele machine is een andere backend nodig.

Een compiler met een back-end die het programma direct uitvoert in plaats van uitvoerbare code te genereren wordt een interpreter genoemd.

De meeste compilers kennen de volgende fases:

  • Frontend (analyse):
    1. De lexical scan of lexicale analyse (woordontleding), waarin de symbolen van de invoer van voor naar achter bekeken worden en de invoer verdeeld wordt in blokken van symbolen welke op een bepaalde manier geïnterpreteerd worden binnen de invoertaal. In het geval van een programmeertaal als invoertaal valt te denken aan het herkennen van sleutelwoorden, operatoren en variabelen uit een rij van invoertekens.
    2. De parsing of syntactische analyse (zinsontleding, dus met betrekking tot de grammatica), waarin gekeken wordt of de invoerrij wel in te passen valt in de context-vrije grammatica van de invoertaal. Hieruit blijkt (gedeeltelijk) of er wel een vertaling mogelijk is en zo ja, (gedeeltelijk) hoe deze vertaling opgesteld dient te worden. In het geval van een programmeertaal valt te denken aan een verificatie dat de syntactische regels van de taal wel geëerbiedigd worden.
    3. De attribuut-evaluatie of semantische analyse. Dit is de 'betekenis' en slaat vooral op typering, waarin gekeken wordt of de invoerrij voldoet aan de context-gevoelige regels van de invoertaal. Hier blijkt definitief uit of een vertaling wel mogelijk is en hoe deze tot stand dient te worden gebracht. In het geval van een programmeertaal valt te denken aan een controle op de eerbiediging van alle typeregels (type checking genoemd).
    4. Het generen van een interne representatie van het invoerprogramma.
  • Backend (synthese):
    1. De registerallocatie, waarbij de compiler bepaalt welke data in welke registers opgeslagen wordt.
    2. De code-generatie, waarin aan de hand van de eerder verzamelde informatie een woord uit de doeltaal wordt gegenereerd. In het geval van een programmeertaal zou bijvoorbeeld machinecode gegenereerd kunnen worden.
    3. Optimalisatie
Een schema van de verschillende fases waaruit compilatie bestaat

De lexical scan[bewerken]

1rightarrow blue.svg Zie Lexicale analyse voor het hoofdartikel over dit onderwerp.

De lexical scan vormt de initiële analyse die toegepast wordt op de invoer van de compiler. Deze invoer is een rij van karakters uit een alfabet, die wellicht een woord vormt in de zin van een formele taal.

De taak van een lexicale scanner binnen de compiler is om de invoer onder te verdelen in kleinere onderdelen genaamd tokens en deze tokens in volgorde door te geven aan de parser. Een token is dan een object dat door de parser herkend kan worden als een sleutelwoord binnen de formele taal, dan wel als een naam, en zodanig behandeld kan worden.

Parsen[bewerken]

1rightarrow blue.svg Zie Parser voor het hoofdartikel over dit onderwerp.

Tijdens het parsen (ontleden) worden de tokens die het resultaat zijn van de lexicale analyse omgezet in een boomstructuur, een syntaxisboom genoemd. Dit gebeurt volgens de regels die gedefinieerd zijn in de context-vrije grammatica van de taal.

Als de parser een serie tokens tegenkomt die aan geen van de regels van de grammatica voldoet is er sprake van een syntax error, een syntaxisfout. In dat geval geeft de compiler een foutmelding.

Het resultaat van het parsen is een concrete syntaxisboom die de structuur van de geparste broncode weergeeft.

Attribuut-evaluatie[bewerken]

De attribuut-evaluatie is een bewerking die wordt uitgevoerd op de afleidingsboom die het resultaat is van de hierboven beschreven parsing.

De parsing definieert een mogelijke afleiding van een woord uit een formele taal in de zin van de context-vrije grammatica van die taal. Een dergelijke afleiding zegt echter niets over de correctheid van de afleiding met betrekking tot de context-gevoelige eigenschappen van bepaalde talen. In het geval van een programmeertaal valt bijvoorbeeld te denken aan een regel dat een variabele gedeclareerd moet zijn voordat deze gebruikt wordt, of dat een bepaalde waarde alleen toegekend kan worden aan een variabele met het juiste type.

De attribuut-evaluator van een compiler doorloopt nogmaals de gehele afleiding (soms wel meer dan één keer) om te bepalen of een afgeleid woord wel alle contextuele regels van de formele taal eerbiedigt. Een veelgebruikte methode hiervoor is die waarbij de attribuut-evaluator deelbomen van de boom beschouwt van wortel naar bladeren en weer terug en daarbij de boom decoreert met invoerinformatie (contextuele beperkingen op deelbomen die van boven uit de boom worden opgelegd – bijvoorbeeld "variabele X heeft hier geen waarde en mag dus niet uitgelezen worden") en uitvoerinformatie (contextuele informatie die bepaalt of een deelboom wel in de bovenliggende boom past – bijvoorbeeld "het type van de uitspraak die gevormd wordt door deze deelboom is A").

Er wordt nog altijd veel werk verricht binnen de informatica aan attribuut-evaluator-generatoren. Er zijn wel verschillende systemen die uit één of andere beschrijving een attribuut-evaluator kunnen genereren, maar er is nog niet een algemene methode waarvan iedereen zegt "ja, DAT is de oplossing".

De code-generatie[bewerken]

De code-generator is de laatste stap van de compilatie. Dit onderdeel beschouwt nog een laatste maal de gedecoreerde afleidingsboom en genereert vertalingen in de doeltaal \mathcal{Q} voor iedere deelboom van de afleidingsboom. Omdat alle deelbomen samen de gehele boom vormen, genereert dit proces de gehele vertaling.

De meest gebruikte methode bij codegeneratoren is dat de code-generator naast driver-code bestaat uit een bibliotheek aan "standaardvertalingen" van stukken afleidingsboom, waarin gaten voorkomen. Deze gaten worden bij de echte code-generatie gevuld met context-gevoelige informatie (te denken valt dan aan de precieze naam van de variabele uit de invoer, dat soort dingen). Omdat code-generatie afhankelijk is van context-gevoelige informatie en er voor attribuut-evaluatie nog niet één echte oplossing is, is er ook nog niet één algemeen mechanisme voor generatie van code-generatoren.

Daarnaast kampen onderzoekers naar code-generatie ook met een ander probleem, namelijk dat er vaak veel meer dan één enkele manier is om een deelboom in een doeltaal te vertalen en niet iedere mogelijke vertaling altijd de beste is. Naar dit soort code-optimalisatie wordt ook nog veel onderzoek gedaan.

Softwareontwikkeling[bewerken]

Compilers worden veelal gebruikt binnen het programmeren. Een tekst in de vorm van broncode in een bepaalde programmeertaal wordt omgezet; meestal naar een vorm waarin het direct door een computer kan worden uitgevoerd. Soms zal het naar een vorm worden omgezet zodanig dat het door een ander programma, een zogenaamde interpreter of run-time module, uitgevoerd kan worden.

Een compiler wordt vanaf 1985 vaak gebruikt als onderdeel van een software-ontwikkelomgeving, zodat het programma direct kan worden getest. Zonder software-ontwikkelomgeving vergt het compileren een aparte handeling van de programmeur.

Een programmeur schrijft de broncode van het programma, bijvoorbeeld in Pascal of C in een teksteditor (een tekstbewerkingprogramma, meestal speciaal geschikt voor de te gebruiken programmeertaal) en slaat deze op in een bestand. Wanneer de programmeur de compiler gebruikt zal deze de broncode omzetten naar een uitvoerbaar bestand.

De resulterende objectbestanden (verwar object hier niet met objectoriëntatie) moeten doorgaans dan nog gelinkt worden (samengevoegd met bijvoorbeeld opstartcode), waarna het klaar is voor uitvoering; de zogenaamde executable is klaar. In het geval van de variant die nog een interpreter vereist, wordt de linkfase gewoonlijk overgeslagen. Het compilatieproces is hierdoor meestal wat sneller, maar de uitvoering trager. Een voordeel van interpreter-gebaseerde compilatie kan wel zijn dat de gegenereerde object code portable is naar andere systemen. De interpreter zelf is dan niet portable en handelt de platformspecifieke zaken af.

Een compiler kan er niet voor zorgen dat er geen bugs in het programma komen. Met een debugger kunnen dat soort fouten opgespoord worden, maar dan zal het compilatieproces opnieuw moeten plaatsvinden.

Voorbeelden[bewerken]

Voorbeelden van compilers zijn (in alfabetische, geen chronologische volgorde):

Zie ook[bewerken]

Externe links[bewerken]