Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Kompilatory
Tok studiów:
2014/2015
Kod:
IIN-1-504-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
5
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
Majewski Janusz (majew@agh.edu.pl)
Osoby prowadzące:
Kuta Marcin (mkuta@agh.edu.pl)
Majewski Janusz (majew@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Zna i rozumie podstawy teoretyczne konstrukcji i opisu języków języków programowania, jak również podstawy teoretyczne budowy translatorów języków programowania IN1A_W04, IN1A_W05 Kolokwium
M_W002 Ma szczegółową wiedzę w zakresie projektowania, budowy i implementacji translatorów języków programowania IN1A_W07, IN1A_W06 Kolokwium
Umiejętności
M_U001 Potrafi sformułować szczegółowy algorytm analizatora leksykalnego, składniowego i semantycznego dostosowany do konkretnego języka. IN1A_U08 Kolokwium
M_U002 Dla danego problemu potrafi stworzyć odpowiedni język, wyspecyfikować jego gramatykę, dobrać system typizacji, odpowiedni kod pośredni oraz infrastrukturę (tablica symboli, …) IN1A_U10, IN1A_U11 Wykonanie ćwiczeń laboratoryjnych
M_U003 Potrafi zaprojektować, zbudować i włączyć do uruchamianego projektu specjalizowany moduł kompilatora, jak np. skaner, parser, analizator semantyczny, generator kodu, optymalizator, Garbage Collector, itp. ; także wykorzystując software'owe narzędzia wspomagające IN1A_U13, IN1A_U12, IN1A_U09 Wykonanie ćwiczeń laboratoryjnych
Kompetencje społeczne
M_K001 Potrafi współdziałać i pracować w zespole, ponosić odpowiedzialność za wspólnie realizowane zadania IN1A_K01 Wykonanie ćwiczeń laboratoryjnych
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Zna i rozumie podstawy teoretyczne konstrukcji i opisu języków języków programowania, jak również podstawy teoretyczne budowy translatorów języków programowania + - - - - - - - - - -
M_W002 Ma szczegółową wiedzę w zakresie projektowania, budowy i implementacji translatorów języków programowania + - - - - - - - - - -
Umiejętności
M_U001 Potrafi sformułować szczegółowy algorytm analizatora leksykalnego, składniowego i semantycznego dostosowany do konkretnego języka. - + + - - - - - - - -
M_U002 Dla danego problemu potrafi stworzyć odpowiedni język, wyspecyfikować jego gramatykę, dobrać system typizacji, odpowiedni kod pośredni oraz infrastrukturę (tablica symboli, …) - + + - - - - - - - -
M_U003 Potrafi zaprojektować, zbudować i włączyć do uruchamianego projektu specjalizowany moduł kompilatora, jak np. skaner, parser, analizator semantyczny, generator kodu, optymalizator, Garbage Collector, itp. ; także wykorzystując software'owe narzędzia wspomagające - - + - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi współdziałać i pracować w zespole, ponosić odpowiedzialność za wspólnie realizowane zadania - - + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Podstawowe pojęcia

    Translatory, kompilatory, interpretery. Główne moduły funkcjonalne translatora.

  2. Analizator leksykalny

    Analiza leksykalna. Skaner. Specyfikacja, rozpoznawanie symboli leksykalnych w oparciu o niedeterministyczny połączony automat skończony oraz deterministyczny automat skończony, implementacja skanera. Generator analizatorów leksykalnych Lex.

  3. Analizator syntaktyczny

    Analiza syntaktyczna. Parser. Gramatyki LL. Projektowanie i implementacja parsera LL metodą procedur rekurencyjnych. Gramatyki LR. Parser LR. Parser SLR, projektowanie parsera redukującego w oparciu o gramatyki niejednoznaczne. Parser LALR. Generator analizatorów syntaktycznych Yacc. Parser oparty o gramatyki z pierwszeństwem operatorów.

  4. Gramatyki atrybutowane i translacja kierowana składnią

    Analiza semantyczna. Gramatyki atrybutowane. Translacja kierowana składnią. Gramatyki S-atrybutowane, obliczenia wstępujące definicji S-atrybutowanych. Gramatyki L-atrybutowane, obliczenia zstępujące i wstępujące definicji L-atrybutowanych. Obliczenia rekurencyjne definicji L-atrybutowanych. Analiza definicji kierowanych składnią. Obliczenia rekurencyjne dla drzewa rozbioru.

  5. Analizator semantyczny; typizacja

    Zadania analizy semantycznej. Mechanizmy realizacji analizy semantycznej. Kontrola typów. System typów, równoważność typów, przeciążalność operatorów, funkcje polimorficzne.

  6. Organizacja pamięci

    Organizacja pamięci. Strategie alokacji pamięci. Dostęp do nazw nielokalnych. Przekazywanie parametrów.

  7. Generacja kodu pośredniego

    Postaci kodu pośredniego. Kod oparty na odwrotnej notacji polskiej. Kod trójadresowy. Tłumaczenie typowych konstrukcji językowych. Generowanie kodu pośredniego na przykładzie kodu dla wyrażeń logicznych.

  8. Optymalizacja kodu pośredniego

    Źródła i kryteria optymalizacji. Bloki podstawowe i grafy przepływu. Analiza przepływu danych, optymalizacja w grafach przepływu. Optymalizacja przez szparkę.

  9. Generacja kodu wynikowego

    Generowanie kodu z drzew syntaktycznych i skierowanych grafów acyklicznych. Przydział i wyznaczanie rejestrów. Algorytmy generowania kodu.

Ćwiczenia laboratoryjne:

Ćwiczenia laboratoryjne poświęcone są implementacji analizatorów leksykalnych, syntaktycznych i semantycznych, z elementami translacji kierowanej składnią, z wykorzystaniem generatorów Lex i Yacc, jak również implementacji pozostałych modułów logicznych kompilatora, jak generatora kodu pośredniego, generatora kodu ostatecznego, garbage collectora, itd.

1. Sprawy organizacyjne. Mechanizmy i algorytmy analizy leksykalnej.
2. Zaznajomienie się z generatorami skanerów na przykładzie ’’tłumaczy’’ plików HTML, logów syslog itp. Zaznajomienie się z generatorami parserów na przykładzie ’’tłumaczy’’ jak wyżej wymuszających pewne reguły gramatyczne.
3. Mechanizmy i algorytmy zstępującej i wstępującej analizy składniowej. Konstrukcja i wykorzystanie gramatyk atrybutowanych.
4. Zastosowanie poznanych technik do analizy syntaktycznej i leksykalnej programów napisanych w uproszczonych wersjach jezyków strukturalnych (C—, Mini Pascal itp.). Budowa drzew syntaktycznych i analiza semantyczna programów napisanych w uproszczonych wersjach języków strukturalnych
5. Generowanie kodu programów napisanych w uproszczonych wersjach języków strukturalnych (C—, Mini Pascal itp.) w wybranych architekturach procesorowych (MIPS, ARM itp.). Zaznajomienie się z różnymi reprezentacjami kodu pośredniego, dobór i implementacja najbardziej odpowiedniego dla danego języka i architektury docelowej i optymalizacji
6. Zaznajomienie się z różnymi systemami typizacji języków (np. statyczna, dynamiczna) i implementacja wybranego systemu typizacji w kompilatorze. Tworzenie infrastruktury kompilatora dla wybranego języka, architektury docelowej i metod optymalizacji (tablica symboli, struktury danych)
7. Generowanie kodu programów napisanych w różnych typach języków (strukturalne, funkcyjne, obiektowe, skryptowe) na wybrane architekturach procesorowe (x86, CUDA, MIPS, ARM itp.)
8. Podsumowanie, zaliczanie zadań

Ćwiczenia audytoryjne:

Realizowane są zajęcia o charakterze audytoryjnym, wyjaśniające szczegóły algorytmów analizy leksykalnej, parsingu oraz prezentujące projektowanie i badanie gramatyk atrybutowanych.
1. Projektowanie automatu skończonego dla wybranych konstrukcji języków programowania, Mechanizmy i algorytmy analizy leksykalnej.
2. Budowanie gramatyki dla elementów języka programowania, jednoznaczność gramatyk.
3. Mechanizmy i algorytmy zstępującej analizy składniowej (LL).
4. Mechanizmy i algorytmy wstępującej analizy składniowej (LR, SLR, LALR).
5. Algorytmy analizy składniowej dla gramatyk niejednoznacznych, usuwanie konfliktów z tablic parserów.
6. Konstrukcja i wykorzystanie gramatyk atrybutowanych do analizy semantycznej i tłumaczenia opartego o parsery działające w oparciu o metodę zstępującą oraz wstępującą.
7. Kolokwium, zaliczanie zajęć.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 106 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 28 godz
Samodzielne studiowanie tematyki zajęć 30 godz
Udział w ćwiczeniach laboratoryjnych 14 godz
Przygotowanie do zajęć 20 godz
Udział w ćwiczeniach audytoryjnych 14 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

1. Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z ćwiczeń laboratoryjnych oraz ćwiczeń audytoryjnych (zaliczenie ćwiczeń audytoryjnych obejmuje także wiedzę z wykładu).
2. Obliczamy średnią wszystkich ocen zaliczeń ćwiczeń laboratoryjnych i ocen zaliczeń ćwiczeń audytoryjnych, uzyskanych we wszystkich terminach.
3. Wyznaczamy ocenę końcową na podstawie zależności:
if sr>4.75 then OK:=5.0 else
if sr>4.25 then OK:=4.5 else
if sr>3.75 then OK:=4.0 else
if sr>3.25 then OK:=3.5 else OK:=3
4. Jeżeli pozytywną ocenę z ćwiczeń laboratoryjnych i ćwiczeń audytoryjnych uzyskano w pierwszym terminie oraz ocena końcowa jest mniejsza niż 5.0 to ocena końcowa jest podnoszona o 0.5

Wymagania wstępne i dodatkowe:

Znajomość materiału z przedmiotu „teoria automatów i języków formalnych” nauczanego w poprzednim semestrze.

Zalecana literatura i pomoce naukowe:

1. A. V. Aho, R. Sethi, J. D. Ullman: Kompilatory. Reguły, metody i narzędzia, WNT, 2002
2. Keith D. Cooper, Linda Torczon: Engineering a compiler, Second Edition ,Morgan Kauffman, 2012
3. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Second Edition. Pearson Addison Wesley, 2007.
4. K. Louden: Compiler construction, PWS Publishing Company, 1997
5. Waite W., Goos G.: Konstrukcja kompilatorów, WNT, 1989.
6. J. E. Hopcroft, R. Motwani, J. D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2005
7. http://kompilatory.agh.edu.pl

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak