Compiler

Vanaf de jaren veertig startten onafhankelijk een paar partijen met het bouwen van computers. Deze computers hadden echter functionele nadelen, zo had de ENIAC als enig doel om snelle berekeningen te maken van trajecten van granaten en raketten. Hardware en software waren eerst onlosmakelijk met elkaar verbonden waardoor telkens een nieuwe computer diende gebouwd te worden voor een specifiek doel.^[4]

In 1951 kregen computers meer mogelijkheden waarna Grace Hopper als eerste inzag om subroutines in het geheugensysteem op te slaan. Het programmeren ging sneller maar de uitvoer ervan trager waardoor haar toenmalige werkgever Remington Rand geen interesse vertoonde.

Omdat ieder bedrijf voor hun computer andere vereisten nodig had, begon Hopper in haar vrije tijd te schrijven aan een compiler. Hoppers geschreven software was daarna in staat om geschreven programma's te vertalen naar machinetaal van een specifieke computer. Deze compiler werd toen onder meer gebruikt om complexe vergelijkingen op te lossen door wiskundigen. Andere programmeurs begonnen haar stukjes code toe te sturen om die aan de bibliotheek van de compiler toe te voegen. De hardware en software waren vanaf dan twee afzonderlijke componenten. Later zei Hopper: "Niemand had daar eerder aan gedacht want ze waren niet zo lui als ik." Uiteindelijk resulteerde haar compiler tot een van de eerste programmeertalen COBOL, waarvan Hopper de technische leiding had.^[4][3]

In 1963 werd daarna de zelfhostende compiler ontwikkeld door Mike Levin en Tim Hart onder leiding van John McCarthy. De compiler werd opgebouwd met een bootstrapping-systeem en zorgde ervoor dat een compiler zichzelf kon compileren. Dit werd voor het eerst in de programmeertaal LISP geïntroduceerd.^[5]

Eind jaren 70 werd de Portable C Compiler ontwikkeld door Stephen C. Johnson, een werknemer van Bell Labs. Het was de eerste compiler die vanwege een aparte front- en backendimplementatie gemakkelijk naar verschillende besturingssystemen en hardwarearchitecturen geporteerd kon worden. De compiler ontstond in 1977 toen er telkens aanpassingen noodzakelijk waren om de oorspronkelijke C-compiler, die voor de populaire PDP-11 geschreven was, compatibel te maken met andere machines.^[6] In het nieuwe design van de Portable C Compiler werd tussen de front- en de backend een intermediaire representatie uitgewisseld. Hierdoor kon S. I. Feldman een tweede frontend schrijven voor de programmeertaal FORTRAN 77.^[6] Tegenwoordig wordt deze architectuur voor de meeste compilers gebruikt.

Een moderne compiler bestaat doorgaans uit drie onderdelen, een frontend, een middle-end, en een backend, niet te verwarren met de frontend (cliënt-side) en backend (server-side) bij web-applicaties.

De frontend van de compiler is specifiek voor een bepaalde programmeertaal geschreven. De frontend is verantwoordelijk voor het verwerken van de broncode. Dit bestaat vaak uit de volgende fases:

• Lexicale analyse
• Parsen
• Semantische analyse
• Genereren van de interne representatie

De broncode wordt omgezet in een tussenrepresentatie en dan doorgestuurd.

De middle-end is zowel programmeertaal- als platformonafhankelijk. In de middle-end worden platformonafhankelijke optimalisaties op de tussenrepresentatie uitgevoerd, zoals het weghalen van code die nooit aangeroepen wordt en het vereenvoudigen van wiskundige formules.

De backend is specifiek voor een bepaald platform, bijvoorbeeld een specifieke processor in combinatie met een specifiek besturingssysteem. Voor iedere processor of besturingssysteem is een andere backend nodig. De backend is verantwoordelijk voor het genereren en optimaliseren van de objectcode. Dit kan uit de volgende fases bestaan:

• Registerallocatie
• Codegeneratie
• Optimalisatie

Deze onderdelen kunnen meer of minder met elkaar verweven zijn. Bij sommige compilers zijn ze precies op elkaar afgestemd. Andere zijn modulair opgebouwd zodat verschillende frontends met verschillende backend gecombineerd kunnen worden, waardoor verschillende programmeertalen voor verschillende platforms gecompileerd kunnen worden. Een voorbeeld hiervan is de GNU Compiler Collection (GCC).

Strikt gezien is compilatie het vertalen van expressies uit een formele taal naar expressies van een ander formele taal of doeltaal. Het compileren gebeurt in verschillende fases. De frontend levert zijn resultaten af aan de backend in de vorm van een interne representatie en een symbol table.^[7]

 

  Zie Lexicale analyse voor het hoofdartikel over dit onderwerp.

De taak van een lexicale scanner in de compiler is om de invoer, die in de regel uit een rij karakters bestaat, onder te verdelen in kleinere onderdelen, die symbolen of tokens genoemd worden. Deze tokens worden aan de parser doorgegeven. Een token is een object dat door de parser als eenheid herkend kan worden. Bij programmeertalen zijn de tokens de sleutelwoorden, de namen, de getallen, enzovoorts.

  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 regels die gedefinieerd zijn in de contextvrije 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 geparsete broncode weergeeft.

De semantische analyse wordt uitgevoerd op de afleidingsboom die het resultaat is van de hierboven beschreven parsen.

De parser definieert een mogelijke afleiding van een woord uit een formele taal in de zin van de contextvrije grammatica van die taal. Een dergelijke afleiding zegt echter niets over de correctheid van de afleiding met betrekking tot de contextgevoelige eigenschappen van de programmeertaal. Een voorbeeld is een regel dat een variabele gedeclareerd moet zijn voordat deze gebruikt wordt, of dat een bepaalde waarde alleen toegekend kan worden aan een variabele van het juiste type.

Een veelgebruikte methode tijdens de semantische analyse is attribuutevaluatie, waarbij semantische regels met een attributengrammatica worden vastgelegd. De attribuutevaluator van een compiler doorloopt nogmaals de gehele afleiding (soms meer dan één keer) om te bepalen of een afgeleid woord alle contextuele regels van de formele taal eerbiedigt. De attribuutevaluator beschouwt vaak deelbomen van de boom van de wortel naar de bladeren en weer terug en decoreert daarbij de boom 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 in de informatica aan attribuutevaluatorgeneratoren. Er zijn wel verschillende systemen die uit een beschrijving een attribuutevaluator kunnen genereren, maar er is nog geen algemene erkende oplosmethode.

  Zie Optimalisatie (compiler) voor het hoofdartikel over dit onderwerp.

Het optimaliseren heeft een belangrijke taak om de snelheid zo efficiënt mogelijk te houden. Technieken die hierbij kunnen worden toegepast zijn onder andere het vereenvoudigen van wiskundige formules en het ontvouwen van lussen.^[8]

  Zie Codegenerator voor het hoofdartikel over dit onderwerp.

De codegenerator is de laatste stap van de compilatie. Dit onderdeel beschouwt nog een laatste maal de gedecoreerde afleidingsboom en genereert vertalingen in de doeltaal 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 codegenerator naast drivercode bestaat uit een bibliotheek aan "standaardvertalingen" van stukken afleidingsboom, waarin gaten voorkomen. Deze gaten worden bij de echte codegeneratie gevuld met contextgevoelige informatie. Te denken valt dan aan de precieze naam van een variabele uit de invoer. Omdat codegeneratie afhankelijk is van contextgevoelige informatie en er voor attribuutevaluatie nog niet één echte oplossing is, is er ook nog niet één algemeen mechanisme voor generatie van codegeneratoren.

Daarnaast kampen onderzoekers naar codegeneratie 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 codeoptimalisatie wordt veel onderzoek gedaan.

Naast compilers zijn er naargelang het beoogde doel nog andere translators of vertalers beschikbaar.^[9]

Bij een interpreter wordt wordt de code direct, regel voor regel, uitgevoerd zonder dat hij vooraf gecompileerd wordt. Hierbij zal de gevraagde broncode telkens opnieuw worden geïnterpreteerd als hij wordt aangeroepen. Een voordeel is dat elk apparaat waarvoor een interpreter beschikbaar is dezelfde code kan uitvoeren, maar het belangrijkste nadeel is dat het programma langzamer wordt uitgevoerd omdat het interpreteren tijd kost.

Een assembler zet assembleertaal om naar machinetaal. Assembleertaal is een mnemonische weergave van machinetaal, waardoor het voor programmeurs makkelijker te begrijpen is dan machinetaal zelf. Sommige compilers produceren assembleertaal in plaats van objectcode, of bieden een optie aan dat te doen.

• De meeste compilers doen hun werk voordat het programma wordt uitgevoerd. Dit wordt een ahead-of-time (AOT)-compiler genoemd. Een just-in-time (JIT)-compiler compileert het programma terwijl het programma wordt uitgevoerd. Functies worden dan gecompileerd op het moment dat ze voor de eerste keer worden aangeroepen. Een JIT-compiler combineert voordelen van compilers en interpreters^[10], maar is ingewikkelder te schrijven en tijdens het compileren loopt het programma langzamer.
• AI-compiler: met kunstmatige intelligentie via machinaal leren om de optimalisatietijd te verkorten. Een voorbeeld is Milepost GCC van IBM.^[11]
• Een self-hosting compiler is een compiler die in zijn eigen brontaal is geschreven, bijvoorbeeld een C++-compiler die in C++ is geschreven of een Rust-compiler die in Rust is geschreven. Aangezien een self-hosting compiler zichzelf nodig heeft om gecompileerd te worden, is het ingewikkeld zo'n compiler naar een uitvoerbaar programma te vertalen. Dit proces wordt bootstrappen genoemd.
• Een cross-compiler is een compiler wiens objectcode op een ander platform wordt uitgevoerd dan het platform waarop de compiler zelf wordt uitgevoerd. Veel mobiele applicaties worden bijvoorbeeld op een pc of laptop geschreven en gecompileerd en vervolgens op een mobiele telefoon uitgevoerd.
• Decompiler: vertaalt een programma van een lagere programmeertaal naar een hogere programmeertaal.
• Native compiler: genereert een codeobject voor hetzelfde platform en besturingssysteem waarop het draait.
• Parallelle compiler: produceert een tussen compilatie en optimaliseert de abstracte syntaxisboom (AST) om te verspreiden naar meerdere processors.
• Source-to-source-compiler of transcompiler: converteert broncode van de ene hogere programmeertaal naar de andere hogere programmeertaal, vaak tot hetzelfde abstractieniveau. Dit wordt ook afgekort tot transpiler. Voorbeeld is C++ naar Python.^[12]

Compilers worden 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 runtime module, uitgevoerd kan worden.

Een programmeur schrijft de broncode van het programma 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 programma klaar is voor uitvoering, de zogenaamde executable.

Tijdens het ontwikkelen worden statische-analyse-tools (zoals Lint) en debuggers gebruikt om fouten op te sporen en te verbeteren.

Vaak zijn alle door de softwareontwikkelaar gebruikte tools, zoals de editor, compiler en de debugger, geïntegreerd in een geïntegreerde ontwikkelomgeving (Engels: integrated development environment, IDE), waardoor de softwareontwikkelaar geen aparate programma's hoeft op te roepen.

De voor -en nadelen van een compiler worden vaak vergeleken met een interpreter. Beide hebben met elkaar gemeen, dat ze broncode transformeren naar uitvoerbare instructies.

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

• Clang (C, C++ en Objective-C)
• GNU Compiler Collection (GCC, verschillende programmeertalen)
• Intel C++ Compiler (Linux, Windows)
• Microsoft Visual C++ (MSVC)
• MinGW
• Roslyn (C# en Visual Basic)

Voorbeelden van integrated development environments met ingebouwde compilers (software-ontwikkelomgeving):

• C++Builder (RAD)
• Delphi (RAD)
• Microsoft Visual Studio
• Turbo Pascal

• (en) A Compact Guide to Lex & Yacc, een korte, praktische introductie tot het schrijven van compilers met behulp van lex en yacc.