Stefan Sokołowski
JĘZYKI FORMALNE I METODY KOMPILACJI

Slajdy do wykładu

W poniższej tabelce kliknięcie

na ,,przegląd'' daje dostęp do wersji drukowanej slajdów do wykładu (przydatne do szybkiego przeglądania);
na ,,slajdy'' wyświetla wykład z pseudoanimacją, tak jak jest prowadzony w sali wykładowej.

Slajdy są tematycznie podzielone na ,,wykłady'', co nie zawsze pokrywa się z podziałem na faktyczne godziny wykładowe.

Slajdy są tylko pomocą do wykładu i nie wystarczą do opanowania materiału przez osoby nieobecne na wykładzie. Na laboratorium będę zakładać, że student przychodzacy na te zajęcia był na wykładzie (i uważał), a następnie co najmniej przejrzał slajdy w domu.

Bardzo proszę o zgłaszanie mi

błędów w slajdach;
błędów w tym, co powiedziałem na wykładzie;
pomysłów, jak można było coś wyjaśnić prościej.

Za każdą dobrze wcelowaną krytykę wykładu przewidziane są punkty podwyższające stopień na zaliczenie wykładu.

Wykłady już odbyte:

0	Info o przedmiocie: źródła wiedzy, wymagania wstępne, zasady zaliczania, itp. Rzut oka na kompilator: co to jest i z czego się składa.	przegląd slajdy
1	Języki formalne: alfabet, słowo, język, sposoby ich opisu. Gramatyka bezkontekstowa: definicja, generowanie języka przez gramatykę, przykłady.	przegląd slajdy
2	Języki regularne: gramatyki prawostronnie liniowe, języki regularne i bezkontekstowe. Uproszczona hierarchia Chomsky'ego oraz nieformalne kryteria bezkontekstowości i regularności języka. Wyrażenia regularne: definiowanie języka przez wyrażenie regularne, informacja o zastosowaniu wyrażeń regularnych do wyszukiwania i zastępowania.	przegląd slajdy
3	Języki bezkontekstowe: notacja Backusa-Naura, drzewa wywodu. Gramatyki niejednoznaczne. Drzewo wywodu a struktura słowa. Pierwszeństwo operatorów.	przegląd slajdy
4	Akceptory: automat skończony. maszyna stosowa. Związki między gramatykami, językami, maszynami.	przegląd slajdy
5	Notacja beznawiasowa Łukasiewicza, Przechodzenie drzew: infix, prefix, postfix obliczenia na stosie. Działania na językach, równania językowe, przekształcenia gramatyk.	przegląd slajdy
6	Schemat kompilatora. Analiza leksykalna: Proszę zapoznać się z programem w C (lub z programem w Javie) realizującym analizę leksykalną języka z wykładu.	przegląd slajdy
7	Metody analizy syntaktycznej. Rekursywny parser zstępujący: pisanie parsera wg gramatyki, leczenie problemów. Proszę zapoznać się z programem realizującym zstępujący parsing rekursywny dla języka z wykładu.	przegląd slajdy
8	Rozbiór wstępujący: gramatyki z pierwszeństwem; konstrukcja tablic pierwszeństwa; poprawianie gramatyki na gramatykę z pierwszeństwem; użycie tablicy pierwszeństwa; wykonanie redukcji. Zalety i wady gramatyk z pierwszeństwem. Proszę zapoznać się z programem realizującym wstępujący parsing z pierwszeństwem dla języka z wykładu.	przegląd slajdy
9	Programowanie niskiego poziomu (język ,,wewnętrzny''). Proszę zapoznać się z programem symulujacym działanie języka wewnętrznego oraz z przykładowymi programami: dwumianem kwadratowym silnią wielomianem dowolnym potęgą Wskazówki dotyczące uruchamiania programów w C na unixlabie znajdują się tutaj.	przegląd slajdy
10	Duży program (z funkcją) w języku ,,wewnętrznym''. Podprogramy/funkcje. Proszę zapoznać się z przykładowymi programami w języku wewnętrznym: na dzielenie z resztą na potegę binarną.	przegląd slajdy
11	Organizacja pamięci.	przegląd slajdy
12	Dwuetapowe generowanie kodu wewnętrznego: przy tłumaczeniu wyrażeń, przy tłumaczeniu instrukcji.	przegląd slajdy
13	Gramatyki atrybutowe. Rzut oka na automatyczne generowanie translatorów: BISON. Proszę zapoznać się z przykładowymi danymi dla BISONa — generatora translatorów: aabbcc.y — sprawdzanie długości trzech części słowa typy.y — sprawdzanie typu komendy przypisania pjo.y — prosty język dla obliczeń	przegląd slajdy

Wykłady najbliższe (jeszcze mogą się zmienić):

14	Gramatyki atrybutowe. Działanie BISONa, c.d. Proszę zapoznać się z przykładowym BISON-owym kompilatorem prostego języczka: kompil.y — prosty kompilator Rzut oka na automatyczne generowanie skanerów: FLEX. Proszę zapoznać się z przykładowymi danymi dla FLEXa — generatora analizatorow leksykalnych: FlexSam FlexBison	przegląd slajdy

Zadania z laboratoriów

Uwaga:
Czasem na początku laboratoriów będą mieć miejsce niezapowiedziane krótkie sprawdziany wiedzy i umiejętności, oraz znajomości wykładów. Stanowią one najłatwiejszą formę zaliczenia — rozbójnik na koniec semestru jest trudniejszy. Proszę więc przygotowywać się na bieżąco, nie spóźniać się na zajęcia i być aktywnym.

Z podanych poniżej zadań niektóre rozwiązujemy razem na zajęciach. Zakładam, że tym niezrobionym stawiają Państwo czoła samodzielnie, w domu. Jeżeli to się z jakiś powodów nie udaje, to ten fakt należy koniecznie zgłosić na początku następnego laboratorium — zrobimy je wspólnie. Kto nie zgłosi trudności, o tym zakładam, że zadania rozwiązał i w przyszłości będzie umiał rozwiązać następne podobne.

Niektóre zadania oznaczone są jako

,,domowe na punkty'' — z ograniczonym czasem przysyłania, lub
,,domowe specjalne'' — na większe punkty, ważne do końca semestru, ale tylko dla pierwszej osoby, która przyśle poprawne rozwiązanie.

Laboratoria już odbyte:

0	treść zadań Rozgrzewka: prosta analiza tekstu programem
1	treść zadań Proszę zapoznać się z programem realizującym wywody słów w zadanej gramatyce.
2	treść zadań Gramatyki prawoliniowe; wyrażenia i języki regularne.
3	treść zadań Notacja Backusa-Naura; drzewa wywodu; pierwszeństwa operatorów.
4	treść zadań Automaty skończone i generowane przez nie języki.
5	treść zadań Maszyny stosowe; notacja prefiksowa i postfiksowa wyrażeń.
6	treść zadań Działania na językach. Analiza leksykalna. Proszę zapoznać się z programem dokonującym analizy leksykalnej dla gramatyki z wykładu 6.
7	treść zadań Parsing rekursywny zstępujący, na razie bez budowania drzew.
8	treść zadań Parsing rekursywny zstępujący z budowaniem drzew. Proszę zapoznać się z programem dokonującym parsingu dla gramatyki wyrażeń wg zasad omówionych w wykładzie 7. Parsing z pierwszeństwem.
9	treść zadań Parsing z pierwszeństwem, c.d. Programy w języku ,,wewnętrznym''.
10	treść zadań Programy w języku ,,wewnętrznym'' c.d.
11	treść zadań Organizacja pamięci.
12	treść zadań Maszyny stosowe.

Laboratoria najbliższe (jeszcze mogą się zmienić):

13	treść zadań Automatyczna interpretacja i kompilacja: BISON i FLEX

Do głównej witrynki przedmiotu
Do mojej głównej witrynki

Ostatnia modyfikacja: 18 stycznia 2025

Stefan Sokołowski JĘZYKI FORMALNE I METODY KOMPILACJI