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

Generowanie kodu pośredniego

Uważni czytelnicy zdążyli już z pewnością zauważyć, że celem działania kompilatora jest przekształcenie kodu źródłowego, napisanego w jakimś języku programowania, na kod docelowy - najczęściej jest to kod maszynowy lub kod dla jakiejś maszyny wirtualnej. Ponieważ proces ten bywa dość złożony, tradycyjnie dzieli się go na pewną liczbę prostszych czynności. Na początku przeprowadza się analizę leksykalną oraz składniową - jej wynikiem jest zazwyczaj jakaś forma drzewa wyprowadzenia. Potem sprawdza się poprawność programu, dokonuje optymalizacji aż w końcu - generuje kod docelowy. Każdą z używanych po drodze struktur danych przechowujących kod programu określa się mianem reprezentacji pośredniej.

Celem tego wykładu będzie zaprezentowanie pewnej konkretnej reprezentacji pośredniej, przydatnej w trakcie optymalizacji kodu, oraz sposobu jej generowania z opisanych wcześniej elementów - drzewa wyprowadzenia i tablicy symboli. Najpierw jednak dokonamy przeglądu różnych spotykanych reprezentacji pośrednich oraz ich zastosowań.

Po co są potrzebne reprezentacje pośrednie?

Formalnie rzecz biorąc, nie są one wcale konieczne. Nic nie stoi na przeszkodzie, żeby generować kod wynikowy bezpośrednio z tekstu źródłowego. Jednak już sama analiza tekstu programu zazwyczaj powoduje wytworzenie dwóch reprezentacji pośrednich - wynikiem analizy leksykalnej jest ciąg leksemów, wynikiem analizy składniowej - drzewo wyprowadzenia. Zgodnie z podanym wyżej określeniem są to już reprezentacje pośrednie. Jak z tego przykładu można wywnioskować, reprezentacje pośrednie dobiera się tak, by korzystające z nich elementy kompilatora mogły pracować efektywnie.

Przyjrzyjmy się przedstawionym poniżej reprezentacjom wyrażenia

x := a[p*4][q+1]

Drzewo wyprowadzenia

t1 := q + 1 t2 := t1 * 32 t3 := p * 4 t4 := t2 + t3 t5 := a[t4] x := t5 Kod czwórkowy

Pierwsza z reprezentacji, drzewo wyprowadzenia, pozwala łatwo stwierdzić, że w tym fragmencie programu chodzi o pobranie wartości z tablicy i przypisanie jej na zmienną. Łatwo jest np. sprawdzić czy zmienna a jest typu tablicowego, a p oraz q - typów umożliwiających adresowanie tablicy. Druga reprezentacja, kod pewnej maszyny wirtualnej, jak okaże się dalej, jest wygodna dla optymalizacji kodu, ale stwierdzenie, że kod ten to tylko odwołanie do tablicy nie jest już takie proste.

Tradycyjnie najwięcej mówi się o reprezentacjach i kodzie pośrednim w kontekście optymalizacji kodu programu. Z uwagi na charakter wielu optymalizacji wygodnie jest posługiwać się tu językiem zbliżonym do języka maszynowego, jednak abstrahując od wielu szczegółów, takich jak liczba rejestrów, dostępne tryby adresowania itp. Oczywiście istnieją też inne optymalizacje, które wygodniej prowadzić na kodzie wyższego poziomu.

Już w latach pięćdziesiątych stwierdzono, iż w analiza kodu programu zależy od języka programowania, a generacja kodu wynikowego - od własności maszyny docelowej. Proces optymalizacji kodu, przynajmniej dla pewnych zbiorów języków, może być jednak wspólny i może korzystać z tego samego języka pośredniego dla wszystkich kompilatorów.

Zyskiem ze wspólnego języka pośredniego jest to, że można podzielić kompilator na 3 części:

