Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (S1)
specjalność: Inżynieria chmurowa

Sylabus przedmiotu Kompilatory:

Informacje podstawowe

Kierunek studiów Informatyka
Forma studiów studia stacjonarne Poziom pierwszego stopnia
Tytuł zawodowy absolwenta inżynier
Obszary studiów charakterystyki PRK, kompetencje inżynierskie PRK
Profil ogólnoakademicki
Moduł
Przedmiot Kompilatory
Specjalność przedmiot wspólny
Jednostka prowadząca Katedra Inżynierii Oprogramowania i Cyberbezpieczeństwa
Nauczyciel odpowiedzialny Piotr Błaszyński <Piotr.Blaszynski@zut.edu.pl>
Inni nauczyciele Piotr Błaszyński <Piotr.Blaszynski@zut.edu.pl>
ECTS (planowane) 4,0 ECTS (formy) 4,0
Forma zaliczenia zaliczenie Język polski
Blok obieralny 6 Grupa obieralna 6

Formy dydaktyczne

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
laboratoriaL6 30 2,00,50zaliczenie
wykładyW6 30 2,00,50zaliczenie

Wymagania wstępne

KODWymaganie wstępne
W-1Programowanie 2
W-2Algorytmy 2
W-3Architektura systemów komputerowych

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Ukształtowanie wiedzy i umiejętności niezbędnych do opracowania kompilatora dla komputera sekwencyjnego o prostej architekturze
C-2Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie tworzenia kompilatorów

Treści programowe z podziałem na formy zajęć

KODTreść programowaGodziny
laboratoria
T-L-1Definiowanie języka3
T-L-2Implementacja analizatora leksykalnego przy pomocy narzędzia FLEX4
T-L-3Implementacja analizatora składniowego przy pomocy narzędzia BISON4
T-L-4Proste akcje semantyczne2
T-L-5Implementacja generatora kodu dla wyrażeń arytmetycznych (z wykorzystaniem ONP)3
T-L-6Generacja kodu dla instrukcji warunkowych i pętli4
T-L-7Metody implementacji korzystania z tablic jedno- i wielowymiarowych3
T-L-8Implementacja generatora kodu dla różnych typów danych3
T-L-9Implementacja wywołań funkcji (na lepsze oceny)2
T-L-10Implementacja struktur (na lepsze oceny)2
30
wykłady
T-W-1Definicja translatora, kompilatora, interpretera. Fazy kompilacji. Struktura przodu kompilatora. Struktura tylnej części kompilatora. Definicja produkcji. Definicja epsilon-produkcji.2
T-W-2Łączność operatorów. Definicja gramatyki. Gramatyki bezkontekstowe. Gramatyki niejednocznaczne. Definicja języka. Drzewa wyprowadzeń. Priorytety operatorów a odpowiednia gramatyka.2
T-W-3Translacja sterowana składnią. Definicja sterowana składnią. Atrybuty syntezowane. Przechodzenie drzewa w głąb. Schemat translacji. Składnia abstrakcyjna i składnia konkretna. Translator dla prostych wyrażeń.2
T-W-4Proste metody analizy leksykalnej: usuwanie znaków odstępu I komentarzy, rozpoznanie identyfikatorów i słów kluczowych. Prosty analizator leksykalny. Implementacja tablicy symboli L-wartości i R-wartości. Translacja wyrażeń z zastosowaniem stosu.2
T-W-5Symbole leksykalne, wzorce, leksemy. Leksemy i tokeny. Atrybuty symboli leksykalnych. Błędy leksykalne. Buforowanie w analizie leksykalnej. Napisy i języki. Operacje na językach.2
T-W-6Wyrażenia regularne. Definicje regularne. Skróty notacyjne w wyrażeniach regularnych. Rozpoznanie symboli leksykalnych. Diagramy przejść. Tworzenie analizatora leksykalnego przy użyciu Leksa. Specyfikacja dla Leksa. Automaty skończone: deterministyczne i niedeterministyczne.2
T-W-7Miejsce analizatora składniowego w kompilatorze. Wyprowadzenie, typy wyprowadzeń. Drzewo wyprowadzeń. Budowa tablic przewidujących. Obliczenie zbioru FIRST. Obliczenie zbioru FOLLOW. Gramatyka LL(1).2
T-W-8Narzędzie YACC. Tworzenie pliku specyfikacji. Akcje semantyczne. Rozwiązywanie konfliktów reduce/reduce. Rozwiązywanie konfliktów shift/reduce.2
T-W-9Analiza semantyczna. Cele analizy semantycznej. Rodzaje kontroli. Przykłady błędów na etapie analizy semantycznej. Zakresy zmiennych, zasięgi nazw.2
T-W-10Generacja kodu maszynowego MIPS/x86 1, symulator SPIM. Język Asembler. Rejestry MIPS/x86 i ich zastosowanie. Operatory porównania. Instrukcje skoków.2
T-W-11Generacja kodu maszynowego MIPS 2/x86, symulator SPIM. Generowanie kodu dla deklaracji. Generowanie kodu dla wyrażeń. Generowanie kodu dla instrukcji sterujących. Wywołanie procedur. Tablice. Wejście/wyjście. Kod dla struktur i klas.2
T-W-12Składnia abstrakcyjna i konkretna. Drzewa konkretne i abstrakcyjne. Zasady tworzenia prostego translatora: kolejność czynności niezbędnych do utworzenia prostego translatora. Dostosowanie schematu translacji na notację polską. Pseudokod translacji na notację polską. Translator w języku Java. Translator w języku C. Translator w oparciu o Lex i Yacc.2
T-W-13Podstawy optymalizacji kodu wynikowego w kompilatorach.2
T-W-14Nowoczesne narzędzia do budowy kompilatorów. Roslyn. LLVM.2
T-W-15Analiza wstępująca. Redukcja. Parsowanie shift-reduce. Zastosowanie stosu. Klasyfikacja gramatyk. Gramatyka LR(1). Gramatyka LR(k). Konflikty w parserach LR(k). Akcje parsera LR(1). Architektura parsera LL(1) i sposób jego działania. Parsowanie zstępujące. Zastosowanie ε-produkcji w parsowaniu zstępującym. Parsowanie przewidujące. Definicja zbioru FIRST i jego zastosowanie w parsowaniu przewidującym. Rekurencja lewostronna. Wyeliminowanie rekurencji lewostronnej. Pseudokod parsowania przewidującego. Projektowanie parsera przewidującego.2
30

Obciążenie pracą studenta - formy aktywności

KODForma aktywnościGodziny
laboratoria
A-L-1uczestnictwo w zajęciach30
A-L-2Praca własna20
50
wykłady
A-W-1uczestnictwo w zajęciach30
A-W-2Praca własna18
A-W-3Konsultacje2
50

Metody nauczania / narzędzia dydaktyczne

KODMetoda nauczania / narzędzie dydaktyczne
M-1Wykład informacyjny/konwersatoryjny
M-2Ćwiczenia laboratoryjne

Sposoby oceny

KODSposób oceny
S-1Ocena formująca: Ocena stopnia wykonywania zadań praktycznych pod koniec każdych laboratoriów
S-2Ocena podsumowująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi

Zamierzone efekty uczenia się - wiedza

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
Itest_1A_C25.3_W01
ma wiedzę w zakresie algorytmów projektowania kompilatorów oraz zna narzędzia do tworzenia kompilatorów
I_1A_W05, I_1A_W03C-2, C-1T-L-5, T-L-6, T-L-7, T-L-8, T-L-9, T-L-10, T-L-3, T-L-1, T-L-2, T-L-4, T-W-5, T-W-1, T-W-2, T-W-3, T-W-4, T-W-6, T-W-15, T-W-7, T-W-13, T-W-14, T-W-8, T-W-9, T-W-12, T-W-10, T-W-11M-1, M-2S-1, S-2

Zamierzone efekty uczenia się - umiejętności

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
Itest_1A_C25.3_U01
potrafi w zakresie podstawowym projektować, implementować i testować kompilatory i translatory
I_1A_U09, I_1A_U05, I_1A_U07C-2, C-1T-L-5, T-L-6, T-L-7, T-L-8, T-L-9, T-L-10, T-L-3, T-L-1, T-L-2, T-L-4, T-W-10, T-W-11M-1, M-2S-1, S-2

Zamierzone efekty uczenia się - inne kompetencje społeczne i personalne

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
Itest_1A_C25.3_K01
świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
I_1A_K01C-2, C-1T-L-5, T-L-6, T-L-7, T-L-8, T-L-9, T-L-10, T-L-3, T-L-1, T-L-2, T-L-4, T-W-5, T-W-1, T-W-2, T-W-3, T-W-4, T-W-6, T-W-15, T-W-7, T-W-13, T-W-14, T-W-8, T-W-9, T-W-12, T-W-10, T-W-11M-1, M-2S-1

Kryterium oceny - wiedza

Efekt uczenia sięOcenaKryterium oceny
Itest_1A_C25.3_W01
ma wiedzę w zakresie algorytmów projektowania kompilatorów oraz zna narzędzia do tworzenia kompilatorów
2,0nie zna podstawowych metod projektowania kompilatorów, nie ma wiedzy o narzędziach do analizy leksykalnej i syntaktycznej
3,0zna podstawowe metody projektowania kompilatorów oraz rozumie potrzebę projektowania kompilatorów na ogólnym poziomie, ma podstawową więdzę o narzędziach do analizy leksykalnej i syntaktycznej
3,5zna szczegółowo podstawowe metody projektowania kompilatorów oraz rozumie potrzebę projektowania kompilatorów na ogólnym poziomie, ma wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych
4,0zna szczegółowo podstawowe metody projektowania kompilatorów oraz wie jak zastosować je do projektowania prostych kompilatorów, ma wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych oraz narzędziu YACC/bison do projektowania analizatorów składniowych
4,5zna szczegółowo zaawansowane metody projektowania kompilatorów oraz wie jak zastosować je do projektowania kompilatorów, ma szczegółową wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych oraz narzędziu YACC/bison do projektowania analizatorów składniowych
5,0zna szczegółowo zaawansowane metody projektowania kompilatorów oraz wie jak zastosować je do projektowania kompilatorów, oraz potrafi udowodnić i uzasadnić swoją wypowiedż, ma szczegółową wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych oraz narzędziu YACC/bison do projektowania analizatorów składniowych oraz wie jak zastosować wiedze do projektowania analizatorów leksykalnych i składniowych

Kryterium oceny - umiejętności

Efekt uczenia sięOcenaKryterium oceny
Itest_1A_C25.3_U01
potrafi w zakresie podstawowym projektować, implementować i testować kompilatory i translatory
2,0nie potrafi zaimplementować prostego kompilatora przekładającego podstawowe wyrażenia arytmetyczne na kod maszynowy.
3,0potrafi zaimplementować bardzo prosty kompilator przekładający podstawowe wyrażenia arytmetyczne operujące na podstawowych typach danych (całkowite i zmiennoprzecinkowe) na kod maszynowy, jest w stanie zaimplementować obsługę instrukcji warunkowych bez zagnieżdżeń.
3,5potrafi wszystko to co na ocenę 3,0 oraz potrafi zastosować zasady dotyczące implementacji instrukcji warunkowych dla zagnieżdżonych konstrukcji.
4,0potrafi wszystko to co na ocenę 3,5 oraz potrafi przeanalizować powstały kod maszynowy w celu minimalizacji liczby skoków przy złożonych instrukcjach warunkowych. Potrafi również zaimplementować kompilację konstrukcji pętli i tablic jednowymiarowych.
4,5potrafi syntezować pozyskane umiejętności w kompletny kompilator generujący kod z wykorzystaniem konstrukcji wymaganych na niższe oceny oraz dodatkowo tablic wielowymiarowych.
5,0potrafi ocenić kompilator generujący kod z wykorzystaniem konstrukcji wymaganych na niższe oceny oraz zaproponować i wykonać dodatkowe funkcjonalności (np. obsługę funkcji, generowanie kodu dla architektury 64-bitowej)

Kryterium oceny - inne kompetencje społeczne i personalne

Efekt uczenia sięOcenaKryterium oceny
Itest_1A_C25.3_K01
świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
2,0nie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
3,0rozumie potrzebę dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
3,5jest w stanie zaprezentować w pełni zaimplementowane rozwiązanie
4,0jest w stanie zaprezentować w pełni i przedyskutować z prowadzącym zaimplementowane rozwiązanie
4,5na bazie kompetencji wymaganych na niższe oceny jest w stanie podzielić się wiedzą w usystematyzowany sposób z grupą
5,0na bazie kompetencji wymaganych na niższe oceny jest w stanie przygotować i zaprezentować własne propozycje w zakresie metod i narzędzi do tworzenia kompilatorów

Literatura podstawowa

  1. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Kompilatory, Reguły, Metody i Narzędzia, WNT, Warszawa, 2002
  2. Aho and al., Compilers: Principles, Techniques, and Tools, Addison Wesley, Boston, 2007

Literatura dodatkowa

  1. R. Wilhelm, D. Maurer, Compiler Design, Addison-Wesley, Boston, 1995

Treści programowe - laboratoria

KODTreść programowaGodziny
T-L-1Definiowanie języka3
T-L-2Implementacja analizatora leksykalnego przy pomocy narzędzia FLEX4
T-L-3Implementacja analizatora składniowego przy pomocy narzędzia BISON4
T-L-4Proste akcje semantyczne2
T-L-5Implementacja generatora kodu dla wyrażeń arytmetycznych (z wykorzystaniem ONP)3
T-L-6Generacja kodu dla instrukcji warunkowych i pętli4
T-L-7Metody implementacji korzystania z tablic jedno- i wielowymiarowych3
T-L-8Implementacja generatora kodu dla różnych typów danych3
T-L-9Implementacja wywołań funkcji (na lepsze oceny)2
T-L-10Implementacja struktur (na lepsze oceny)2
30

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Definicja translatora, kompilatora, interpretera. Fazy kompilacji. Struktura przodu kompilatora. Struktura tylnej części kompilatora. Definicja produkcji. Definicja epsilon-produkcji.2
T-W-2Łączność operatorów. Definicja gramatyki. Gramatyki bezkontekstowe. Gramatyki niejednocznaczne. Definicja języka. Drzewa wyprowadzeń. Priorytety operatorów a odpowiednia gramatyka.2
T-W-3Translacja sterowana składnią. Definicja sterowana składnią. Atrybuty syntezowane. Przechodzenie drzewa w głąb. Schemat translacji. Składnia abstrakcyjna i składnia konkretna. Translator dla prostych wyrażeń.2
T-W-4Proste metody analizy leksykalnej: usuwanie znaków odstępu I komentarzy, rozpoznanie identyfikatorów i słów kluczowych. Prosty analizator leksykalny. Implementacja tablicy symboli L-wartości i R-wartości. Translacja wyrażeń z zastosowaniem stosu.2
T-W-5Symbole leksykalne, wzorce, leksemy. Leksemy i tokeny. Atrybuty symboli leksykalnych. Błędy leksykalne. Buforowanie w analizie leksykalnej. Napisy i języki. Operacje na językach.2
T-W-6Wyrażenia regularne. Definicje regularne. Skróty notacyjne w wyrażeniach regularnych. Rozpoznanie symboli leksykalnych. Diagramy przejść. Tworzenie analizatora leksykalnego przy użyciu Leksa. Specyfikacja dla Leksa. Automaty skończone: deterministyczne i niedeterministyczne.2
T-W-7Miejsce analizatora składniowego w kompilatorze. Wyprowadzenie, typy wyprowadzeń. Drzewo wyprowadzeń. Budowa tablic przewidujących. Obliczenie zbioru FIRST. Obliczenie zbioru FOLLOW. Gramatyka LL(1).2
T-W-8Narzędzie YACC. Tworzenie pliku specyfikacji. Akcje semantyczne. Rozwiązywanie konfliktów reduce/reduce. Rozwiązywanie konfliktów shift/reduce.2
T-W-9Analiza semantyczna. Cele analizy semantycznej. Rodzaje kontroli. Przykłady błędów na etapie analizy semantycznej. Zakresy zmiennych, zasięgi nazw.2
T-W-10Generacja kodu maszynowego MIPS/x86 1, symulator SPIM. Język Asembler. Rejestry MIPS/x86 i ich zastosowanie. Operatory porównania. Instrukcje skoków.2
T-W-11Generacja kodu maszynowego MIPS 2/x86, symulator SPIM. Generowanie kodu dla deklaracji. Generowanie kodu dla wyrażeń. Generowanie kodu dla instrukcji sterujących. Wywołanie procedur. Tablice. Wejście/wyjście. Kod dla struktur i klas.2
T-W-12Składnia abstrakcyjna i konkretna. Drzewa konkretne i abstrakcyjne. Zasady tworzenia prostego translatora: kolejność czynności niezbędnych do utworzenia prostego translatora. Dostosowanie schematu translacji na notację polską. Pseudokod translacji na notację polską. Translator w języku Java. Translator w języku C. Translator w oparciu o Lex i Yacc.2
T-W-13Podstawy optymalizacji kodu wynikowego w kompilatorach.2
T-W-14Nowoczesne narzędzia do budowy kompilatorów. Roslyn. LLVM.2
T-W-15Analiza wstępująca. Redukcja. Parsowanie shift-reduce. Zastosowanie stosu. Klasyfikacja gramatyk. Gramatyka LR(1). Gramatyka LR(k). Konflikty w parserach LR(k). Akcje parsera LR(1). Architektura parsera LL(1) i sposób jego działania. Parsowanie zstępujące. Zastosowanie ε-produkcji w parsowaniu zstępującym. Parsowanie przewidujące. Definicja zbioru FIRST i jego zastosowanie w parsowaniu przewidującym. Rekurencja lewostronna. Wyeliminowanie rekurencji lewostronnej. Pseudokod parsowania przewidującego. Projektowanie parsera przewidującego.2
30

Formy aktywności - laboratoria

KODForma aktywnościGodziny
A-L-1uczestnictwo w zajęciach30
A-L-2Praca własna20
50
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1uczestnictwo w zajęciach30
A-W-2Praca własna18
A-W-3Konsultacje2
50
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięItest_1A_C25.3_W01ma wiedzę w zakresie algorytmów projektowania kompilatorów oraz zna narzędzia do tworzenia kompilatorów
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W05Ma wiedzę o nowoczesnych metodach projektowania, analizowania, wytwarzania, testowania oprogramowania oraz rozwiązywania wybranych zadań inżynierskich obejmujących w szczególności narzędzia wspomagające wytwarzanie oprogramowania na różnych etapach powstawania, eksploatacji i rozwoju systemów informatycznych.
I_1A_W03Ma szczegółową wiedzę w zakresie wybranych specjalności informatyki technicznej.
Cel przedmiotuC-2Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie tworzenia kompilatorów
C-1Ukształtowanie wiedzy i umiejętności niezbędnych do opracowania kompilatora dla komputera sekwencyjnego o prostej architekturze
Treści programoweT-L-5Implementacja generatora kodu dla wyrażeń arytmetycznych (z wykorzystaniem ONP)
T-L-6Generacja kodu dla instrukcji warunkowych i pętli
T-L-7Metody implementacji korzystania z tablic jedno- i wielowymiarowych
T-L-8Implementacja generatora kodu dla różnych typów danych
T-L-9Implementacja wywołań funkcji (na lepsze oceny)
T-L-10Implementacja struktur (na lepsze oceny)
T-L-3Implementacja analizatora składniowego przy pomocy narzędzia BISON
T-L-1Definiowanie języka
T-L-2Implementacja analizatora leksykalnego przy pomocy narzędzia FLEX
T-L-4Proste akcje semantyczne
T-W-5Symbole leksykalne, wzorce, leksemy. Leksemy i tokeny. Atrybuty symboli leksykalnych. Błędy leksykalne. Buforowanie w analizie leksykalnej. Napisy i języki. Operacje na językach.
T-W-1Definicja translatora, kompilatora, interpretera. Fazy kompilacji. Struktura przodu kompilatora. Struktura tylnej części kompilatora. Definicja produkcji. Definicja epsilon-produkcji.
T-W-2Łączność operatorów. Definicja gramatyki. Gramatyki bezkontekstowe. Gramatyki niejednocznaczne. Definicja języka. Drzewa wyprowadzeń. Priorytety operatorów a odpowiednia gramatyka.
T-W-3Translacja sterowana składnią. Definicja sterowana składnią. Atrybuty syntezowane. Przechodzenie drzewa w głąb. Schemat translacji. Składnia abstrakcyjna i składnia konkretna. Translator dla prostych wyrażeń.
T-W-4Proste metody analizy leksykalnej: usuwanie znaków odstępu I komentarzy, rozpoznanie identyfikatorów i słów kluczowych. Prosty analizator leksykalny. Implementacja tablicy symboli L-wartości i R-wartości. Translacja wyrażeń z zastosowaniem stosu.
T-W-6Wyrażenia regularne. Definicje regularne. Skróty notacyjne w wyrażeniach regularnych. Rozpoznanie symboli leksykalnych. Diagramy przejść. Tworzenie analizatora leksykalnego przy użyciu Leksa. Specyfikacja dla Leksa. Automaty skończone: deterministyczne i niedeterministyczne.
T-W-15Analiza wstępująca. Redukcja. Parsowanie shift-reduce. Zastosowanie stosu. Klasyfikacja gramatyk. Gramatyka LR(1). Gramatyka LR(k). Konflikty w parserach LR(k). Akcje parsera LR(1). Architektura parsera LL(1) i sposób jego działania. Parsowanie zstępujące. Zastosowanie ε-produkcji w parsowaniu zstępującym. Parsowanie przewidujące. Definicja zbioru FIRST i jego zastosowanie w parsowaniu przewidującym. Rekurencja lewostronna. Wyeliminowanie rekurencji lewostronnej. Pseudokod parsowania przewidującego. Projektowanie parsera przewidującego.
T-W-7Miejsce analizatora składniowego w kompilatorze. Wyprowadzenie, typy wyprowadzeń. Drzewo wyprowadzeń. Budowa tablic przewidujących. Obliczenie zbioru FIRST. Obliczenie zbioru FOLLOW. Gramatyka LL(1).
T-W-13Podstawy optymalizacji kodu wynikowego w kompilatorach.
T-W-14Nowoczesne narzędzia do budowy kompilatorów. Roslyn. LLVM.
T-W-8Narzędzie YACC. Tworzenie pliku specyfikacji. Akcje semantyczne. Rozwiązywanie konfliktów reduce/reduce. Rozwiązywanie konfliktów shift/reduce.
T-W-9Analiza semantyczna. Cele analizy semantycznej. Rodzaje kontroli. Przykłady błędów na etapie analizy semantycznej. Zakresy zmiennych, zasięgi nazw.
T-W-12Składnia abstrakcyjna i konkretna. Drzewa konkretne i abstrakcyjne. Zasady tworzenia prostego translatora: kolejność czynności niezbędnych do utworzenia prostego translatora. Dostosowanie schematu translacji na notację polską. Pseudokod translacji na notację polską. Translator w języku Java. Translator w języku C. Translator w oparciu o Lex i Yacc.
T-W-10Generacja kodu maszynowego MIPS/x86 1, symulator SPIM. Język Asembler. Rejestry MIPS/x86 i ich zastosowanie. Operatory porównania. Instrukcje skoków.
T-W-11Generacja kodu maszynowego MIPS 2/x86, symulator SPIM. Generowanie kodu dla deklaracji. Generowanie kodu dla wyrażeń. Generowanie kodu dla instrukcji sterujących. Wywołanie procedur. Tablice. Wejście/wyjście. Kod dla struktur i klas.
Metody nauczaniaM-1Wykład informacyjny/konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Ocena stopnia wykonywania zadań praktycznych pod koniec każdych laboratoriów
S-2Ocena podsumowująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi
Kryteria ocenyOcenaKryterium oceny
2,0nie zna podstawowych metod projektowania kompilatorów, nie ma wiedzy o narzędziach do analizy leksykalnej i syntaktycznej
3,0zna podstawowe metody projektowania kompilatorów oraz rozumie potrzebę projektowania kompilatorów na ogólnym poziomie, ma podstawową więdzę o narzędziach do analizy leksykalnej i syntaktycznej
3,5zna szczegółowo podstawowe metody projektowania kompilatorów oraz rozumie potrzebę projektowania kompilatorów na ogólnym poziomie, ma wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych
4,0zna szczegółowo podstawowe metody projektowania kompilatorów oraz wie jak zastosować je do projektowania prostych kompilatorów, ma wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych oraz narzędziu YACC/bison do projektowania analizatorów składniowych
4,5zna szczegółowo zaawansowane metody projektowania kompilatorów oraz wie jak zastosować je do projektowania kompilatorów, ma szczegółową wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych oraz narzędziu YACC/bison do projektowania analizatorów składniowych
5,0zna szczegółowo zaawansowane metody projektowania kompilatorów oraz wie jak zastosować je do projektowania kompilatorów, oraz potrafi udowodnić i uzasadnić swoją wypowiedż, ma szczegółową wiedzę o narzedziu LEX do projektowania analizatorów leksykalnych oraz narzędziu YACC/bison do projektowania analizatorów składniowych oraz wie jak zastosować wiedze do projektowania analizatorów leksykalnych i składniowych
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięItest_1A_C25.3_U01potrafi w zakresie podstawowym projektować, implementować i testować kompilatory i translatory
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U09Potrafi dobrać właściwe metody i narzędzia do rozwiązywania wybranych zadań informatycznych w warunkach nie w pełni przewidywalnych.
I_1A_U05Potrafi zaplanować i zrealizować eksperymenty w zakresie oceny wydajności, złożoności, efektywności systemów informatycznych i ich składowych.
I_1A_U07Potrafi samodzielnie posługiwać się materiałami źródłowymi w zakresie analizy i syntezy zawartych w nich informacji oraz poddawać je krytycznej ocenie w odniesieniu do problemów informatycznych.
Cel przedmiotuC-2Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie tworzenia kompilatorów
C-1Ukształtowanie wiedzy i umiejętności niezbędnych do opracowania kompilatora dla komputera sekwencyjnego o prostej architekturze
Treści programoweT-L-5Implementacja generatora kodu dla wyrażeń arytmetycznych (z wykorzystaniem ONP)
T-L-6Generacja kodu dla instrukcji warunkowych i pętli
T-L-7Metody implementacji korzystania z tablic jedno- i wielowymiarowych
T-L-8Implementacja generatora kodu dla różnych typów danych
T-L-9Implementacja wywołań funkcji (na lepsze oceny)
T-L-10Implementacja struktur (na lepsze oceny)
T-L-3Implementacja analizatora składniowego przy pomocy narzędzia BISON
T-L-1Definiowanie języka
T-L-2Implementacja analizatora leksykalnego przy pomocy narzędzia FLEX
T-L-4Proste akcje semantyczne
T-W-10Generacja kodu maszynowego MIPS/x86 1, symulator SPIM. Język Asembler. Rejestry MIPS/x86 i ich zastosowanie. Operatory porównania. Instrukcje skoków.
T-W-11Generacja kodu maszynowego MIPS 2/x86, symulator SPIM. Generowanie kodu dla deklaracji. Generowanie kodu dla wyrażeń. Generowanie kodu dla instrukcji sterujących. Wywołanie procedur. Tablice. Wejście/wyjście. Kod dla struktur i klas.
Metody nauczaniaM-1Wykład informacyjny/konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Ocena stopnia wykonywania zadań praktycznych pod koniec każdych laboratoriów
S-2Ocena podsumowująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi
Kryteria ocenyOcenaKryterium oceny
2,0nie potrafi zaimplementować prostego kompilatora przekładającego podstawowe wyrażenia arytmetyczne na kod maszynowy.
3,0potrafi zaimplementować bardzo prosty kompilator przekładający podstawowe wyrażenia arytmetyczne operujące na podstawowych typach danych (całkowite i zmiennoprzecinkowe) na kod maszynowy, jest w stanie zaimplementować obsługę instrukcji warunkowych bez zagnieżdżeń.
3,5potrafi wszystko to co na ocenę 3,0 oraz potrafi zastosować zasady dotyczące implementacji instrukcji warunkowych dla zagnieżdżonych konstrukcji.
4,0potrafi wszystko to co na ocenę 3,5 oraz potrafi przeanalizować powstały kod maszynowy w celu minimalizacji liczby skoków przy złożonych instrukcjach warunkowych. Potrafi również zaimplementować kompilację konstrukcji pętli i tablic jednowymiarowych.
4,5potrafi syntezować pozyskane umiejętności w kompletny kompilator generujący kod z wykorzystaniem konstrukcji wymaganych na niższe oceny oraz dodatkowo tablic wielowymiarowych.
5,0potrafi ocenić kompilator generujący kod z wykorzystaniem konstrukcji wymaganych na niższe oceny oraz zaproponować i wykonać dodatkowe funkcjonalności (np. obsługę funkcji, generowanie kodu dla architektury 64-bitowej)
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięItest_1A_C25.3_K01świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_K01Jest gotów do krytycznej oceny posiadanej wiedzy oraz ma świadomość jej znaczenia w procesie rozwiązywania szeregu problemów inżynierskich i technicznych w dziedzinie informatyki.
Cel przedmiotuC-2Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie tworzenia kompilatorów
C-1Ukształtowanie wiedzy i umiejętności niezbędnych do opracowania kompilatora dla komputera sekwencyjnego o prostej architekturze
Treści programoweT-L-5Implementacja generatora kodu dla wyrażeń arytmetycznych (z wykorzystaniem ONP)
T-L-6Generacja kodu dla instrukcji warunkowych i pętli
T-L-7Metody implementacji korzystania z tablic jedno- i wielowymiarowych
T-L-8Implementacja generatora kodu dla różnych typów danych
T-L-9Implementacja wywołań funkcji (na lepsze oceny)
T-L-10Implementacja struktur (na lepsze oceny)
T-L-3Implementacja analizatora składniowego przy pomocy narzędzia BISON
T-L-1Definiowanie języka
T-L-2Implementacja analizatora leksykalnego przy pomocy narzędzia FLEX
T-L-4Proste akcje semantyczne
T-W-5Symbole leksykalne, wzorce, leksemy. Leksemy i tokeny. Atrybuty symboli leksykalnych. Błędy leksykalne. Buforowanie w analizie leksykalnej. Napisy i języki. Operacje na językach.
T-W-1Definicja translatora, kompilatora, interpretera. Fazy kompilacji. Struktura przodu kompilatora. Struktura tylnej części kompilatora. Definicja produkcji. Definicja epsilon-produkcji.
T-W-2Łączność operatorów. Definicja gramatyki. Gramatyki bezkontekstowe. Gramatyki niejednocznaczne. Definicja języka. Drzewa wyprowadzeń. Priorytety operatorów a odpowiednia gramatyka.
T-W-3Translacja sterowana składnią. Definicja sterowana składnią. Atrybuty syntezowane. Przechodzenie drzewa w głąb. Schemat translacji. Składnia abstrakcyjna i składnia konkretna. Translator dla prostych wyrażeń.
T-W-4Proste metody analizy leksykalnej: usuwanie znaków odstępu I komentarzy, rozpoznanie identyfikatorów i słów kluczowych. Prosty analizator leksykalny. Implementacja tablicy symboli L-wartości i R-wartości. Translacja wyrażeń z zastosowaniem stosu.
T-W-6Wyrażenia regularne. Definicje regularne. Skróty notacyjne w wyrażeniach regularnych. Rozpoznanie symboli leksykalnych. Diagramy przejść. Tworzenie analizatora leksykalnego przy użyciu Leksa. Specyfikacja dla Leksa. Automaty skończone: deterministyczne i niedeterministyczne.
T-W-15Analiza wstępująca. Redukcja. Parsowanie shift-reduce. Zastosowanie stosu. Klasyfikacja gramatyk. Gramatyka LR(1). Gramatyka LR(k). Konflikty w parserach LR(k). Akcje parsera LR(1). Architektura parsera LL(1) i sposób jego działania. Parsowanie zstępujące. Zastosowanie ε-produkcji w parsowaniu zstępującym. Parsowanie przewidujące. Definicja zbioru FIRST i jego zastosowanie w parsowaniu przewidującym. Rekurencja lewostronna. Wyeliminowanie rekurencji lewostronnej. Pseudokod parsowania przewidującego. Projektowanie parsera przewidującego.
T-W-7Miejsce analizatora składniowego w kompilatorze. Wyprowadzenie, typy wyprowadzeń. Drzewo wyprowadzeń. Budowa tablic przewidujących. Obliczenie zbioru FIRST. Obliczenie zbioru FOLLOW. Gramatyka LL(1).
T-W-13Podstawy optymalizacji kodu wynikowego w kompilatorach.
T-W-14Nowoczesne narzędzia do budowy kompilatorów. Roslyn. LLVM.
T-W-8Narzędzie YACC. Tworzenie pliku specyfikacji. Akcje semantyczne. Rozwiązywanie konfliktów reduce/reduce. Rozwiązywanie konfliktów shift/reduce.
T-W-9Analiza semantyczna. Cele analizy semantycznej. Rodzaje kontroli. Przykłady błędów na etapie analizy semantycznej. Zakresy zmiennych, zasięgi nazw.
T-W-12Składnia abstrakcyjna i konkretna. Drzewa konkretne i abstrakcyjne. Zasady tworzenia prostego translatora: kolejność czynności niezbędnych do utworzenia prostego translatora. Dostosowanie schematu translacji na notację polską. Pseudokod translacji na notację polską. Translator w języku Java. Translator w języku C. Translator w oparciu o Lex i Yacc.
T-W-10Generacja kodu maszynowego MIPS/x86 1, symulator SPIM. Język Asembler. Rejestry MIPS/x86 i ich zastosowanie. Operatory porównania. Instrukcje skoków.
T-W-11Generacja kodu maszynowego MIPS 2/x86, symulator SPIM. Generowanie kodu dla deklaracji. Generowanie kodu dla wyrażeń. Generowanie kodu dla instrukcji sterujących. Wywołanie procedur. Tablice. Wejście/wyjście. Kod dla struktur i klas.
Metody nauczaniaM-1Wykład informacyjny/konwersatoryjny
M-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Ocena stopnia wykonywania zadań praktycznych pod koniec każdych laboratoriów
Kryteria ocenyOcenaKryterium oceny
2,0nie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
3,0rozumie potrzebę dokształcania i dzielenia się wiedzą w zakresie metod i narzędzi do tworzenia kompilatorów
3,5jest w stanie zaprezentować w pełni zaimplementowane rozwiązanie
4,0jest w stanie zaprezentować w pełni i przedyskutować z prowadzącym zaimplementowane rozwiązanie
4,5na bazie kompetencji wymaganych na niższe oceny jest w stanie podzielić się wiedzą w usystematyzowany sposób z grupą
5,0na bazie kompetencji wymaganych na niższe oceny jest w stanie przygotować i zaprezentować własne propozycje w zakresie metod i narzędzi do tworzenia kompilatorów