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

  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


Listy zadań na laboratorium


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.
  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. Krótki wstęp do teorii obliczeń.
  14. Podsumowanie wykładu.
  15. Powtórzenie najtrudniejszych fragmentów 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.
  2. 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.
  3. 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

  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.

Ocena końcowa

  1. 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).
  2. Kolokwium zaliczeniowe odbędzie się na ostatnim wykładzie.
  3. Kolokwium można poprawiać tylko raz ale na ocenę co najwyżej 3.0.
  4. 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.

Counter Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl