Drukuj sylabus

Techniki kompilacji

Informacje ogólne

Kod przedmiotu:

103C-INIIT-ISP-TKOM

Kod Erasmus / ISCED:

(brak danych) / (brak danych)

Nazwa przedmiotu:

Techniki kompilacji

Jednostka:

Wydział Elektroniki i Technik Informacyjnych

Grupy:

( Algorytmy i języki - albo - Projektowanie systemów )-Inżynieria systemów informatycznych-inż.-EITI
( Przedmioty techniczne )---EITI

Punkty ECTS i inne:

5.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:

roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

Język prowadzenia:

polski

Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

TKOM

Numer wersji:

Skrócony opis:

Prezentacja, w możliwie pragmatycznym ujęciu, głównych pojęć, metod i wyników analizy złożoności algorytmów obliczeniowych.

Pełny opis:

Prezentacja, w możliwie pragmatycznym ujęciu, głównych pojęć, metod i wyników analizy złożoności algorytmów obliczeniowych.

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. 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ą, przykład translacji wyrażeń
prostych do odwrotnej postaci polskiej. 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):
Systemy przepisywania, L-systemy, gramatyki
generacyjne. 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.).

Poprzedniki

Typ poprzednika	Nr poprzednika	Kod poprzednika	Nazwa poprzednika
Zalecany	1	103C-INIIT-ISP-AAL	Analiza algorytmów
Zalecany	1	103D-INIIT-ISP-AAL	Analiza algorytmów

Literatura:

Aho A.V, R.Sethi , J.D.Ullman: Kompilatory: reguły, metody i
narzędzia, WNT 2002.

Hopcroft J., Ullman J.: Wprowadzenie do teorii automatów, języków
i obliczeń, PWN, 1994.

Waite W., Goos G.: Konstrukcja kompilatorów, WNT Warszawa 1990.

Gries D., Konstrukcja translatorów dla maszyn cyfrowych, PWN,
Warszawa 1984.

Pająk A., Wigura A.: Makrogeneratory, asemblery i konsolidatory,
PWN, Warszawa 1983.

Materiały elektroniczne na stronie przedmiotu

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. zimowy" (zakończony)

Okres:	2021-10-01 - 2022-02-22	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 30 miejsc więcej informacji Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski, Konrad Grochowski, Witold Wysota
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. letni" (zakończony)

Okres:	2021-02-20 - 2021-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 60 miejsc więcej informacji Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Anna Derezińska, Piotr Gawkowski, Konrad Grochowski, Agnieszka Malanowska, Witold Wysota
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. zimowy" (zakończony)

Okres:	2020-10-01 - 2021-02-19	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 30 miejsc więcej informacji Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski, Konrad Grochowski, Witold Wysota
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (zakończony)

Okres:	2020-02-22 - 2020-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 60 miejsc więcej informacji Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Anna Derezińska, Piotr Gawkowski, Konrad Grochowski, Witold Wysota
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (zakończony)

Okres:	2019-10-01 - 2020-02-21	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 36 miejsc więcej informacji Wykład, 30 godzin, 36 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski, Konrad Grochowski
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres:	2019-02-18 - 2019-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 60 miejsc więcej informacji Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Anna Derezińska, Piotr Gawkowski, Waldemar Grabski, Konrad Grochowski, Witold Wysota
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres:	2018-10-01 - 2019-02-17	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 36 miejsc więcej informacji Wykład, 30 godzin, 36 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. letni" (zakończony)

Okres:	2018-02-19 - 2018-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 60 miejsc więcej informacji Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski, Waldemar Grabski, Konrad Grochowski
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. zimowy" (zakończony)

Okres:	2017-10-01 - 2018-02-18	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 36 miejsc więcej informacji Wykład, 30 godzin, 36 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. letni" (zakończony)

Okres:	2017-02-20 - 2017-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 64 miejsc więcej informacji Wykład, 30 godzin, 64 miejsc więcej informacji
Koordynatorzy:	Ilona Bluemke
Prowadzący grup:	Ilona Bluemke
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. zimowy" (zakończony)

Okres:	2016-10-01 - 2017-02-19	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 36 miejsc więcej informacji Wykład, 30 godzin, 36 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. letni" (zakończony)

Okres:	2016-02-23 - 2016-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 70 miejsc więcej informacji Wykład, 30 godzin, 70 miejsc więcej informacji
Koordynatorzy:	Ilona Bluemke
Prowadzący grup:	Ilona Bluemke
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. zimowy" (zakończony)

Okres:	2015-10-01 - 2016-02-22	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 34 miejsc więcej informacji Wykład, 30 godzin, 34 miejsc więcej informacji
Koordynatorzy:	Piotr Gawkowski
Prowadzący grup:	Piotr Gawkowski
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. letni" (zakończony)

Okres:	2015-02-23 - 2015-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 41 miejsc więcej informacji Wykład, 30 godzin, 41 miejsc więcej informacji
Koordynatorzy:	Ilona Bluemke
Prowadzący grup:	Ilona Bluemke
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. zimowy" (zakończony)

Okres:	2014-09-29 - 2015-02-22	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 25 miejsc więcej informacji Wykład, 30 godzin, 25 miejsc więcej informacji
Koordynatorzy:	Ilona Bluemke
Prowadzący grup:	Ilona Bluemke
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. letni" (zakończony)

Okres:	2014-02-24 - 2014-09-28	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 60 miejsc więcej informacji Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy:	Ilona Bluemke
Prowadzący grup:	Ilona Bluemke
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. letni" (zakończony)

Okres:	2013-02-20 - 2013-09-30	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 48 miejsc więcej informacji Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy:	Ilona Bluemke
Prowadzący grup:	Ilona Bluemke
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. zimowy" (zakończony)

Okres:	2012-10-01 - 2013-02-19	Wybrany podział planu: ten tydzień cykl przedmiotu zobacz plan zajęć
Typ zajęć:	Projekt, 30 godzin, 48 miejsc więcej informacji Wykład, 30 godzin, 48 miejsc więcej informacji
Koordynatorzy:	Andrzej Pająk
Prowadzący grup:	Andrzej Pająk
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin
Jednostka realizująca:	103200 - Instytut Informatyki

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.