Własny język programowania

03.02.2010 - Maciej Piróg
TrudnośćTrudność

Część 1.    Część 2.    Część 3.    Część 4.

Jeśli kiedykolwiek w Twojej głowie zrodził się pomysł, by wymyślić własny język programowania, zapraszamy do lektury cyklu artykułów poświęconych temu zagadnieniu. Zaczniemy od napisania kalkulatora wyrażeń arytmetycznych z nawiasami i kolejnością działań (chociaż bardzo prosty, to też jest pewien rodzaj języka programowania). Potem rozbudujemy go o zmienne, pętle i warunki, czyli wszystko, co jest potrzebne w "dorosłym" języku.

Naszym celem jest stworzenie interpretera, czyli programu, który bierze na wejściu programy napisane w naszym języku i wykonuje wszystkie zawarte w nich instrukcje. Ponieważ to jest nasz język programowania, sami możemy zdecydować jakie będą w nim konstrukcje i jakie będzie ich znaczenie. Pierwszym, bardzo prostym językiem będą wyrażenia arytmetyczne, których interpreterem jest oczywiście kalkulator, czyli program, który oblicza ich wartość.

Użyjemy mechanizmów programowania obiektowego udostępnianych przez język C++, by reprezentować wyrażenia i obliczać wartości. Potem dodamy obsługę zmiennych, by móc zajmować się wyrażeniami postaci 2 + x * y.

Wyrażenia - napisy czy drzewa?

Wyrażenia to napisy składające się z odpowiednio połączonych liczb, operatorów arytmetycznych, takich jak +, -, *, oraz nawiasów, które wraz z kolejnością działań (czyli priorytetami operatorów) pozwalają wyrażenia odpowiednio interpretować. Do wyrażeń dołączymy później także zmienne.

Każde wyrażenie ma swoją wewnętrzną strukturę, którą można przedstawić w postaci drzewa. Na przykład wyrażenie 2 + (1 + 7) * (4 * 5) można zinterpretować jako następujące drzewo:

Takie drzewo nazywamy drzewem wyrażenia. Jego węzły są poetykietowane nazwami operatorów, a liście -- liczbami. Drzewo jest binarne, ponieważ każdy z używanych przez nas operatorow jest binarny (to znaczy, że łączy dokładnie dwa wyrażenia).

Czasem nie jesteśmy pewni jak wygląda drzewo wyrażenia. Np. wyrażenie 2 * 3 * 4 może mieć następujące dwa drzewa:

Oczywiście oba są poprawne! Lewe reprezentuje wyrażenie, które możemy zapisać jako (2 * 3) * 4, a prawe 2 * (3 * 4). Mnożenie jest łączne, więc (2 * 3) * 4 = 2 * (3 * 4). Nawiasy w takich wyrażeniach możemy pominąć, gdyż nie jest ważne, czy zinterpretujemy je jak drzewo po lewej czy po prawej stronie. Problem zaczyna się, gdy operator nie jest łączny, np. operator dzielenia (/). Wyrażenie 20 / 10 / 2 możemy zinterpretować jako (20 / 10) / 2 = 2 / 2 = 1, albo jako 20 / (10 / 2) = 20 / 5 = 4. By uniknąć tego typu problemów ustalmy, że w tym artykule wszystkie operatory łączą w lewo, tzn. a + b + c rozumiemy jako (a + b) + c. Dlatego dla nas drzewem wyrażenia 2 * 3 * 4 będzie drzewo po lewej stronie.

4.8
Twoja ocena: Brak Ocena: 4.8 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com