Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Elementy konstrukcji kompilatorów
Tok studiów:
2014/2015
Kod:
EAR-2-104-IS-s
Wydział:
Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Poziom studiów:
Studia II stopnia
Specjalność:
Informatyka w sterowaniu i zarządzaniu
Kierunek:
Automatyka i Robotyka
Semestr:
1
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
Klimek Radosław (rklimek@agh.edu.pl)
Osoby prowadzące:
Klimek Radosław (rklimek@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 podstawowe problemy związane z lingwistyką matematyczną, w tym pojęcia związane z definiowaniem języków formalnych AR2A_W13, AR2A_W02, AR2A_W08 Egzamin
M_W002 Zna podstawowe zasady i moduły pracy kompilatora/translatora AR2A_W13, AR2A_W02, AR2A_W08 Egzamin
M_W003 Ma podstawową wiedzę pozwalającą skonstruować kompilator/translator AR2A_W13, AR2A_W02, AR2A_W08 Egzamin
Umiejętności
M_U001 Potrafi zdefiniować języki formalne korzystając z pojęcia gramatyki (automatu lub wyrażenia regularnego) AR2A_U06, AR2A_U16, AR2A_U02, AR2A_U04, AR2A_U01 Projekt
M_U002 Potrafi dokonać oceny korzyści i wykorzystać dostępne generatory skanerów i parserów AR2A_U06, AR2A_U16, AR2A_U02, AR2A_U04, AR2A_U01 Projekt
M_U003 Potrafi zbudować kompilator/translator, w tym moduł analizatora składniowego AR2A_U06, AR2A_U16, AR2A_U02, AR2A_U04, AR2A_U01 Projekt
Kompetencje społeczne
M_K001 Zna znaczenie języków formalnych i naturalnych we współczesnej rzeczywistości AR2A_U02, AR2A_U01 Egzamin
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 podstawowe problemy związane z lingwistyką matematyczną, w tym pojęcia związane z definiowaniem języków formalnych + - - - - - - - - - -
M_W002 Zna podstawowe zasady i moduły pracy kompilatora/translatora + - - - - - - - - - -
M_W003 Ma podstawową wiedzę pozwalającą skonstruować kompilator/translator + - - - - - - - - - -
Umiejętności
M_U001 Potrafi zdefiniować języki formalne korzystając z pojęcia gramatyki (automatu lub wyrażenia regularnego) - - - + - - - - - - -
M_U002 Potrafi dokonać oceny korzyści i wykorzystać dostępne generatory skanerów i parserów - - - + - - - - - - -
M_U003 Potrafi zbudować kompilator/translator, w tym moduł analizatora składniowego - - - + - - - - - - -
Kompetencje społeczne
M_K001 Zna znaczenie języków formalnych i naturalnych we współczesnej rzeczywistości + - - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

  1. Pojęcia podstawowe związane z lingwistyką formalną (2 godz.)
    Pojęcie języka, języki naturalne i sztuczne (formalne), składnia, semantyka i pragmatyka języka – metody formalizacji, język a metajęzyk, podstawowe sposoby opisu składni.
  2. Gramatyka generacyjna i przykłady gramatyk (4 godz.)
    Podstawowe pojęcia i operacje dla różnych klas języków, definicja gramatyki generacyjnej, wyprowadzenie, klasyfikacja Chomsky’ego. Przykłady języków i gramatyk, odnajdywanie języka generowanego przez gramatykę, budowanie gramatyki dla języka.
  3. Metody rozbioru gramatycznego (2 godz.)
    Definicje związane z rozbiorem, wieloznaczność i jednoznaczność gramatyk, rekursywność gramatyki, strategie generacyjna i redukcyjna rozbioru gramatycznego, wyprowadzenie kanoniczne, wybrane problemy rozbiory gramatycznego.
  4. Automaty deterministyczne i niedeterministyczne (4 godz.)
    Automat deterministyczny Rabina-Scotta, język akceptowany przez automat, przykłady automatów, stany nieosiągalne i nierozróżnialne, automat niedeterministyczny, język akceptowany przez automat niedeterministyczny, metoda usuwania niedeterminizmu i algorytm przejścia pomiędzy automatami, algorytmy przejścia pomiędzy gramatykami a automatami, optymalizacja automatu, usuwanie stanów nieosiągalnych i nierozróżnialnych, przykład redukowania automatu. Lemat o pompowaniu.
  5. Wyrażenia regularne (2 godz.)
    Pojęcie wyrażenia regularnego, podstawowe własności i operacje na wyrażeniach. Algorytm przejścia od wyrażenia regularnego do automatu niedeterministycznego, przykłady.
  6. Kompilator i budowa kompilatora (4 godz.).
    Podstawowe pojęcia, kompilator, translator, interpreter, preprocesor, postprocesor. Ogólna budowa i zasada działania kompilatora, skaner, parser, optymalizator, generator. Przykłady kompilatorów, szczegółowa prezentacja pewnego procesu translacji obejmującego analizę syntaktyczną, analizę składniową, analizę semantyczną oraz generację kodu wynikowego.
  7. Przegląd metod parsingu (4 godz.)
    Metoda zstępująca, metoda wstępująca, przykłady, problem wyboru produkcji, problem wyboru osnowy. Problem nawrotów. Analizatory klasy LL, analizatory klasy LR. Metoda precedencyjna analizy syntaktycznej, relacje Wirtha-Webera, gramatyki precedencyjne. Wykrywanie błędów i wydobywanie się z błędów, przebudowa drzewa składniowego i kontynuowanie analizy składniowej, komunikaty o błędach.
  8. Analizatory składniowe klasy LL (4 godz.)
    Funkcje PRFX i FOLLOW, definicja gramatyki LL, własności i twierdzenia. Budowa automatu i algorytm rozkładu LL. Przykłady parsingu na przykładzie analizatorów LL, tablica sterująca gramatyki. Własności gramatyk i parserów LL, usuwanie lewostronnej rekursji, lewostronna faktoryzacja gramatyki, problem epsilon produkcji.
  9. Generatory parserów i skanerów (2 godz.)

Ćwiczenia projektowe:

W ramach przedmiotu prowadzone są ćwiczenia projektowe. Treści tych zajęć ugruntowują i rozszerzają wiedzę przekazywaną podczas wykładów. Celem zajęć jest projekt i implementacja prostych kompilatorów ograniczonego języka, języka istniejącego lub nowo zdefiniowanego. Wykorzystanie narzędzi do automatycznej generacji skanerów i parserów, także kompilacja skrośna.

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

Ocena końcowa jest wyliczana jako średnia z projektu oraz z egzaminu, przy czym ocena z egzaminu jest brana z wagą 0,6. Jeżeli ocena z projektu lub egzaminu jest uzyskana w innym niż pierwszym terminie, to ocena końcowa nie może być większa niż 3.0. Warunkiem dopuszczenia do egzaminu jest pozytywna ocena z projektu.

Wymagania wstępne i dodatkowe:

Znajomość języków programowania przewidzianych w programie studiów, bardzo pobieżna znajomość procesu kompilacji/translacji

Zalecana literatura i pomoce naukowe:
  1. Hopcroft J.E., Motwani R., Ullman J.D.: Wprowadzenie do teorii automatów, języków i obliczeń. PWN. 2005.
  2. Aho A.V., Sethi R., Ullman J.D.: Kompilatory. Reguły, metody i narzędzia. WNT 2001.
  3. Waite W.M., Goos G.: Konstrukcja kompilatorów. WNT 1989.
  4. Cichy M., Nomańczuk J., Szpakowicz S.: Zbiór zadań z propedeutyki informatyki. PWN 1977.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak