Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Techniki kompilacji
Koordynator przedmiotu:
Ilona Bluemke
Status przedmiotu:
Fakultatywny ograniczonego wyboru
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne
Kod przedmiotu:
TKOM
Semestr nominalny:
6 / rok ak. 2018/2019
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
30 godz. wykładu 15 godz. spotkań projektowych 30 godz. przygotowanie do sprawdzianu i egzaminu 45 godz. samodzielna praca nad projektem 6 godz. konsultacje i egzamin w sumie 126
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
30 godz. wykładu 15 godz. spotkań projektowych 6 godz. konsultacje i egzamin w sumie 51 co daje 2 ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
15 godz. spotkań projektowych 45 godz. samodzielna praca nad projektem w sumie 60 co daje ok. 2,5 ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt30h
  • Lekcje komputerowe0h
Wymagania wstępne:
Brak
Limit liczby studentów:
40
Cel przedmiotu:
Prezentacja metod opisu, rozpoznawania i przetwarzania języków formalnych, regularnych i bezkontekstowych.
Treści kształcenia:
Treść wykładu Wprowadzenie (2h). Ogólnie o problemie kompilacji / interpretacji; język pośredni, poziom interpretacji, głębokość kompilacji; struktura kompilatora dla programów wielomodułowych; składniki zależne od języka źródłowego (front end) i od platformy docelowej (generator kodu). Potrzebne techniki i narzędzia (również teoretyczne); języki i gramatyki; style definiowania języka; przegląd metanotacji (BNF, EBNF, ISO-14977, ABNF, diagramy składniowe). Przetwarzanie sterowane składnią i makrogeneracja (5h). Przetwornik tekstu (translator) sterowany składnią - własności, przykłady. Makrogeneracja, typy substytucji tekstowych, rozpoznawanie makrodefinicji i makrowywołań, organizacja biblioteki makrodefinicji, reguły przesłaniania i dostępności; mechanizmy wiązania parametrów. Makrogenerator MG. Makrogenerator uniwersalny GPM. Podstawy teoretyczne (3h). Hierarchia języków wg Chomskiego, formy kanoniczne gramatyk (CNF, GNF, KNF). Generacja i rozpoznawanie, drzewa wyprowadzeń dla gramatyk bezkontekstowych. Niejednoznaczność języka bezkontekstowego. Klasy gramatyk bezkontekstowych i strategie rozbioru. Języki regularne i analiza leksykalna (4h). Reprezentacje języków regularnych, formalizm wyrażeń regularnych (WR), gramatyki regularne (GPL, GLL); automaty niedeterministyczne (AN) i deterministyczne (AD). Konwersja wyrażeń regularnych na automaty, algorytm Thompsona, konwersja AN na AD (algorytm podzbiorowy), konwersja WR na AD. Właściwości klasy języków regularnych. Zastosowania do wyszukiwania wzorców i analizy leksykalnej. Zachłanny analizator leksykalny dla języka MiniPascal. Generatory analizatorów leksykalnych. Języki bezkontektstowe i rozbiór (6h). Reprezentacje języków bezkontekstowych; właściwości gramatyk bezkontekstowych. Przekształcanie gramatyk: substytucja, usuwanie nieużytków, usuwanie produkcji pustych i jednostkowych; postacie normalne CNF / GNF. Usuwanie rekursji lewostronnej, faktoryzacja lewostronna. Zbiory FIRST i FOLLOW; rozbiór rekursywnie zstępujący. Schematy translacji. Schemat translacji wyrażeń arytmetycznych do odwrotnej notacji polskiej. Rekursywnie zstępujący analizator składniowy dla MiniPascal'a. Obsługa błędów składniowych. Analiza semantyczna (3h). Atrybuty identyfikatorów, organizacja tabel symboli, tebele z funkcją mieszającą, tabele z porządkiem leksykograficznym - drzewa binarne; tabele symboli w rozbiorze struktur blokowych. Akcje semantyczne w rozbiorze rekursywnie zstępującym dla MiniPascal'a. Generacja kodu (3h). 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ń. Rozbiór sterowany tablicami (4h). Schemat ogólny metod tabelarycznych. Parser zstępujący predykcyjny LL(1) - struktura i własności. Rozbiór wstępujący, 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. Algorytmy uogólnione, algorytm Erley'a, algorytm CYK. Własności i problemy decyzyjne języków BK. Zakres projektu Celem projektu jest zapoznanie się z metodami budowy kompilatorów, w szczególności opanowanie 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, intrpretacja języków opisu scen geometrycznych itp.).
Metody oceny:
Sprawdziany, projekt, egzamin.
Egzamin:
tak
Literatura:
1. Aho A.V, R.Sethi , J.D.Ullman: Kompilatory: reguły, metody i narzędzia, WNT 2002. 2. Hopcroft J., Ullman J.: Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 1994. 3. Waite W., Goos G.: Konstrukcja kompilatorów, WNT Warszawa 1990. 4. Gries D., Konstrukcja translatorów dla maszyn cyfrowych, PWN, Warszawa 1984. 5. Pająk A., Wigura A.: Makrogeneratory, asemblery i konsolidatory, PWN, Warszawa 1983. 6. Materiały elektroniczne na stronie przedmiotu
Witryna www przedmiotu:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103C-INIIT-ISP-TKOM
Uwagi:
Brak

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka TKOM_W01
ma uporządkowaną wiedzę na temat metod opisu języków formalnych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka TKOM_W02
ma uporządkowaną wiedzę na temat hierarchii języków wg Chomskiego i ich modeli generacyjnych / obliczeniowych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka TKOM_W03
zna mechanizmy makrogeneracji i ich dostępność w środowiskach programistycznych
Weryfikacja: projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_W12
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka TKOM_W04
ma uporządkowaną wiedzę na temat reprezentacji i przetwarzania języków regularnych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_W11, K_W12, K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka TKOM_W05
ma uporządkowaną wiedzę na temat analizy jednoznacznych języków bezkontekstowych (parser rekursywnie zstępujący, rozbiór wstępujący)
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka TKOM_W06
ma uporządkowaną wiedzę na temat podstawowych metod uwzględniania semantyki języka i generowania kodu wynikowego
Weryfikacja: projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_W11, K_W12, K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka TKOM_W07
ma uporządkowaną wiedzę na temat rozstrzygalności głównych problemów decyzyjnych w klasach języków regularnych i bezkontekstowych
Weryfikacja: sprawdziany; egzamin
Powiązane charakterystyki kierunkowe: K_W12, K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka TKOM_U01
potrafi zdefiniować formalnie składnię języka w metanotacji EBNF (lub podobnej)
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_U01
Powiązane charakterystyki obszarowe: III.P6S_UW.2.o, I.P6S_UW
Charakterystyka TKOM_U02
potrafi przekształcić gramatykę języka wg zadanych kryteriów (sprawdzić kryteria LL(1), usunąć produkcje jednostkowe, sprowadzić do postaci normalnej Chomskiego)
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_U01
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.2.o
Charakterystyka TKOM_U03
potrafi przekształcać dowolnie reprezentację języka regularnego (wyrażenia regularne, automaty skończone, gramatyki regularne)
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_U13, K_U15
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.4.o, III.P6S_UW.3.o
Charakterystyka TKOM_U04
potrafi zrealizować analizator leksykalny i parser rekursywnie zstępujący wg zadanej gramatyki
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_U13, K_U14, K_U15, K_U19
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.4.o, III.P6S_UW.3.o
Charakterystyka TKOM_U05
potrafi zastosować model przetwarzania sterowanego składnią (schemat translacji) do prostych problemów obliczeniowych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane charakterystyki kierunkowe: K_U13, K_U15
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.4.o, III.P6S_UW.3.o
Charakterystyka TKOM_U06
potrafi zaprojektować środowisko programowe do osadzenia akcji semantycznych dla prostego języka bezkontekstowego
Weryfikacja: projekt semestralny
Powiązane charakterystyki kierunkowe: K_U15, K_U19, K_U13, K_U14
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.3.o, III.P6S_UW.4.o
Charakterystyka TKOM_U07
potrafi planować działania projektowe wg wymaganego terminu
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe: K_UK04
Powiązane charakterystyki obszarowe: I.P6S_UO
Charakterystyka TKOM_U08
potrafi samodzielnie pozyskiwać poszerzające informacje o rozwiązywanym problemie i dostępnych narzędziach programowych
Weryfikacja: projekt
Powiązane charakterystyki kierunkowe: K_UK01
Powiązane charakterystyki obszarowe: I.P6S_UU