• pierwszą specyficzną dla danego języka programowania, składającą się z analizatora leksykalnego, składniowego i semantycznego, której wyjściem jest kod pośredni,
• drugą korzystającą z kodu pośredniego do optymalizacji (tę część można zresztą pominąć, jeśli optymalizacje nie są potrzebne),
• trzecią, generującą z kodu pośredniego kod specyficzny dla konkretnej maszyny docelowej.

W takim modelu, gdy chcemy stworzyć kompilatory M języków dla N maszyn docelowych, musimy napisać M+N modułów - M analizatorów, po jednym dla każdego języka źródłowego oraz N generatorów kodu. Możemy też napisać wspólny optymalizator. Gdybyśmy tworzyli oddzielnie monolityczne kompilatory, musielibyśmy napisać M*N programów (choć w praktyce niewątpliwie istaniałyby wspólne części tych programów).

Podejście to jest stosowane w istniejących kompilatorach - choćby popularny zestaw kompilatorów GCC (m.in. kompilatory C, C++, Javy, Fortranu dla bardzo wielu komputerów) - korzysta ze wspólnych reprezentacji pośrednich (jest tam używana więcej niż jedna reprezentacja). Pierwsze prace, w których wspominany jest taki kod pośredni pod nazwą UNCOL (ang. UNiversal Computer Oriented Language) pochodzą z lat pięćdziesiątych. Wówczas jednak przedstawiono samą ideę, bez propozycji konkretnej reprezentacji.

Innym zastosowaniem reprezentacji pośrednich, wspominanym również w kontekście UNCOLu, jest uzyskanie przenośności programów rozumianej jako uruchamianie jednego programu na wielu różnych architekturach komputerów <ref name="pierwsza">Oczywiście sprawa przenośności programów to nie tylko kwestia kodu programu, ale także bibliotek standardowych. Również dystrybucja kodu pośredniego nie jest jedynym sposobem na osiągnięcie przenośności.</ref>. Stosowane do tego celu reprezentacje to najczęściej kod jakiejś maszyny wirtualnej - np. takiej jak opisana w poprzednich dwóch wykładach. Szerzej spotykane maszyny wirtualne to JVM dla Javy i maszyna .NET. Kompilatory w tych środowiskach składają się z dwóch części - pierwszej generującej kod dla maszyny i drugiej - kompilującej kod maszyny wirtualnej do kodu wynikowego, czy to w trakcie wykonywania programu (JIT - Just In Time compiling), czy przed jego wykonaniem. Kod pośredni może też być interpretowany na każdej maszynie docelowej - tak było w przypadku P-kodu (ang. P-code), reprezentacji pośredniej dla programów w Pascalu, opracowanej w latach siedemdziesiątych. Kompilator języka OCaml może generować zarówno kod docelowy dla pewnych architektur, jak i kod pośredni, który jest potem interpretowany.

Głównym problemem związanym z takim zastosowaniem języków pośrednich jest stworzenie reprezentacji która będzie dobrze pasowała do różnych języków programowania oraz różnych maszyn.

W pewnych sytuacjach za reprezentację pośrednią można uznać kod w innym języku programowania, generowany przez dany kompilator czy raczej translator. Przy kompilowaniu języków wysokiego poziomu popularnym wyborem jest generowanie kodu w języku C (np. kompilator języka Modula-3 firmy DEC) z uwagi na dostępność kompilatorów języka C dla wielu różnych platform.

Rodzaje kodu pośredniego

Do tej pory zamiennie posługiwaliśmy się pojęciami reprezentacja pośrednia i kod pośredni. Teraz przedstawimy podział reprezentacji pośrednich na dwie klasy; określenie kod pośredni będzie dobrze pasowało tylko do drugiej z nich.

Reprezentacje grafowe

W tym rodzaju reprezentacji kod jest przechowywany jako zbiór wierzchołków i krawędzi łączących te wierzchołki. Kilka przykładowych reprezentacji tego typu to:

