Bison, Flex i maszyna wirtualna - trzecia praca domowa.

Historia zmian:

1 kwietnia 2007
Dodanie brakującego symbolu mul do listy rozkazów do zaimplementowania, dodanie dodatkowych rad do implementacji maszyny wirtualnej.
10 kwietnia 2007
Dodanie jednej porady do budowy leksera i parsera.
12 kwietnia 2007
Wskazanie przyczyny błędu maszyny podczas przetwarzania zaimplementowanych przez siebie skoków warunkowych.

Jeśli zaraz po ściągnięciu kod maszyny wirtualnej się nie kompiluje z następującym błędem (albo podobnym):

analyzer.cpp:212: error: ‘errno’ was not declared in this scope

należy dodać do pliku analyzer.cpp (na początku) następującą instrukcję:

#include <errno.h>

Maszyna Wirtualna.

Lista (kompletna?) brakujących instrukcji:

  1. mul,
  2. mod
  3. div,
  4. sub,
  5. jne,
  6. jle,
  7. jg,
  8. jl,
  9. read,
  10. realtoint,
  11. inttoreal,
  12. and,
  13. or

Przy okazji - w regulaminie stoi, że można sobie zaimplementować instrukcje w zależności od tego co jest nam potrzebne. Radzę zatem poza konkursem zaimplementować sobie instrukcję not (binarna maszyna jej nie ma). Ułatwi potem generowanie kodu dla pętli w kompilatorze.

Praktycznie wszystkie instrukcje można zaimplementować przez podobieństwo do już zaimplementowanych (w pliku machine.cpp). I tak:

  1. mul, div, sub, and, or oraz mod powinny być podobne do już zaimplementowanego add, z tym, że mod nie akceptuje argumentów będących liczbami rzeczywistymi (z tego co mi wiadomo).
  2. jne, jle, jg i jl powinny być podobne do już zaimplementowanego jge.
  3. inttoreal i realtoint powinny być podobne do już zaimplementowanego mov, z tym, że dojdzie tutaj rzutowanie i typowanie "na zmianę", oraz instrukcje nie będą same rozpoznawały typu zmiennej (czyli nie będzie AT_NONE, lecz AT_INTEGER albo AT_REAL).
  4. read powinno być podobne do zaimplementowanego write tylko w drugą stronę (UWAGA: patrz porady poniżej).

Porady.

Jeśli nie rozumiesz poniższych porad, proponuję na początek poczytać omówienie kodu maszyny wirtualnej, które znajduje się poniżej.

  1. Przy dodawaniu kodów operacji zadbaj, by OC_FINAL pozostał ostatnim kodem w typie wyliczeniowym opcode.
  2. Zauważ, że to do czego przepisujemy zawsze pobieramy przez get…_ref - ta wiedza jest ważna, kiedy próbujesz zaimplementować instrukcję read na podstawie instrukcji write.
  3. Najprawdopodobniej trzeba będzie zaimplementować dodatkową funkcję walidującą - taką która zachowuje się jak s_threearg, ale dodatkowo wymusza na argumentach typ UINT (może okazać się konieczna do zaimplementowania instrukcji mod).
  4. skoki warunkowe muszą być specjalnie traktowane!! Jeśli zajrzysz do funkcji void analyze (const char *s) w pliku analyzer.cpp to znajdziesz tam następującą linijkę:
if ((instr.oc != OC_JE) && (instr.oc != OC_JGE))    //jumps are special - last arg always integer

Do tego warunku należy także dodać opcode'y własnych skoków.

Omówienie kodu maszyny wirtualnej:

vm.h

unsigned int PC
Program Counter. Przy implementowaniu własnych instrukcji (szczególnie skoków) trzeba będzie często z niego korzystać.
unsigned int BP
Base Pointer.
unsigned int SP
Stack Pointer.
enum opcode
identyfikatory liczbowe kolejnych instrukcji, zebrane w typ wyliczeniowy dla wygody i dobra implementacji (to, że instrukcje są numerowane od 0 po kolei ma konkretne znaczenie). Ten enum jest dość ważny, ponieważ do niego trzeba dodać identyfikatory implementowanych przez siebie instrukcji.
enum argtype
Typ argumentów instrukcji. Będzie potrzebne przy implementacji ciał instrukcji.
enum addrmode
tryb adresowania argumentu. Raczej wykorzystywany przez tę część kodu, której nie będziemy dotykać.
enum basereg
Raczej nie będzie potrzebne.
struct argaddr
adres argumentu instrukcji. Warto zauważyć w kodzie tej struktury unię typów UINT i REAL. To oznacza, że nie musimy robić dwóch implementacji instrukcji w zależności od typu, tylko zarówno dla typu REAL jak i UINT podawać taką samą strukturę, a kod instrukcji sam sobie pobierze wartość odpowiedniego typu. O tym, jak kod rozpozna, z jakim typem argumentów ma do czynienia (bo musi go znać, żeby wiedzieć, czy sięgnąć do wartości całkowitej czy rzeczywistej) można się dowiedzieć z oględzin poniższej struktury.
struct instruction
instrukcja zawierająca: kod operacji, typ argumentów (po nim właśnie rozpoznajemy, czy dobrać się do wartości całkowitej czy rzeczuwistej w unii zawartej w polu am) oraz tablicę argumentów, zawsze o trzech komórkach. Jeśli funkcja przyjmuje mniej niż 3 argumenty, to w pozostałych komórkach ustawia się tryb adresowania na AM_NONE (btw: Jest to konieczne, ponieważ argumenty dla każdej instrukcji są walidowane przez odpowiednie funkcje - zarówno pod względem liczebności jak i typu).
opcode_table
???
dispatch_table
tutaj na skutek działania funkcji setup_opcodes() są przepisywane wskaźniki do funkcji implementujących ciała instrukcji w takiej kolejności w jakiej występują w strukturach opcode_info w tablicy instrukcji (znajdującej się na początku pliku analyzer.cpp). Potem podczas wykonywania programu odnosi się tylko do tej tablicy w następujący sposob: dispatch_table[instr.oc](instr); (czyli indeksując dispatch_table kodem instrukcji otrzymujemy wskaźnik do funkcji którą wykonujemy z instrukcją jako argumentem).
syntax_table
???
class segmentation_fault
ze sposobu w jaki jest używana w kodzie, wnioskuję, że jest to wyjątek.
vector<instruction> instructions
wektor, do którego są ładowane kolejne linijki programu (w assemblerze 1 linijka = 1 instrukcja), Załadowanie całego programu do wektora pozwala na łatwe manipulowanie wartością PC (program counter), ponieważ w takiej sytuacji PC jest po prostu indeksem do wektora instructions.
map<string, UINT>symtab
tablica symboli dla assemblera. nic dodać nic ująć. Zaimplementowana w postaci mapy indeksowanej napisem, a przechowującej wartości typu UINT.
UINT current_address
???
struct opcode_info
bardzo ważna struktura, która przechowuje po kolei: nazwę instrukcji, kod instrukcji, typ argumentów, wskaźnik do funkcji implementującej cialo instrukcji oraz wskaźnik do funkcji walidującej poprawność argumentów (pisałem o tym przy okazji omówienia struktury instruction). Tak naprawdę zaimplementowanie nowych instrukcji będzie polegało właśnie na stworzeniu niektórych danych (i dobranie pozostałych), a potem wypełnienie nimi takiej struktury i dodanie jej do tablicy instrukcji (która to znajduje się zaraz na początku pliku analyzer.cpp).
void execute ()
wykonuje program. Nie będziemy musieli tego dotykać.
void analyze (const char *s)
???
void setup_opcodes ()
wypełnia opcode_table, dispatch_table oraz syntax_table wartościami z tablicy instrukcji.
void s_threearg (const instruction &)
walidator argumentów instrukcji. Sprawdza, czy zostały podane dokładnie trzy argumenty i czy ostatni argument jest l-wartością. Jeśli któryś z warunków nie jest spełniony, rzuca wyjątek.
void s_threearg_jump (const instruction &)
walidator argumentów instrukcji. Sprawdza, czy zostały podane dokładnie trzy argumenty. Jeśli nie, rzuca wyjątek.
void s_oneinteger (const instruction &)
walidator argumentów instrukcji. Sprawdza, czy został podany dokładnie jeden argument typu UINT. Jeśli nie, rzuca wyjątek.
void s_onearg (const instruction &)
walidator argumentów instrukcji. Sprawdza, czy został podany dokładnie jeden argument. Jeśli nie, rzuca wyjątek.
void s_none (const instruction &)
walidator argumentów instrukcji. Sprawdza, czy instrukcja została wywołana bez żadnych argumentów. Jeśli nie, rzuca wyjątek.
void s_one (const instruction &)
chyba tylko przez przypadek nie został wywalony, bo nie jest nigdzie wykorzystywany i bez niego maszyna wciąż kompiluje się bezbłędnie.
void s_twoarg (const instruction &)
walidator argumentów instrukcji. Sprawdza, czy zostały podane dokładnie dwa argumenty. Jeśli nie, rzuca wyjątek.

