Własny język programowania

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

Dodajemy zmienne

Teraz rozbudujemy nasze wyrażenia -- prócz stałych liczbowych będą zawierać także zmienne. Przykładowym wyrażeniem może być 2 * x + y.

Wyrażenie reprezentujące zmienną przechowuje jedynie nazwę zmiennej. Można to zaprogramować następująco:

1
2
3
4
5
6
7
class Variable : public Expression
{
    string name;
 
  public:
    Variable(string n) : name(n) { }
};

Dodanie zmiennych pociąga za sobą konieczność zmiany sposobu obliczania wyrażeń. Nie możemy obliczyć wartości wyrażenia 2 * x + y, jeśli nie znamy wartości zmiennych x i y. Dlatego wprowadzimy nowe pojęcie -- pamięć. Pamięć to struktura, w której przechowujemy wartości zmiennych. Doskonale nadaje się do tego słownik (map) z biblioteki standardowej.

Słownik przechowuje pary kluczy i przypisanych do nich wartości. Kluczami są oczywiście nazwy zmiennych (typu string), a wartościami -- wartości zmiennych (typu int):

1
typedef map<string, int> Memory;

Przy obliczaniu wartości wyrażenia trzeba przekazać pamięć jako argument metody eval. Ponieważ obiekt reprezentujący słownik może być duży (w systemie używanym przez autora tego artykułu -- 42 bajty), będziemy przekazywać go przez referencję:

1
2
3
4
5
class Expression
{
  public:
    virtual int eval(Memory& m) = 0;
};

Typ metody eval jest teraz inny, więc musimy ją zmodyfikować w każdej klasie. Dotychczasowe klasy nie używają pamięci, ale wartości zmiennych mogą być potrzebne do obliczenia wartości podwyrażeń, więc przekazujemy pamięć między wywołaniami.

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
31
32
33
class Constant : public Expression
{
    int value;
  
  public:
    Constant(int v) : value(v) {}
 
    virtual int eval(Memory& m)
    {
      return value;
    }
};
 
class Binary_operator : public Expression
{
    char symbol;
    Expression *left, *right;
 
  public:
    Binary_operator(char s, Expression* l, Expression* r)
      : symbol(s), left(l), right(r) {}
 
    virtual int eval(Memory& m)
    {
      switch (symbol)
      {
        case '*': return left->eval(m) * right->eval(m);
        case '+': return left->eval(m) + right->eval(m);
        case '-': return left->eval(m) - right->eval(m);
        // ... inne operatory
      }
    }
};

Pamięć przyda się dopiero podczas obliczania wartości zmiennej. Ale co jeśli danej zmiennej nie ma w pamięci? Wówczas zgłosimy wyjątek, który poinformuje, że wyrażenie używa zmiennej o nieznanej wartości, więc nie można obliczyć wyrażenia.

1
class Variable_not_found { };

Samo obliczenie wartości zmiennej jest łatwe -- jeśli zmienna jest w pamięci, to zwracamy jej wartość, a jeśli jej nie ma, to zgłaszamy wyjątek. W słowniku wyszukujemy parę (klucz, wartość) przy użyciu metody find, która zwraca iterator (jego pole first przechowuje klucz, a pole second przechowuje wartość znalezionej pary).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Variable : public Expression
{
    string name;
 
  public:
    Variable(string n) : name(n) { }
  
    virtual int eval(Memory m)
    {
      Memory::iterator it = m.find(name);
      if (it == m.end()) // Nie ma zmiennej w pamięci
        throw Variable_not_found();
      return it->second;
    }
};

By zaprezentować działanie wyrażeń ze zmiennymi, obliczmy wartość wyrażenia 2 * x + y dla x = 10 i y = 5:

1
2
3
4
5
6
7
8
9
  Expression* e = new Binary_operator('+',
    new Binary_operator('*', new Constant(2), new Variable("x")),
    new Variable("y"));
 
  Memory m;
  m["x"] = 10;
  m["y"] = 5;
  
  cout << e->eval(m);

Tak jak można się spodziewać, powyższy fragment spowoduje wypisanie na ekranie liczby 25.

Podsumowanie

Napisaliśmy program, który umie przechowywać i obliczać wartości drzew wyrażeń. Trudno jednak nazwać go pełnym interpreterem, gdyż na wejściu bierze on pewną strukturę języka C++, a nie kod (czyli dane tekstowe) żadnego języka. Kodem w naszym języku wyrażeń są oczywiście napisy postaci 2 * 2 * 3 + 7, które interpreter powinien zamieniać na drzewa i obliczać ich wartość. By dokończyć kalkulator (czyli interpreter wyrażeń arytmetycznych), musimy napisać parser, czyli element interpretera, który będzie tę zamianę przeprowadzał. Tym właśnie zajmiemy się w części 2. cyklu!
4.8
Twoja ocena: Brak Ocena: 4.8 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com