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ż przeprowadzone:

Odbywanie zajęć: dni i godziny.
   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

Języki formalne:
alfabet, słowo, język, sposoby ich opisu.
Gramatyka bezkontekstowa:
definicja, generowanie języka przez gramatykę, przykłady.

przegląd
slajdy

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

Języki bezkontekstowe:
   notacja Backusa-Naura, drzewa wywodu.
   Gramatyki niejednoznaczne. Drzewo wywodu a struktura słowa.
   Pierwszeństwo operatorów.

przegląd
slajdy

Akceptory:
automat skończony.
maszyna stosowa.
Związki między gramatykami, językami, maszynami.

przegląd
slajdy

Notacja beznawiasowa Łukasiewicza.
   Przechodzenie drzew: infix, prefix, postfix
   obliczenia na stosie.
Działania na językach,
   równania językowe, przekształcenia gramatyk.
Rekursja lewostronna.

przegląd
slajdy

Schemat kompilatora.
Analiza leksykalna:
Proszę zapoznać się z programem w C realizującym analizę leksykalną języka z wykładu.

przegląd
slajdy

Metody analizy syntaktycznej.
Rekursywny parser zstępujący:
   pisanie parsera wg gramatyki,
   leczenie problemów.
   Proszę zapoznać się z trzema programami realizującymi parsing zstępujący omawianymi na wykładzie: dla gramatyki bez rekursji, dla gramatyki z rekursją nielewostronną oraz dla gramatyki z rekursją lewostronną.

przegląd
slajdy

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

Programowanie niskiego poziomu (język ,,wewnętrzny'').
   Proszę zapoznać się z programem symulujacym działanie języka wewnętrznego
   oraz z przykładowymi programami:
     trojmianem kwadratowym
     silnią
     wielomianem dowolnym
     potęgą.
   Wskazówki dotyczące uruchamiania programów w C na unixlabie znajdują się tutaj.

przegląd
slajdy

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

Program w języku wewnętrzym w realnym komputerze.
Organizacja pamięci dla danych (prostych, tablicowych, itp.).
Organizacja pamięci dla funkcji (parametry, zm. lokalne, rekursja).

przegląd
slajdy

Dwuetapowe generowanie kodu wewnętrznego:
przy tłumaczeniu wyrażeń,
przy tłumaczeniu instrukcji.

przegląd
slajdy

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ń
Interpretacja a kompilacja.
   Proszę zapoznać się z działaniem prościutkiego kompilatora w Bisonie.

przegląd
slajdy

Rzut oka na automatyczne generowanie skanerów: FLEX.
Współpraca Flexa z Bisonem.
   Proszę zapoznać się z przykładowymi danymi dla FLEXa — generatora analizatorow leksykalnych:
   FlexSam
   FlexBison

przegląd
slajdy

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

15	Wykład powtórkowy.	przeglad

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.