Stefan Sokołowski

JĘZYKI FORMALNE I METODY KOMPILACJI
rok III, sem. zimowy 2024/2025
wykład i laboratorium w ANS (Elbląg)

Wyniki w sesji podstawowej:
    Studenci dzienni BD
Wyniki w sesji poprawkowej:
    Studenci dzienni BD



wykładlaboratorium
15 godzin 30 godzin
slajdy do wykładów
zadania z laboratoriów
program wykładu
program laboratorium
literatura
   
kliknij

Oceny

Na ocenę składać się będą:
  • zaliczenie laboratorium (60%),
  • zaliczenie wykładu (40%),
  • ew. punkty dodatkowe za znalezienie błędu w slajdach.
(szczegółowe warunki zaliczenia -- wykład 0 oraz spis wymagań)

Uwaga:
  • Nie przewiduje się żadnych zwolnień z zaliczania wykładu na podstawie zaliczenia laboratorium.
  • Obecność na laboratorium jest sprawdzana; nieobecności powodują konsekwencje przewidziane w regulaminie studiów.
  • Studenci czwartego roku, mający zgodę na zaliczanie warunkowe, proszeni są o interesowanie się treścią wykładu i laboratorium w tym roku i nadrabianie ew. różnic. Zaliczać będą na dokładnie tych samych warunkach, co studenci z trzeciego roku, bez żadnej specjalnej taryfy.
na ocenępunktów
5
od 92 w górę
4+
83 -- 91
4
73 -- 82
3+
63 -- 72
3
56 -- 62
2
0 -- 55

Kontakt ze mną

Program wykładu

Oficjalny sylabus przedmiotu znajduje się tutaj.
  1. Języki formalne i gramatyki (3 godz.):
    • pojęcie gramatyki i definiowanie języków za pomocą gramatyk;
    • języki regularne, bezkontekstowe, inne;
    • wyrażenia regularne;
    • problem istnienia gramatyki dla danego języka;
    • leksyka i składnia języków programowania.
  2. Teoretyczne modele urządzeń liczących (3 godz.):
    • automaty skończone; ich związek z językami regularnymi;
    • wyrażenia regularne;
    • maszyny ze stosem; ich związek z językami bezkontekstowymi.
  3. Analiza leksykalna (1 godz.):
    • pojęcie leksemu;
    • podział tekstu programu na leksemy za pomocą automatu skończonego;
    • komputerowa realizacja analizatora leksykalnego czyli skanera.
  4. Analiza składniowa (2 godz.):
    • analiza składniowa, czyli budowa drzewa rozbioru;
    • zstępująca analiza rekursywna;
    • wstępująca analiza z pierwszeństwem;
    • komputerowa realizacja analizatora składni czyli parsera.
  5. Programowanie w kodzie wewnętrznym maszyny (1 godz.).
  6. Analiza semantyczna i generacja kodu (2 godz.):
    • kontekstowe cechy języków programowania;
    • gospodarka pamięcią;
    • kompilacja programów z języka wysokiego poziomu na język abstrakcyjnej maszyny stosowej;
    • kompilacja programów z języka abstrakcyjnej maszyny stosowej na kod wewnętrzny.
  7. Narzędzia programistyczne do produkcji kompilatorów (2 godz.):
    • LEX (FLEX) do analizy leksykalnej;
    • YACC (BISON) do analizy składniowej.
  8. Powtórka (1 godz.).

Program laboratorium

(kolor czarny: zajęcia przy tablicy;
kolor niebieski: zajęcia przy komputerze)
  1. Wyprowadzanie słów i konstruowanie drzew wywodu w różnych rodzajach gramatyk (regularnych i bezkontekstowych).
  2. Konstruowanie możliwie prostych gramatyk regularnych i bezkontekstowych do zadanych języków.
  3. Badanie, czy dane dwie gramatyki definiują ten sam język.
  4. Ręczna symulacja działania zadanych automatów skończonych i automatów ze stosem.
  5. Konstruowanie automatów skończonych i automatów ze stosem do zadanych problemów i języków.
  6. Działania z wyrażeniami regularnymi.
  7. Komputerowa realizacja programów ze stosem (np. obliczanie wartości wyrażeń arytmetycznych).
  8. Programowanie prostego wstępującego analizatora składni.
  9. Programowanie w języku przypominającym wewnętrzny (na dostarczonym symulatorze).
  10. Tłumaczenie prostych programów z języka wysokiego poziomu na język maszyny stosowej.
  11. Interpretacja programów maszyny stosowej.
  12. Użycie programu FLEX do analizy leksykalnej.
  13. Użycie programu Bison do analizy składniowej.

Literatura podstawowa

[1] Foryś M., Foryś W., Roman A.   Języki, automaty i obliczenia.   Uniwersytet Warszawski, 2007. Witryna internetowa.

[2] Waite W.M., Goos G.   Konstrukcja kompilatorów..   Wydawnictwa Naukowo-Techniczne, 1989. Jest w Bibliotece ANS Elbląg.

[3] Aho A.V., Lam M.S., Sethi R., Ullman J.D.   Kompilatory.   PWN, 2019. Tu dostepny jest oryginał angielski.

Literatura uzupełniająca

[4] Levine J.   Flex and Bison. Text Processing Tools.   O’Reilly Media, 2009 Witryna internetowa zawierająca Rozdział 1 książki.


Do slajdów
Do mojej głównej witrynki

Ostatnia modyfikacja: 22 lutego 2025