• drzewa wyprowadzenia - przedstawiane przy okazji analizy składniowej programu, wiernie przedstawiają wyniki procesu analizy składniowej,

Różne reprezentacje grafowe dla a:=b*c+b*c

• drzewa składniowe (AST) - nieco bardziej zwięzła reprezentacja, pozbawiona niepotrzebnych wierzchołków odpowiadających symbolom gramatyki. W praktyce AST to reprezentacja, która jest wyjściem analizatora składniowego i to właśnie na AST prowadzi się analizę semantyczną,
• DAGi - skierowane grafy acykliczne (ang. Direct Acyclic Graph), które są modyfikacją AST polegającą na połączeniu identycznych poddrzew (dla wyrażenia b * c na przykładowym rysunku), zwłaszcza w wyrażeniach. Budując DAG trzeba mieć na uwadze fakt, że poddrzewa, które wyglądają identycznie, nie muszą wcale być identyczne w czasie wykonania programu. O ile w przypadku wyrażeń bez przypisań i wywoływania funkcji ze skutkami ubocznymi wartość identycznych poddrzew zawsze będzie taka sama, to łatwo jest skonstruować wyrażenie z przypisaniami, w którym wyniki wyliczenia identycznych poddrzew będą różne. Jeśli jednak uda się połączyć pewne poddrzewa, oznacza to, że wartość takiego poddrzewa można wyliczać tylko raz. Tworzenie DAGów pozwala więc łatwo przeprowadzić pewne optymalizacje,

• grafy przepływu sterowania, stosowane najczęściej w kontekście bloków bazowych opisanych w kolejnym wykładzie. Graf przepływu sterowania przedstawia instrukcje lub grupy instrukcji połączone krawędziami oznaczającymi skoki (wykonywane zawsze lub warunkowo)

Reprezentacje liniowe

Reprezentacje liniowe to takie, w których kod jest reprezentowany jako ciąg pewnego rodzaju instrukcji. Nie oznacza to, że program w tej reprezentacji wykonywany jest dokładnie w kolejności instrukcji - dowolny odpowiednio skomplikowany program zawiera przecież pętle lub skoki. Rozsądna reprezentacja liniowa musi więc dopuszczać jakąś formę przekazywania sterowania w inne miejsce niż do kolejnej instrukcji. Widać też, czemu do tego rodzaju reprezentacji pasuje określenie "kod pośredni" - bo reprezentacja liniowa to po prostu kod jakiejś maszyny wirtualnej. Mimo że z pojęciem kod kojarzy się tekstowa lista kolejnych instrukcji, w praktyce wygodniej jest te instrukcje przechowywać w postaci pewnej struktury danych, najczęściej rekordu zawierającego rozkaz (zakodowany jako liczbę) oraz określenie adresów jego argumentów i wyniku.

Zazwyczaj reprezentacje liniowe klasyfikuje się z uwagi na liczbę adresów, które mogą być argumentami instrukcji. Weźmy instrukcję

x := y * (z + 2)

i przyjrzyjmy się jej prawej stronie. Są tam używane dwa operatory arytmetyczne, + i *. Każdy z nich ma dwa argumenty oraz wynik, który trzeba gdzieś zapamiętać. Okazuje się jednak (można to było zauważyć w trakcie poprzednich dwóch wykładów), że definiując domyślne miejsce, z którego pobierane są argumenty i/lub domyślne miejsce dla wyniku, instrukcje nie muszą pobierać tak wielu argumentów.

W literaturze spotyka się następujące rodzaje reprezentacji liniowych:

