Część 1. [1] Część 2. [2] Część 3. Część 4. [3]
W trzeciej części cyklu stworzymy w końcu "dorosły" (choć bardzo prosty) język programowania przypominający język C oraz napiszemy samo serce interpretera, czyli klasy, które przechowują w pamięci oraz wykonują programy napisane w naszym języku.
Napisy 2+(3 * (2+ 2))
i ((2) + 3 * ((2 + 2)))
nie są takie same, choć reprezentują wyrażenia o dokładnie takich samych drzewach. Z drugiej strony, napisy 3 + 1
i 2 + 2
to dwa różne wyrażenia, które mają taką samą wartość.
Podobnie jest z programami napisanymi w jakimś języku programowania. Porównajmy dwa poniższe programy napisane w C++:
1 2 3 4 5 6 7 8 9 10 | int main() { int i = 0; while (i < 10) { std::cout << i; i++; } return 0; } |
1 2 3 4 5 | int main() { int i = 0; while (i < 10) { std::cout << i; i++; } return 0; } |
Chociaż formatowanie kodu jest inne, te programy tak naprawdę są takie same. Natomiast poniższy program, choć wynik jego działania jest taki sam, jest inny:
1 2 3 4 5 6 7 8 9 10 | int main() { int i = 10; while (true) { std::cout << 10 - i--; if (! i) break; } return 0; } |
Podobnie jak w przypadku wyrażeń arytmetycznych, będziemy myśleć o programach jako o drzewach. Pierwsze dwa programy mają takie same drzewa, natomiast trzeci program ma inne drzewo.
Drzewo pierwszego programu mogłoby wyglądać tak:
Kolor żółty oznacza instrukcje, zielony - wyrażenia, a pomarańczowy - L-wyrażenia (czyli takie, które mogą znaleźć się po lewej stronie znaku '=').
Bardzo ważną obserwacją jest to, że drzewa równoważnych programów zapisanych w różnych językach programowania są bardzo podobne i abstrahują od tego, jak poszczególne instrukcje są zapisane w języku (np. czy bloki wyrażeń oddzielamy nawiasami { }
czy też słowami kluczowymi BEGIN
i END
jak w języku Pascal). To, jakie konstrukcje występują w języku i jakich instrukcji i/lub wyrażeń potrzebują, nazywamy składnią abstrakcyjną. Natomiast reguły ich zapisywania w postaci tekstu to składnia konkretna.
Nasz język programowania będzie językiem imperatywnym, więc działającym w stylu języka C. W takim języku są dwa rodzaje instrukcji:
Instrukcje proste to np. instrukcja przypisania. W języku C++ instrukcja taka ma postać:
1 | x = 2 * x + y; |
W naszym języku dodatkowo będziemy mieli oddzielne instrukcje do wypisywania wartości zmiennej na ekran i wczytywania zmiennej z wejścia.
Instrukcje złożone to instrukcje powstałe ze złożenia innych instrukcji i wyrażeń arytmetycznych. Przykładem instrukcji złożonej jest warunek if
, który składa się z wyrażenia arytmetycznego (warunku) i dwóch instrukcji (tej, która ma wykonać się, jeśli warunek jest prawdziwy i tej, która wykonuje się w przeciwnym przypadku). W języku C++ przyjmuje ona postać:
1 2 3 4 | if (warunek) instrukcja_then; else instrukcja_else; |
Szczególnym przypadkiem instrukcji złożonej jest instrukcja złożenia, która łączy instrukcje w ciąg. Instrukcje w ciągu wykonywane są po kolei. W języku C++ ma ona postać bloku:
1 2 3 4 5 6 | { instrukcja_1; instrukcja_2; instrukcja_3; // ... } |
Możemy więc myśleć o całym programie jako o pojedynczej instrukcji, która najczęściej jest złożeniem wielu instrukcji. Przykładowo, przeanalizujmy ciało znanej już nam funkcji:
1 2 3 4 5 6 7 8 9 10 | int main() { int i = 0; while (i < 10) { std::cout << i; i++; } return 0; } |
Zawartość tej funkcji to instrukcja będąca złożeniem 3 instrukcji: przypisania, pętli i operatora return
. Instrukcja pętli składa się z wyrażenia arytmetycznego i < 10
i ciała, które jest instrukcją będącą złożeniem 2 instrukcji: pierwsza wypisuje na ekran wartość zmiennej i
(jest to aplikacja opeatora <<
do strumienia cout
i zmiennej i
), a druga zwiększa wartość zmiennej i
o jeden (jest to postfiksowy operator ++
zaaplikowany do zmiennej i
).
Teraz stworzymy nasz język programowania, a właściwie jego główną część, czyli ustalimy jakie instrukcje są potrzebne i jak je reprezentować wewnątrz interpretera. Póki co, w ogóle nie będziemy interesować się jego składnią, czyli tym, jak konstrukcje będą reprezentowane w postaci tekstowej (tym zajmiemy się w części czwartej).
Poszczególne instrukcje będą reprezentowane w postaci klas dziedziczących z nadrzędnej klasy Program
:
1 2 3 | class Program { }; |
skip. Pierwsza instrukcja w naszym języku będzie banalna. Nie robi ona dokładnie nic -- jej wykonanie nie zmienia wartości zmiennych, ani nie wpływa na przebieg programu. Przyda się nam, gdyż instrukcja warunkowa będzie miała obowiązkową gałąź 'else'.
Klasa, która opisuje instrukcje skip na razie może być zdefiniowana jako:
1 2 3 | class Skip : public Program { }; |
przypisanie. Przypisanie w naszym języku to instrukcja, która ma dwa argumenty - nazwę zmiennej do której przypisujemy i wyrażenie, którego wartość jest przypisywana (Expression
to klasa, którą zajmowaliśmy się w 1. artykule cyklu):
1 2 3 4 5 6 7 8 | class Assign : public Program { string var; Expression* expr; public: Assign(string v, Expression* e) : var(v), expr(e) { } }; |
read. Jest to instrukcja, która pobiera od użytkownika liczbę i zapisuje w zmiennej będącej argumentem:
1 2 3 4 5 6 7 | class Read : public Program { string var; public: Read(string v) : var(v) { } }; |
write. Instrukcja siostrzana w stosunku do read. Jej zadanie to wypisywanie na ekran wartości zmiennej:
1 2 3 4 5 6 7 | class Write : public Program { string var; public: Write(string v) : var(v) { } }; |
złożenie. Złożenie instrukcji będzie binarne, to znaczy będziemy mogli składać ze sobą tylko dwie instrukcje. Oczywiście taką złożoną instrukcję możemy złożyć z inną instrukcją, w ten sposób dostając "złożenie" trzech instrukcji. Trochę podobnie jest z dodawaniem: możemy zapisać "1 + 2 + 3 + 4", choć operator '+' jest binarny, a wyrażenie tak naprawdę oznacza ((1 + 2) + 3) + 4, tak samo blok {i1; i2; i3; i4;}
można rozumieć jako blok {{{i1; i2}; i3}; i4}
. Oczywiście w składni języka nie będzie tego widać (będzie podobnie jak w języku C++, ale o tym dowiemy się w 4. części cyklu). Złożenie można zdefiniować jako:
1 2 3 4 5 6 7 | class Composition : public Program { Program* left, * right; public: Composition(Program* l, Program* r) : left(l), right(r) { } }; |
warunek. Warunek składa się z wyrażenia i dwóch instrukcji (jeśli wyrażenie będzie różne od zera, wykonujemy pierwszą instrukcję, jeśli wyrażenie będzie równe zero, wykonujemy drugą instrukcję).
1 2 3 4 5 6 7 8 9 | class If : public Program { Program* branch_then, * branch_else; Expression* condition; public: If(Expression* c, Program* t, Program* e) : condition(c), branch_then(t), branch_else(e) { } }; |
pętla. Pętla składa się z wyrażenia i instrukcji będącej ciałem pętli. Ciało wykonujemy dopóki wartość wyrażenia jest różna od zera.
1 2 3 4 5 6 7 8 9 | class While : public Program { Program *body; Expression* condition; public: While(Expression* c, Program* b) : condition(c), body(b) { } }; |
Mamy już klasy, które przechowują w pamięci program w postaci drzewa. Teraz wystarczy dopisać metodę, która interpretuje poszczególne węzły i liście tego drzewa.
Efekt wykonania programu zależy od stanu pamięci, tj. wartości wszystkich zmiennych. Przypomnijmy, że pamięć definiujemy jako:
1 | typedef map<string, int> Memory; |
Teraz dodamy wirtualną metodę, która odpowiada za interpretację danej instrukcji:
1 2 3 4 5 | class Program { public: virtual void eval(Memory& m) = 0; }; |
Interpretacja instrukcji skip jest banalna. Skoro intrukcja nic nie robi, metoda obliczająca wynik jej działania jest pusta:
1 2 3 4 5 | class Skip : public Program { public: virtual void eval(Memory& m) { } }; |
Instrukcja przypisania oblicza wartość wyrażenia i aktualizuje pamięć:
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Assign : public Program { string var; Expression* expr; public: Assign(string v, Expression* e) : var(v), expr(e) { } virtual void eval(Memory& m) { m[var] = expr->eval(m); } }; |
Instrukcje read i write wczytują i wypisują na ekran zmienne:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | class Read : public Program { string var; public: Read(string v) : var(v) { } virtual void eval(Memory& m) { int n; cin >> n; m[var] = n; } }; class Write : public Program { string var; public: Write(string v) : var(v) { } virtual void eval(Memory& m) { Memory::iterator it = m.find(var); if (it == m.end()) throw Variable_not_found(); cout << m[var] << endl; } }; |
By zinterpretować złożenie, wystarczy zinterpetować po kolei jego elementy:
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Composition : public Program { Program* left, * right; public: Composition(Program* l, Program* r) : left(l), right(r) { } virtual void eval(Memory& m) { left->eval(m); right->eval(m); } }; |
Interpretacja warunku? Oczywiście najpierw oblicamy wartość wyrażenia, a potem, w zależności od wyniku, odpowiednią wartość.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class If : public Program { Program* branch_then, * branch_else; Expression* condition; public: If(Expression* c, Program* t, Program* e) : condition(c), branch_then(t), branch_else(e) { } virtual void eval(Memory& m) { if (condition->eval(m) != 0) branch_then->eval(m); else branch_else->eval(m); } }; |
Pozostała jeszcze pętla. Najpierw obliczamy wartość wyrażenia. Jeśli jest ono równe 0, to interpretacja jest zakończona. W przeciwnym wypadku uruchamiamy ciało pętli, by po jego zakończeniu powtórzyć całą procedurę.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class While : public Program { Program *body; Expression* condition; public: While(Expression* c, Program* b) : condition(c), body(b) { } virtual void eval(Memory& m) { if (condition->eval(m) != 0) { body->eval(m); this->eval(m); } } }; |
Nadszedł czas na mały test. Napiszmy program, który wypisuje liczby od 0 do 9. W pseudokodzie taki program mógbły wyglądać tak (pamiętajmy, że póki co nie interesuje nas konkretna składnia, będziemy się nią zajmować w kolejnej części cyklu):
1 2 3 4 | int i = 0 while 10 - i write i i = i + 1 |
Ponieważ nasz jężyk nie ma jeszcze składni, a tym bardziej parsera, drzewo programu trzeba wpisać ręcznie:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int main() { Program* p = new Composition( new Assign("i", new Constant(0)), new Whaile( new Binary_operator('-', new Constant(10), new Variable("i")), new Composition( new Write("i"), new Assign("i", new Binary_operator('+', new Variable("i"), new Constant(1))) ) ) ); Memory m; p->eval(m); return 0; } |
Po uruchomieniu tej funkcji, na ekranie pokaże się kolumna z cyframi od 0 do 9, więc zgodnie z planem.
Odnośniki:
[1] http://informatyka.wroc.pl/node/391
[2] http://informatyka.wroc.pl/node/431
[3] http://informatyka.wroc.pl/node/487
[4] http://informatyka.wroc.pl/upload/interpreter/progr.cpp