Własny język programowania. Część 3: Reprezentacja i interpretacja języka programowania

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

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

W trzeciej części cyklu stworzymy w końcu "dorosły" (choć bardzo prosty) język programowania przypominający język C oraz napiszemy samo serce interpretera, czyli klasy, które przechowują w pamięci oraz wykonują programy napisane w naszym języku.

Programy - napisy czy drzewa?

Napisy 2+(3 * (2+ 2)) i ((2) + 3 * ((2 + 2))) nie są takie same, choć reprezentują wyrażenia o dokładnie takich samych drzewach. Z drugiej strony, napisy 3 + 1 i 2 + 2 to dwa różne wyrażenia, które mają taką samą wartość.

Podobnie jest z programami napisanymi w jakimś języku programowania. Porównajmy dwa poniższe programy napisane w C++:

1
2
3
4
5
6
7
8
9
10
int main()
{
  int i = 0;
  while (i < 10)
  {
    std::cout << i;
    i++;
  }
  return 0;
}

1
2
3
4
5
int main() {
  int i = 0;
  while (i < 10) { std::cout << i; i++; }
  return 0;
}

Chociaż formatowanie kodu jest inne, te programy tak naprawdę są takie same. Natomiast poniższy program, choć wynik jego działania jest taki sam, jest inny:

1
2
3
4
5
6
7
8
9
10
int main()
{
  int i = 10;
  while (true)
  {
    std::cout << 10 - i--;
    if (! i) break;
  }
  return 0;
}

Podobnie jak w przypadku wyrażeń arytmetycznych, będziemy myśleć o programach jako o drzewach. Pierwsze dwa programy mają takie same drzewa, natomiast trzeci program ma inne drzewo.

Drzewo pierwszego programu mogłoby wyglądać tak:

Kolor żółty oznacza instrukcje, zielony - wyrażenia, a pomarańczowy - L-wyrażenia (czyli takie, które mogą znaleźć się po lewej stronie znaku '=').

Bardzo ważną obserwacją jest to, że drzewa równoważnych programów zapisanych w różnych językach programowania są bardzo podobne i abstrahują od tego, jak poszczególne instrukcje są zapisane w języku (np. czy bloki wyrażeń oddzielamy nawiasami { } czy też słowami kluczowymi BEGIN i END jak w języku Pascal). To, jakie konstrukcje występują w języku i jakich instrukcji i/lub wyrażeń potrzebują, nazywamy składnią abstrakcyjną. Natomiast reguły ich zapisywania w postaci tekstu to składnia konkretna.

Parsowaniem programów, czyli zamianą tekstu programu na drzewo programu (składni konkretnej na składnię abstrakcyjnej), zajmiemy się w czwartej części cyklu.

Instrukcje

Nasz język programowania będzie językiem imperatywnym, więc działającym w stylu języka C. W takim języku są dwa rodzaje instrukcji:

Instrukcje proste to np. instrukcja przypisania. W języku C++ instrukcja taka ma postać:

1
x = 2 * x + y;

W naszym języku dodatkowo będziemy mieli oddzielne instrukcje do wypisywania wartości zmiennej na ekran i wczytywania zmiennej z wejścia.

Instrukcje złożone to instrukcje powstałe ze złożenia innych instrukcji i wyrażeń arytmetycznych. Przykładem instrukcji złożonej jest warunek if, który składa się z wyrażenia arytmetycznego (warunku) i dwóch instrukcji (tej, która ma wykonać się, jeśli warunek jest prawdziwy i tej, która wykonuje się w przeciwnym przypadku). W języku C++ przyjmuje ona postać:

1
2
3
4
if (warunek)
  instrukcja_then;
else
  instrukcja_else;

Szczególnym przypadkiem instrukcji złożonej jest instrukcja złożenia, która łączy instrukcje w ciąg. Instrukcje w ciągu wykonywane są po kolei. W języku C++ ma ona postać bloku:

1
2
3
4
5
6
{
  instrukcja_1;
  instrukcja_2;
  instrukcja_3;
  // ...
}

Możemy więc myśleć o całym programie jako o pojedynczej instrukcji, która najczęściej jest złożeniem wielu instrukcji. Przykładowo, przeanalizujmy ciało znanej już nam funkcji:

1
2
3
4
5
6
7
8
9
10
int main()
{
  int i = 0;
  while (i < 10)
  {
    std::cout << i;
    i++;
  }
  return 0;
}

Zawartość tej funkcji to instrukcja będąca złożeniem 3 instrukcji: przypisania, pętli i operatora return. Instrukcja pętli składa się z wyrażenia arytmetycznego i < 10 i ciała, które jest instrukcją będącą złożeniem 2 instrukcji: pierwsza wypisuje na ekran wartość zmiennej i (jest to aplikacja opeatora << do strumienia cout i zmiennej i), a druga zwiększa wartość zmiennej i o jeden (jest to postfiksowy operator ++ zaaplikowany do zmiennej i).

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com