Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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
( Algorytmy i języki programowania )-Inżynieria systemów informatycznych-inż.-EITI
( Przedmioty techniczne )---EITI
Punkty ECTS i inne: 5.00
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

TKOM

Numer wersji:

3

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 poprzednikaNr poprzednikaKod poprzednikaNazwa poprzednika
Zalecany1103C-INIIT-ISP-AALAnaliza algorytmów
Zalecany1103D-INIIT-ISP-AALAnaliza algorytmów

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

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

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
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 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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:


powiększ
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.