Kompilator

Från Wikipedia, den fria encyklopedin
Hoppa till navigation Hoppa till sökning

En kompilator (även kompilator; från engelska compile, gather 'eller latin compilare, heap') är ett datorprogram , källkoden för ett visst programmeringsspråk översatt till en form av en dator (direkt) kan utföras. Detta skapar ett mer eller mindre direkt körbart program. Detta ska särskiljas från tolkar , t.ex. för tidiga versioner av BASIC , som inte genererar maskinkod .

Ibland görs en åtskillnad mellan termerna översättare och kompilator. En översättare översätter ett program från ett formellt källspråk till en semantisk motsvarighet på ett formellt målspråk. Kompilatorer är speciella översättare som konverterar programkod från problemorienterade programmeringsspråk , så kallade högnivåspråk, till körbar maskinkod för en specifik arkitektur eller en mellanliggande kod ( bytecode , p-kod eller .NET-kod ). Denna åtskillnad mellan termerna översättare och kompilator görs inte i alla fall.

Processen för översättning är också känd som sammanställning eller omvandling (eller med motsvarande verb ). Motsatsen, det vill säga omvänd översättning av maskinspråk till källtext av ett visst programmeringsspråk, kallas dekompilering och motsvarande program kallas dekompilatorer .

terminologi

En översättare är ett program som accepterar ett program som är formulerat på ett källspråk och översätter det till ett semantiskt ekvivalent program på ett målspråk. [1] I synnerhet krävs att det genererade programmet levererar samma resultat som det givna programmet. Källspråkssamlare ses ofta som ett undantag - dess översättare (i maskinkod) kallas "assembler" och är i. A. kallas inte "kompilator". Översättarens arbete omfattar ett brett spektrum av deluppgifter från syntaxanalys till mål kodgenerering. En annan viktig uppgift är att identifiera och rapportera fel i källprogrammet.

Ordet "kompilator" kommer från engelska "att kompilera" och betyder "kompilator" i ordets egentliga bemärkelse. På 1950 -talet var termen ännu inte fast förankrad i datorvärlden. [2] Ursprungligen hänvisade kompilatorn till ett hjälpprogram som sammanförde ett övergripande program från enskilda delrutiner eller formelutvärderingar för att utföra särskilda uppgifter. (Denna uppgift utförs nu av länken , som dock också kan integreras i kompilatorn.) De enskilda delrutinerna skrevs fortfarande "för hand" på maskinspråk . Från 1954 kom termen "algebraisk kompilator" för ett program som automatiskt konverterade formler till maskinkod. Det "algebraiska" föll bort med tiden. [3]

I slutet av 1950-talet var termen kompilator fortfarande kontroversiell i engelsktalande länder. Fortrans utvecklingsteam höll på termen "översättare" i flera år för att referera till kompilatorn. Denna beteckning ingår till och med i namnet på själva Fortran -programmeringsspråket: Fortran består av For mula och Tran -slation, det är ungefär formelöversättning. Det var inte förrän 1964 som termen kompilator vann över termen översättare i samband med Fortran. Enligt Carsten Busch finns det en "speciell ironi i historien" att termen kompilator översätts som "översättare" på tyska. [2] [4] Vissa tyska publikationer använder dock också den engelska termen kompilator istället för översättare. [5]

I en smalare mening använder dock vissa tyskspråkiga publikationer endast den tekniska termen kompilator om källspråket är ett högre programmeringsspråk än målspråket. [6] Typiska applikationer är översättning av ett programmeringsspråk på hög nivå till maskinspråk på en dator, samt översättning till bytekod för en virtuell maskin . Kompilers målspråk (i denna mening) kan också vara ett församlingsspråk . En översättare för att översätta assembler -källprogram till maskinspråk kallas en assembler . [7]

berättelse

Konrad Zuse planerade redan en kompilator för det första designade högre programmeringsspråket, Plankalkül av Konrad Zuse - enligt dagens terminologi. Zuse kallas ett enda program en beräkning planen och så tidigt som 1944 fick idén till en så kallad planen produktionsordning, som automatiskt ska generera en stansad tejp med en motsvarande maskin plan för Zuse Z4 datorn från en matematiskt formulerad beräkning plan. [Åttonde]

Mer konkret än Zuses idé om en planproduktionsanordning var ett koncept av Heinz Rutishauser [9] för automatisk beräkning av planproduktion . I en föreläsning som hölls för Society for Applied Mathematics and Mechanics ( GAMM ) samt i hans habiliteringsuppsats vid ETH Zürich 1951 beskrev han vilka ytterligare programmeringskommandon (instruktioner) och hårdvarutillägg som var nödvändiga för Z4, som sedan användes vid ETHZ Datorn kan också användas som hjälpmedel för automatisk skapande av program. [10] [11] [12]

Grace Hopper (1984)

En tidig kompilator designades av matematikern Grace Hopper 1949. Fram till dess måste programmerare skapa maskinkod direkt. (Den första montören skrevs av Nathaniel Rochester för en IBM 701 mellan 1948 och 1950.) För att förenkla denna process utvecklade Grace Hopper en metod som gjorde det möjligt att skriva program och deras underprogram på ett mer mänskligt än maskinspråkigt sätt att uttrycka. [13] Den 3 maj 1952 presenterade Hopper den första kompilatorn A-0 , som kallade algoritmer från en katalog, skrev om kod, sammanställde den i lämplig ordning, reserverade minnesutrymme och organiserade allokeringen av minnesadresser . [14] I början av 1955 presenterade Hopper en prototyp av kompilatorn B-0 , som genererade program enligt engelska, franska eller tyska instruktioner. [15] Hopper kallade hennes tal om den första kompilatorn "The Education of a Computer".

Kompilatorns konstruktionshistoria formades av de nuvarande programmeringsspråken (se tidtabellen för programmeringsspråk ) och hårdvaruarkitekturer. Andra tidiga milstolpar är den första Fortran -kompilatorn 1957 och den första COBOL -kompilatorn 1960. Många arkitektoniska särdrag hos dagens kompilatorer utvecklades dock inte förrän på 1960 -talet.

Tidigare kallades program ibland också som kompilatorer, som sätter ihop delprogram. [16] Detta kringgår dagens kärnuppgift för en kompilator, eftersom numera kan subrutiner infogas på andra sätt: Antingen i själva källkoden , till exempel av en förbehandlare (se även förkompilerare ) eller av en oberoende länk för kompilerade komponenter .

Arbetssätt

De grundläggande stegen för att översätta en källkod till en målkod är:

Syntaxkontroll
Det kontrolleras om källkoden representerar ett giltigt program, det vill säga om det motsvarar syntaxen för källspråket. Eventuella fel som registreras loggas. Resultatet är en mellanliggande representation av källkoden.
Analys och optimering
Mellanbilden analyseras och optimeras. Omfattningen av detta steg varierar mycket beroende på kompilator och användarinställningar. Det sträcker sig från enklare effektivitetsoptimeringar till programanalys .
Kodgenerering
Den optimerade mellandisplayen översätts till motsvarande kommandon på målspråket. Vidare kan målspråkspecifika optimeringar göras här.
Obs: Moderna kompilatorer (mestadels) genererar inte längre kod själva.
Kodgenerering under körning möjliggör:
  • optimeringar över flera moduler,
  • exakta justeringar av målplattformen (instruktionsuppsättning, anpassning till processorkapaciteten),
  • Användning av profilinformation.

En kompilators struktur

Kompilatorkonstruktion , det vill säga programmering av en kompilator, är en oberoende disciplin inom datavetenskap .

Moderna kompilatorer är indelade i olika faser, som var och en tar på sig olika deluppgifter för kompilatorn. Några av dessa faser kan implementeras som oberoende program (se förkompilerare , förbehandlare ). De körs sekventiellt . I grund och botten kan två faser urskiljas: frontänden (även analysfasen ), som analyserar källtexten och genererar ett tillskrivet syntaxträd från den, och backend (även syntesfasen ), som genererar målprogrammet från den .

Frontend (även "analysfas")

I frontänden analyseras, struktureras och kontrolleras koden för fel. Det är självt uppdelat i faser. Språk som modern C ++ tillåter inte syntaxanalysen att delas in i lexikal analys, syntaktisk analys och semantisk analys på grund av oklarheter i deras grammatik. Deras kompilatorer är på motsvarande sätt komplexa.

Lexikal analys

Den lexikaliska analysen delar upp den importerade källtexten i lexikaliska enheter ( tokens ) av olika typer, till exempel nyckelord , identifierare , siffror , strängar eller operatörer . Denna del av kompilatorn kallas en tokenizer, skanner eller lexer.

En skanner använder ibland en separat skärm för att hoppa över blanksteg ( blanksteg , dvs. mellanslag, flikar, radändningar, etc.) och kommentarer .

En annan funktion av den lexikaliska analysen är att associera igenkända tokens med deras position (t.ex. radnummer) i källtexten. Om fel hittas i källtexten i den ytterligare analysfasen, som är baserad på tokens (t.ex. av syntaktisk eller semantisk karaktär), kan de felmeddelanden som genereras tillhandahållas med en hänvisning till felens plats.

Lexikalfel är tecken eller strängar som inte kan tilldelas en token. Till exempel tillåter de flesta programmeringsspråk inte identifierare som börjar med siffror (t.ex. "3foo").

