Języki formalne i techniki translacji 2012

Środa 15¹⁵ - 16⁵⁵ A-1/204 wykład

Środa 9¹⁵ - 11⁰⁰ TN/TP C-7/303 ćwiczenia - mgr inż. Szymon Wilczek

Środa 11¹⁵ - 13⁰⁰ TN C-11/2.11 ćwiczenia - mgr inż. Anna Lauks-Dutka

Poniedziałek 15¹⁵ - 16⁵⁵ TN/TP D-1/317.3 laboratorium - mgr inż. Anna Lauks-Dutka

Poniedziałek 17⁰⁵ - 18⁴⁵ TN/TP D-1/317.3 laboratorium

Czwartek 11¹⁵ - 13⁰⁰ TN/TP D-1/317.3 laboratorium - mgr inż. Piotr Syga

Literatura

1. A.V. Aho, R. Sethi, J.D. Ullman, Kompilatory. Reguły, metody i narzędzia, WNT, Warszawa 2002, (ISBN: 83-204-2656-1)
2. 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)
3. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
4. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
5. Studia Informatyczne - Podstawy kompilatorów (http://wazniak.mimuw.edu.pl/)

Listy zadań na ćwiczenia

• Lista nr 1 na 15 lutego
• Lista nr 2 na 22/29 lutego
• Lista nr 3 na 7/14 marca
• Lista nr 4 na 21/28 marca
• Lista nr 5 na 4/11 kwietnia
• Lista nr 6 na 18/25 kwietnia
• Lista nr 7 na 2/9 maja
• Lista nr 8 na 16/23 maja

Listy zadań na laboratorium

• Lista nr 1 (oddanie przed 3 marca)
• Lista nr 2 (oddanie przed 31 marca)
• Lista nr 3 (oddanie przed 28 kwietnia)
• Projekt (oddanie przed 1 czerwca) (Kod maszyny rejestrowej i przykłady) ) (Przykłady do testów ) [modyfikacje z 21-05-2012]

Tematy wykładów (w przybliżeniu)

1. Wprowadzenie do wykładu. DFA, NFA i RE.
2. Równoważność DFA, NFA i RE. Minimalny DFA.
3. Własności języków regularnych. Analiza leksykalna. (przykład z wykładu)
4. Gramatyki bezkontekstowe. Postacie normalne Chomsky'ego i Greibach.
5. Automat ze stosem (PDA). Równoważność PDA i gramatyk bezkontekstowych.
6. Własności języków bezkontekstowych.
7. Zstępująca analiza składniowa.
8. Gramatyki typu LL(k).
9. Analiza wstępująca. Gramatyki LR(k). (przykład z wykładu)
10. Gramatyki SLR, LR(1) i LALR.
11. Translacja sterowana składnią i zależności kontekstowe. (przykład z wykładu)
12. Synteza kodu i środowisko czasu wykonywania.
13. Hierarchia Chomsky'ego.
14. Krótki wstęp do teorii obliczeń.
15. Podsumowanie wykładu.

Zasady zaliczenia kursu

Zaliczenie ćwiczeń

1. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru. Ocena z ćwiczeń jest oceną jakości i intensywności pracy studenta w czasie semestru.
2. Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach studenci prezentują rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości dotyczące rozwiązania oraz przedstawiane alternatywne rozwiązania.
3. Podstawą do wystawienia oceny są wyniki krótkich sprawdzianów. Sprawdziany będą polegały na rozwiązaniu jednego zadania i punktowane od 0 do 5. Materiałem obowiązującym na sprawdzianie są 2 poprzednie listy. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi. Nieobecność na sprawdzianie daje 0.
4. Podstawą do obliczenia oceny z kursu jest średnia ze sprawdzianów zaokrąglona w górę do 0.5. Średnia może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach.
5. 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.
6. Dodatkowym warunkiem zaliczenia 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.
7. Punktacja nie podlega poprawianiu po zakończeniu zajęć.

Zaliczenie laboratorium

1. Na laboratoriach studenci powinni oddawać implementacje list przygotowanych do kursu.
2. Listy powinny być oddane na ostatnich zajęciach przed datą podaną na liście.
3. Oddawane rozwiązania powinny być samodzielnie napisane.
4. 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.
5. Nieusprawiedliwione nie oddanie w terminie programu powoduje obniżenie oceny z projektu kompilatora o 0.5 za każdy spóźniony program.
6. Zaliczenie projektu kompilatora jest warunkiem koniecznym zaliczenia kursu

Egzamin

1. Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
2. Egzamin można poprawiać tylko raz ale na ocenę co najwyżej 3.0.
3. Na egzaminie 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.

Ocena końcowa

Ocena końcowa liczona jest według wzoru 0.2*PC+0.4*OP+0.4*OE i zaokrąglana w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).
[PC - średnia punktów z ćwiczeń, OP - ocena z projektu, OE - ocena z egzaminu.]