Przedmiot jest przeznaczony dla młodszych studentów, którzy opanowali
podstawy programowania w języku C i chcą zdobyć podstawowe wiadomości
na temat przetwarzania danych tekstowych za pomocą narzędzi znanych
z teorii języków formalnych: automatów, wyrażeń regularnych i gramatyk.
Przedmiot nie ma ambicji teoretycznych i skupia się na omówieniu
podstawowych narzędzi przydatnych w praktyce, a podstawy matematyczne
są ograniczone do niezbędnego minimum. Ukończenie przedmiotu gwarantuje
posiadanie umiejętności wystarczających do formalnego opisania prostego
języka programowania i zaprogramowania jego interpretera. Językami
wykładowymi są polski oraz C.
#### Program zajęć
1. Alfabet, słowo, język. Problem formalnego opisu języka. Języki
programowania. Analiza leksykalna i składniowa. Składnia konkretna
i abstrakcyjna. Parse, unparse i postać kanoniczna. Języki wyrażeń.
Operatory prefiksowe, postfiksowe, infiksowe i miksfiksowe.
Priorytety i kierunki łączności operatorów. Parsowanie wyrażeń
postfiksowych i infiksowych za pomocą stosu.
2. Deterministyczne automaty skończone. Wykorzystanie koncepcji
automatu do opisu różnych procesów w informatyce (diagramy stanów
protokołów itp.) Symulowanie automatu za pomocą programu.
Wykorzystanie automatu do wyszukiwania wzorca w tekście. Automaty
z wyjściem. Analizator leksykalny.
3. Wyrażenia regularne. Niedeterministyczne automaty z ε-przejściami.
Synteza automatu rozpoznającego język opisany przez wyrażenie
regularne. Wyszukiwanie w tekście według wyrażenia regularnego.
POSIX.2 RE. Wersje wyrażeń regularnych używane w Linuksie i Uniksie.
Programy grep, sed itp. Automatyczne generowanie analizatorów
leksykalnych, flex.
4. Gramatyki bezkontekstowe. Drzewa wyprowadzenia. Jednoznaczność
rozbioru składniowego. Notacje do opisu gramatyk (BNF, EBNF).
Opis języków wyrażeń za pomocą gramatyk — jednoznacznie gramatyki
uwzględniające priorytety i kierunki łączności operatorów. Praktyczne
aspekty opisu składni języków programowania. Gramatyki atrybutowe.
Abstrakcyjne drzewa rozbioru.
5. Parsowanie z góry na dół, parsery LL(k). Parsowanie za pomocą zbioru
funkcji rekurencyjnych. Usuwanie rekursji lewostronnej z gramatyki.
Wyprowadzanie parsera z gramatyki. Automatyczne generowanie
parserów. ANTLR3. Informacja o parserach kombinatorowych.
6. Parsowanie z dołu do góry, parsery LR(k). Parsowanie za pomocą
automatu ze stosem. GNU Bison.
7. Interpretacja abstrakcyjnych drzew rozbioru. Semantyka naturalna.
Budowanie interpreterów prostych języków programowania.
8. Przetwarzanie danych tekstowych w programach. Serializacja danych.
Przegląd języków, narzędzi i bibliotek do zapisu i odczytu danych
strukturalnych (XML, JSON, S-wyrażenia, INI itp.)
#### Literatura
1. A.V. Aho, R. Sethi, J.D. Ullman, _Kompilatory. Reguły, metody
i narzędzia_, WNT 2002.
2. J.E. Hopcroft, R. Motwani, J.D. Ullman, _Wprowadzenie do teorii
automatów, języków i obliczeń_, PWN 2012.
