Projekt z Technik Translacji 2007 (zima)

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      → VAR declarations START commands END

declarations → declarations identifier
             | ε

commands     → commands command
             | ε

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

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

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

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.
5. w programie można użyć komentarzy postaci: (* komentarz *);
6. komentarze nie mogą być zagnieżdżone;

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

VAR
    a b c
START
    READ a;
    READ b;
    IF a<b THEN
        c:=a;
        a:=b;
        b:=c;
    ELSE
    END
    WHILE b>0 DO
        c:=a%b;
        a:=b;
        b:=c;
    END
    PRINT a;
END

Przykładowy kod maszyny rejestrowej

READ 7
READ 8
LOAD 8
SUB 7
JZ 12
LOAD 7
STORE 9
LOAD 8
STORE 7
LOAD 9
STORE 8
JUMP 12
LOAD 8
SUBC 0
JZ 48
LOAD 8
JZ 42
STORE 1
LOAD 7
STORE 0
ZERO
ADDC 1
ADD 0
SUB 1
JZ 41
LOAD 1
STORE 2
ZERO
ADDC 1
ADD 0
SUB 2
SUB 2
JZ 37
LOAD 2
ADD 2
STORE 2
JUMP 27
LOAD 0
SUB 2
STORE 0
JUMP 20
LOAD 0
STORE 9
LOAD 8
STORE 7
LOAD 9
STORE 8
JUMP 12
PRINT 7
HALT

Optymalność wykonywania mnożenia i dzielenia

Dla następującego programu

VAR
    n m reszta potega dzielnik
START
    READ n;
    dzielnik:=2;
    m:=4;
    WHILE n>=m DO
        potega:=0;
        reszta:=n%dzielnik;
        WHILE reszta=0 DO
            n:=n/dzielnik;
            potega:=potega+1;
            reszta:=n%dzielnik;
        END
        IF potega>0 THEN
            PRINT dzielnik;
            PRINT potega;
        ELSE
            dzielnik:=dzielnik+1;
            m:=dzielnik*dzielnik;
        END
    END
    IF n!=1 THEN
        PRINT n;
        PRINT 1;
    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: 4261288, wykorzystano rejestrów: 11).

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

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