Syntaktisk analys

Den syntaktiska analysen kontrollerar om den importerade källkoden har rätt struktur för källspråket som ska översättas, dvs motsvarar den kontextfria syntaxen (grammatiken) för källspråket. Ingången konverteras till ett syntaxträd . Den syntaktiska analysatorn är också känd som en parser . Om källkoden inte stämmer överens med grammatiken för källspråket matar parsern ut ett syntaxfel . Syntaxträdet som skapas på detta sätt kommenteras med "innehållet" i noderna för nästa fas (semantisk analys); Det betyder till exempel att variabelidentifierare och siffror skickas vidare tillsammans med informationen som de är. Den syntaktiska analysen kontrollerar till exempel om parenteserna är korrekta, dvs varje öppningsfäste följs av en stängningskonsol av samma typ, såväl som utan parentesinvikling. Nyckelorden ger också vissa strukturer.

Semantisk analys

Den semantiska analysen kontrollerar den statiska semantiken , det vill säga villkor i programmet som går utöver den syntaktiska analysen. Till exempel måste en variabel vanligtvis ha deklarerats innan den används, och tilldelningar måste göras med kompatibla (kompatibla) datatyper . Detta kan göras med hjälp av attributgrammatik . Noderna i syntaxträdet som genereras av parsern ges attribut som innehåller information. Till exempel kan en lista över alla deklarerade variabler skapas. Resultatet av den semantiska analysen kallas då ett dekorerat eller tillskrivet syntaxträd.

Backend (även "syntesfas")

Backend genererar programkoden för målspråket från det tillskrivna syntaxträdet som skapats av frontend.

Generering av mellanliggande kod

Många moderna kompilatorer genererar en mellanliggande kod från syntaxträdet, som redan kan vara relativt nära maskinen, och utför till exempel programoptimeringar på denna mellanliggande kod. Detta är särskilt användbart för kompilatorer som stöder flera källspråk eller olika målplattformar . Här kan mellankoden också vara ett utbytesformat.

Programoptimering

Mellankoden är grunden för många programoptimeringar. Se programoptimering .

Kodgenerering

Under kodgenerering genereras programkoden för målspråket antingen direkt från syntaxträdet eller från mellanliggande kod. Om målspråket är ett maskinspråk kan resultatet bli ett körbart program direkt eller en så kallad objektfil som, genom att länka till runtime- biblioteket och eventuellt andra objektfiler, leder till ett bibliotek eller ett körbart program . Allt detta utförs av kodgeneratorn, som är en del av kompilatorsystemet, ibland som en del av kompilatorprogrammet, ibland som en separat modul.

Klassificering av olika typer av kompilatorer

Ursprunglig kompilator
Kompilator som genererar målkoden för plattformen där den körs själv. Koden är plattformsspecifik.
Cross compiler
Kompilator som körs på en plattform och genererar målkod för en annan plattform, till exempel ett annat operativsystem eller en annan processorarkitektur .
En typisk applikation är skapandet av program för ett inbäddat system som i sig inte innehåller några verktyg eller inga bra verktyg för programvaruutveckling, liksom skapandet eller porten av ett operativsystem till en ny plattform.
Enpassningskompilator
Kompilator som genererar målkoden från källkoden i ett enda pass (i motsats till multipass-kompilatorn); kompilatorn läser källtexten från framsidan till baksidan bara en gång och genererar resultatprogrammet samtidigt. En sådan kompilator är vanligtvis mycket snabb, men kan bara utföra enkla optimeringar. En enkelpassskompilator kan bara skapas för vissa programmeringsspråk, till exempel Pascal , C och C ++ , eftersom programmeringsspråket inte får innehålla några framåtreferenser (inget får användas som inte redan har deklarerats "ovan" i källkod).
Multipass-kompilator
Med denna typ av kompilator översätts källkoden till målkoden i flera steg (ursprungligen: källkoden läses in flera gånger eller bearbetas helt flera gånger "från framsidan till baksidan"). Under de första dagarna av kompilatorbyggandet delades översättningsprocessen huvudsakligen upp i flera körningar eftersom datorn ofta inte hade tillräckligt med kapacitet för att hålla hela kompilatorn och programmet som skulle översättas i huvudminnet samtidigt. Numera används en multi-pass-kompilator huvudsakligen för att lösa framåt referenser ( deklaration av en identifierare "längre ner i källkoden" som första användning) och för att utföra komplexa optimeringar.

