Metody realizacji języków programowania/MRJP Wykład 4

Autor: Artur Zaroda (zaroda@mimuw.edu.pl)

Wprowadzenie do maszyn wirtualnych

Rodzaje realizacji języków programowania

Wspólnym elementem realizacji języków programowania jest tzw. przód (ang. front-end), który zajmuje się rozpoznawaniem programu w języku źródłowym. Rezultat jego pracy, np. w formie drzewa struktury uzupełnionego o tablicę symboli, trafia na wejście tzw. tyłu (ang. back-end), którego zadaniem jest umożliwienie wykonania rozpoznanego programu.

Ze względu na sposób pracy tego drugiego etapu, 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ę 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 kompilatora a 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 procesora wykonującego program kompilator nie wykorzystuje. W takiej sytuacji można powiedzieć, że maszyna docelowa jest podzbiorem maszyny rzeczywistej wykonującej program.

Po drugie, podczas pracy program musi wykonywać operacje związane np. z zarządzaniem pamięcią czy wejściem-wyjściem, które nie mają swoich odpowiedników na liście instrukcji rozumianych przez procesor. Dlatego też generowany kod jest uzupełniany o tzw. system czasu wykonania (ang. run-time system), który można uznać za rozszerzenie maszyny docelowej.

Autor kompilatora ma więc możliwość odrzucenia pewnych cech maszyny docelowej i uzupełnienia jej o inne. Może też posłużyć się zupełnie nowym modelem maszyny, która nie będzie miała bezpośredniego związku z żadną maszyną rzeczywistą. Konstrukcję taką nazywamy maszyną wirtualną (używa się też określenia "maszyna abstrakcyjna").

Głównym powodem stosowania maszyny wirtualnej do realizacji języka programowania jest chęć 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. Między innymi ułatwia przenoszenie kompilatora - a nawet wygenerowanego przez niego kodu - na inne systemy, ułatwia też kontrolowanie programu podczas jego wykonywania.

Zwykle nie stosuje się maszyn wirtualnych, gdy efektywność kodu wynikowego jest dla nas ważniejsza od łatwości realizacji języka programowania.

Projektowanie maszyn wirtualnych

Maszynę wirtualną projektujemy tak, by jak najbardziej uprościć generator kodu. Choć nie musi ona mieć żadnego związku z maszyną rzeczywistą, projektując ją, powinniśmy też brać pod uwagą łatwość i efektywność jej realizacji.

Mimo wielokrotnie podejmowanych prób, jak dotąd nie udało się zaprojektować uniwersalnej maszyny wirtualnej. Te, które powstają, są przeznaczone dla realizacji określonego języka lub rodziny podobnych języków, np. maszyny wirtualne Javy (tzw. JVM), Smalltalka, Prologu.

W latach siedemdziesiątych na potrzeby realizacji języka Pascal stworzono maszynę wirtualną nazywaną p-code. Nazwa ta do dziś bywa używana 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 takie nazywamy maszynami stosowymi (ang. stack machine). Stosowy model maszyny jest szczególnie przydatny w realizacjach języków proceduralnych. Po uzupełnieniu o niezbędne elementy można go też stosować w realizacjach języków obiektowych. Przykładem maszyny stosowej jest maszyna wirtualna Javy.

Wadą stosowego modelu maszyny wirtualnej jest brak możliwości efektywnego wykorzystania rejestrów rzeczywistego procesora wykonującego kod tak, by ograniczyć ilość operacji przesyłania wartości z i do pamięci. Można przyjąć, że wartość znajdująca się na wierzchołku stosu będzie przechowywana w wyróżnionym rejestrze a nie w pamięci. Rozszerzenie tego pomysłu na większą liczbę wartości, by wykorzystać kilka czy kilkanaście dostępnych rejestrów, jest jednak w praktyce zbyt trudne. Dlatego też jako alternatywę lub rozszerzenie modelu stosowego używa się czasem tzw. maszyn rejestrowych (ang. register machine), w których argumenty operacji przechowywane są w (wirtualnych) rejestrach. Ponieważ nadal mamy tu do czynienia z maszyną wirtualną, nie jesteśmy w tym przypadku ograniczeni liczbą rejestrów rzeczywistego procesora. Możemy np. przyjąć, że nasza maszyna ma 256 rejestrów.

Przykład maszyny wirtualnej

Najprostszym modelem maszyny wirtualnej dla realizacji języków proceduralnych, takich jak Pascal lub C, jest maszyna stosowa. 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 stosu, który jest adresem wartości znajdującej się aktualnie na wierzchołku 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 ze 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 wierzchołku stosu

DROP

usuwa wartość z wierzchołka stosu

SWAP

zamienia kolejność dwóch wartości na wierzchołku 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 po instrukcji CALL

EQ

zdejmuje ze stosu dwie wartości i wkłada na stos wartość niezerową, jeśli wartości były równe, lub 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 wierzchołkiem stosu jest mniejsza od wartości na wierzchołku 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 sprawdza, czy większa lub równa

IFTRUE

zdejmuje ze stosu adres a potem wartość i skacze pod ten adres, jeśli wartość była reprezentacją prawdy (wartość niezerowa)

IFFALSE

zdejmuje ze stosu adres a potem 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ść ze 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ść, możemy w jednym wierszu zapisać 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.

Pamięć maszyny wirtualnej

Podczas wykonania programu w pamięci znajduje się jego kod. Ze względów bezpieczeństwa można go umieścić w obszarze chronionym przed zapisem.

Dane programu dzielimy na:

automatyczne

Ich czas życia jest wyznaczony przez czas działania procedury/funkcji. Dane te umieszczane są zwykle na stosie. Więcej na ten temat będzie w następnym wykładzie.

kontrolowane

Mogą powstawać i ginąć, na żądanie programisty, w dowolnym momencie wykonania programu. Dane te umieszczane są na stercie (ang. heap), której obsługa jest tematem oddzielnego wykładu.

statyczne

Istnieją przez cały czas wykonania programu (np. stałe).

Na dane należące do każdej z tych kategorii przeznaczamy zwykle oddzielny obszar pamięci.

Sposób reprezentacji danych zależy tylko od ich typu, nie od miejsca, w którym się znajdują. Liczba całkowita w pamięci będzie wyglądała tak samo na stosie jak i na stercie.

Wpływ na reprezentację danych mają również cechy realizowanego języka programowania. Języki z typami dynamicznymi wymagają, by dane w pamięci zawierały informację o typie. W przypadku języków z typami statycznymi, których realizację będziemy omawiali w dalszej części tego wykładu, informacja o typie znajduje się tylko w kodzie źródłowym.

Reprezentacja danych

Decydując o sposobie reprezentacji danych w pamięci maszyny wirtualnej mamy do wyboru:

• zbudować reprezentację od podstaw

• skorzystać z reprezentacji obowiązującej na maszynie rzeczywistej, na której będzie uruchamiany kod maszyny wirtualnej

Pierwsze rozwiązanie daje nam większą swobodę ustalania, jak programy będą działały. Pozwala też na osiągnięcie pełnej przenośności kodu maszyny wirtualnej.

Główną zaletą rozwiązania drugiego jest łatwość implementacji.

Liczby całkowite

Współczesne maszyny rzeczywiste mają wbudowaną obsługę liczb całkowitych z pewnego ograniczonego przedziału. Powszechnie stosowana jest reprezentacja w kodzie uzupełnieniowym do dwójki a wartości zapisywane są na 16, 32 lub 64 bitach.

Jeśli zdecydujemy się zbudować samodzielnie reprezentację liczb całkowitych, możemy sięgnąć po reprezentację, która nie nakłada ograniczeń na liczby całkowite. Liczba całkowita byłaby reprezentowana jako ciąg cyfr, np. w układzie o podstawie 256.

Jeśli nasz program często będzie wczytywał i wypisywał liczby, możemy skorzystać z reprezentacji w postaci ciągu cyfr dziesiętnych.

Liczby rzeczywiste

Wiele maszyn potrafi sprzętowo obsługiwać liczby rzeczywiste w reprezentacji zmiennopozycyjnej. Realizacja maszyny wirtualnej może skorzystać z tego mechanizmu lub wykonywać obliczenia na wartościach rzeczywistych na drodze programowej. W tym drugim przypadku, alternatywą dla reprezentacji zmiennopozycyjnej może być reprezentacja stałopozycyjna.

Wartości typów wyliczeniowych

Stałe typu wyliczeniowego numerujemy (np. od 0) i reprezentujemy jak liczby całkowite.

Wartości logiczne

