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

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

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).

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ć s1 +/- s2 +/- ... +/- sn. 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.

Przykładowo wyrażenie (1 + 1 * 1) to "suma" jednego składnika, a mianowicie (1 + 1 * 1), który ma jeden czynnik, mianowicie (1 + 1 * 1). Czynnik ten to "suma" 1 + 1 * 1 wzięta w nawias, która składa się z dwóch składników 1 i 1 * 1. Drugi składnik ma dwa czynniki: 1 oraz 1.

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 { };

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com