Särskilda former

  • En transkompilator (även känd som en transpiler eller korsöversättare ) är en speciell kompilator som översätter källkoden för ett programmeringsspråk till källkoden för ett annat programmeringsspråk, till exempel från Pascal till C. [17] Denna process kallas "kodomvandling" eller "översätt". Men eftersom många programmeringsspråk har speciella egenskaper och prestandafunktioner kan effektivitetsförluster uppstå om dessa inte tas med i beräkningen av omvandlaren. [18] Eftersom programmeringsspråk mestadels följer olika programmeringsparadigm är den nyskapade källkoden ofta svårläst för utvecklare. Ibland är manuell efterbehandling av koden nödvändig eftersom den automatiska översättningen inte fungerar smidigt i alla fall. Det finns också omfattande delprogrambibliotek på många moderna programmeringsspråk. Genomförandet av bibliotekssamtal komplicerar också sammanställningen.
  • Kompilatorkompilatorer och kompilatorgeneratorer är hjälpprogram för automatisk generering av kompilatordelar eller kompletta kompilatorer. Se även: ANTLR , Coco / R , JavaCC , Lex , Yacc
  • Just-in-time-kompilatorer (eller JIT-kompilatorer ) översätter inte källkod eller mellanliggande kod till maskinkod förrän programmet körs. Programdelar sammanställs bara när de körs för första gången eller flera gånger. Graden av optimering beror vanligtvis på frekvensen för användning av motsvarande funktion.
  • Med tolkaren översätts programmets källkod först till en mellanliggande kod, som sedan tolkas vid körning. Compreters bör kombinera fördelarna med kompilatorn med fördelarna med tolk . För att minska körningstiden implementeras många av dagens tolkar effektivt internt som datorer som översätter källkoden vid körning innan programmet körs. En bykodstolk är också en kompeterare, t.ex. B. de virtuella maskinerna från Java till version 1.2.

Programoptimering (i detalj)

Många optimeringar som tidigare var kompilatorns uppgift utförs nu inom CPU: n medan koden bearbetas. Maskinkod är bra när den har korta kritiska vägar och få överraskningar på grund av felaktigt förutsagda hopp, begär data från minnet i god tid och använder alla exekveringsenheter i CPU: n lika mycket.

Parallell beräkning av mängden Mandelbrot på en Haswell i7 CPU (2014). Grafiken visar beräkningarna som sker samtidigten kärna (datatyp: flytpunkt, enkel precision), det vill säga mellan 64 och 128 beräkningar i 8 till 16 kommandon per kärna, uppdelade i 2 trådar. På en Haswell Core i7-5960X (8 kärnor) sker upp till 1024 parallella beräkningar (96 miljarder iterationer / sek), på en Haswell Xeon E7-8890 V3 upp till 2304 (180 miljarder iterationer / sek per uttag). Moderna kompilators uppgift är att optimera kod för att möjliggöra kapsling av instruktioner. Detta är ett fundamentalt annat jobb än kompilatorer gjorde i slutet av 1980 -talet.

För att styra översättningen kan källtexten innehålla ytterligare speciella kompilatorinstruktioner utöver instruktionerna i programmeringsspråket.

En kompilator erbjuder vanligtvis alternativ för olika optimeringar i syfte att förbättra körningstiden för målprogrammet eller minimera lagringskraven . Optimeringarna baseras delvis på maskinvarans egenskaper, till exempel hur många och vilka register som datorns processor gör tillgänglig. Det är möjligt för ett program att köra långsammare efter optimering än det skulle ha gjort utan optimering. Detta kan till exempel inträffa när en optimering för en programkonstruktion ger längre kod som faktiskt skulle köras snabbare, men kräver mer tid för att laddas in i cachen . Det är därför bara fördelaktigt om det används ofta.

Vissa optimeringar resulterar i att kompilatorn genererar målspråkkonstruktioner för vilka det inte finns några direkta ekvivalenter i källspråket. En nackdel med sådana optimeringar är att det då knappast är möjligt att följa programflödet med en interaktiv felsökning på källspråket.

Optimeringar kan vara mycket tidskrävande. I många fall, särskilt i moderna JIT -kompilatorer, är det därför nödvändigt att avväga om det är värt att optimera en del av programmet. Med kompilatorer i förväg används alla vettiga optimeringar i den slutliga sammanställningen, men ofta inte under mjukvaruutveckling (detta minskar den kompileringstid som krävs). För icke-automatiska optimeringar från programmerarens sida kan tester och applikationsscenarier köras igenom (se Profiler ) för att ta reda på var komplexa optimeringar är värda.

I det följande övervägs några optimeringsalternativ för en kompilator . Den största potentialen för optimering ligger dock ofta i att ändra själva källprogrammet, till exempel genom att ersätta en algoritm med en mer effektiv. I de flesta fall kan denna process inte automatiseras, utan måste utföras av programmeraren . Å andra sidan kan enklare optimeringar delegeras till kompilatorn för att hålla källkoden läsbar.

