Kompilator

Kompilator – program służący do automatycznego tłumaczenia kodu napisanego w jednym języku (języku źródłowym) na równoważny kod w innym języku (języku wynikowym). Proces ten nazywany jest kompilacją. W informatyce kompilatorem nazywa się najczęściej program do tłumaczenia kodu źródłowego w języku programowania na język maszynowy. Niektóre z nich tłumaczą najpierw do języka asemblera, a ten na język maszynowy jest tłumaczony przez asembler.

Różnica pomiędzy kompilatorem a asemblerem polega na tym, iż każde polecenie języka programowania może zostać rozbite na wiele podpoleceń języka maszynowego (przy czym nowoczesne asemblery również posiadają składnię umożliwiającą zapis wielu poleceń maszynowych jako jednego polecenia kodu źródłowego oraz opcje optymalizacji kodu). Kompilatory mogą mieć możliwość automatycznej alokacji pamięci dla zmiennych, implementowania struktur kontrolnych lub procedur wejścia-wyjścia.

Stosowanie kompilatorów ułatwia programowanie (programista nie musi znać języka maszynowego) i pozwala na większą przenośność kodu pomiędzy platformami.

Zarys historyczny 
Oprogramowanie pierwszych komputerów było przez wiele lat pisane jedynie w języku asemblera. Języki wysokiego poziomu nie były stosowane, dopóki korzyści z użycia tych samych programów na różnych rodzajach procesorów nie stały się istotnie większe od kosztu pisania kompilatora. Bardzo ograniczona pojemność pamięci wczesnych komputerów sprawiała również wiele problemów przy implementacji kompilatorów.

Pod koniec lat 50. zaproponowano po raz pierwszy maszynowe języki programowania, w następstwie czego powstały pierwsze, eksperymentalne kompilatory. Pierwszy kompilator napisała Grace Hopper w 1952 dla języka A-0.
Uznaje się, że ekipa FORTRAN z IBM, prowadzona przez Johna Backusa, wprowadziła do użycia pierwszy kompletny kompilator w 1957. W 1960 COBOL był jednym z pierwszych języków, który można było kompilować na różnych architekturach.

W wielu dziedzinach zastosowań idea programowania wysokopoziomowego szybko się przyjęła. Rozszerzanie funkcjonalności zapewnianej przez nowsze języki programowania oraz wzrastająca złożoność architektur systemów komputerowych spowodowały, że kompilatory stawały się coraz bardziej skomplikowane.

Wczesne kompilatory były pisane w asemblerze. Pierwszym kompilatorem zdolnym do skompilowania własnego kodu źródłowego napisanego w języku wysokiego poziomu był kompilator języka Lisp, stworzony przez Harta i Levina z MIT w 1962. Od lat siedemdziesiątych stało się powszechną praktyką implementowanie kompilatora w języku przezeń kompilowanym, pomimo że zarówno Pascal, jak i C, był chętnie wybierany przy implementacji. Problem konstrukcji samokompilującego się kompilatora określa się mianem bootstrap – pierwszy kompilator musi być albo skompilowany kompilatorem napisanym w innym języku, albo (jak w przypadku kompilatora języka Lisp autorstwa Harta i Levina) kompilowany przez uruchomienie kompilatora w interpreterze.

Przebieg kompilacji 
Kompilacja to proces automatycznego tłumaczenia kodu źródłowego na kod wynikowy przez kompilator. Kompilacja jest przeważnie głównym etapem ogólniejszego procesu translacji, a tworzony w jej trakcie kod wynikowy jest przekazywany do innych programów, np. do konsolidatora (linkera). Możliwe jest również tłumaczenie do postaci zrozumiałej dla człowieka.

Określenie kompilacja używane jest zazwyczaj w kontekście tłumaczenia z języka wysokiego poziomu na język niskiego poziomu, natomiast tłumaczenie w odwrotnym kierunku to dekompilacja.

Na proces kompilacji składają się następujące etapy:
 wykonanie poleceń preprocesora
 analiza leksykalna
 analiza składniowa (ang. parsing)
 analiza semantyczna
 optymalizacja kodu wynikowego
 generacja kodu.

Trójetapowa struktura kompilatorów 

Niezależnie od rzeczywistej ilości faz w strukturze kompilatorów, fazy te mogę być podzielona na 3 etapy nazywane front-endem, middle-endem i back-endem. Front-end weryfikuje składnię i semantykę w zależności od danego języka programowania. Middle-end wykonuje optymalizacje kodu, które są niezależne od docelowej architektury procesora. Back-end wykonuje dalsze  analizy, transformacje i optymalizacje, które są specyficzne dla docelowej architektury procesora.