• Kod jednoadresowy, czyli zazwyczaj kod dla maszyn stosowych. Instrukcje pobierają z pamięci co najwyżej jeden adres, a pozostałe argumenty są pobierane ze stosu. Również wynik większości operacji jest umieszczany na stosie, a nie w pamięci. Kod jednoadresowy jest dobrą abstrakcją sprzętowych maszyn stosowych - procesorów, które nie mają dostępnych dla programisty rejestrów. Przykładem takiego procesora jest Burroughs B5000. Zaletą kodu jednoadresowego jest jego zwięzłość - instrukcje są krótkie, a wiele ich argumentów jest pobieranych z ustalonych miejsc. Wadą jest to, że liczba rozkazów potrzebnych do zapisania wybranej konstrukcji z kompilowanego języka bywa większa niż w przypadku kodu dwu- czy trójadresowego. Mimo to kod jednoadresowy jest podstawą maszyn wirtualnych dla niektórych implementacji Smalltalka 80. Był też stosowany w jednym z pierwszych szeroko znanych kompilatorów przenośnych pomiędzy architekturami, kompilatorze Pascala Ursa Ammanna <ref name="druga">Maszyna stosowa, NMW, z poprzednich wykładów jest właściwie maszyną zeroadresową, jej instrukcje nie pobierają bezpośrednio żadnego adresu. Jednak rozkazy odwołujące się do pamięci - LOAD i STORE - pobierają pojedynczy adres ze stosu.</ref>.
• Kod dwuadresowy, w którym zazwyczaj instrukcje wymagające dwóch argumentów i wyniku zapisują swój rezultat w miejscu jednego z argumentów. Tę postać stosowano w kompilatorach generujących kod dla maszyn, których procesory miały tak działające rozkazy. Ponieważ wiele obecnie stosowanych procesorów obsługuje rozkazy odpowiadające lepiej opisanemu poniżej kodowi trójadresowemu, kod dwuadresowy jest rzadko spotykany.

push 2 push y mul push x sub Kod jednoadresowy	t1 := 2 mul t1, y t2 := x sub t2, t1 Kod dwuadresowy	t1 := 2 t2 := t1 * y t3 := x - t2 Kod trójadresowy
Różne reprezentacje liniowe dla wyrażenia x - 2 * y

• Kod trójadresowy, w którym położenie obu argumentów instrukcji oraz miejsce na wynik są jawnie specyfikowane. Odpowiada to dobrze architekturze wielu procesorów RISC (Sparc, PowerPC, MIPS), a niezbyt dobrze - popularnej architekturze procesorów x86. Mimo tego kod trójadresowy jest stosowany także w kompilatorach generujących kod dla procesorów Intela, np. w GCC<ref name"trzecia">Patrz opis reprezentacji GIMPLE i GENERIC</ref>. Najbardziej oczywistą implementacją kodu trójadresowego są czwórki - rekordy (lub coraz częściej obiekty) zawierające rozkaz (operację), jego dwa argumenty i wynik, czyli np. pola op,arg1,arg2 i wynik. Stąd pochodzi często spotykana nazwa tej implementacji - kod czwórkowy. Gdy któryś z rozkazów - np. operator logiczny not - potrzebuje tylko jednego argumentu, to pole arg2 pozostaje nieużywane.
  
  Trzeba zauważyć, że w chwili generowania kodu pośredniego nie mamy jeszcze przydzielonych adresów w pamięci odpowiadających zmiennym. Wobec tego jako arg1, arg2 i wynik zamiast adresów zmiennych używamy wskaźników na ich wpisy w tablicy symboli. Jednak, jak widać w przykładowym kodzie, użycie instrukcji dwuargumentowych w przypadku wyliczania skomplikowanych wyrażeń zmusza nas do przechowywania wyników fragmentów obliczeń w tymczasowo przydzielonym miejscu, nieodpowiadającym żadnej ze zmiennych z kodu źródłowego. Te zmienne, nazywane zmiennymi tymczasowymi są automatycznie tworzone przez kompilator. Żeby zachować jednolitą zawartość czwórek, takie zmienne tymczasowe muszą być dopisywane do tablicy symboli.
  
  Aby pominąć konieczność dopisywania zmiennych tymczasowych do tablicy symboli, można stosować trójki - reprezentację zbliżoną do kodu dwuadresowego, przy czym wynik rozkazu zamiast zapamiętania pod podanym adresem jest wpisywany do specjalnej zmiennej tymczasowej powiązanej z danym rozkazem (np. poprzez jego kolejny numer). Wówczas oczywiście niepotrzebne jest pole wyniku, a pola argumentów w rekordzie mogą zawierać albo wskaźnik na wpis w tablicy symboli, albo numer instrukcji. Oprócz takiej kłopotliwej zawartości pól argumentów, wadą trójek jest konieczność zmiany wszystkich odwołań do danego wyniku w przypadku zmiany kolejności instrukcji. Ponieważ utrudnia to bardzo optymalizację kodu, więc trójki nie są zbyt często stosowane.
  
  Ostatnią wadę trójek można zniwelować stosując trójki pośrednie. W tej reprezentacji pole argumentu zawiera wskaźnik na wpis w tablicy symboli albo na wpis w specjalnej tablicy zawierającej powiązanie chwilowego numeru rozkazu z jego aktualnym położeniem. Ta dodatkowa tablica jest w istocie uproszczoną pomocniczą tablicą symboli. W związku z tym trójki pośrednie pozwalają zazwyczaj oszczędzić trochę pamięci w trakcie kompilacji (gdyż instrukcje mają tylko trzy pola zamiast czterech, a wpisy w uproszczonej tablicy są zapewne krótsze niż w głównej tablicy symboli) kosztem bardziej skomplikowanej reprezentacji - gdyż pole argumentu może wskazywać wpisy w tablicach o różnej strukturze.