Spara maskinkommandon

På många programmeringsspråk på hög nivå behöver du till exempel en hjälpvariabel för att byta innehållet i två variabler:

Spara maskinkommandon (MB)
Källkod Maskinkommandon
utan optimering med optimering
hilf := a a → registrera 1
Registrera 1 → hjälp
a → registrera 1
a := b b → Registrera 1
Registrera 1 → a
b → Registrera 2
Registrera 2 → a
b := hilf hjälp → Registrera 1
Registrera 1 → b
Registrera 1 → b
Obligatoriskt ...
variabler 3 2
Registrera 1 2
Operationer 6: e 4: e

Med optimering är bara fyra monteringskommandon krävs i stället för sex, och minnesutrymme för den extra variabeln hilf inte nödvändigt. Detta innebär att denna byte utförs snabbare och kräver mindre huvudminne . Detta gäller dock bara om tillräckliga register finns tillgängliga i processorn . Att lagra data i register istället för huvudminne är ett vanligt optimeringsalternativ.

Kommandosekvensen som visas ovan som optimerad har en annan egenskap som kan vara en fördel i moderna processorer med flera processrörledningar: De två läskommandona och de två skrivkommandona kan bearbetas parallellt utan problem, de är inte beroende av resultatet av Övrig. Endast det första skrivkommandot måste definitivt vänta tills det sista läskommandot har utförts. Mer fördjupade optimeringsprocesser kan därför infoga maskinkommandon mellan b → register 2 och register 2 → a som tillhör en helt annan kommandorad på hög nivå.

Statisk formelutvärdering vid sammanställningstid

Beräkningen av omkretsen med

 pi = 3,14159
u = 2 * pi * r

kan en kompilator redan vid kompileringstid för att u = 6.28318 * r utvärdera. Denna formelutvärdering sparar multiplikationen 2 * pi under körtiden för det genererade programmet. Denna procedur kallas konstant vikning.

Eliminering av död programkod

Om kompilatorn kan inse att en del av programmet aldrig kommer att köras igenom, kan den utelämna denna del från sammanställningen.

Exempel:

 100   gå till 900
200   k = 3
900   jag = 7
...   ...

Om det aldrig finns en GOTO på hoppetiketten 200 i detta program kan instruktionen 200 k=3 undvikas. Hoppinstruktionen 100 goto 900 är då också överflödig.

Upptäckt av oanvända variabler

Om en variabel inte krävs behöver inget minnesutrymme reserveras och ingen målkod måste genereras.

Exempel:

 subrutin test (a, b)
    b = 2 * a
    c = 3,14 * b
    återvända b

Variabeln c krävs inte här: Den finns inte i parameterlistan , används inte i efterföljande beräkningar och matas inte ut. Därför kan instruktionen c = 3.14 * b utelämnas.

Optimera slingor

I synnerhet försöker man optimera slingor genom att till exempel

  • har så många variabler som möjligt i registren (vanligtvis åtminstone slingvariabeln);
  • i stället för ett index, med elementen i ett fält ( engelska är åtkomstmatris), pekare som används för elementen, kännetecknade att ansträngningen att komma åt fältelement är låg;
  • Beräkningar inom slingan som ger samma resultat i varje körning utförs bara en gång före slingan (loop-invariant kodrörelse);
  • kombinerar två slingor som går över samma värdeintervall till en slinga, så att den administrativa ansträngningen för slingan endast uppstår en gång;
  • slingan delvis eller (när det gäller slingor med ett konstant, lågt antal passningar) rullar helt upp (engelsk slinga ), så att instruktionerna i slingan utförs flera gånger i direkt följd, utan kontroll av slingans tillstånd och ett hopp till början av slingan som sker varje gång efter instruktionerna;
  • vänder slingan (särskilt med räkningsslingor med för ), eftersom effektiva hoppkommandon (Jump-Not-Zero) kan användas när man räknar ner till 0;
  • omformar öglan så att kontrollen av avslutningsvillkoret utförs i slutet av slingan (slingor med en första kontroll har alltid en villkorlig och en ovillkorlig hoppinstruktion, medan slingor med en slutkontroll bara har en villkorlig hoppinstruktion);
  • tog bort hela slingan om den (efter några justeringar) har en tom kropp. Detta kan dock leda till att köer som är avsedda att bromsa ett program tas bort. Operativsystemets funktioner bör dock användas för detta ändamål så långt som möjligt.
  • Ordnar kapslade slingor (loopar i loopar) - om programmeringslogiken som används tillåter det - i stigande ordning, från den yttersta slingan med de minsta loop -passeringarna till den innersta loop med flest loop -passeringar. Detta förhindrar flera multipla initialiseringar av de inre kretsarna.