Dalej występują deklaracje funkcji implementujących ciała instrukcji, z przedrostkiem h_. Dla własnych instrukcji też trzeba będzie napisać takie funkcje.

analyzer.cpp

struct opcode_info opcodes[]
tablica instrukcji. Tutaj trzeba będzie dopisać kolejne struktury typu opcode_info. Warto zauważyć, że instrukcja exit ma przyporządkowaną implementację h_none - to na wypadek jakby ktoś się zastanawiał, gdzie jest h_exit;).
pozostałe funkcje z tego pliku
służą raczej do przetwarzania danych wejściowych. Nie sądzę, żebyśmy musieli w nich grzebać.

machine.cpp

Oprócz implementacji już wspomnianych funkcji, plik ten zawiera definicje funkcji, które są używane do implementacji istniejących instrukcji, zatem pewnie będą też konieczne do zaimplementowania własnych instrukcji:

REAL& get_real_operand_ref (const argaddr& aa)
zwraca referencję do operandu typu rzeczywistego na podstawie odpowiadającej mu struktury typu argaddr. Używane do zmiennych typu REAL kiedy chcemy do nich coś przypisać.
UINT& get_int_operand_ref (const argaddr& aa)
zwraca referencję do operandu typu całkowitego na podstawie odpowiadającej mu struktury typu argaddr. Używane do zmiennych typu INTEGER kiedy chcemy do nich coś przypisać.
REAL get_real_operand (const argaddr & aa)
zwraca wartość operandu typu rzeczywistego na podstawie odpowiadającej mu struktury typu argaddr. Używane do zmiennych typu REAL kiedy chcemy z nich coś odczytać.
UINT get_int_operand (const argaddr & aa)
zwraca wartość operandu typu całkowitego na podstawie odpowiadającej mu struktury typu argaddr. Używane do zmiennych typu INTEGER kiedy chcemy z nich coś odczytać.

Krótki zarys dodawania nowej instrukcji.

Pokażę to na przykładzie fikcyjnej instrukcji hello, która będzie mogła być wykonana tylko jako hello.i będzie przyjmować jeden parametr - liczbę mówiącą ile razy ma zostać wypisany napis "hello".

Dodanie kodu operacji do opcode w vm.h.

Należy po prostu dopisać nową pozycję do typu wyliczeniowego opcode (czyli nowy kod operacji), koniecznie przed OC_FINAL. Nazwa tej nowej pozycji jest istotna tylko o tyle, że będziemy się potem do niej odnosić. Ja nazwę tę pozycję OC_HELLO.

Deklaracja funkcji implementującej ciało instrukcji w vm.h.

funkcje implementujące ciała instrukcji to są te h_cośtam. Wszystkie trzymają się tej samej sygnatury - nic nie zwracają oraz przyjmują jako argument referencję do stałej typu instruction. Trzeba się tego trzymać. Nasza funkcja będzie miała sygnaturę:

void h_hello ( const instruction& i );

którą to dopisujemy obok innych h_cośtam.

Dodanie sygnatury instrukcji do tablicy opcodes w analyzer.cpp.