• Niektórzy autorzy wykazują zalety stosowania rekordów o zmiennej długości (n-tek, Frailey), czyli np. przechowywanie całego wyrażenia A+B+C jako jednego rozkazu. Uzasadniane to jest wygodą przy prowadzeniu pewnych rodzajów optymalizacji.

Zdarza się też, że łączy się różne rodzaje reprezentacji pośrednich w jedną. Często spotykane jest łączenie jakiejś reprezentacji grafowej dla konstrukcji wyższego rzędu i reprezentacji liniowej dla fragmentów kodu.

Kod pośredni używany w trakcie dalszych wykładów

Wprowadźmy teraz kod pośredni, z którego będziemy korzystali podczas kolejnych wykładów, do przedstawienia optymalizacji i innych związanych z tym tematów. Kod ten pochodzi z książki Kompilatory Aho, Sethi'ego i Ullmana. Do opisu kodu posłużymy się jego reprezentacją tekstową, wygodniejszą do czytania niż przedstawiane wcześniej implementacje.

Jest to kod trójadresowy dla bardzo prostej maszyny wirtualnej. Zakładamy, że dysponujemy nieograniczoną pamięcią dla danych, dane i kod są trzymane w oddzielnych przestrzeniach adresowych, kod jest niemodyfikowalny. Jedynym obsługiwanym typem danych są słowa o nieokreślonej długości. Adresy instrukcji i danych to liczby wielkości słowa maszyny.

Dla uproszczenia zamiast adresami w pamięci będziemy się posługiwali etykietami oznaczającymi adres w kodzie i nazwami zmiennych zamiast adresów danych. W implementacjach tej reprezentacji do przekształcania nazw na adresy służy, oczywiście, tablica symboli, a pola czwórki wskazują na jej wpisy.

Maszyna obsługuje następujące rozkazy:

1. Przypisanie postaci x := y op z, gdzie op to jeden z operatorów +,-,*,/,and,or,xor.
2. Przypisanie jednoargumentowe postaci x := op y, gdzie op to -, not.
3. Kopiowanie postaci x := y
4. Skoki bezwarunkowe postaci goto L, gdzie L to adres w kodzie, zazwyczaj reprezentowany przez etykietę; w związku z tym dopuścimy zapis rozkazów w postaci etykieta: oznaczający etykietę odnoszącą się do pierwszego adresu występującego po niej.
5. Skoki warunkowe postaci if x oprel y goto L, gdzie oprel to operator relacyjny (<,>,=,<=,>=, !=). Jeśli warunek jest spełniony, to skok jest wykonywany.
6. Wywoływanie funkcji, obsłgiwane przez dwa rozkazy - param x i call L, n, służące odpowiednio do przekazania x jako kolejnego parametru funkcji oraz wywołania funkcji pod adresem L z n parametrami. Powrót z funkcji dokonywany jest przez rozkaz return x, gdzie x to wartość zwracana.
7. Przypisania indeksowane postaci x := y[i] oraz x[i] := y. Pierwszy z tych rozkazów powoduje umieszczenie pod adresem x zawartości pamięci spod adresu y + i, drugi - umieszczenie pod adresem x + i wartości spod adresu y.
8. Przypisania wskaźnikowe postaci x := &y, x := *y, *x := y, rozumiane tak, jak analogiczne konstrukcje z języka C.

Warto pamiętać, że kompilator może korzystać z wielu postaci kodu pośredniego. Przykładowo, GCC używa do wysokopoziomowych optymalizacji postaci GIMPLE i GENERIC, a do niskopoziomowych - RTL. W związku z tym, gdy mówi się o generowaniu kodu pośredniego, trzeba określić z jakiej reprezentacji generuje się ten kod. My przyjmiemy, że generujemy kod pośredni dysponując drzewem składniowym dla bliżej nieokreślonego imperatywnego języka programowania ze standardowymi wyrażeniami arytmetycznymi i logicznymi (z operatorami dwuargumentowymi), instrukcjami if, while, for itp. Nie będziemy się zajmowali złożonymi typami danych, dostępne są tylko liczby odpowiadające słowom maszyny oraz tablice (wielowymiarowe) tych liczb.

Metodę generowania kodu kodu pośredniego można formalnie wyrazić jako wspomniany w trakcie poprzedniego wykładu schemat translacji sterowanej składnią. W praktyce, przy przyjętych założeniach, kompilator obchodziłby drzewo AST, zaczynając od korzenia. Dla każdego typu wierzchołka odpowiadająca mu procedura (metoda) wybierałaby kolejność odwiedzania dalszych wierzchołków. Wynikiem działania każdej procedury byłby kod dla poddrzewa zakorzenionego w wierzchołku, który ona obsługiwała.

My posłużymy się nieformalnym opisem generowania kodu dla poszczególnych konstrukcji języka, co zdecydowanie uprości prezentację.

W wielu sytuacjach potrzebne nam będzie tworzenie zmiennych tymczasowych i zapamiętywanie ich w tablicy symboli. Przyjmijmy, że tablica symboli udostępnia funkcję nowa_tymczasowa, która oczywiście tworzy wpis dla nowej zmiennej tymczasowej i zwraca jej nazwę. Analogicznie będziemy potrzebowali etykiet do wykonywania skoków, funkcja nowa_etykieta będzie zwracała nazwę nowo stworzonej etykiety.

Zajmijmy się teraz konstrukcjami języka programowania. Ograniczymy się do tłumaczenia pojedynczej funkcji.

Deklaracje

Obsługę deklaracji można ograniczyć do tworzenia wpisów dla napotkanych zmiennych w tablicy symboli. Nawet to nie musi być konieczne, bo tablica symboli związana z odpowiednim poddrzewem obchodzonego AST może powstać wcześniej i być używana w trakcie generowania kodu pośredniego.

Wyrażenia arytmetyczne

Ponieważ przyjęliśmy, że w języku są tylko operatory dwuargumentowe, takie jak operatory maszyny, tłumaczenie wyrażeń jest proste. Weźmy dla przykładu wierzchołek z operatorem +.