Vissa av dessa optimeringar är till ingen nytta eller till och med kontraproduktiva med nuvarande processorer.

Insättning av subrutiner

När det gäller små subrutiner är ansträngningen som krävs för att ringa till subrutinen mer betydelsefull än det arbete som utförs av subrutinen. Kompilatorer försöker därför att infoga maskinkoden för mindre subrutiner direkt - ungefär som hur vissa kompilatorer / montörer / förkompilerare bryter ner makroinstruktioner till källkod. Denna teknik är också känd som inlining. I vissa programmeringsspråk är det möjligt att använda inline -nyckelord för att indikera för kompilatorn att vissa underrutiner ska infogas. Insättning av subrutiner öppnar ofta ytterligare möjligheter till optimering, beroende på parametrarna.

Håller värden i register

Anstatt mehrfach auf dieselbe Variable im Speicher, beispielsweise in einer Datenstruktur, zuzugreifen, kann der Wert nur einmal gelesen und für weitere Verarbeitungen in Registern oder im Stack zwischengespeichert werden. In C , C++ und Java muss dieses Verhalten ggf. mit dem Schlüsselwort volatile abgeschaltet werden: Eine als volatile bezeichnete Variable wird bei jeder Benutzung wiederholt vom originalen Speicherplatz gelesen, da ihr Wert sich unterdessen geändert haben könnte. Das kann beispielsweise der Fall sein, wenn es sich um einen Hardware-Port handelt oder ein parallel laufender Thread den Wert geändert haben könnte.

Beispiel:

 int a = array [ 25 ] -> element . x ;
int b = 3 * array [ 25 ] -> element . x ;

Im Maschinenprogramm wird nur einmal auf array[25]->element.x zugegriffen, der Wert wird zwischengespeichert und zweimal verwendet. Ist x volatile, dann wird zweimal zugegriffen.

Es gibt außer volatile noch einen anderen Grund, der eine Zwischenspeicherung in Registern unmöglich macht: Wenn der Wert der Variablen v durch Verwendung des Zeigers z im Speicher verändert werden könnte, kann eine Zwischenspeicherung von v in einem Register zu fehlerhaftem Programmverhalten führen. Da die in der Programmiersprache C oft verwendeten Zeiger nicht auf ein Array beschränkt sind (sie könnten irgendwohin im Hauptspeicher zeigen), hat der Optimizer oft nicht genügend Informationen, um eine Veränderung einer Variablen durch einen Zeiger auszuschließen.

Verwendung schnellerer äquivalenter Anweisungen

Statt einer Multiplikation oder Division von Ganzzahlen mit einer Zweierpotenz kann ein Schiebebefehl verwendet werden. Es gibt Fälle, in denen nicht nur Zweierpotenzen, sondern auch andere Zahlen (einfache Summen von Zweierpotenzen) für diese Optimierung herangezogen werden. So kann zum Beispiel ( n << 1 ) + ( n << 2 ) schneller sein als n * 6 . Statt einer Division durch eine Konstante kann eine Multiplikation mit dem Reziprokwert der Konstante erfolgen. Selbstverständlich sollte man solch spezielle Optimierungen auf jeden Fall dem Compiler überlassen.

Weglassen von Laufzeitüberprüfungen

Programmiersprachen wie Java fordern Laufzeitüberprüfungen beim Zugriff auf Felder oder Variablen. Wenn der Compiler ermittelt, dass ein bestimmter Zugriff immer im erlaubten Bereich sein wird (zum Beispiel ein Zeiger, von dem bekannt ist, dass er an dieser Stelle nicht NULL ist), kann der Code für diese Laufzeitüberprüfungen weggelassen werden.

Reduktion von Paging zur Laufzeit

Eng zusammenhängende Codebereiche, zum Beispiel ein Schleifenrumpf, sollte zur Laufzeit möglichst auf der gleichen oder in möglichst wenigen Speicherseiten („Page“, zusammenhängend vom Betriebssystem verwalteter Speicherblock) im Hauptspeicher liegen. Diese Optimierung ist Aufgabe des (optimierenden) Linkers. Dies kann zum Beispiel dadurch erreicht werden, dass dem Zielcode an geeigneter Stelle Leeranweisungen („NOPs“ – N o OP eration) hinzugefügt werden. Dadurch wird der erzeugte Code zwar größer, aber wegen der reduzierten Anzahl notwendiger TLB-Cache-Einträge und notwendiger Pagewalks wird das Programm schneller ausgeführt.

Vorziehen bzw. Verzögern von Speicherzugriffen