Do zapamiętania wartości logicznej wystarczy jeden bit. Ponieważ jednak dostęp do pojedyńczych bitów jest kłopotliwy, zwykle na wartość logiczną przeznaczamy jedną komórkę pamięci maszyny. Fałsz zapisujemy wówczas jako ciąg bitów 0 a prawdę jako ciąg 1 lub dowolny układ bitów, w którym jest choć jedna 1.

Napisy

Reprezentacja napisów zależy od operacji, które chcemy efektywnie realizować. Można się posługiwać adresem napisu a długość umieścić na początku tekstu lub zakończyć napis wyróżnionym znakiem (np. o kodzie 0). Inne możliwości, to np. reprezentacja w postaci pary <adres,długość> (stały koszt pobrania fragmentu napisu) lub pamiętanie znaków napisu na liście (stały koszt sklejania napisów).

Zbiory

Jeśli dziedzina, której elementy należą do zbioru jest mała (w Pascalu jest ograniczenie - nie więcej, niż 256 elementów), zbiór reprezentuje tzw. wektor charakterystyczny. Dla każdej wartości z dziedziny mamy jeden bit mówiący, czy jest ona w zbiorze. Działania na zbiorach realizujemy operacjami na ciągach bitów – przecięcie to bitowy AND, suma to OR itd.

Jeśli dziedzina, której elementy mogą należeć do zbioru jest duża, używamy list, drzew itp.

Rekordy

Rekord jest reprezentowany przez obszar pamięci, w którym znajdują się wartości poszczególnych pól. Jeśli wymaga tego maszyna, na której program będzie wykonywany, pomiędzy polami pozostawiamy odpowiednie wyrównanie (ang. alignment) tak, by wartości znalazły się pod właściwymi adresami (np. liczba całkowita na niektórych maszynach musi mieć w pamięci adres parzysty).

Tablice

Tablica jednowymiarowa jest w pamięci reprezentowana przez ciąg elementów. Np. tablica o deklaracji:

var t:array [100..1000] of integer;

zajmie obszar pamięci, w którym zmieści się 901 liczb całkowitych. Będzie tam kolejno wartość t[100], wartość t[101] itd.

Tablica dwuwymiarowa może być reprezentowana jak jednowymiarowa tablica jednowymiarowych tablic. W pamięci znajdą się kolejne wiersze tablicy, a w każdym elementy z kolejnych kolumn.

Stosuje się też reprezentacje tablic umożliwiające zmianę rozmiaru istniejącej tablicy podczas działania programu.

Realizacja maszyny wirtualnej

Instrukcje maszyn wirtualnych zazwyczaj nie są bezpośrednio rozumiane przez sprzęt, choć spotyka się też projekty ich sprzętowej realizacji.

Najczęściej kod generowany na maszynę wirtualną jest zapisywany np. do pliku, a następnie trafia na wejście oddzielnego programu nazywanego interpreterem maszyny wirtualnej, który go wykonuje. Główną częścią interpretera jest pętla odczytująca kolejne instrukcje do wykonania. Wewnątrz tej pętli znajduje się instrukcja wyboru (case, switch) rozpoznająca i wykonująca instrukcję maszyny wirtualnej. Całość może wyglądać np. tak:

program interpreter_kodu_maszyny_wirtualnej;
... {deklaracje}
var
  pc   : integer; {licznik rozkazów}
  prog : array [0..N] of instrukcja; {interpretowany program}
  aktualna : instrukcja;
begin
  ... {wczytanie programu do tablicy prog}
  pc := 0;
  while true do begin
    aktualna := prog[pc];
    pc := pc + 1;
    case aktualna of
      ADD : ... {wykonanie instrukcji}
      ... {gałęzie case obsługujące pozostałe instrukcje}
    end
  end
end.

Gdyby okazało się, że efektywność tak zbudowanej realizacji nie jest dla nas wystarczająca, możemy sięgnąć po inne rozwiązania. Najprostszym byłoby przesłanie kodu maszyny wirtualnej generowanego przez nasz kompilator na wejście kolejnego kompilatora, który przetłumaczy go na kod maszyny rzeczywistej. Można też bezpośrednio połączyć oba kompilatory tak, by generator kodu kompilatora pierwszego nie tworzył instrukcji maszyny wirtualnej, lecz informował kompilator drugi, co chce wygenerować. Generator kodu kompilatora drugiego po otrzymaniu takiej informacji produkowałby kod maszyny rzeczywistej, który ma taki efekt, jaki powinna mieć aktualna instrukcja maszyny wirtualnej.

Na przykład instrukcję:

ADD

Naszej Maszyny Wirtualnej moglibyśmy przetłumaczyć na dwie instrukcje procesora Pentium (zapisane w składni AT&T):

popl %eax
addl %eax, (%esp)

W niektórych przypadkach na instrukcje maszyny docelowej można tłumaczyć nie pojedyncze instrukcje maszyny wirtualnej, lecz ich ciągi. Np. ciąg instrukcji:

FP LOAD 2 ADD LOAD

można, przy założeniu, że rolę rejestru FP maszyny wirtualnej będzie pełnił rejestr %ebp procesora, przetłumaczyć na:

pushl 8(%ebp)

Spotyka się też rozwiązania będące hybrydą interpretera i kompilatora - interpreter podczas wykonania programu uruchamia kompilator, by przetłumaczyć fragmenty kodu szczególnie istotne dla jego efektywności. Technika ta nosi nazwę JIT (ang. just-in-time compilation). Przy jej zastosowaniu, generując kod, możemy korzystać z informacji, które są dostępne podczas wykonania programu, np. informacji o tym, jak często, gdy wykonujemy daną instrukcję warunkową, warunek jest spełniony. Ta wiedza może nam umożliwić wybór bardziej efektywnego wariantu kodu i tym samym poprawić efektywność całego programu.

Jeśli stwierdzimy, że tłumaczenie instrukcji maszyny wirtualnej na instrukcje maszyny rzeczywistej, nawet z wykorzystaniem informacji dostępnych podczas działania programu, nie daje nam kodu wystarczająco efektywnego, musimy sięgnąć po inny sposób realizacji języka programowania. Klasyczny model kompilacji, w którym generuje się kod pośredni podlegający następnie optymalizacji, będzie tematem kolejnych wykładów.

Podstawy kompilacji na maszynę wirtualną

Budowa kompilatora generującego kod maszyny wirtualnej, który jest następnie interpretowany, jest często najłatwiejszym i najmniej pracochłonnym sposobem realizacji języka programowania.

Algorytm generatora kodu

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 generatora kodu.

Realizacja wyrażeń

Stałe

Dla danych występujących bezpośrednio w kodzie źródłowym programu, nazywanych też literałami, generujemy kod konstruujący odpowiednią wartość na stosie. W przypadku wartości typu integer na NMW będzie to jedna instrukcja CONST.

Np. dla wyrażenia postaci:

15

wygenerujemy kod:

          CONST 15

Alternatywnym rozwiązaniem jest wypełnienie podczas kompilacji obszaru pamięci wartościami stałych, a następnie sięganie do wartości tam zapisanych, jak do zmiennych.

Zmienne

Odwołanie do zmiennej w wyrażeniu wymaga sięgnięcia pod odpowiedni adres w odpowiednim obszarze pamięci (stos, sterta, obszar danych statycznych).

Dla zmiennej prostej:

x

wygenerujemy kod NMW:

          adres_x ; odkładamy adres zmiennej x na stos
          LOAD

Ustalenie adresu wartości będącej elementem zmiennej typu złożonego wymaga dodatkowych obliczeń.

Dla każdego pola rekordu kompilator może obliczyć jego przesunięcie w pamięci względem początku rekordu (pierwsze pole będzie miało przesunięcie 0, dla każdego kolejnego pola przesunięcie będzie sumą rozmiarów wcześniejszych pól).

Wyrażenie postaci:

r.x

gdzie r jest rekordem a x jego polem przetłumaczymy więc na:

          adres_r        ; odkłada na stos adres rekordu r
          przesunięcie_x ; odkłada na stos przesunięcie pola x w rekordzie
          ADD
          LOAD

Analogicznie postępujemy odwołując się do elementów tablicy. Trochę bardziej skomplikowany jest jednak sposób obliczania przesunięcia elementu względem początku tablicy. Jeśli mamy do czynienia z tablicą zadeklarowaną:

var t : array [d..g] of X

adres t[i] jest wartością wyrażenia:

adres_t+(i-d)*rozmiar_X

