Budowa Kompilatorow

Budowa kompilatorów

Prowadzący

Jędrzej Jabłoński

Zajawka

Napisanie prawdziwego kompilatora wydaje się zadaniem trudnym i przerażającym, . Podczas tych warsztatów zaprezentuję metody wypracowane przez pokolenia specjalistów. Omówimy techniki stosowane w rzeczywistych kompilatorach fortrana, C/C++ (gcc) oraz ocamla. Pod koniec przekonacie się, że budowa kompilatora jest przodową zabawą, a wiedza o technikach optymalizacji jest nieoceniona podczas zwykłego klepania kodu w C/C++.

Opis

Omówię strukturę kompilatora (podział na warstę leksykalną, składniową, kontekstową, generowanie kodu pośredniego, optymalizacje, generowanie kodu docelowego). Następnie zajmiemy się (w zależności od zainteresowania słuchaczy i ilością dostępnego czasu niektórymi z następujących tematów):

  • definiowanie języka programownia
  • analiza leksykalna (automaty)
  • analiza składniowa (parsery LL, LR, SLR, LALR, GLR)
  • analiza kontekstowa
  • łączenie analizy składniowej z kontekstową
  • standardowe problemy generowania kodu (reprezentacja tablic, list, struktur, obiektów, dziedziczenie klas, szablony, dynamiczne typowanie, programowanie funkcyjne, wyliczanie typów, etc.).
  • optymalizacje

Wymagania

Wymagana będzie ogólna umiejętność programowania oraz znajomość jednego z języków: C, C++, Ocaml, Pascal.

Kwalifikacja

Do rozwiązania są trzy zadania różnie punktowane. Należy nadesłać je mailem do 20.07.09 na adres: lp.moc.iee|5www-nirolo#lp.moc.iee|5www-nirolo. Każde zadanie można wysłać dokładnie jeden raz. Do przyjęcia na warsztat wystarczy 21pkt.

1. (10pkt) Napisz program, który ze standardowego wejścia wczytuje dokładnie jedną linię, będącą działaniem arytmetycznym zawierającym dodawanie, odejmowanie, liczby naturalne <10^9 oraz nawiasy.

Przykład0:
1-3+2

Przykład1:
1-(3+2)

Rozwiązanie ma wypisywać reprezentację /drzewa składni wczytanego wyrażenia/. /Drzewo składni/ jest takim drzewem binarnym, że /zawartością/ każdego wierzchołka-liścia jest liczba naturalna <10^9, a zawartością pozostałych wierzchołków może być albo działanie "+" albo działanie "-".

Wartością wierzchołka z liczbą nazwiemy tę liczbę; wartością wierzchołka z "+" nazwiemy sumę wartości synów; wartością wierzchołka z "-" nazwiemy różnicę wartości lewego syna i prawego syna.

/Drzewo składni wyrażenia/ jest drzewem składni o wartości takiej jak wartość wyrażenia, oraz takim, że każda liczba znajdująca się w wyrażeniu znajduje się w dokładnie jednym wierzchołku tego drzewa.

Reprezentacja drzewa składni wypisywana na standardowe wyjście powinna być następująca:

  • Zawartość wierzchołka
  • Reprezentacja lewego poddrzewa
  • Reprezentacja prawego poddrzewa

Przykład0: 1-3+2
+
1
-
2
3

Przykład1: 1-(3+2)
-
1
+
3
2

Uwagi:
Można założyć, że wyrażenie na wejściu jest poprawnie nawiasowane.
Jeżeli w wyrażeniu pewna liczba występuje n razy, to w drzewie też musi wystąpić w dokładnie n wierzchołkach.

2. (15pkt) Zimplementuj interpreter języka R6.
Program w języku R6 składa się z liczb <10^9 oraz znaków:

+,*,-,/,|,d,p,t,e,;,r

Program w R6 dysponuje stosem, który przy starcie jest pusty.

  • Instrukcja będąca znakiem ; nic nie robi
  • Instrukcja będąca liczbą powoduje odłożenie tej liczby na stosie.
  • Instrukcja będąca znakiem + powoduje zdjęcie dwóch górnych liczb ze stosu, dodanie ich i odłożenie wyniku na stosie.
  • Instrukcja będąca znakiem - powoduje zdjęcie dwóch górnych liczb ze stosu, odjęcie pierwszej od drugiej i odłożenie wyniku na stosie.
  • Instrukcja będąca znakiem * powoduje zdjęcie dwóch górnych liczb ze stosu, pomnożenie ich i odłożenie wyniku na stosie.
  • Instrukcja będąca znakiem / powoduje zdjęcie dwóch górnych liczb ze stosu, podzielenie drugiej przez pierwszą i odłożenie wyniku na stosie.
  • Instrukcja będąca znakiem | powoduje zdjęcie górnej liczby ze stosu i odłożenie jej wartości absolutnej na stosie.
  • Instrukcja będąca znakiem d powoduje zdjęcie górnej liczby ze stosu i odłożenie jej dwa razy na stosie.
  • Instrukcja będąca znakiem p powoduje zdjęcie górnej liczby ze stosu
  • Instrukcja będąca znakiem t powoduje zdjęcie trzech górnych liczb ze stosu i odłożenie ich w kolejności:

pierwsza, trzecia, druga

  • Instrukcja będąca znakiem e powoduje wypisanie górnej liczby ze stosu na standardowe wyjście i zakończenie programu z błędem.
  • Instrukcja będąca znakiem r sprawdza czy górna liczba ze stosu jest równa 0 i jeśli nie to wraca do ostatniej instrukcji, będącej znakiem ;

Jeżeli do wykonania instrukcji potrzebne jest więcej liczb na stosie niż jest program powinien zakończyć się natychmiastowo z błędem.

Instrukcja t powinna przeprowadzić stos:
<— dół stosu — c b a
na stos:
<— dół stosu — a c b

Po wykonaniu wszystkich instrukcji następuje wypisanie wszystkich liczb ze stosu.

3. (5pkt) Zaimplementuj program liczący NWD dwóch liczb w języku R6. (argumenty programu będą leżeć na stosie na początku jego wykonania).

Dodatkowe 10pkt można zdobyć za program z zadania 2. przechodzący szybko testy. Brana będzie pod uwagę suma po wszystkich testach: (czas przejścia / czas przejścia przez wzorcówkę). 10 pkt dostaną wszystkie programy działające niewolniej niż 7% wolniej od najszybszego.

Dodatkowe 2pkt można zdobyć za najkrótszy z wysłanych program z zadania 3.

FAQ

Wszelkie pytania proszę wysyłać na adres: lp.moc.iee|5www-nirolo#lp.moc.iee|5www-nirolo

  1. Instrukcje w języku R6 oddzielone są pojedynczą spacją
  2. Liczby w języku R6 są *naturalne* i mniejsze niż 10^9
  3. Liczby znajdujące się na stosie podczas wykonania programu w R6 nie muszą być naturalne, ale zakładamy, że zmieszczą się w zmiennej typu (long long).
  4. Programy będą kompilowane (jak na OI) poleceniami:
    1. Dla C - gcc -O2 -static abc.c -lm
    2. Dla C++ - g++ -O2 -static abc.cpp -lm
    3. Dla Pascala - ppc386 -O2 -XS -Xt abc.pas
    4. Dla Ocamla - ocamlopt -nodynlink abc.ml

Dla tych, którzy nie mogą się doczekać

Dla tych, którzy nie mogą się doczekać przygotowałem stronę z dodatkowymi materiałami: [http://mindoscope.net/~olorin/www5].

Wyniki kwalifikacji

  1. Aby zakwalifikować się na warsztat wystarczy i potrzeba mieć co najmniej 19 punktów.
  2. Z powodu mojej nieobecności w drugiej połowie lipca zgłaszanie reklamacji w przypadku niektórych osób było niemożliwe. Dlatego wszystkim, którzy nie uzyskali 14-18 punktów i nie oddali jednego zadania (we wszystkich przypadkach było to zadanie 3) proponuję, aby wysłali mi to zadanie do 5.VIII, a ja postaram się przekonać organizatorów warsztatów, że jeszcze mogę dopisać ich nazwiska do listy zakwalifikowanych.
  3. Punkty dodatkowe za zadanie 2. można było zdobyć jedynie w przypadku kiedy program działał :) tzn m.in. miał dynamiczny stos oraz operacje na zmiennych typu (long long). Byłoby nie fair porównywać szybsze programy bez dynamicznego stosu operujące na intach z poprawnymi, przez co wolniejszymi.
  4. Hall of Fame:
    1. Szymon Gut (38pkt - zad1: 5+3 - zad2: 10+5 - zad3: 5 - bonus1: 10 - bonus2: 0)
    2. Marcin Paśko (31pkt - zad1: 5+4 - zad2: 10+5 - zad3: 5 - bonus1: 0 - bonus2: 2)
    3. Paweł Kubiak (28pkt - zad1: 5+3 - zad2: 10+5 - zad3: 5 - bonus1: 0 - bonus2: 0)
  5. Lista zakwalifikowanych (w kolejności pseudolosowej):
    1. Jan.Kwasniak
    2. Karol.Brzuskiewicz
    3. Marcin.Pasko
    4. Mateusz.Jurczyk
    5. Pawel.Kubiak
    6. Pawel.Zuk
    7. Szymon.Gut
    8. Tomasz.Jedrzejewski
    9. Marcin.Labanowski
  6. Programy wzorcowe:
    1. Zadanie 2: [http://mindoscope.net/~olorin/content/www5/R6.cpp]
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License