Durch das Vorziehen von Speicherlesezugriffen und das Verzögern von Schreibzugriffen lässt sich die Fähigkeit moderner Prozessoren zur Parallelarbeit verschiedener Funktionseinheiten ausnutzen. So kann beispielsweise bei den Befehlen: a = b * c; d = e * f; der Operand e bereits geladen werden, während ein anderer Teil des Prozessors noch mit der ersten Multiplikation beschäftigt ist.

Ein Beispielcompiler

Folgendes in ANTLR erstelltes Beispiel soll die Zusammenarbeit zwischen Parser und Lexer erklären. Der Übersetzer soll Ausdrücke der Grundrechenarten beherrschen und vergleichen können. Die Parser grammatik wandelt einen Dateiinhalt in einen abstrakten Syntaxbaum (AST) um.

Grammatiken

Die Baumgrammatik ist in der Lage, die im AST gespeicherten Lexeme zu evaluieren. Der Operator der Rechenfunktionen steht in der AST-Schreibweise vor den Operanden als Präfixnotation . Daher kann die Grammatik ohne Sprünge Berechnungen anhand des Operators durchführen und dennoch Klammerausdrücke und Operationen verschiedener Priorität korrekt berechnen.

 tree grammar Eval ;
options {
	tokenVocab = Expression ;
	ASTLabelType = CommonTree ;
}
@header {
import java.lang.Math ;
}
start : line + ; //Eine Datei besteht aus mehreren Zeilen
line : compare { System . out . println ( $compare . value );}
	;

compare returns [ double value ]
	: ^ ( '+' a = compare b = compare ) { $value = a + b ;}
	| ^ ( '-' a = compare b = compare ) { $value = a - b ;}
	| ^ ( '*' a = compare b = compare ) { $value = a * b ;}
	| ^ ( '/' a = compare b = compare ) { $value = a / b ;}
	| ^ ( '%' a = compare b = compare ) { $value = a \ % b ;}
	| ^ ( UMINUS a = compare ) { $value = - 1 * a ;} //Token UMINUS ist notwendig, um den binären
                                                      //Operator nicht mit einem Vorzeichen zu verwechseln
	| ^ ( '^' a = compare b = compare ) { $value = Math . pow ( a , b );}
	| ^ ( '=' a = compare b = compare ) { $value = ( a == b ) ? 1 : 0 ;} //wahr=1, falsch=0
	| INT { $value = Integer . parseInt ( $INT . text );}
	;

Ist eines der oben als compare bezeichnete Ausdrücke noch kein Lexem, so wird es von der folgenden Lexer-Grammatik in einzelne Lexeme aufgeteilt. Dabei bedient sich der Lexer der Technik des rekursiven Abstiegs . Ausdrücke werden so immer weiter zerlegt, bis es sich nur noch um Token vom Typ number oder Operatoren handeln kann.

 grammar Expression ;
options {
	output = AST ;
	ASTLabelType = CommonTree ;
}
tokens {
	UMINUS ;
}
start : ( line { System . out . println ( $line . tree == null ? "null" : $line . tree . toStringTree ());}) + ;
line : compare NEWLINE -> ^ ( compare ); //Eine Zeile besteht aus einem Ausdruck und einem
                                              //terminalen Zeichen
compare : sum ( '=' ^ sum ) ? ; //Summen sind mit Summen vergleichbar
sum : product ( '+' ^ product | '-' ^ product ) * ; //Summen bestehen aus Produkten (Operatorrangfolge)
product : pow ( '*' ^ pow | '/' ^ pow | '%' ^ pow ) * ; //Produkte (Modulo-Operation gehört hier dazu) können
                                                  //aus Potenzen zusammengesetzt sein
pow : term ( '^' ^ pow ) ? ; //Potenzen werden auf Terme angewendet
term : number //Terme bestehen aus Nummern, Subtermen oder Summen
		| '+' term -> term
		| '-' term -> ^ ( UMINUS term ) //Subterm mit Vorzeichen
		| '(' ! sum ')' ! //Subterm mit Klammerausdruck
		;
number : INT ; //Nummern bestehen nur aus Zahlen
INT : '0' .. '9' + ;
NEWLINE : '\r' ? '\n' ;
WS : ( ' ' | '\t' | '\n' | '\r' ) + { skip ();}; //Whitespace wird ignoriert

Die Ausgabe hinter dem Token start zeigt außerdem den gerade evaluierten Ausdruck.

Ausgabe des Beispiels

Eingabe:

 5 = 2 + 3
32 * 2 + 8
(2 * 2^3 + 2) / 3

Ausgabe (in den ersten Zeilen wird nur der Ausdruck der Eingabe in der AST-Darstellung ausgegeben):

 (= 5 (+ 2 3))
