[WikiDyd] [TitleIndex] [WordIndex

Języki formalne i kompilatory

Prowadzący: dr inż. BartoszSawicki

Poprzednia wersja przedmiotu z lat 2005-2009: wykład, laboratorium

Opis przedmiotu:

Przedmiot zajmuje się teoretycznymi i praktycznymi aspektami konstrukcji kompilatorów. Przedstawione są wszystkie etapy pracy kompilatora: analiza leksykalna, składniowa, semantyczna, generacja kodu pośredniowego i kodu maszynowego. Omówione zostaną także zasady opisywania języków przy pomocy gramatyk bezkontekstowych oraz gramatyk regularnych.

Wykłady:

  1. Wprowadzenie do przedmiotu. Przedstawienie tematyki i regulaminu przedmiotu.
  2. Wprowadzenie do kompilacji. Etapy przetwarzania kodu źródłowego.
  3. Prosty kompilator jednoprzebiegowy w języku C (definicja prostej gramatyki, notacja Backusa-Naura (BNF), analiza składniowa przy pomocy rekurencyjnych wywołań funkcji).
  4. Prosty kompilator jednoprzebiegowy w języku C (analiza leksykalna, obsługa tablicy symboli).
  5. Analiza leksykalna cz.1, Schemat analizatora leksykalnego, generator analizatorów leksykalnych (Lex/flex)
  6. Analiza leksykalna cz.2, Wyrażenia regularne, Tworzenie drzewa wyrażenia regularnego, Niedeterministyczny Automat Skończony, Deterministyczny Automat Skończony, Przekształcanie NAS na DAS, Redukcja DAS.
  7. Analiza składniowa cz.1, Rola analizatora składniowego. Obsługa błędów składniowych. Gramatyka bezkontekstowa, gramatyka kontekstowa. Formalna definicja gramatyki. Wyprowadzenia i drzewa wyprowadzeń. Lewostronne i prawostronne wyprowadzenie. Niejednoznaczność gramatyki. Gramatyki regularne. Poprawianie gramatyki (Eliminacja lewostronnej rekurencji, Eliminowanie niejednoznaczności, Faktoryzacja lewostronna). Przykłady języków kontekstowych.
  8. Analiza składniowa cz.2, Analiza zstępująca, Rekurencyjne analizator przewidujący, Nierekurencyjny analizator ze stosem (budowa tablicy analizatora, zbiory FIRST i FOLLOW), Analizator LL(n), Odzyskiwanie kontroli po błędach
  9. Analiza składniowa cz.3, Analiza wstępująca, Zasada działania analizatora redukującego opartego na stosie, Analizatory LR,
  10. Analiza składniowa cz.4, Tworzenie tablic analizatorów SLR (operacja domknięcia, operacja przejścia),
  11. Analiza składniowa cz.5, Generatory analizatorów składniowych: YACC (zasada działania, składnia plików, przykłady)
  12. Wprowadzenie do programu ANTLR.
  13. Podstawy translacji sterowana składnią. Akcje semantyczne. Artybuty symboli. Atrybuty synezowane i dziedziczone. Abstrakcyjne drzewo składni (AST), a graf (DAG) dla wyrażeń.
  14. Powtórka przed egzaminem.

Literatura:

  1. A. V. Aho, R. Sethi, J. D. Ullman - "Compilers: Principles, Techniques and Tools", Addison-Wesley, 1986 powyższa książka jest również dostępna w wersji polskiej ("Kompilatory: reguły, metody, narzędzia", WNT, 2002)
  2. Torben Mogensen, Basics of Compiler Design )

  3. W. M. Waite, G. Goos - "Konstrukcja kompilatorów", WNT, 1989
  4. John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman: "Wprowadzenie do teorii automatów, języków i obliczeń" (org. Introduction to Automata Theory, Languages and Computation), Wydawnictwo PWN, Październik 2005
  5. Materiały do przedmiotu Podstawy kompilatorów z serwisu Ważniak MIMUW.

  6. Materiały do przedmiotu Języki, automaty i obliczenia z serwisu Ważniak MIMUW.

Zasady zaliczenia:

  1. Ocena końcowa z przedmiotu zależna jest od uzyskanej sumarycznej liczby punktów.
  2. Na zaliczenie przedmiotu składają się:
    • egzamin końcowy (50 pkt),
    • kartkówki na wykładzie (10 pkt),
    • zadania projektowe (40 pkt).
  3. Warunkiem zaliczenia przedmiotu jest uzyskanie 50% sumy wszystkich punktów oraz oddanie wszystkich trzech projektów.
  4. Spóźnione obrony projektów:
    1. Spóźnienie do jednego tygodnia skutkuje obniżeniem oceny o 20%.
    2. Spóźnienie dłuższe niż jeden tydzień powoduje wyzerowanie oceny (chociaż konieczne oddanie wszystkich projektów).
    3. Podstawą do przedłużenia terminu jest stopień zaawansowania prac nad projektem.

Zadania projektowe:

W trakcie przedmiotu studenci będą realizować zadania projektowe zgodne z treścią wykładu. Planowane są dwa 2 mniejsze projekty, a następnie duży projekt wymagający samodzielnej realizacji pełnego kompilatora.

Projekt 1 (10p): Walidator składni danych w formacie JSON (opisanym w RFC4627). Celem jest sprawdzenie, czy podany tekst jest zgodny ze składnią oraz wskazanie ewentualnych błędów.
Projekt można pisać w dowolnym języku programowania, ale koncepcyjnie musi to być zgodne z przykładem. Zwrócić uwagę na:

Na obronę projektu proszę przynieść wydrukowaną wersję zaprojektowanej gramatyki w notacji BNF.
Termin realizacji: 7 marca (obrona gramatyki), 14 marca (obrona działającego programu).

Projekt 2 (10p): Zaprojektuj automat dopasowań wyrażenia regularnego ....
Część pierwsza (wyprowadzenie DAS - 5pkt): przedstawienie drzewa wyrażenia regularnego, przekształcenie drzewa na NAS, przekształcenie NAS->DAS, redukcja (minimalizacja) DAS
Część druga (realizacja algorytmu - 5pkt): program realizujący dopasowywanie automatem skończonym. Wymagania: przechowywanie grafu wydzielone od logiki kodu. Do obrony konieczna jest papierowa dokumentacja projektu (co najmniej diagram klas i ostateczna wersja DAS).

Na przykład:
.....

Czas realizacji: .... (część papierowa), .... (działający program)

Projekt 3 (20p): Napisać częściowy interpreter ....
Dobry przykład na początek : Simple Tree-Based Interpreter (pobierz Tree-based interpreter (ANTRL).zip)

Harmonogram:

Projekty powinny być realizowane w dwuosobowych zespołach. Należy jednak jasno określić i opisać w sprawozdaniu podział pracy pomiędzy członków zespołu. Praca zespołowa może być zorganizowana przy pomocy repozytorium "Projektor SVN" (dostępne z e-dziekanatu).

Egzamin


2015-09-23 06:43