Języki formalne i techniki translacji 2011
Środa 1515 - 1655 A-1/204 wykład
Wtorek 1315 - 1500 TP C-4/35 ćwiczenia
Środa 915 - 1100 TN/TP C-7/303 ćwiczenia
Poniedziałek 730 - 900 TN/TP D-1/317.3 laboratorium
Poniedziałek 1515 - 1655 TN/TP D-1/317.3 laboratorium
Poniedziałek 1705 - 1845 TN/TP D-1/317.3 laboratorium
Literatura
- A.V. Aho, R. Sethi, J.D. Ullman, Kompilatory. Reguły, metody i
narzędzia, WNT, Warszawa 2002, (ISBN: 83-204-2656-1)
- J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii
automatów, języków i obliczeń, WNT, Warszawa 2005 (ISBN
83-01-14502-1)
- J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków
i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów,
WNT, Warszawa 1997 (ISBN 83-204-2144-6)
- Studia
Informatyczne - Podstawy kompilatorów (http://wazniak.mimuw.edu.pl/)
Listy zadań na ćwiczenia
- Lista nr 1 na 22,23 lutego/2 marca
- Lista nr 2 na 8,9,16 marca
- Lista nr 3 na 22,23,30 marca
- Lista nr 4 na 5,6,13 kwietnia
- Lista nr 5 na 19 kwietnia/4,11 maja
- Lista nr 6 na 17,18,25 maja
- Lista nr 7 na 31 maja/1,8 czerwca
Listy zadań na laboratorium
Tematy wykładów (w przybliżeniu)
- Wprowadzenie do wykładu. DFA, NFA i RE.
- Równoważność DFA, NFA i RE. Minimalny DFA.
- Własności języków regularnych. Analiza leksykalna.
- Gramatyki bezkontekstowe. Postacie normalne Chomsky'ego i Greibach.
- Automat ze stosem (PDA). Równoważność PDA i gramatyk bezkontekstowych.
- Własności języków bezkontekstowych.
- Zstępująca analiza składniowa.
- Gramatyki typu LL(k).
- Analiza wstępująca. Gramatyki LR(k).
(przykład z wykładu)
- Gramatyki SLR, LR(1) i LALR.
- Translacja sterowana składnią i zależności kontekstowe.
(przykład z wykładu)
- Synteza kodu i środowisko czasu wykonywania.
- Hierarchia Chomsky'ego.
Krótki wstęp do teorii obliczeń.
- Podsumowanie wykładu.
- Powtórzenie najtrudniejszych fragmentów wykładu.
Zasady zaliczenia kursu
Zaliczenie ćwiczeń
- Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad
opanowaniem materiału w czasie całego semestru.
- Na każde ćwiczenia jest przygotowywana osobna lista zadań, ogłaszana
co najmniej na trzy dni przed zajęciami. Na ćwiczeniach rozwiązywane są
wybrane zadania z tej listy. Decyzję odnośnie wyboru zadań do
rozwiązania podejmuje prowadzący.
- Jednym z warunków zaliczenia kursu jest oddanie przez studenta w
formie pisemnej (PDF) wyznaczonych zadań zrobionych na ćwiczeniach.
Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i
przejrzysty. Zadanie wyznacza prowadzący ćwiczenia.
Zaliczenie laboratorium
- Na laboratoriach studenci powinni oddawać implementacje list
przygotowanych do kursu.
- Listy powinny być oddane na ostatnich zajęciach przed datą podaną na
liście.
- Oddawane rozwiązania powinny być samodzielnie napisane.
- Ostatnie zadanie (projekt kompilatora) podlega wspólnej ocenie dla
całego roku według kryterium poprawności i szybkości wynikowego kodu.
Oceny są przyznawane w następujący sposób: najlepsze 5 rozwiązań - ocena
5.5, rozwiązania od 6 do 10 - 5.0, od 11 do 20 - 4.5, od 21 do 30 - 4.0,
od 31 do 40 - 3.5, pozostałe oddane i poprawne - 3.0.
- Nieusprawiedliwione nie oddanie w terminie programu powoduje
obniżenie oceny z projektu kompilatora o 0.5 za każdy spóźniony
program.
Ocena końcowa
- Ocena końcowa kursu jest średnią z oceny z kolokwium końcowego i
projektu kompilatora (obie oceny muszą być pozytywne) zaokrągloną w górę
do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).
- Kolokwium zaliczeniowe odbędzie się na ostatnim wykładzie.
- Kolokwium można poprawiać tylko raz ale na ocenę co najwyżej 3.0.
- Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu a4
podpisana w ten sposób aby z odległości 2 metrów dało się ustalić jej
właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek,
książek i innych pomocy. Kartki z treścią zadań i miejscem na
rozwiązania oraz brudnopisy dostarcza wykładowca.