co daje nam, dla wyrażenia t[i], kod na NMW:

          adres_t    ; adres tablicy na stos
          i          ; obliczenie indeksu
          d          ; dolna granica indeksu
          SUB
          rozmiar_X  ; rozmiar jednego elementu na stos
          MUL
          ADD
          LOAD

Podane wcześniej wyrażenie możemy nieco zmodyfikować grupując te elementy, których wartość jest znana podczas kompilacji. Otrzymamy w rezultacie:

(adres_t-d*rozmiar_X)+i*rozmiar_X

Wartość wyrażenia w nawiasach możemy traktować jako adres fikcyjnego zerowego elementu tablicy. Gdy d jest równe 0 (tablica indeksowana od zera), wyrażenie to ma wartość adres_t. Gdy d jest niezerowe, wyrażenie liczymy podczas kompilacji. Ostatecznie otrzymamy nową postać kodu dla t[i]:

          zmodyfikowany_adres_t ; adres (fikcyjnego) t[0]
          i                     ; obliczenie indeksu
          rozmiar_X             ; rozmiar jednego elementu na stos
          MUL
          ADD
          LOAD

W przypadku szczególnym, gdy rozmiar elementu tablicy jest równy 1, jak dla liczb całkowitych na NMW, dostanimy kod:

          zmodyfikowany_adres_t ; adres (fikcyjnego) t[0]
          i                     ; obliczenie indeksu
          ADD
          LOAD

Dla tablic wielowymiarowych przedstawioną powyżej konstrukcję odpowiednio modyfikujemy.

Operacje arytmetyczne i relacyjne

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 

Tłumaczeniem:

x/(y-5)

będzie więc:

         adres_x
         LOAD
         adres_y
         LOAD
         5
         SUB
         DIV

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.

Operacje logiczne

Wyrażenia logiczne można liczyć tak jak arytmetyczne. Ponieważ często występują w instrukcjach warunkowych lub w pętlach, gdzie kierują przepływem sterowania, możliwa jest też inna realizacja, w której obliczenie wyrażenia zawsze kończy się skokiem w jeden z dwóch punktów w programie w zależności od tego, czy warunek był prawdziwy czy nie.

Jeśli założymy skrócone obliczanie wyrażeń (przerywamy, gdy znamy wynik), może w nich być wiele instrukcji skoku wykonujących się gdy wyrażenie jest prawdziwe lub nie. Nazwiemy je skokami dla prawdy i dla fałszu.

W tłumaczeniu instrukcji:

if E1 and E2 then I1 else I2

skoki dla prawdy z E1 powinny prowadzić do E2 a z E2 do I1. Skoki dla fałszu z E1 oraz E2 kierujemy do I2.

W tłumaczeniu instrukcji:

if E1 or E2 then I1 else I2

skoki dla prawdy z E1 oraz E2 kierujemy do I1, skoki dla fałszu z E1 do E2 a z E2 do I2.

W tłumaczeniu:

if not E then I1 else I2

z E dla fałszu skaczemy do I1 a dla prawdy do I2.

Np. tłumaczeniem:

if (a or b) and not c then I1 else I2

będzie:

        adres_a LOAD
        L1 IFFALSE
        L2 GOTO
L1:     adres_b LOAD
        L4 IFFALSE
        L2 GOTO
L2:     adres_c LOAD
        L3 IFFALSE
        L4 GOTO
L3:     [I1]            ; tu znajdzie się tłumaczenie I1
        L5 GOTO
L4:     [I2]            ; tu znajdzie się tłumaczenie I2
L5:

Jakość tego kodu można poprawić, zmieniając niektóre skoki warunkowe z IFFALSE na IFTRUE i usuwając instrukcje skoku, które prowadzą do następnej instrukcji. Po dokonaniu tych uproszczeń otrzymamy:

        adres_a LOAD
        L2 IFTRUE
        adres_b LOAD
        L4 IFFALSE
L2:     adres_c LOAD
        L4 IFTRUE
        [I1]            ; tu znajdzie się tłumaczenie I1
        L5 GOTO
L4:     [I2]            ; tu znajdzie się tłumaczenie I2
L5:

Realizacja instrukcji

Przypisanie

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ą. Przypisanie postaci:

zmienna := E

tłumaczymy więc na:

         [E]
         adres_zmiennej
         STORE

gdzie adres_zmiennej reprezentuje adres, pod którym w pamięci znajduje się wartość zmiennej, na którą przypisujemy.

