Katalog przedmiotów

Języki formalne

Cele
Celem kształcenia jest przekazanie wiedzy teoretycznej dotyczącej języków formalnych – lingwistyki matematycznej oraz pokazanie praktycznych możliwości zastosowania zdobytej wiedzy podczas pisania różnego typu kompilatorów (klasycznych kompilatorów, parserów zapytań do bazy danych, filtrów i skanerów pakietów w sieci, generacja obiektów graficznych, L-systemy itp.). W trakcie wykładu omawiane są: języki regularne i automaty skończone- skaner (oraz ich minimalizacja), języki bezkontekstowe i automaty ze stosem-parser (gramatyki typu LL(K) i LR(K)), oraz gramatyki atrybutywne. Studenci poznają różne narzędzia programistyczne wspierające automatyczne parsowanie, w tym: Flex, Yacc etc. Poza tym, wprowadzone zostają: metody generacji kodów: pośredniego i docelowego, oraz metody ich optymalizacji (w tym ograniczenie liczby wykorzystywanych rejestrów).

Zakres
Ogólna budowa kompilatorów. Analiza leksykalna, automaty skończone, języki regularne. Minimalizacja automatów skończonych. Analiza syntaktyczna, automaty ze stosem, języki bezkontekstowe. Gramatyki LL(k), LR(k), Yacc, analiza sematyczna. Środowisko przetwarzania, przekazywanie parametrów do funkcji, stos programu, zarządzanie pamięcią. Generacja kodu, maszyny wirtualna i docelowa, optymalizacja kodu. Zagadnienia dodatkowe: kompilatory języków opisu sprzętu, L-systemy i generacja fraktali. Studenci realizują projekt prostego kompilatora języka podobnego do C, który generuje kod na daną maszynę wirtualną. Maszyna ta jest emulatorem uproszczonego procesora typu Intel 80/86.

Literatura podstawowa
1. J. Hopcroft, J. Ullman: Wprowadzenie do teorii automatów, językówi obliczeń, WNT.
2. A. Aho, R. Sethi, J. Ullman: Kompilatory, reguły, metody i narzędzia, WNT.

Literatura uzupełniająca
1. A. Appel: Modern compiler implementation in Java, Cambridge University Press.
2. K. Louden: Compiler Construction, PWS.

Punkty ECTS
2 - stacjonarne

Rodzaje studiów, na których przedmiot jest realizowany
stacjonarne - 2-go stopnia

Specjalności, na których przedmiot jest realizowany
Inteligencja komputerowa,
Inżynieria programowo - sprzętowa,
Teleinformatyka

Prowadzący
dr Piotr Sapiecha