Kompilator

Schemat blokowy kompilatora wieloprzebiegowego

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:

  1. wykonanie poleceń preprocesora
  2. analiza leksykalna
  3. analiza składniowa (ang. parsing)
  4. analiza semantyczna
  5. optymalizacja kodu wynikowego
  6. generacja kodu.

Trójetapowa struktura kompilatorów

Główne etapy struktury 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:

  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 problemu bootstrappingu

Zobacz też

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

Przypisy

  1. ↑ 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

Media użyte na tej stronie

Compiler design.svg
Autor: Pronesto, Licencja: CC BY-SA 3.0
Three phase compiler structure design.
  • Front end is specific for each source language
  • Middle end performs optimizations, without caring about the source language nor the target platform
  • Back end is target dependent
An example of a compiler infrastructure implemented in this way is the LLVM project.
Multi-passcompiler.png
Schemat kompilatora wielo-przebiegowego