Dark Mode

Przejdz do zawartosci

Kompilator

Z Wikipedii, wolnej encyklopedii
Schemat blokowy kompilatora wieloprzebiegowego

Kompilator - program sluzacy do automatycznego tlumaczenia kodu napisanego w jednym jezyku (jezyku zrodlowym) na rownowazny kod w innym jezyku (jezyku wynikowym)[1]. Proces ten nazywany jest kompilacja. W informatyce kompilatorem nazywa sie najczesciej program do tlumaczenia kodu zrodlowego w jezyku programowania na jezyk maszynowy. Niektore z nich tlumacza najpierw do jezyka asemblera, a ten na jezyk maszynowy jest tlumaczony przez asembler[2].

Roznica pomiedzy kompilatorem a asemblerem polega na tym, iz kazde polecenie jezyka programowania moze zostac rozbite na wiele podpolecen jezyka maszynowego (przy czym nowoczesne asemblery rowniez posiadaja skladnie umozliwiajaca zapis wielu polecen maszynowych jako jednego polecenia kodu zrodlowego oraz opcje optymalizacji kodu). Kompilatory moga miec mozliwosc automatycznej alokacji pamieci dla zmiennych, implementowania struktur kontrolnych lub procedur wejscia-wyjscia.

Stosowanie kompilatorow ulatwia programowanie (programista nie musi znac jezyka maszynowego) i pozwala na wieksza przenosnosc kodu pomiedzy platformami.

Zarys historyczny

[edytuj | edytuj kod]

Oprogramowanie pierwszych komputerow bylo przez wiele lat pisane jedynie w jezyku asemblera. Jezyki wysokiego poziomu nie byly stosowane, dopoki korzysci z uzycia tych samych programow na roznych rodzajach procesorow nie staly sie istotnie wieksze od kosztu pisania kompilatora. Bardzo ograniczona pojemnosc pamieci wczesnych komputerow sprawiala rowniez wiele problemow przy implementacji kompilatorow.

Pod koniec lat 50. zaproponowano po raz pierwszy maszynowe jezyki programowania, w nastepstwie czego powstaly pierwsze, eksperymentalne kompilatory. Pierwszy kompilator napisala Grace Hopper w 1952 dla jezyka A-0. Uznaje sie, ze ekipa FORTRAN z IBM, prowadzona przez Johna Backusa, wprowadzila do uzycia pierwszy kompletny kompilator w 1957. W 1960 COBOL byl jednym z pierwszych jezykow, ktory mozna bylo kompilowac na roznych architekturach.

W wielu dziedzinach zastosowan idea programowania wysokopoziomowego szybko sie przyjela. Rozszerzanie funkcjonalnosci zapewnianej przez nowsze jezyki programowania oraz wzrastajaca zlozonosc architektur systemow komputerowych spowodowaly, ze kompilatory stawaly sie coraz bardziej skomplikowane.

Wczesne kompilatory byly pisane w asemblerze. Pierwszym kompilatorem zdolnym do skompilowania wlasnego kodu zrodlowego napisanego w jezyku wysokiego poziomu byl kompilator jezyka Lisp, stworzony przez Harta i Levina z MIT w 1962. Od lat siedemdziesiatych stalo sie powszechna praktyka implementowanie kompilatora w jezyku przezen kompilowanym, pomimo ze zarowno Pascal, jak i C, byl chetnie wybierany przy implementacji. Problem konstrukcji samokompilujacego sie kompilatora okresla sie mianem bootstrap - pierwszy kompilator musi byc albo skompilowany kompilatorem napisanym w innym jezyku, albo (jak w przypadku kompilatora jezyka Lisp autorstwa Harta i Levina) kompilowany przez uruchomienie kompilatora w interpreterze.

Przebieg kompilacji

[edytuj | edytuj kod]

Kompilacja to proces automatycznego tlumaczenia kodu zrodlowego na kod wynikowy przez kompilator. Kompilacja jest przewaznie glownym etapem ogolniejszego procesu translacji, a tworzony w jej trakcie kod wynikowy jest przekazywany do innych programow, np. do konsolidatora (linkera). Mozliwe jest rowniez tlumaczenie do postaci zrozumialej dla czlowieka.

Okreslenie kompilacja uzywane jest zazwyczaj w kontekscie tlumaczenia z jezyka wysokiego poziomu na jezyk niskiego poziomu, natomiast tlumaczenie w odwrotnym kierunku to dekompilacja.

Na proces kompilacji skladaja sie nastepujace etapy:

  1. wykonanie polecen preprocesora
  2. analiza leksykalna
  3. analiza skladniowa (ang. parsing)
  4. analiza semantyczna
  5. optymalizacja kodu wynikowego
  6. generowanie kodu.

Trojetapowa struktura kompilatorow

[edytuj | edytuj kod]
Glowne etapy struktury kompilatorow

Niezaleznie od rzeczywistej ilosci faz w strukturze kompilatorow, fazy te moge byc podzielona na 3 etapy nazywane front-endem, middle-endem i back-endem. Front-end weryfikuje skladnie i semantyke w zaleznosci od danego jezyka programowania. Middle-end wykonuje optymalizacje kodu, ktore sa niezalezne od docelowej architektury procesora. Back-end wykonuje dalsze analizy, transformacje i optymalizacje, ktore sa specyficzne dla docelowej architektury procesora.

Przyklad kompilatora

[edytuj | edytuj kod]

Nastepujacy program implementuje bardzo prosty jednoprzebiegowy kompilator napisany w jezyku C. Ten kompilator kompiluje wyrazenia zdefiniowane w notacji infiksowej do ONP, a takze do asemblera. Kompilator realizuje strategie rekurencyjnego zaglebiania sie w wyrazenie. Kazde wywolanie funkcji odpowiada napotkaniu symbolu nieterminalnego nalezacego do gramatyki jezyka.

#include
#include
#include

#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;
}

Przyklad mozliwego wyjscia, wygenerowanego podczas wykonania powyzszego 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

[edytuj | edytuj kod]

Konstrukcja i optymalizacja kompilatorow sa wykladane na uniwersytetach jako czesc programu studiow informatycznych. Takie kursy sa zazwyczaj uzupelniane implementowaniem przez studentow kompilatora pewnego edukacyjnego jezyka programowania. Dobrze udokumentowanym przykladem jest kompilator jezyka PL/0, ktory byl pierwotnie uzywany przez Niklausa Wirtha do nauczania metod konstrukcji kompilatorow w latach siedemdziesiatych. Pomimo swojej prostoty kompilator PL/0 wprowadzil do terminologii kilka pojec, ktore odtad staly sie standardami w nauczaniu:

  1. Uzycie Program Development by Stepwise Refinement
  2. Uzycie recursive descent parser
  3. Uzycie notacji EBNF do specyfikowania skladni jezyka
  4. Uzycie P-code podczas generowania przenosnego kodu wynikowego
  5. Uzycie T-diagramow do formalnego opisu problemu bootstrappingu

Zobacz tez

[edytuj | edytuj kod]
Zobacz haslo kompilator w Wikislowniku

Przypisy

[edytuj | edytuj kod]
  1. | A.V. Aho, R. Sethi, J.D. Ullman, Kompilatory. Reguly, metody i narzedzia, WNT, Warszawa 2002, ISBN 83-204-2656-1.
  2. | Alfred V.A.V. Aho Alfred V.A.V. i inni red., Compilers: principles, techniques, & tools, wyd. 2. ed., Pearson internat. ed, Boston Munich: Pearson Addison-Wesley, 2007, s. 3-12, ISBN 978-0-321-48681-3 [dostep 2025-03-24] .

Linki zewnetrzne

[edytuj | edytuj kod]