Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Języki formalne i kompilatory
Tok studiów:
2019/2020
Kod:
IINF-1-704-n
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
7
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Niestacjonarne
Prowadzący moduł:
Majewski Janusz (majew@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Student ma podstawową wiedzę w zakresie teorii języków formalnych i automatów, a także w zakresie podstaw budowy kompilatorów INF1A_W04, INF1A_W02 Kolokwium
Umiejętności: potrafi
M_U001 Student potrafi zaprojektować i zaimplementować proste programy będące prototypami wybranych modułów funkcjonalnych kompilatora, wykorzystując dostępne narzędzia specjalizowane oraz języki ogólnego stosowania. Potrafi ocenić przydatność narzędzi specjalizowanych do rozwiązywania wybranych problemów. INF1A_U07, INF1A_U05 Projekt
M_U002 Dla danego problemu potrafi stworzyć odpowiedni język, wyspecyfikować jego gramatykę, dobrać system typizacji, odpowiedni kod pośredni oraz infrastrukturę (tablica symboli, …) INF1A_U06 Projekt
Kompetencje społeczne: jest gotów do
M_K001 Potrafi odpowiednio określić priorytety służące realizacji praktycznych zadań związanych z budową kompilatora oraz adekwatnie zaplanować pracę. INF1A_K04 Projekt
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
32 16 16 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Student ma podstawową wiedzę w zakresie teorii języków formalnych i automatów, a także w zakresie podstaw budowy kompilatorów + - - - - - - - - - -
Umiejętności
M_U001 Student potrafi zaprojektować i zaimplementować proste programy będące prototypami wybranych modułów funkcjonalnych kompilatora, wykorzystując dostępne narzędzia specjalizowane oraz języki ogólnego stosowania. Potrafi ocenić przydatność narzędzi specjalizowanych do rozwiązywania wybranych problemów. - + - - - - - - - - -
M_U002 Dla danego problemu potrafi stworzyć odpowiedni język, wyspecyfikować jego gramatykę, dobrać system typizacji, odpowiedni kod pośredni oraz infrastrukturę (tablica symboli, …) - + - - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi odpowiednio określić priorytety służące realizacji praktycznych zadań związanych z budową kompilatora oraz adekwatnie zaplanować pracę. - - - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 135 godz
Punkty ECTS za moduł 5 ECTS
Udział w zajęciach dydaktycznych/praktyka 32 godz
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 48 godz
Samodzielne studiowanie tematyki zajęć 48 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (16h):
  1. Język formalny, gramatyka, automat, wyrażenie regularne, automat skończony

    Język naturalny a język formalny. Definiowanie języka formalnego. Gramatyka i automat. Podstawowe pojęcia: symbol, alfabet, łańcuch, język. Wyrażenia regularne, języki regularne. Deterministyczny i niedeterministyczny automat skończony.

  2. Kompilacja, interpretacja. Analiza leksykalna

    Translatory, kompilatory, interpretery. Główne moduły funkcjonalne kompilatora.Analiza leksykalna. Projektowanie i implementacja analizatora leksykalnego.

  3. Gramatyka bezkontekstowa, automat ze stosem

    Gramatyka bezkontekstowa, wyprowadzenia, drzewa rozbioru, jednoznaczność gramatyki. Rozbiór gramatyczny, algorytm top-down i bottom-up. Deterministyczny i niedeterministyczny automat ze stosem.

  4. Analiza syntaktyczna

    Analiza syntaktyczna. Projektowanie parsera generacyjnego LL. Projektowanie parsera redukującego SLR w oparciu o gramatyki niejednoznaczne

  5. Analiza semantyczna; tłumaczenie do kodu pośredniego

    Analiza semantyczna. Gramatyki atrybutywne. Translacja kierowana składnią. Generacja kodu pośredniego. Kod trójadresowy.

  6. Optymalizacja; generacja kodu ostatecznego

    Optymalizacja kodu pośredniego. Grafy przepływu. Transformacje poprawiające kod. Optymalizacja przez szparkę. Generacja kodu wynikowego. Generowanie kodu z drzew syntaktycznych i skierowanych grafów acyklicznych.

  7. Hierarchia Chomsky'ego

    Klasyfikacja Chomsky’ego. Deterministyczne i niedeterministyczne maszyny Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. Problemy nierozstrzygalne. Języki nie będące rekurencyjnie przeliczalnymi.

Ćwiczenia audytoryjne (16h):
-
Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:

1. Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z ćwiczeń projektowych oraz kolokwium zaliczeniowego.
2. Obliczamy średnią z wszystkich ocen zaliczeń ćwiczeń projektowych oraz kolokwium zaliczeniowego uzyskanych we wszystkich terminach.
3. Wyznaczmy 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ń projektowych i kolokwium zaliczeniowego uzyskano w pierwszym terminie oraz ocena końcowa jest mniejsza niż 5.0 to ocena końcowa jest podnoszona o 0.5

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Znajomość materiału z przedmiotu „matematyka dyskretna” oraz “wstęp do informatyki”

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. W. Homenda, „Elementy lingwistyki matematycznej i teorii automatów”, Oficyna Wydawnicza Politechniki Warszawskiej, 2005
8. Materiały dydaktyczne na stronach www: http://kompilatory.agh.edu.pl/ oraz http://wazniak.mimuw.edu.pl

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

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak