Projekt z Technik Translacji 2007

Używając BISON-a i LEX-a napisz kompilator prostego języka imperatywnego do kodu maszyny rejestrowej. 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, ...), a w przypadku braku błędów zwracać kod na maszynę rejestrową. Kod wynikowy powinien wykorzystywać jak najmniej rejestrów i wykonywać się jak najszybciej (w miarę optymalnie, zobacz przykład na końcu strony).

Prosty język imperatywny

program      → LET declarations IN commands END

declarations → declarations identifier
             | declarations identifier = num
             | ε

commands     → commands command
             | ε

command      → identifier := expression;
             | IF condition THEN commands ELSE commands END
             | WHILE condition DO commands END
             | READ identifier;
             | PRINT identifier;

expression   → identifier 
             | identifier + identifier
             | identifier - identifier
             | identifier * identifier
             | identifier / identifier
             | identifier % identifier

condition    → identifier = identifier
             | identifier != identifier
             | identifier < identifier
             | identifier > identifier
             | identifier <= identifier
             | identifier >= identifier

Język powinien być zgodny z powyższą gramatyką i spełniać następujące warunki:

1. identifier jest opisany wyrażeniem regularnym [_a-z]+;
2. num jest liczbą naturalną w zapisie dziesiętnym;
3. działania arytmetyczne są wykonywane na liczbach naturalnych, w szczególności a-b=max{a-b,0}, dzielenie przez zero daje wynik 0 i resztę także 0;
4. rozróżniamy małe i duże litery.

Maszyna rejestrowa

Maszyna rejestrowa składa się ze specjalnego rejestru a, licznika rozkazów k oraz zbioru rejestrów r_i, dla i=0,1,2,.... Maszyna pracuje na liczbach naturalnych (wynikiem odejmowanie większej liczby od mniejszej jest 0). 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 jest nieokreślona. Poniżej jest lista rozkazów wraz z ich interpretacją:

Przejście do nieistniejącego rozkazu jest traktowane jako błąd.

Prosty interpreter kodu MR w C++.

Przykładowy kod programu

LET
    a b c d=0
IN
    READ a;
    READ b;
    IF a<b THEN
        c:=a;
        a:=b;
        b:=c;
    ELSE
    END
    WHILE b>d DO
        c:=a%b;
        a:=b;
        b:=c;
    END
    PRINT a;
END

Przykładowy kod maszyny rejestrowej

FIX 0
STORE 6
READ 3
READ 4
LOAD 4
SUB 3
JZ 14
LOAD 3
STORE 5
LOAD 4
STORE 3
LOAD 5
STORE 4
LOAD 4
SUB 6
JZ 33
LOAD 4
JZ 27
FIX 1
ADD 3
STORE 0
SUB 4
JGE 20
FIX 1
STORE 1
LOAD 0
SUB 1
STORE 5
LOAD 4
STORE 3
LOAD 5
STORE 4
JUMP 13
PRINT 3
HALT

Optymalność wykonywania mnożenia i dzielenia

Dla następującego programu

LET
    n m=4 reszta potega dzielnik=2 zero=0 jeden=1
IN
    READ n;
    WHILE n>=m DO
        potega:=zero;
        reszta:=n%dzielnik;
        WHILE reszta=zero DO
            n:=n/dzielnik;
            potega:=potega+jeden;
            reszta:=n%dzielnik;
        END
        IF potega>zero THEN
            PRINT dzielnik;
            PRINT potega;
        ELSE
            dzielnik:=dzielnik+jeden;
            m:=dzielnik*dzielnik;
        END
    END
    IF n!=jeden THEN
        PRINT n;
        PRINT jeden;
    ELSE
    END
END

kod wynikowy powinien działać w czasie porównywalnym do poniższych wyników

Uruchamianie programu.
? 1234567890
2
1
3
2
5
1
3607
1
3803
1
Skończono program (wykonano kroków: 3867104, wykorzystano rejestrów: 12).

Uruchamianie programu.
? 12345678901
857
1
14405693
1
Skończono program (wykonano kroków: 4942416, wykorzystano rejestrów: 12).

Uruchamianie programu.
? 12345678903
3
1
4115226301
1
Skończono program (wykonano kroków: 112938143, wykorzystano rejestrów: 12).