Tu trzeba umieścić sygnaturę swojej instrukcji. Taka sygnatura składa się kolejno z: nazwy, kodu operacji, rodzaju przyjmowanych argumentów, wskaźnika do funkcji implementującej ciało instrukcji (czyli po prostu nazwy tej funkcji) oraz funkcji walidującej ilość i typ argumentów.

Nasza instrukcja ma mieć nazwę "hello", więc na pierwszej pozycji rekordu wstawiamy łańcuch "hello".

Nasza instrukcja ma mieć kod operacji OC_HELLO (który sami dla niej zdefiniowaliśmy), więc na drugiej pozycji wstawiamy OC_HELLO.

Nasza instrukcja może być wywoływana tylko z argumentami typu UINT, zatem na trzeciej pozycji wstawiamy AT_INTEGER (gdyby można ją było wywołać tylko z REAL, to wybralibyśmy AT_REAL, a gdyby można ją było wywołać z argumentami typu UINT bądź REAL, wybralibyśmy AT_NONE i typ argumentów z którymi została wywołana instrukcja sprawdzalibyśmy w samej implementacji instrukcji).

Nasza instrukcja będzie implementowana przez funkcję o nazwie h_hello, zatem na czwartej pozycji wstawiamy h_hello.

Nasza instrukcja będzie przyjmowała jeden argument typu INTEGER i tylko na to może pozwolić funkcja walidująca. To zagwarantuje nam funkcja s_oneinteger(), zatem jej nazwę wstawiamy na piątej pozycji (czywiście bez tych nawiasów).

Po tych wszystkich zabiegach tablica opcodes powinna wyglądać następująco:

struct opcode_info opcodes[] = {
    //...
    //sygnatury pozostałych instrukcji
    //...
    {"hello", OC_HELLO, AT_INTEGER, h_hello, s_oneinteger},
};

Napisanie implementacji instrukcji w pliku machine.cpp.

Naszą instrukcję będzie implementować funkcja h_hello, warto zatem napisać jej definicję:

void h_hello (const instruction& i)
{
    UINT helloCount = get_int_operand (i.args[0]);
    UINT i = 0;
    for(i = 0 ; i < helloCount ; ++i)
    {
        std::cout << "hello" << ' ';
    }
    ++PC;
}

Widać, że korzystamy z pola struktury instruction - tablicy args, która zawiera w sobie wszystkie argumenty z jakimi instrukcja została wywołana. Argumenty instrukcji pobieraliśmy z niej - poprzez funkcję pomocniczą get_int_operand(). Tych funkcji pomocniczych jest kilka w zależności od potrzeb i są dokładniej omówione wyżej - przy omawianiu kodu maszyny wirtualnej.

Zauważmy, że tutaj znamy z góry typ instrukcji. Gdybyśmy dopuszczali wywołanie zarówno hello.i jaki hello.r, to musielibyć my użyć następującej konstrukcji widocznej w innych implementacjach:

if (AT_INTEGER == i.at) // <- jeśli hello.i
{
    //cośtam
}
else //< - w innym wypadku mamy hello.r
{
    //cośtam innego
}

Budowa analizatora leksykalnego i składniowego.

Porady:

  1. Jeśli nadasz tokenowi nazwę BEGIN i kompilator zacznie Ci krzyczeć o redefinicji, po czym wyświetli różne inne błędy, spróbuj zmienić tę nazwę na jakąś inną. U mnie BEGIN jest stała wykorzystywana przez Flexa albo Bisona jako nazwa jakiejś stałej wewnętrznej i miałem błędy kompilacji (pomimo że redefinicja BEGIN została wyświetlona tylko jako ostrzeżenie, to ona była przyczyną).
  2. Podczas projektowania leksera pamiętaj, że kiedy napotkasz EOF, musisz zwrócić zero (0). Jest to jedyna wartość, która informuje parsera, że przetwarzanie się zakończyło. Jeśli będziesz zwracać cokolwiek innego, zawsze na końcu przetwarzania będziesz mieć parse error.
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-Share Alike 2.5 License.