Np. tłumaczeniem:

x:=y*z

będzie:

         adres_y
         LOAD
         adres_z
         LOAD
         MUL
         adres_x
         STORE

Podobnie realizujemy przypisania, po których lewej stronie występuje nie zmienna prosta, lecz złożone wyrażenie, reprezentujące np. odwołanie do elementu tablicy, pola rekordu itp. W wyniku obliczenia wyrażenia po lewej stronie przypisania otrzymamy nie jego wartość, jak to jest z wypadku wyrażenia po prawej stronie, lecz adres komórki pamięci, do której mamy wpisać wartość. Tłumaczenie instrukcji przypisania:

E := F

będzie więc miało postać:

         [F]
         [E]
         STORE

Pętla "repeat ... until ..."

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.

Spośród wszystkich rodzajów pętli najłatwiej będzie nam zrealizować pętlę:

repeat L until E

którą tłumaczymy na:

tresc:
         [L]
         [E]
         tresc
         IFFALSE

Np. tłumaczeniem:

repeat
  x:=x+2
until x>10

będzie:

tresc:
         adres_x
         LOAD
         2
         ADD
         adres_x
         STORE
         adres_x
         LOAD
         10
         GT
         tresc
         IFFALSE

Instrukcja warunkowa "if ... then ..."

Najprostszą formą instrukcji warunkowej jest:

if E then I

którą możemy tłumaczyć na:

         [E]
         koniec
         IFFALSE
         [I]
koniec:

Np. tłumaczeniem:

if x<0 then
  x:=0-x

będzie:

         adres_x
         LOAD
         0
         LT
         koniec
         IFFALSE
         0
         adres_x
         LOAD
         SUB
         adres_x
         STORE
koniec:

Instrukcja warunkowa "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:

Np. tłumaczeniem:

if x<y
  then z:=y
  else z:=x

będzie:

         adres_x
         LOAD
         adres_y
         LOAD
         LT
         po_else
         IFFALSE
         adres_y
         LOAD
         adres_z
         STORE
         koniec
         GOTO
po_else:
         adres_x
         LOAD
         adres_z
         STORE
koniec:

Pętla "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.

Np. tłumaczeniem:

while x>0 do
  x:=x-10

zgodnie z pierwszym z tych schematów będzie:

warunek:
         adres_x
         LOAD
         0
         GT
         koniec
         IFFALSE
         adres_x
         LOAD
         10
         SUB
         adres_x
         STORE
         warunek
         GOTO
koniec:

Instrukcja wyboru "case"

Najprostszy sposob realizacji instrukcji wyboru (case w Pascalu, switch w C) tłumaczy ją jak ciąg instrukcji warunkowych. Np. dla:

case x of
  1: I
  5: J
  7: K
end

generujemy kod taki, jak dla:

if x=1 then
  I
else if x=5 then
  J
else if x=7 then
  K

Rozwiązanie to jest nieefektywne, gdy instrukcja wyboru ma wiele gałęzi. W takiej sytuacji, zamiast ciągu instrukcji warunkowych możemy z nich zrobić zrównoważone drzewo binarne. Np.

case x of
  1: I1
  2: I2
  3: I3
  4: I4
  5: I5
  6: I6
  7: I7
  8: I8
end

tłumaczyć tak, jak:

if x<5 then
  if x<3 then
    if x<2 then begin
      if x=1 then
        I1
    end else
      I2
  else
    if x=3 then
      I3
    else
      I4
else
  if x<7 then
    if x=5 then
      I5
    else
      I6
  else
    if x=7 then
      I7
    else
      if x=8 then
        I8

Ten sposób tłumaczenia umożliwia wybór właściwej gałęzi w czasie proporcjonalnym do logarytmu z liczby gałęzi instrukcji wyboru. Jeśli zależy nam na rozwiązaniu jeszcze bardziej efektywnym, możemy się posłużyć skokiem wyliczonym. Tworzymy tablicę lub słownik, w którym dla każdej wartości, jaką może przyjąć zmienna x w instrukcji "case x of ... end" będzie zapisany adres początku kodu odpowiadającej jej gałęzi. Wykonanie instrukcji wyboru sprowadzi wówczas do odczytania adresu z odpowiedniej pozycji tej tablicy i wykonania skoku pod ten adres.