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)^[1]. 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:

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

↑ A.V. Aho, R. Sethi, J.D. Ullman, Kompilatory. Reguły, metody i narzędzia, WNT, Warszawa 2002, ISBN 83-204-2656-1.

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)

[autonazwa1-1] A.V. Aho, R. Sethi, J.D. Ullman, Kompilatory. Reguły, metody i narzędzia, WNT, Warszawa 2002, ISBN 83-204-2656-1.

[1]