Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Techniki kompilacji

Informacje ogólne

Kod przedmiotu: 103D-INIOP-ISP-TKOM Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Techniki kompilacji
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Inżynieria oprogramowania )-Inżynieria oprogramowania-inż.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 4.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

TKOM

Numer wersji:

4

Skrócony opis:

Celem przedmiotu jest zapoznanie studentów z głównymi pojęciami, metodami i algorytmami związanymi z transformacją tekstów oraz podstawami budowy kompilatorów i stosowanych w nich metodach i algorytmach. W szczególności, studenci zapoznają się/pogłębiają wiedzę i umiejętności praktyczne w zakresie wyrażeń regularnych (aspektów użytkowych jak i samego sposobu realizacji mechanizmu wyrażeń regularnych – automaty niedeterministyczne i deterministyczne), gramatyki i języki (metody specyfikacji, różne klasy gramatyk – metody weryfikacji przynależności do danej klasy, przekształcanie gramatyk), gramatyki bezkontekstowe, teoretyczne i praktyczne aspekty analizy leksykalnej, składniowej, semantycznej, interpretacja i generacja kodu. W sposób praktyczny student zdobywa i weryfikuje swoją wiedzę i umiejętności poprzez realizację, w ramach zajęć projektowych, np. interpretera własnego języka programowania czy fragmentu kompilatora.

Pełny opis:

Celem przedmiotu jest zapoznanie studentów z głównymi pojęciami, metodami i algorytmami związanymi z transformacją tekstów oraz podstawami budowy kompilatorów i stosowanych w nich metodach i algorytmach. W szczególności, studenci zapoznają się/pogłębiają wiedzę i umiejętności praktyczne w zakresie wyrażeń regularnych (aspektów użytkowych jak i samego sposobu realizacji mechanizmu wyrażeń regularnych – automaty niedeterministyczne i deterministyczne), gramatyki i języki (metody specyfikacji, różne klasy gramatyk – metody weryfikacji przynależności do danej klasy, przekształcanie gramatyk), gramatyki bezkontekstowe, teoretyczne i praktyczne aspekty analizy leksykalnej, składniowej, semantycznej, interpretacja i generacja kodu. W sposób praktyczny student zdobywa i weryfikuje swoją wiedzę i umiejętności poprzez realizację, w ramach zajęć projektowych, np. interpretera własnego języka programowania czy fragmentu kompilatora.



Treść wykładu

  1. Wprowadzenie (1 godz.)
    Ogólnie o problemie kompilacji / interpretacji; wprowadzenie do budowy kompilatorów i procesu kompilacji; składniki zależne od języka źródłowego (front end) i od platformy docelowej. Potrzebne techniki i narzędzia (również teoretyczne).
  2. Języki regularne i analiza leksykalna (5 godz.)
    Reprezentacje języków regularnych, formalizm wyrażeń regularnych (WR), gramatyki regularne; automaty niedeterministyczne (AN) i deterministyczne (AD). Konwersja wyrażeń regularnych na automaty, algorytm Thompsona, konwersja AN na AD (algorytm podzbiorowy), bezpośrednia konwersja WR na AD. Właściwości klasy języków regularnych. Zastosowania do wyszukiwania wzorców i analizy leksykalnej. Przykład implementacji analizatora leksykalnego i obsługi źródeł. Generatory analizatorów leksykalnych.
  3. Makrogeneracja – parametryczne przetwarzanie tekstów (3 godz.)
    Typy substytucji tekstowych, rozpoznawanie makrodefinicji i makrowywołań, organizacja biblioteki makrodefinicji, reguły przesłaniania i dostępności; mechanizmy wiązania parametrów. Przykłady makrogeneratorów.
  4. Podstawy teoretyczne – języki i gramatyki (3 godz.)
    Języki i gramatyki; style definiowania języka; konwencje notacyjne; przegląd metanotacji (BNF, EBNF, ISO-14977, ABNF, diagramy składniowe); Gramatyki generacyjne; Hierarchia języków wg Chomskiego, formy kanoniczne gramatyk (CNF, GNF, KNF); Twierdzenie o pompowaniu dla gramatyk bezkontekstowych; Drzewa wyprowadzeń dla gramatyk bezkontekstowych. Niejednoznaczność w gramatykach bezkontekstowych - przykłady.
  5. Języki bezkontekstowe i ich rozbiór (2 godz.)
    Reprezentacje języków bezkontekstowych; właściwości gramatyk bezkontekstowych. Przekształcanie gramatyk (substytucja, usuwanie symboli niedostępnych, usuwanie produkcji pustych i jednostkowych); Usuwanie rekursji lewostronnej, faktoryzacja lewostronna. Zbiory FIRST i FOLLOW.
  6. Rozbiór rekursywnie zstępujący (5 godz.)
    Schematy translacji. Schemat translacji wyrażeń arytmetycznych. Rozbiór rekursywnie zstępujący sterowany składnią (RD); Rekursywnie zstępujący analizator składniowy – przykłady praktyczne; struktury pomocnicze w analizie składniowej; Współpraca analizator składniowy – analizator leksykalny; Obsługa błędów; Rozbiór sterowany tablicą - parser LL(1).
  7. Analizatory składniowe wstępujące (5 godz.)
    Schemat ogólny metod wstępujących; LR-formy; Automat LR(0) i sterownik parsera LR(0), rozbiór wyrażeń wg LR(0). Konflikty w tabelach LR(0), rozbiór SLR(1), konflikty w SLR(1). Rozbiór LR(1), LR1-formy, wyznaczanie tabeli dla parsera LR(1), redukcja LR(1) - LALR(1). Porównanie parserów. Własności i problemy decyzyjne języków bezkontekstowych.
  8. Gramatyki z atrybutami i operatorowe (2 godz.)
    Gramatyki operatorowe; Rozbiór wyrażeń w gramatykach operatorowych; przykład translacji wyrażeń do Odwrotnej Notacji Polskiej (ONP); Gramatyki z atrybutami i ich wykorzystanie w generatorach parserów; Akcje semantyczne parsera.
  9. Analiza semantyczna (2 godz.)
    Struktury danych i schematy programistyczne w kompilatorze; Atrybuty identyfikatorów, organizacja tabel symboli; organizacja rekursji i zmiennych lokalnych na przykładzie interpreterów.
  10. Generacja kodu i techniki optymalizacyjne (2 godz.)
    Komunikacja analizatora z generatorem, alokacja pamięci w strukturach blokowych, generacja kodu dla wyrażeń i struktur sterowania; przejście z konwencji maszyny stosowej do konwencji procesora docelowego. Elementy optymalizacji kodu, optymalizacje lokalne i globalne; algorytm optymalizacji wyrażeń.



Zakres projektu

Celem projektu jest zapoznanie się z metodami wytwarzania i budową kompilatorów. W szczególności, opanowanie przez studenta praktycznych umiejętności realizacji przetwarzania sterowanego składnią w odniesieniu do różnych typów zastosowań wykorzystujących notację sformalizowaną (symulacja, przetwarzanie i rozpoznawanie tekstu, interpretacja prostych języków). Wymagane jest przygotowanie projektu (w szczególności: zebranie i wyspecyfikowanie wymagań w toku dyskusji z prowadzącym projekt, opracowanie gramatyki własnego języka, koncepcji rozwiązania) oraz dokumentacji końcowej.

Literatura:

  • Aho A.V., Lam M., Sethi R., Ullman J.D.: “Compilers: Principles, Techniques & Tools”, 2nd edition, Pearson, Addison-Wesley, 2013.
  • Aho A.V., Sethi R., Ullman J.D.: Kompilatory: reguły, metody i narzędzia, WNT 2006.
  • Bennet J.P.: “Introduction to Compiling Techniques: A First Course Using ANSI C, Lex, and Yacc”, 2nd edition, Mc Graw Hill, 1996.
  • Grune D., van Reeuwijk K., Bal H. E., Jacobs C. J. H., Langendoen K.: “Modern Compiler Design”, Springer, 2016.
  • Reinhard W.: “Compiler Design”, Springer-Verlag Berlin and Heidelberg, 2013.
  • K.D. Cooper, L.Torcon: “Engineering a Compiler”, 2nd edition, Elsevier, 2011.
  • Mak R.:“Writing Compilers and Interpreters: A Modern Software Engineering Approach Using Java”, 2014.
  • Galles D.: “Modern Compiler Design”, Addison-Wesley, 2004.
  • Aho A.V., Sethi R., Ullman J.D., Lam J.D.: „21st Century Compilers”, Addison-Wesley, 2006.
  • M. T. Aegidius: “Introduction to Compiler Design”, Springer, 2011.
  • Pająk A., Wigura A.: Makrogeneratory, asemblery i konsolidatory, PWN, 1983.
  • Strona domowa i dokumentacja projektu ANTLR - https://www.antlr.org
  • Materiały elektroniczne na stronie przedmiotu
Metody i kryteria oceniania:

Sprawdzanie założonych efektów kształcenia realizowane jest przez:

  • ocenę wiedzy i umiejętności związanych z realizacją tematów projektowych;
  • formatywną ocenę związaną z rozwiązaniem zadań przedkolokwialnych, a także z interaktywną forma prowadzenia wykładu oraz z ćwiczeniami;
  • ocenę wiedzy i umiejętności wykazanych na kolokwiach (na kolokwiach student może korzystać z wybranych materiałów dydaktycznych oraz książek);
  • ocenę wiedzy i umiejętności wykazanych na egzaminie (student może korzystać z wybranych materiałów dydaktycznych oraz książek).

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. letni" (jeszcze nie rozpoczęty)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103200 - Instytut Informatyki

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.