Kompilator

Opis zadania

Kompilator powinien sygnalizować miejsce i rodzaj błędu (np. druga deklaracja zmiennej, użycie niezadeklarowanej zmiennej, nieznana nazwa procedury, ...), a w przypadku braku błędów zwracać kod na maszynę wirtualną. Kod wynikowy powinien być jak najkrótszy i wykonywać się jak najszybciej (w miarę optymalnie, mnożenie i dzielenie powinny być wykonywane w czasie logarytmicznym w stosunkudo wartości argumentów). Ocena końcowa zależy od obu wielkości. Program powinien być oddany z plikiem Makefile kompilującym go oraz z plikiem README opisującym dostarczone pliki oraz zawierającym dane autora. W przypadku użycia innych języków niż C/C++ należy także zamieścić dokładne instrukcje co należy doinstalować dla systemu Ubuntu. Wywołanie programu powinno wyglądać następująco:

kompilator <nazwa pliku wejściowego> <nazwa pliku wyjściowego>

czyli dane i wynik są podawane przez nazwy plików (nie przez strumienie). Przy przesyłaniu do wykładowcy program powinien być spakowany programem zip a archiwum nazwane numerem indeksu studenta. Archiwum nie powinno zawierać żadnych zbędnych plików.

specyfikacja języka imperatywnego

Język powinien być zgodny z gramatyką zamieszczoną w pliku gramatyka.txt i spełniać następujące warunki:

1. Działania arytmetyczne są wykonywane na liczbach naturalnych, wynikiem odejmowania liczby większej od mniejszej jest 0, ponadto dzielenie przez zero powinno dać wynik 0 i resztę także 0.
2. Deklaracja tab[10:30] oznacza zadeklarowanie tablicy o 21 elementach indeksowanych od 10 do 30; identyfikator tab[i] oznacza odwołanie do i-tego elementu tablicy tab; deklaracja zawierająca pierwszą liczbę większą od drugiej powinna być zgłaszana jako błąd.
3. Procedury nie mogą zawierać wywołań rekurencyjnych, parametry formalne przekazywane są przez referencje (parametry IN-OUT, tryb domyślny), zmienne używane w procedurze muszą być jej parametrami formalnymi lub być zadeklarowane wewnątrz procedury; nazwa tablicy w parametrach formalnych powinna być poprzedzona literą T.
4. W procedurze można wywołać tylko procedury zdefiniowane wcześniej w kodzie programu, a jako ich parametry formalne można podać zarówno parametry formalne procedury wywołującej, jak i jej zmienne lokalne.
5. Poprzedzenie w parametrach formalnych zmiennej literą I oznacza, że ma być traktowana w procedurze jak stała (nie wolno jej modyfikować, może być przekazana do podprocedury tylko w miejscu także oznaczonym przez I). Poprzedzenie przez O oznacza, że zmienna ma nieokreśloną wartość (nie wolno jej czytać przed podstawieniem wartości, nie może być przekazana do podprocedury w miejscu oznaczonym przez I).
6. Pętla FOR ma iterator lokalny, przyjmujący wartości od wartości stojącej po FROM do wartości stojącej po TO/DOWNTO kolejno w odstępie +1 lub odpowiednio w odstępie -1; liczba iteracji pętli FOR jest ustalana na początku i nie podlega zmianie w trakcie wykonywania pętli (nawet jeśli zmieniają się wartości zmiennych wyznaczających początek i koniec pętli); iterator pętli FOR nie może być modyfikowany wewnątrz pętli (kompilator w takim przypadku powinien zgłaszać błąd).
7. Pętla REPEAT-UNTIL kończy pracę kiedy warunek napisany za UNTIL jest spełniony (pętla wykona się przynajmniej raz).
8. Instrukcja READ czyta wartość z zewnątrz i podstawia pod zmienną, a WRITE wypisuje wartość zmiennej/liczby na zewnątrz.
9. Pozostałe instrukcje są zgodne z ich znaczeniem w większości języków programowania.
10. pidentifier jest opisany wyrażeniem regularnym [_a-z]+.
11. num jest liczbą naturalną w zapisie dziesiętnym (w kodzie wejściowym liczby podawane jako stałe są ograniczone do typu 64 bitowego, na maszynie wirtualnej nie ma ograniczeń na wielkość liczb, obliczenia mogą generować dowolną liczbę naturalną ).
12. Małe i duże litery są rozróżniane.
13. W programie można użyć komentarzy zaczynających się od # i obowiązujących do końca linii.

Maszyna wirtualna

Maszyna wirtualna składa się z 8 rejestrów (ra, rb, rc, rd, re, rf , rg, rh), licznika rozkazów k oraz ciągu komórek pamięci pi, dla i = 0, 1, 2, ... (z przyczyn technicznych i ⩽ 262). Maszyna pracuje na liczbach naturalnych. Program maszyny składa się z ciągu rozkazów, który niejawnie numerujemy od zera. W kolejnych krokach wykonujemy zawsze rozkaz o numerze k aż napotkamy instrukcję HALT. Początkowa zawartość rejestrów i komórek pamięci jest nieokreślona, a licznik rozkazów k ma wartość 0. W Tabeli 2 jest podana lista rozkazów wraz z ich interpretacją i kosztem wykonania. W programie można zamieszczać komentarze w postaci: # komentarz, które sięgają do końca linii. Białe znaki w kodzie są pomijane. Przejście do nieistniejącego rozkazu lub wywołanie nieistniejącego rejestru jest traktowane jako błąd

Tabela 2:

Rozkaz	Interpretacja	Czas
READ	pobraną liczbę zapisuje w rejestrze ra oraz $k \leftarrow k + 1$	100
WRITE	wyświetla zawartość rejestru ra oraz $k \leftarrow k + 1$	100
LOAD $j$	$ra \leftarrow p_j$ oraz $k \leftarrow k + 1$	50
STORE $j$	$p_j \leftarrow ra$ oraz $k \leftarrow k + 1$	50
RLOAD $x$	$ra \leftarrow p_{rx}$ oraz $k \leftarrow k + 1$	50
RSTORE $x$	$p_{rx} \leftarrow ra$ oraz $k \leftarrow k + 1$	50
ADD $x$	$ra \leftarrow ra + rx$ oraz $k \leftarrow k + 1$	5
SUB $x$	$ra \leftarrow \max{ra - rx, 0}$ oraz $k \leftarrow k + 1$	5
SWP $x$	$ra \leftrightarrow rx$ oraz $k \leftarrow k + 1$	5
RST $x$	$rx \leftarrow 0$ oraz $k \leftarrow k + 1$	1
INC $x$	$rx \leftarrow rx + 1$ oraz $k \leftarrow k + 1$	1
DEC $x$	$rx \leftarrow \max{rx - 1, 0}$ oraz $k \leftarrow k + 1$	1
SHL $x$	$rx \leftarrow 2 * rx$ oraz $k \leftarrow k + 1$	1
SHR $x$	$rx \leftarrow \lfloor rx/2 \rfloor$ oraz $k \leftarrow k + 1$	1
JUMP $j$	$k \leftarrow j$	1
JPOS $j$	jeśli $ra > 0$ to $k \leftarrow j$, w p.p. $k \leftarrow k + 1$	1
JZERO $j$	jeśli $ra = 0$ to $k \leftarrow j$, w p.p. $k \leftarrow k + 1$	1
CALL $j$	$ra \leftarrow k + 1$ oraz $k \leftarrow j$	1
RTRN	$k \leftarrow ra$	1
HALT	zatrzymaj program	0

Przykłady

przykładowe programy napisane w języku imperatywnym znajdują się w folderze testy2025