Własny język programowania. Część 2: Parser + wyrażenia = kalkulator

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

W drugiej części cyklu dotyczącego interpretera prostego języka programowania zajmiemy się parsowaniem, czyli przekształcaniem napisów reprezentujących wyrażenia w drzewa wyrażeń. Ponieważ umiemy już obliczać wartości wyrażeń przedstawionych jako drzewa, powstanie kalkulator (czyli interpreter języka wyrażeń arytmetycznych).

Pobierz cały kod źródłowy opisany w artykule

Część programu, która przekształca wyrażenia (a także inne napisy, jak na przykład kod programu) w drzewa wyrażeń (lub inne struktury danych np. reprezentujące strukturę programu), nazywa się parserem. Teraz napiszemy parser, który będzie budował drzewa wyrażeń opisane w poprzedniej części, co pozwoli nam zbudować prosty kalkulator -- użytkownik będzie wpisywał wyrażenie, które będzie parsowane, a potem zostanie obliczona jego wartość.

Struktura wyrażeń

By napisać parser wspomożemy się następującą obserwacją na temat wyrażeń:

• Każde wyrażenie jest "sumą", czyli elementami (zwanymi składnikami) oddzielonymi znakami '+' lub '-'. Innymi słowy każde wyrażenie ma postać s₁ +/- s₂ +/- ... +/- s_n. Przykładowo wyrażenie W = 1 + 2 * 4 + (3 + 5) - 8 ma cztery składniki: 1, 2 * 4, (3 + 5) oraz 8. Składnika (3 + 5) nie uważamy za dwa składniki 3 i 5 w wyrażeniu W ze względu na otaczające go nawiasy (oczywiście 3 i 5 to składniki wyrażenia 3 + 5). Istnieją wyrażenia, które mają tylko jeden składnik, np. (2 + 2) * 5 * (4 + 3 + 4).
• Każdy składnik składa się z połączonych operatorami '*', '/', '%' tzw. czynników. Dla przykładu, wyrażenie 2 * 4 + (2 + 3) + 4 * (7 + 1) % 6 ma 3 składniki:
  • 2 * 4 to składnik, który ma dwa czynniki: 2 i 4
  • (2 + 3) to składnik, który ma jeden czynnik: (2 + 3)
  • 4 * (7 + 1) % 6 to składnik, który ma trzy czynniki: 4, (7 + 1) i 6
• Każdy czynnik to albo liczba, albo dowolna "suma" wzięta w nawiasy.

Struktura parsera

Parser będzie klasą, która przechowuje w swoich polach analizowany tekst i wskaźnik na aktualnie "oglądany" znak. Szereg metod będzie odpowiedzialnych za parsowanie danego "poziomu" wyrażenia: oddzielne metody będą odpowiedzialne za parsowanie "sum", składników, czynników, liczb i nazw zmiennych. Po wykonaniu swojego zadania, metoda zwraca odpowiednie wyrażenie i przesuwa wskaźnik na pierwszy znak po nim.

Przykładowo, metoda do parsowania składnika będzie używać metody do parsowania czynników w następujący sposób:

1. Wywołanie metody parsowania składnika to poproszenie o zbudowanie drzewa wyrażenia z podwyrażenia zaczynającego się w miejscu aktualnie pokazywanym przez wskaźnik.
2. Ponieważ składnik to czynniki oddzielone znakami '*', '/' lub '%', wywołujemy metodę parsującą czynnik.
3. Metoda parsująca czynnik ustawi wskaźnik za czynnikiem, więc sprawdzamy, czy za czynnikiem (pomijając białe znaki, czyli spacje i znaki nowego wiersza) jest symbol '*', '/' lub '%'. Jeśli tak, to parsujemy kolejny czynnik i czynność powtarzamy.
4. Jeśli znakiem za czynnikiem nie jest '*', '/' ani '%' (może tam znaleźć się np. '+', ')' albo koniec wejścia), to oznacza, że skończyliśmy parsowanie składnika, więc łączymy drzewa wyrażeń zwrócone przez metody parsowania czynników w drzewo reprezentujące składnik, pamiętając, że (tak jak umówiliśmy się w poprzedniej części) wyrażenie 2 * 3 * 4 oznacza (2 * 3) * 4.

Ponieważ metoda parsująca ostatni czynnik ustawi wskaźnik na pierwszym znaku za ostatnim czynnikiem, w tym momencie mamy ustawiony wskaźnik na pierwszym znaku za całym składnikiem (bo ostatni znak ostatniego czynnika to ostatni znak całego składnika).

Strukturę parsera opisuje następująca deklaracja:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Parser
{
    string input;    // analizowany tekst
    size_t position; // wskaźnik na aktualnie "oglądany" znak
 
  public:
 
    Parser(string input);
    
    // Pomija wszystkie białe znaki i przesuwa wskaźnik
    // na pierwszy znak, który nie jest biały.
    void skip_whitespace();
 
    // Pomija białe znaki i informuje jaki znak "oglądamy". 
    char look_ahead();
 
    Expression* parse_Expression(); // Parsuje wyrażanie.
    Expression* parse_sum();        // Parsuje "sumę".
    Expression* parse_mult();       // Parsuje składnik.
    Expression* parse_term();       // Parsuje czynnik.
    Expression* parse_Constant();   // Parsuje liczbę.
    Expression* parse_Variable();   // Parsuje nazwę zmiennej.
    Expression* parse_paren();      // Parsuje "sumę" w nawiasie.
};

Przyda się nam także wyjątek, który zgłosimy, jeśli parsowanie się nie powiedzie, gdy tekst zadany do analizy nie jest prawidłowym wyrażeniem:

1

class Not_parsed { };