e1 i e2 to jakieś poddrzewa reprezentujące podwyrażenia. Przyjmijmy konwencję, że procedura tworząca kod dla podwyrażenia oprócz samego kodu zwraca nazwę zmiennej, na której zapamiętany jest wynik. Wówczas nasza procedura mogłaby wyglądać następująco:

zmienna1, kod1 = generuj(e1)
zmienna2, kod2 = generuj(e2)
wynik = nowa_tymczasowa()
kod = kod1 + kod2 + wynik + " := " + zmienna1 + " + " + zmienna2
return wynik, kod

co spowoduje wygenerowanie kodu, który w pamięci będzie wyglądał następująco:

Przypisania

Przypisania są jeszcze prostsze. W drzewie reprezentuje je wierzchołek:

Ponieważ przypisanie będzie dotyczyło pewnej istniejącej zmiennej, więc nazwa zmiennej tymczasowej wracana przez funkcje tworzące kod dla wyrażeń nie będzie musiała być zwracana przez kod dla przypisania.

Możemy więc wygenerować następujący kod:

zmienna, kod1 = generuj(e)
kod = kod1 + z + " := " + zmienna
return kod

Kolejne instrukcje

Czyli taki wierzchołek z drzewa:

Trzeba po prostu wygenerować kod dla i1 i i2, umieścić po sobie i zwrócić.

Pętla while

Wierzchołek przedstawiający taką pętlę wygląda następująco:

Trzeba stworzyć kod, który będzie wyglądał np. tak:

co można zrealizować w poniższy sposób:

etykieta_warunku := nowa_etykieta()
zmienna, kod1 := generuj(e)
kod2 := generuj(i)
etykieta_końca_kodu := nowa_etykieta()
kod := etykieta_warunku + ":" +
       kod1 +
       "if" + zmienna + " = 0 goto " + etykieta_końca_kodu +
       kod2 +
       "goto " + etykieta_warunku +
       etykieta_końca_kodu + ":"
return kod

przy założeniu, że wyrażenia logiczne będą wyliczane jak wyrażenia arytmetyczne, a 0 będzie oznaczało fałsz. Warto zauważyć, że etykieta_końca_kodu odnosi się już do rozkazu, który będzie po kodzie wygenerowanym przez tę procedurę.

Wyrażenia logiczne

Istnieją dwie rozpowszechnione metody tłumaczenia wyrażeń logicznych. Pierwsza, chyba prostsza w realizacji, zakłada, że wyrażenia logiczne tłumaczy się tak jak arytmetyczne, przyjmując pewną konwencję dotyczącą wartości oznaczających prawdę i fałsz. Często zakłada się, że fałsz to 0, a dowolna wartość niezerowa to prawda. Trzeba jednak stwierdzić, że taka prosta metoda obliczania wartości logicznych spowoduje, że dla następującego wyrażenia z języka źródłowego: x != 0 and 10/x > 3 zostaną zawsze wyliczone oba podwyrażenia - x != 0 i 10/x > 3. W wielu językach programowania stosuje się skrócone wyliczanie wyrażeń logicznych, które w tym przypadku spowodowałoby, że po stwierdzeniu, że x = 0 od razu widać, że całe wyrażenie musi być fałszem i drugie podwyrażenie nie jest wyliczane.

Takie skrócone wyliczanie łatwiej jest zaimplementować za pomocą tzw. kodu skaczącego. W tym podejściu nie używa się zmiennych tymczasowych do pamiętania wartości podwyrażeń, a zamiast tego procedurom generującym kod dla tych podwyrażeń dostarcza się dwie etykiety - jedną, do której należy skoczyć, gdy wartość wyrażenia jest prawdą i drugą, do której należy skoczyć, gdy wartość jest fałszem. Wartość wyrażenia jest więc związana z miejscem, do którego wykona się skok po jego wyliczeniu.

Realizację pozostałych konstrukcji języka pozostawiamy jako ćwiczenie.

Uwagi

<references/>