MRJP Wykład 4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Klasyfikacja realizacji języków programowania

Realizacje języków programowania można podzielić na kilka kategorii:

  • kompilator - tłumaczy program w języku źródłowym na program w języku docelowym
  • translator - jak wyżej, ale tłumaczenie konstrukcji języka źródłowego na konstrukcje języka docelowego odbywa się w dużym stopniu jeden do jednego
  • interpreter - wykonuje program posługując się jakąś jego reprezentacją

Podział ten nie jest ścisły - wiele realizacji można zaliczyć do kilku kategorii. W szczególności, realizacje języków programowania tradycyjnie nazywane interpreterami składają się zwykle z dwóch części: program źródłowy jest kompilowany do postaci pośredniej, która następnie trafia na wejście interpretera.

Język docelowy, maszyny wirtualne

Język docelowy kompilatora zwykle nie pokrywa się z językiem maszyny rzeczywistej, na której programy mają działać. Po pierwsze, niektórych cech maszyny kompilator nie wykorzystuje. Ponadto, ponieważ podczas wykonania programu mogą być potrzebne operacje, które nie są realizowane bezpośrednio przez sprzęt (np. zarządzanie pamięcią), wygenerowany kod jest uzupełniany o tzw. system czasu wykonania (ang. run-time system), który można traktować jako rozszerzenie maszyny docelowej.

Często stosowanym rozwiązaniem jest też tworzenie maszyny docelowej od podstaw, z myślą o realizacji konkretnego języka. Instrukcje tej maszyny zwykle nie są bezpośrednio rozumiane przez sprzęt, więc nazywamy ją maszyną wirtualną (abstrakcyjną). Kod wygenerowany na maszynę wirtualną może być wykonywany przez interpreter lub przekazany na wejście kolejnego kompilatora, który przetłumaczy go na kod maszyny rzeczywistej. Spotyka się też rozwiązania pośrednie - połączenie interpretera i kompilatora uruchamianego podczas wykonania programu, by przetłumaczyć fragmenty szczególnie istotne dla jego efektywności. Technika ta nosi nazwę JIT (ang. just-in-time compilation).

Maszynę abstrakcyjną projektujemy tak, by jak najbardziej uprościć generator kodu a jednocześnie umożliwić w miarę łatwą i efektywną realizację na maszynie rzeczywistej.

Zaprojektowanie uniwersalnej maszyny wirtualnej, mimo wielu prób, jak dotąd nie udało się. Te, które powstają, są przeznaczone dla realizacji określonego języka lub rodziny podobnych języków, np. maszyny wirtualne Javy, Smalltalka, Prologu. Maszynę stworzoną w latach 70 dla realizacji języka Pascal nazywano p-code i określenie to bywa do dziś używane jako synonim języka maszyny wirtualnej. W p-code i maszynach do niej podobnych większość instrukcji pobiera argumenty ze stosu i tam odkłada wynik. Maszyny te nazywamy maszynami stosowymi (ang. stack machine) w odróżnieniu od maszyn wykorzystujących do tego celu rejestry (ang. register machine).

Stosowanie maszyn wirtualnych

Głównym powodem stosowania maszyn wirtualnych w realizacjach języków programowania jest uproszczenie kompilatora. Znacznie łatwiej napisać generator kodu na zaprojektowaną przez nas maszynę, niż generator kodu maszynowego rzeczywistego procesora. Szczególnie dobrze widać to na przykładzie procesorów x86, których nieregularna lista instrukcji i trybów adresowania połączona z bardzo małą liczbą dostępnych rejestrów sprawia wiele problemów autorom generatorów kodu.

Oprócz względnej łatwości implementacji generatora kodu, zastosowanie maszyny wirtualnej w realizacji języka programowania ma i inne zalety - ułatwia przenoszenie kompilatora, a nawet wygenerowanego przez niego kodu, na inne systemy, ułatwia też kontrolowanie programu podczas jego wykonania.

Maszyn wirtualnych zwykle nie stosuje się w realizacji języka programowania, gdy bardzo zależy nam na efektywności kodu wynikowego. Choć istnieją techniki efektywnej realizacji maszyny wirtualnej, jak np. wspomniana wyżej JIT, autorzy kompilatorów sięgaja raczej po klasyczny model kompilacji, w którym generuje się kod pośredni, który następnie podlega optymalizacji.

Przykład prostej maszyny wirtualnej

Najprostszym modelem maszyny wirtualnej dla realizacji języków proceduralnych, takich jak Pascal lub C, jest maszyna stosowa. W przykładach w dalszej części tekstu będziemy się posługiwali maszyną wirtualną, którą nazwiemy Naszą Maszyną Wirtualną (w skrócie NMW). Poniżej przedstawiamy jej definicję.

Pamięć NMW składa się ze słów, z których każde mieści liczbę całkowitą lub adres. Adresy kolejnych słów w pamięci różnią się o 1.

W pamięci znajduje się stos, który rośnie w kierunku malejących adresów. W chwili rozpoczęcia wykonania programu stos jest pusty.

Dwa słowa w pamięci, których adresy będziemy oznaczali symbolicznie SP i FP, mają specjalne znaczenie. W komórce o adresie SP jest zapisany wskaźnik czubka stosu, będący adresem wartości znajdującej się aktualnie na czubku stosu. Zawartość tej komórki jest automatycznie modyfikowana przez instrukcje maszyny. Komórką pamięci o adresie FP będziemy się posługiwali podczas realizacji mechanizmu wywołania i powrotu z funkcji/procedury.

Oto instrukcje rozpoznawane przez NMW:

  • CONST stała - odkłada na stos wartość stałej przekazanej jako argument
  • LOAD - odkłada na stos wartość pobraną spod adresu zdjętego z czubka stosu
  • STORE - zdejmuje ze stosu adres, następnie zdejmuje ze stosu wartość i wkłada ją pod ten adres
  • ADD - dodawanie, zdejmuje ze stosu najpierw prawy a następnie lewy argument i odkłada na stos ich sumę
  • SUB - jak wyżej, ale liczy różnicę
  • MUL - jak wyżej, ale liczy iloczyn
  • DIV - jak wyżej, ale liczy iloraz
  • DUP - odkłada na stos wartość znajdującą się na czubku stosu
  • DROP - usuwa wartość z czubka stosu
  • SWAP - zamienia kolejność dwóch wartości na czubku stosu
  • GOTO - zdejmuje ze stosu adres i skacze do instrukcji znajdującej się pod tym adresem
  • CALL - zdejmuje ze stosu adres i skacze do instrukcji znajdującej się pod tym adresem, na stos odkłada adres następnej instrukcji za instrukcją CALL
  • EQ - zdejmuje ze stosu dwie wartości i wkłada na stos wartość niezerową, jeśli wartości były równe, a zero, jeśli były różne
  • NE - jak wyżej, ale sprawdza, czy wartości są różne
  • LT - jak wyżej, ale sprawdza, czy wartość pod czubkiem stosu jest mniejsza od wartości na czubku stosu
  • LE - jak wyżej, ale sprawdza, czy mniejsza lub równa
  • GT - jak wyżej, ale sprawdza, czy większa
  • GE - jak wyżej, ale spreawdza, czy większa lub równe
  • IFTRUE - zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była reprezentacją prawdy (wartość niezerowa)
  • IFFALSE - zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była reprezentacją fałszu (czyli zerem)
  • READ - wczytuje z wejścia liczbę całkowitą i wkłada jej wartość na stos
  • WRITE - zdejmuje wartość z czubka stosu i wypisuje ją na wyjście
  • STOP - zatrzymuje pracę maszyny

W dalszej części tego tekstu, zapisując kod, będziemy pomijali słowo CONST w instrukcji odkładającej na stos stałą. Dzięki temu każda instrukcja będzie zapisywana jako pojedyncze słowo w tekście programu, co ułatwi czytanie kodu

Nie zakładamy, że każda instrukcja musi się znajdować w odzielnym wierszu kodu źródłowego. Tam, gdzie to poprawi czytelność, w jednym wierszu zapiszemy kilka instrukcji.

Ponadto, zapisując kod będziemy się posługiwali adresami symbolicznymi (etykietami) instrukcji. Miejsce w kodzie, które chcemy oznaczyć, poprzedzimy identyfikatorem z dwukropkiem. Adres tego miejsca będzie dostępny za pośrednictwem użytego identyfikatora.

Generowanie kodu

Po zakończeniu analizy programu w języku źródłowym rozpoczyna się synteza programu w języku docelowym. Głównym modułem kompilatora biorącym w niej udział jest generator kodu tworzący np. na podstawie drzewa struktury i tablicy symboli, reprezentację programu w języku maszyny docelowej. Zwykle nie jest to gotowy program wykonywalny na maszynie rzeczywistej. Generuje się np. kod w postaci struktury ułatwiającej pracę optymalizatorowi. Poza tym często, by uprościć generator kodu lub zapewnić przenośność, za maszynę docelową obieramy maszynę abstrakcyjną a nie maszynę rzeczywistą, na której będzie uruchamiany program powstały w rezultacie kompilacji.

Najprostszy algorytm generacji kodu opiera się na schemacie translacji sterowanej składnią. Generator kodu ma postać rekurencyjnej procedury, która rozwiązuje problem tłumaczenia pojedynczej konstrukcji składniowej, zwykle reprezentowanej przez jeden węzeł w drzewie struktury. Jeśli węzeł ten nie jest liściem, jego poddrzewami zajmują się rekurencyjne wywołania.

Realizacja wyrażeń

Maszyna stosowa może wykonywać operacje arytmetyczne wyłącznie na wartościach znajdujących się na stosie. Jedynym sensownym sposobem realizacji wyrażeń arytmetycznych jest więc obliczenie obu argumentów (wyniki będą na stosie) a następnie wykonanie na nich operacji, np. „W1+W2” tłumaczymy jako:

         [W1]
         [W2]
         ADD 

Kosztem, jaki płacimy za łatwość generacji kodu dla wyrażeń na maszynę stosową jest nieefektywność kodu. Maszyny rzeczywiste mają zwykle możliwość operowania na wartościach w rejestrach lub pod wskazanymi adresami w pamięci. Na maszynie stosowej z tego nie korzystamy.

Realizacja przypisania

Kod dla przypisania, gdy po lewej stronie jest zwykła zmienna, składa się z instrukcji liczących wartość wyrażenia z prawej strony i z instrukcji STORE zdejmującej wynik na zmienną, np. „x:=E” tłumaczymy na:

         [E]
         adres_x STORE

gdzie adres_x reprezentuje adres zmiennej x w pamięci.

Jeśli język pozwala na złożona postać lewej strony przypisania (elementy tablicy, rekordu itp.), traktujemy ją jak wyrażenie, którego wartość (tzw. l-wartość) określa lokację w pamięci, w którą wpisujemy wartość prawej strony (r-wartość).

Realizacja instrukcji warunkowych i pętli

Teraz przejdziemy do omówienia sposobu realizacji konstrukcji, które wymagają bardziej złożonego schematu przepływu sterowania. Skupimy się na realizacji instrukcji warunkowych i pętli.

Realizacja pętli typu "repeat ... until ..."

Spośród wszystkich rodzajów pętli, najłatwiej będzie nam zrealizować pętlę „repeat L until E”:

tresc:
         [L]
         [E]
         tresc IFFALSE

Realizacja instrukcji warunkowej "if ... then ..."

Najprostszą formą instrukcji warunkowej jest „if E then I”, którą możemy tłumaczyć na:

         [E]
         koniec IFFALSE
         [I]
koniec:

Realizacja instrukcji warunkowej "if ... then ... else ..."

Dla instrukcji warunkowej „if E then I1 else I2” naturalnym tłumaczeniem jest:

         [E]
         po_else IFFALSE
         [I1]
         koniec GOTO
po_else:
         [I2]
koniec:

Realizacja pętli "while ... do ..."

Dla pętli "while ... do ..." można podać trzy różne sposoby realizacji, z których każdy jest sensowny:

warunek:
         [E]
         koniec IFFALSE
         [I]
         warunek GOTO
koniec:
         warunek GOTO
tresc:
         [I]
warunek:
         [E]
         tresc IFTRUE
         [E]
         koniec IFFALSE
tresc:
         [I]
         [E]
         tresc IFTRUE
koniec:

Pierwszy wariant jest efektywny, jeśli często warunek pętli jest od razu fałszywy a wariant drugi, jeśli do treści pętli zwykle wchodzi się przynajmniej raz. Wariant trzeci łączy oba rozwiązania, ale daje dłuższy kod (wyrażenie występuje dwa razy), co może spowodować, że będzie działał wolniej.