Przykład kompilatora 
Następujący program implementuje bardzo prosty jednoprzebiegowy kompilator napisany w języku C. Ten kompilator kompiluje wyrażenia zdefiniowane w notacji infiksowej do ONP, a także do asemblera. Kompilator realizuje strategię rekurencyjnego zagłębiania się w wyrażenie. Każde wywołanie funkcji odpowiada napotkaniu symbolu nieterminalnego należącego do gramatyki języka.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MODE_POSTFIX 	0
#define MODE_ASSEMBLY 	1

char lookahead;
int pos;
int	compile_mode;
char expression[20+1];

void error()
{
        printf("Syntax error!\n");
}

void match( char t )
{
        if( lookahead == t )
        {
                pos++;
                lookahead = expression[pos];
        }
        else
                error();
}

void digit()
{
        switch( lookahead )
        {
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
			if( compile_mode == MODE_POSTFIX )
				printf("%c", lookahead);
			else
				printf("\tPUSH %c\n", lookahead);

                        match( lookahead );
                        break;
                default:
                        error();
                        break;
        }
}

void term()
{
        digit();
        while(1)
        {
                switch( lookahead )
                {
                        case '*':
                                match('*');
                                digit();

                                printf( "%s", compile_mode == MODE_POSTFIX ? "*"
					: "\tPOP B\n\tPOP A\n\tMUL A, B\n\tPUSH A\n");

                                break;
                        case '/':
                                match('/');
                                digit();

                                printf( "%s", compile_mode == MODE_POSTFIX ? "/"
					: "\tPOP B\n\tPOP A\n\tDIV A, B\n\tPUSH A\n");
                                break;
                        default:
                                return;
                }
        }
}

void expr()
{
        term();
        while(1)
        {
                switch( lookahead )
                {
                        case '+':
                                match('+');
                                term();

                                printf( "%s", compile_mode == MODE_POSTFIX ? "+"
					: "\tPOP B\n\tPOP A\n\tADD A, B\n\tPUSH A\n");
                                break;
                        case '-':
                                match('-');
                                term();

                                printf( "%s", compile_mode == MODE_POSTFIX ? "-"
					: "\tPOP B\n\tPOP A\n\tSUB A, B\n\tPUSH A\n");
                                break;
                        default:
                                return;
                }
        }
}

int main ( int argc, char** argv )
{
        printf("Please enter an infix-notated expression with single digits:\n\n\t");
        scanf("%20s", expression);

        printf("\nCompiling to postfix-notated expression:\n\n\t");
	compile_mode = MODE_POSTFIX;
        pos = 0;
        lookahead = *expression;
        expr();

        printf("\n\nCompiling to assembly-notated machine code:\n\n");
        compile_mode = MODE_ASSEMBLY;
        pos = 0;
        lookahead = *expression;
        expr();

        return 0;
}

Przykład możliwego wyjścia, wygenerowanego podczas wykonania powyższego programu:

Please enter an infix-notated expression with single digits:

        3-4*2+2

Compiling to postfix-notated expression:

        342*-2+

Compiling to assembly-notated machine code:

        PUSH 3
        PUSH 4
        PUSH 2
        POP B
        POP A
        MUL A, B
        PUSH A
        POP B
        POP A
        SUB A, B
        PUSH A
        PUSH 2
        POP B
        POP A
        ADD A, B
        PUSH A

Kompilatory w edukacji 
Konstrukcja kompilatorów i optymalizacja kompilatorów są wykładane na uniwersytetach jako część programu studiów informatycznych. Takie kursy są zazwyczaj uzupełniane implementowaniem przez studentów kompilatora pewnego edukacyjnego języka programowania. Dobrze udokumentowanym przykładem jest kompilator języka PL/0, który był pierwotnie używany przez Niklausa Wirtha do nauczania metod konstrukcji kompilatorów w latach siedemdziesiątych.
Pomimo swojej prostoty kompilator PL/0 wprowadził do terminologii kilka pojęć, które odtąd stały się standardami w nauczaniu:

 Użycie Program Development by Stepwise Refinement
 Użycie recursive descent parser
 Użycie notacji EBNF do specyfikowania składni języka
 Użycie P-code podczas generowania przenośnego kodu wynikowego
 Użycie T-diagramów do formalnego opisu problemu bootstrappingu

Zobacz też 

 transpilator
 autocoder
 dekompilator
 generacja kodu
 JIT (just-in-time compilation)
 kompilator skrośny (cross compiler)
 translator

Przypisy

Linki zewnętrzne 
 Podstawy kompilatorów (materiały dydaktyczne MIMUW na studia informatyczne I stopnia)
 Metody realizacji języków programowania (materiały dydaktyczne MIMUW na studia informatyczne II stopnia)
 Teoria Kompilacji (materiały dydaktyczne WIEiT na studia informatyczne I stopnia)