Kompilator JFTT 2024/2025

Projekt kompilatora zrealizowany w ramach kursu "Języki Formalne i Techniki Translacji" w semestrze zimowym 2024/2025 na Politechnice Wrocławskiej.

Wymagane oprogramowanie

• Python 3.12+

• kopię modułu sly umieszczono w źródłach projektu, systemowa instalacja nie jest konieczna

Przykładowe wywołanie programu

./main.py tests/program0.imp out0.mr
./main.py [--help|-h]

TREŚĆ POLECENIA Z LISTY ZADAŃ

Używając BISON-a i FLEX-a, lub innych narzędzi o podobnej funkcjonalności, napisz kompilator prostego języka imperatywnego do kodu maszyny wirtualnej. Specyfikacja języka i maszyny jest zamieszczona poniżej. 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 stosunku do 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>

Definicja języka wejściowego

Język powinien być zgodny z gramatyką zamieszczoną w Tablicy 1 i spełniać następujące warunki:

1. Działania arytmetyczne są wykonywane na liczbach całkowitych, ponadto dzielenie przez zero powinno dać wynik 0 i resztę także 0; reszta z dzielenia powinna mieć taki sam znak jak dzielnik.

2. Deklaracja tab[-10:10] oznacza zadeklarowanie tablicy o 21 elementach indeksowanych od −10 do 10; 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), 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. 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.

4. 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).

5. Pętla REPEAT-UNTIL kończy pracę kiedy warunek napisany za UNTIL jest spełniony (pętla wykona się przynajmniej raz).

6. Instrukcja READ czyta wartość z zewnątrz i podstawia pod zmienną, a WRITE wypisuje wartość zmiennej/liczby na zewnątrz.

7. Pozostałe instrukcje są zgodne z ich znaczeniem w większości języków programowania.

8. pidentifier jest opisany wyrażeniem regularnym [_a-z]+.

9. num jest liczbą całkowitą 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ę całkowitą).

10. Małe i duże litery są rozróżniane.

11. W programie można użyć komentarzy zaczynających się od # i obowiązujących do końca linii.

prog_all  -> {procedure} main
procedure -> PROCEDURE name(argdefs) IS [vardefs] BEGIN commands END
main      -> PROGRAM IS [vardefs] BEGIN commands END

commands  -> {command} command
vardefs   -> {name[[num:num]],} name[[num:num]]
argdefs   -> {[T] name,} [T] name
args      -> {name,} name

simpleVar -> name | name[name] | name[num]
value     -> num | simpleVar
condition -> value COMP value
proc_call -> name(args)

command   -> simpleVar := value [BINOP value];
           | IF condition THEN commands ELSE commands ENDIF
           | IF condition THEN commands ENDIF
           | WHILE condition DO commands ENDWHILE
           | REPEAT commands UNTIL condition;
           | FOR name FROM value TO value DO commands ENDFOR
           | FOR name FROM value DOWNTO value DO commands ENDFOR
           | proc_call;
           | READ simpleVar;
           | WRITE value;

Tabela 1: Gramatyka języka

Opis maszyny wirtualnej

Maszyna wirtualna składa się z licznika rozkazów k oraz ciągu komórek pamięci p[i], dla i = 0, 1, 2, ... (z przyczyn technicznych i ⩽ 262). Komórka p[0] pełni rolę akumulatora. Maszyna pracuje na liczbach całkowitych. 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ść komórek pamięci jest nieokreślona, a licznik rozkazów k ma wartość 0. W Tablicy 2 jest podana lista rozkazów wraz z ich interpretacją i kosztem wykonania.

W programie można zamieszczać komentarze w postaci: #komentarz. Białe znaki w kodzie są pomijane. Przejście do nieistniejącego rozkazu jest traktowane jako błąd.

Rozkaz	Koszt	Interpretacja
GET i	100	pobraną liczbę zapisuje w p[i], k++
PUT i	100	wyświetla zawartość p[i], k++
LOAD i	10	p[0] := p[i], k++
STORE i	10	p[i] := p[0], k++
LOADI i	20	p[0] := p[p[i]], k++
STOREI i	20	p[p[i]] := p[0], k++
ADD i	10	p[0] += p[i], k++
SUB i	10	p[0] -= p[i], k++
ADDI i	20	p[0] += p[p[i]], k++
SUBI i	20	p[0] -= p[p[i]], k++
SET x	50	p[0] = x, k++
HALF	5	p[0] = floor(p[0]/2), k++
JUMP j	1	k = k+j
JPOS j	1	(p[0]>0) ? k = k+j : k++
JZERO j	1	(p[0]==0) ? k = k+j : k++
JNEG j	1	(p[0]<0) ? k = k+j : k++
RTRN i	10	k = p[i]
HALT	0	zatrzymuje program

Tabela 2: Rozkazy maszyny wirtualnej (x, i oraz j są ograniczone do liczb całkowitych 64-bitowych).

Wszystkie przykłady oraz kod maszyny wirtualnej napisany w C++ zostały zamieszczone w pliku labor4.zip (kod maszyny jest w dwóch wersjach: podstawowej na liczbach typu long long oraz w wersji cln na dowolnych liczbach całkowitych, która jest jednak wolniejsza w działaniu ze względu na użycie biblioteki dużych liczb).