(+ (* 32 2) 8)
(/ (+ (* 2 (^ 2 3)) 2) 3)
1.0
72.0
6.0

Der erste Ausdruck wird also als wahr (1) evaluiert, bei den anderen Ausdrücken wird das Ergebnis der Rechnung ausgegeben.

Literatur

Weblinks

Wiktionary: Compiler – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
Wiktionary: kompilieren – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise

  1. Michael Eulenstein: Generierung portabler Compiler. Das portable System POCO. (= Informatik-Fachberichte 164) Springer Verlag: Berlin, ua, 1988, S. 1; Hans-Jochen Schneider (Hrsg.): Lexikon Informatik und Datenverarbeitung. 4. Auflage, Oldenbourg Verlag: München, Berlin, 1998, 900; Manfred Broy: Informatik. Eine grundlegende Einführung. Band 2: Systemstrukturen und Theoretische Informatik. 2. Auflage, Springer Verlag: Berlin, Heidelberg, 1998, S. 173.
  2. a b Carsten Busch: Mataphern in der Informatik. Modellbildung - Formalisierung - Anwendung. Springer Fachmedien: Wiesbaden, 1998, S. 171.
  3. Axel Rogat: Aufbau und Arbeitsweise von Compilern , Kapitel 1.11: Geschichte ; Thomas W. Parsons: Introduction to Compiler Construction. Computer Science Press: New York, 1992, S. 1.
  4. Zur Übersetzung des englischen „compiler“ mit dem deutschen „Übersetzer“ siehe ua: Hans-Jürgen Siegert, Uwe Baumgarten: Betriebssysteme. Eine Einführung. 6. Auflage, Oldenbourg Verlag: München, Wien, 2007, S. 352; Christoph Prevezanos: Computer-Lexikon 2011. Markt+Technik Verlag: München, 2010, S. 940; Christoph Prevenzanos: Technisches Schreiben. Für Informatiker, Akademiker, Techniker und den Berufsalltag. Hanser Verlag: München, 2013, S. 130.
  5. So beispielsweise Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compiler. Prinzipien, Techniken und Werkzeuge. 2. Auflage, Pearson Studium: München, 2008.
  6. Siehe dazu Hans-Jochen Schneider (Hrsg.): Lexikon Informatik und Datenverarbeitung. 4. Auflage, Oldenbourg Verlag: München, Berlin, 1998: Artikel „Compiler“, S. 158, und Artikel „Übersetzer“, S. 900.
  7. Hartmut Ernst, Jochen Schmidt; Gert Beneken: Grundkurs Informatik. Grundlagen und Konzepte für die erfolgreiche IT-Praxis. Eine umfassende, praxisorientierte Einführung. 5. Auflage, Springer: Wiesbaden, 2015, S. 409.
  8. Hans Dieter Hellige: Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Springer, Berlin 2004, ISBN 3-540-00217-0 , S. 45, 104, 105.
  9. Evelyn Boesch Trüeb: Heinz Rutishauser. In: Historisches Lexikon der Schweiz . 12. Juli 2010 , abgerufen am 21. Oktober 2014 .
  10. Stefan Betschon: Der Zauber des Anfangs. Schweizer Computerpioniere. In: Franz Betschon , Stefan Betschon, Jürg Lindecker, Willy Schlachter (Hrsg.): Ingenieure bauen die Schweiz. Technikgeschichte aus erster Hand. Verlag Neue Zürcher Zeitung, Zürich 2013, ISBN 978-3-03823-791-4 , S. 381–383.
  11. Friedrich L. Bauer: My years with Rutishauser.
  12. Stefan Betschon: Die Geschichte der Zukunft. In: Neue Zürcher Zeitung, 6. Dezember 2016, S. 11
  13. Inventor of the Week Archive.Massachusetts Institute of Technology , Juni 2006, abgerufen am 25. September 2011 .
  14. Kurt W. Beyer: Grace Hopper and the invention of the information age . Massachusetts Institute of Technology, 2009, ISBN 978-0-262-01310-9 ( Google Books [abgerufen am 25. September 2011]).
  15. Kathleen Broome Williams: Grace Hopper . Naval Institute Press, 2004, ISBN 1-55750-952-2 ( Google Books [abgerufen am 25. September 2011]).
  16. FL Bauer, J. Eickel: Compiler Construction: An Advanced Course . Springer, 1975.
  17. Transcompiler. In: Neogrid IT Lexikon. Abgerufen am 18. November 2011 : „Wenn ein Compiler aus dem Quellcode einer Programmiersprache den Quellcode einer anderen erzeugt (z. B. C in C++) so spricht man von einem Transcompiler.“
  18. Transpiler. bullhost.de, abgerufen am 18. November 2012 .