Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Techniki kompilacji
Koordynator przedmiotu:
Andrzej PAJĄK
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. 2012/2013
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
126
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
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). 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.).
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://studia.elka.pw.edu.pl/priv/12L/TKOM.A/
Uwagi:
Brak

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt TKOM_W01
ma uporządkowaną wiedzę na temat metod opisu języków formalnych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt 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 efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt TKOM_W03
zna mechanizmy makrogeneracji i ich dostępność w środowiskach programistycznych
Weryfikacja: projekt semestralny; egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt TKOM_W04
ma uporządkowaną wiedzę na temat reprezentacji i przetwarzania języków regularnych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt 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 efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt 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 efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt 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 efekty kierunkowe:
Powiązane efekty obszarowe:

Profil ogólnoakademicki - umiejętności

Efekt TKOM_U01
potrafi zdefiniować formalnie składnię języka w metanotacji EBNF (lub podobnej)
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt 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 efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt 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 efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt TKOM_U04
potrafi zrealizować analizator leksykalny i parser rekursywnie zstępujący wg zadanej gramatyki
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt TKOM_U05
potrafi zastosować model przetwarzania sterowanego składnią (schemat translacji) do prostych problemów obliczeniowych
Weryfikacja: sprawdziany; projekt semestralny; egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt TKOM_U06
potrafi zaprojektować środowisko programowe do osadzenia akcji semantycznych dla prostego języka bezkontekstowego
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Efekt TKOM_K01
potrafi planować działania projektowe wg wymaganego terminu
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:
Efekt TKOM_K02
potrafi samodzielnie pozyskiwać poszerzające informacje o rozwiązywanym problemie i dostępnych narzędziach programowych
Weryfikacja: projekt semestralny
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe: