Kompilator

Diagram działania wieloplatformowego oraz wielojęzykowego kompilatora.

Kompilator (ang. compiler) to 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 pojęciem kompilatora wyznacza się najczęściej program do tłumaczenia kodu źródłowego w języku programowania na język maszynowy. Pewne 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 opiera się na tym, iż każde polecenie języka programowania może zostać rozbite na wiele podpoleceń języka maszynowego (przy czym nowoczesne asemblery także posiadają składnię umożliwiającą zapis wielu poleceń maszynowych jako jednego polecenia kodu źródłowego oraz opcje optymalizacji kodu). Kompilatory potrafią posiadać możliwość automatycznej alokacji pamięci dla zmiennych, implementowania struktur kontrolnych albo procedur wejścia-wyjścia.

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

Prawdopodobnie pierwszym kompilatorem był Autocoder, napisany w roku 1952.

Popularnym zestawem kompilatorów jest GCC.

Proces kompilacji

 Osobny artykuł: Kompilacja (informatyka).

Kompilatory realizują zwykle wszystkie, albo przeważajaca ilość z następujących operacji:

• wykonanie poleceń preprocesora,
• analiza leksykalna,
• analiza składniowa (ang. parsing),
• analiza semantyczna,
• optymalizacja kodu wynikowego,
• generacja kodu.

Historia

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

Pod koniec lat pięćdziesiątych 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 roku, dla języka A-0. Uznaje się, że ekipa FORTRAN z IBM prowadzona przez Johna Bacusa wprowadziła do użycia pierwszy, kompletny kompilator w roku 1957. W roku 1960, COBOL był jednym z pierwszych języków, który da się było kompilować na wielorakich architekturach. [1]

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 assemblerze. Pierwszym kompilatorem zdolnym do skompilowania własnego kodu źródłowego napisanego w języku wysokiego poziomu był kompilator języka Lisp, zbudowany przez Harta oraz Levina z MIT w roku 1962 [2]. Od lat siedemdziesiątych stało się powszechną praktyką implementowanie kompilatora w języku przezeń kompilowanym, pomimo że zarówno Pascal jak oraz C były chętnie wybierane przy implementacji. Problem konstrukcji samokompilującego się kompilatora wyznacza się mianem Bootstrappingu — pierwszy taki kompilator musi być albo skompilowany kompilatorem napisanym w innym języku, albo (jak w przypadku kompilatora języka Lisp autorstwa Harta oraz Levina) kompilowany przez uruchomienie kompilatora w interpreterze.

Kompilatory w edukacji

Konstrukcja kompilatorów oraz optymalizacja kompilatorów, są wykładane na uniwersytetach jako cząstka programu studiów informatycznych. Takie kursy są zwykle 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 parę pojęć, które odtąd są standardami w nauczaniu:

1. Użycie Program Development by Stepwise Refinement
2. Użycie Recursive descent parser
3. Użycie notacji EBNF do specyfikowania składni języka
4. Użycie P-Code podczas generowania przenośnego kodu wynikowego
5. Użycie T-diagramów do formalnego opisu dylematu Bootstrappingu

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 assemblera. 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 expression20+1;
 
void error()
{
        printf("Syntax error!\n");
}
 
void match( char t )
{
        if( lookahead == t )
        {
                pos++;
                lookahead = expressionpos;            
        }
        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

Sprawdź też

Sprawdź hasło kompilator w Wikisłowniku

• Translator
• Interpreter
• JIT
• Generacja kodu
• Cross-kompilator
• Preprocesor

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)

Przypisy