Module also offered within study programmes:
General information:
Name:
Elementy konstrukcji kompilatorów
Course of study:
2014/2015
Code:
EAR-2-104-IS-s
Faculty of:
Faculty of Electrical Engineering, Automatics, Computer Science and Biomedical Engineering
Study level:
Second-cycle studies
Specialty:
Informatyka w sterowaniu i zarządzaniu
Field of study:
Automatics and Robotics
Semester:
1
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
Klimek Radosław (rklimek@agh.edu.pl)
Academic teachers:
Klimek Radosław (rklimek@agh.edu.pl)
Module summary

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Zna znaczenie języków formalnych i naturalnych we współczesnej rzeczywistości AR2A_U02, AR2A_U01 Examination
Skills
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 Project
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 Project
M_U003 Potrafi zbudować kompilator/translator, w tym moduł analizatora składniowego AR2A_U06, AR2A_U16, AR2A_U02, AR2A_U04, AR2A_U01 Project
Knowledge
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 Examination
M_W002 Zna podstawowe zasady i moduły pracy kompilatora/translatora AR2A_W13, AR2A_W02, AR2A_W08 Examination
M_W003 Ma podstawową wiedzę pozwalającą skonstruować kompilator/translator AR2A_W13, AR2A_W02, AR2A_W08 Examination
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Zna znaczenie języków formalnych i naturalnych we współczesnej rzeczywistości + - - - - - - - - - -
Skills
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 - - - + - - - - - - -
Knowledge
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 + - - - - - - - - - -
Module content
Lectures:

  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.)

Project classes:

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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 120 h
Module ECTS credits 4 ECTS
Participation in lectures 30 h
Realization of independently performed tasks 30 h
Participation in project classes 30 h
Completion of a project 30 h
Additional information
Method of calculating the final grade:

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.

Prerequisites and additional requirements:

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

Recommended literature and teaching resources:
  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.
Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

None