Compilatie (informatica)
Uit Wikipedia, de vrije encyclopedie
Compilatie of compileren is het vertalen van expressies uit een formele invoertaal 
naar expressies uit een formele uitvoertaal of doeltaal 
door middel van een compiler.
De implementatie van een dergelijke vertaling verloopt in een aantal stappen, die samen tot doel hebben om een aantal zaken vast te stellen. Met name:
- Of de invoer wel een correct woord van de invoertaal is (en dus, of een vertaling überhaupt wel mogelijk is)
- Wat de structuur van de invoer is, om vast te stellen hoe deze vertaald dient te worden
Inhoud |
[bewerk] Onderdelen
Compileren gebeurt in verschillende fases die grotendeels parallel lopen. In sterk vereenvoudigde vorm zijn dit:
- Analysefase, om te zien of er geen taalfouten zijn gemaakt.
- 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.
- 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.
- De attribuut-evaluatie of semantische analyse (de 'betekenis', 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.
- Synthesefase
- 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.
[bewerk] De lexical scan
De lexical scan vormt de initiële analyse die toegepast wordt op de invoer van de compiler. Deze invoer is een rij van symbolen uit een alfabet, die wellicht een woord vormt in de zin van een formele taal.
Een dergelijke formele taal onderscheidt in een woord meestal twee categorieën van deelrijen (rijen symbolen die voor kunnen komen als onderdeel van een langere invoer): de rijen die een speciale betekenis hebben binnen de formele taal (in programmeertalen vaak sleutelwoorden of keywords genoemd, of anders operatoren (wiskundige operatoren als + en *, bijvoorbeeld)) en de min of meer vrijgevormde rijen die namen aanduiden binnen de invoer (in het geval van een programmeertaal valt te denken aan variabelen).
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.
De werking van de lexical scanner berust op het berekeningsmodel van een eindigetoestandsautomaat: iedere deelrij van de invoer heeft een eindige lengte en de invoer wordt symbool voor symbool ingelezen – het is dus na ieder symbool direct mogelijk om te zien of de deelrij waaraan de scanner bezig is nog een sleutelwoord kan zijn, of dat het onmogelijk is en dat de deelrij dus een naam moet zijn. Het model van tekeninvoer en toestandsovergangen van de eindigetoestandsautomaat is de perfecte ondersteuning voor dit proces.
Naast het herkennen van sleutelwoorden en namen is de lexical scanner uiteraard ook toegerust om "lege" karakters te herkennen (de karakters die het einde markeren van een deelrij binnen de invoer – in programmeertalen wordt hiervoor vaak de spatie gebruikt) en meestal ook om namen te herkennen die verkeerd gevormd zijn (bijvoorbeeld omdat zij karakters bevatten die door de invoertaal van de compiler niet toegestaan zijn in namen, of bepaalde karakters bevatten op plaatsen waar die karakters niet voor mogen komen). Daarmee is de lexical scanner niet alleen een hulpmiddel voor de parser, maar ook toegerust om de eerste van een serie analyses uit te voeren die bepaalt of de invoer van een compiler werkelijk tot de invoertaal behoort.
Zoals eerder opgemerkt berust de lexical scanner als systeem op de eindige automaat. Deze automaat is gerelateerd aan de reguliere expressie, die uiteraard gebruikt kan worden om tokens te beschrijven (een letterlijke opeenvolging van symbolen voor sleutelwoorden, een algemenere beschrijving voor namen, een categorie voor lege karakters, enzovoorts). Reguliere expressies zijn in staat om de reguliere taal te beschrijven die alle mogelijke tokens van een taal omvat. Reguliere expressies kunnen ook automatisch vertaald worden in eindige automaten. En eindige automaten kunnen via een vast schema geïmplementeerd worden op een computer. Het is dus mogelijk om uit een verzameling reguliere expressies volautomatisch een lexicale scanner te genereren voor gebruik in een compiler. Een programma dat een lexical scanner genereert op basis van een beschrijving heet een lexical scanner generator.
[bewerk] De parsing
De parsing vormt het grootste gedeelte van de analyse binnen de compilatie. Het doel van de parsing is om te bepalen of de opeenvolging van tokens (zoals aangeleverd door de lexical scanner) een woord is binnen de formele taal die de compiler kan vertalen. De parser bepaalt dit door te proberen een boomstructuur op te bouwen waarin het startelement de wortel is, de tokens de bladeren en de kanten van de boom de opeenvolging van toegepaste productieregels.
Bij definitie is een woord van een formele taal een opeenvolging van tekens uit het alfabet van die taal die opgebouwd kan worden uit een beginsituatie door een aantal toepassingen van grammaticale regels van die taal. Omdat het voor de vertaling van een woord nodig is om te weten hoe dat woord in elkaar zit en of dat woord wel zinnig is, probeert de parser een afleiding op te stellen voor de rij van tokens die de parser ingevoerd krijgt. Als dat lukt, is de invoer bij definitie een woord uit de taal met een begrijpelijke structuur; lukt het niet, dan kan de compilatie eindigen want de invoer is dan onvertaalbaar.
Over het algemeen zijn er twee methoden van compilatie: de top-down compilatie en de bottom-up compilatie. In het eerste geval werkt de compiler door bij het startsymbool van zijn taal te beginnen en een boom op te stellen die uitkomt bij de tokens; in het tweede geval start de parser bij de tokens en probeert dan naar het startsymbool toe te bouwen. Daarbinnen is er nog keuze uit de precieze vorm van de afleiding (links-naar-rechts volgorde in de keuze tussen welke mogelijke variabele verder te produceren of andersom); top-down wordt vaak toegepast bij links-naar-rechts, bottom-up bij rechts-naar-links. In beide gevallen worden de tokens uit de invoer van voor naar achter behandeld en in beide gevallen maakt de parser vaak gebruik van voorkennis over welke tokens (een k-aantal) komen na het "huidige" token om een keuze te maken uit de mogelijke productieregels (als er meerdere mogelijk zijn in een gegeven situatie). Dit laatste heet een look-ahead van k tokens. Een compiler wordt sneller en accurater naarmate k groter is, maar de code wordt wel complexer – een waarde 1 voor k wordt vaak gebruikt als een mooie compromis-waarde.
Voor beide methoden van parsing zijn standaard softwaretools voorhanden om de parser automatisch te genereren uit een beschrijving van de grammatica van de taal. Iedere methode kent zijn eigen vorm van parser.
-
- Topdownparsers zijn verbonden met recursive descent-parsers. Deze parsers bestaan uit een verzameling functies of procedures – om precies te zijn, één per symbool van de grammatica van de taal. Het verwerken van een symbool komt neer op het aanroepen van de bijbehorende procedure. Voor een terminal symbool is de bijbehorende procedure vaak zeer kort (een verificatie dat het symbool inderdaad precies dat symbool is), voor een non-terminal symbool bevat de procedure code om productieregels te onderscheiden waarvan het non-terminal-symbool de linkerkant is en vervolgens code om de verwerking van juiste symbolen aan de rechterkant van de regel uit te voeren (dit zijn dan weer procedure-aanroepen). De verwerking van een invoer door dit soort parser is dus een opeenvolging van procedure-aanroepen die zo de boom afdalen (vandaar het Engelse descent). En omdat dit mogelijk recursief gaat (een non-terminal kan in één zowel linker- als rechterkant zijn) heet dit recursive descent.
- Bottom-up parsers zijn verbonden met LR-parsers. Deze parsers bestaan uit een standaard stuk code voor iedere mogelijke invoertaal en een tabel die per invoertaal bepaalt welke stappen de parser in welke situatie zet. Het genereren van een dergelijke parser bestaat uit het invullen van deze tabel. Deze techniek maakt sterk gebruik van de band tussen parsing en formele taal, die een toestandsautomaat bevat. De tabel die stappen bepaalt kijkt naar de toestand waarin de parsing zich bevindt (die een samenvatting is van alles wat de parser tot dan toe aan invoer gezien heeft) en legt voor iedere tostand vast wat de parser moet doen voor ieder mogelijk invoersymbool. Vaak is dit niets (omdat de invoer dan niet meer zinnig is), soms is het een overgang naar een volgende toestand en in één geval is het eindiging van de parsing in een accepterende toestand (er is dan gebleken dat de hele invoer een correcte invoer is). Er zijn vele verfijningen van dit parsing-principe die spelen rond de reductie van de grootte van de tabel (een zeer bekende die gebruikmaakt van look-ahead is de LALR-parser).
[bewerk] De attribuut-evaluatie
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 uigelezen 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".
[bewerk] De code-generatie
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 voor iedere deelbom 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.
