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

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

Sprzątamy

Jak widać nasz parser działa. Uważny czytelnik zauważy jednak, że w razie wystąpienia błędu parsowania, wszystkie częściowo utworzone wyrażenia pozostaną w pamięci, ale wskaźniki do nich zostaną stracone, więc nastąpi wyciek pamięci. Choć w przypadku prostego kalkulatora nie ma to większego znaczenia, przyzwoitość wymaga, by po sobie posprzątać. Zmodyfikujmy więc parser tak, by w razie błędu usuwał z pamięci niepotrzebne wyrażenia.

Zarządzanie pamięcią (czyli odpowiednie używanie operatorów new i delete) bardzo komplikuje się, jeśli próbujemy łączyć je z mechanizmem wyjątków. Na szczęście nasz parser jest na tyle prosty, że nie będzie to aż tak trudne.

Na początek dodamy do wyrażeń odpowiednie wirtualne destruktory:

1
2
3
4
5
6
class Expression
{
  public:
    virtual ~Expression() {}
    // ...
};

Zmodyfikować musimy też klasę Binary_operator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Binary_operator : public Expression
{
    char symbol;
    Expression *left, *right;
 
  public:
 
    virtual ~Binary_operator()
    {
      delete left;
      delete right;
    }
 
    // ...
};

W ten sposób usunięcie korzenia drzewa wyrażenia spowoduje usunięcie całego drzewa. Klas Constant i Variable nie musimy modyfikować.

W parserze musimy zmodyfikować tylko te metody, które budują pewne poddrzewo, a dopiero potem dowiadują się, że gdzieś dalej wystąpił błąd. Ich zadaniem będzie usunięcie z pamięci niepotrzebnych poddrzew. Zmiany wymagają metody parse_Expression, parse_sum, parse_mult oraz parse_paren:

1
2
3
4
5
6
7
8
9
10
11
Expression* Parser::parse_Expression()
{
  Expression* e = parse_sum();
  if (look_ahead() == EOS)
    return e;
  else
  {
    delete e;
    throw Not_parsed();
  }
}

Jeśli po sparsowaniu wyrażenia nie widzimy końca wejścia (taka sytuacja może wystąpić np. gdy parsujemy ciąg znaków 2 + 3 5), wyrażenie nie jest potrzebne, więc musimy koniecznie usunąć je z pamięci.

Podobnie, jeśli nie uda nam się sparsować prawego podwyrażenia w "sumie" lub składniku, to musimy usunąć lewe, już zbudowane, podwyrażenie. Pamiętajmy, że w C++ bezpieczne jest wywołanie operatore delete na wskaźniku o wartości NULL.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Expression* Parser::parse_sum()
{
  Expression* e = NULL;
 
  try
  {
    e = parse_mult();
    char c = look_ahead();
 
    while(c == '+' || c == '-')
    {
      position++;
      e = new Binary_operator(c, e, parse_mult());
      c = look_ahead();
    }
  }
  catch (Not_parsed)
  {
    delete e;
    throw Not_parsed();
  }
 
  return e;
}
 
Expression* Parser::parse_mult()
{
  Expression* e = NULL;
  
  try
  {
    e = parse_term();
    char c = look_ahead();
  
    while(c == '*' || c == '/' || c == '%')
    {
      position++;
      e = new Binary_operator(c, e, parse_term());
      c = look_ahead();
    }
  }
  catch (Not_parsed)
  {
    delete e;
    throw Not_parsed();
  }
 
  return e;
}

Bardzo podobnie dla nawiasów:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Expression* Parser::parse_paren()
{
  position++; // parse_term zapewnia, że wskaźnik
              // stoi na nawiasie otwierającym '('
  Expression* e = parse_sum();
  if (look_ahead() == ')')
  {
    position++;
    return e;
  }
  else
  {
    delete e;
    throw Not_parsed();
  }
}

Ogólniej o parserach

Parser dla wyrażeń arytmetycznych okazał się dość zawiły i rozwlekły. A wyrażenia arytmetyczne są bardzo proste w porównaniu do pełnych języków programowania. Jak więc pisać dla nich parsery, by nie zaplątać się w przesuwanie wskaźnika i usuwanie zbędnych podwyrażeń w razie błędu parsowania? Jedną z możliwości jest użycie specjalnego oprogramowania, które automatycznie wygeneruje parser dla odpowiednio opisanego języka. Do najpopularniejszych generatorów parserów należą Yacc, Bison, ANTLR i Lemon.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com