Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

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:

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 2021/2022 - sem. zimowy" (zakończony)

Okres: 2021-10-01 - 2022-02-22
Wybrany podział planu:
Przejdź do planu
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:
Przejdź do planu
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:
Przejdź do planu
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:
Przejdź do planu
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:
Przejdź do planu
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:
Przejdź do planu
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:
Przejdź do planu
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

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)