Jak zbudować składnię języka programowania: Analiza gramatyki i praktyczne przykłady

Gramatyka formalna jest podstawą wielu języków programowania, w tym także tych starszych, jak na przykład Tiny BASIC. W kontekście programowania często spotykamy się z pojęciem produkcji, które są regułami określającymi sposób rozkładu struktury składniowej języka. Gramatyka w notacji Backusa-Naur (BNF) jest jednym z popularniejszych sposobów opisywania składni języków, a w tym rozdziale przyjrzymy się, jak tworzyć i analizować takie gramatyki na konkretnych przykładach.

Rozpocznijmy od prostej analizy składniowej języka, który przyjmuje pewne terminale i definiuje je za pomocą reguł produkcji. Na przykład, za pomocą kilku prostych reguł można opisać zbiór dopuszczalnych znaków:

go
Copy code
to be: ::= * ::= 'A' | 'B' | '1' | '2'

Taki zapis pozwala na wprowadzenie elementów, które mogą występować w różnych kombinacjach, tworząc bardziej złożone wyrażenia. Możemy jeszcze uprościć tę definicję, eliminując drugą regułę produkcji i zapisując ją w prostszej formie:

css
Copy code
to be: ::= ('A' | 'B' | '1' | '2')*

Choć eliminacja zbędnych reguł produkcji jest często praktyką zalecaną, w przypadku bardziej złożonych gramatyk istnieje sens wprowadzenia dodatkowych symboli, które reprezentują długie listy terminali. Jeśli taki symbol pojawi się w kilku miejscach w gramatyce, unikniemy powtarzania długich ciągów terminali, co uprości strukturę. Przykład jest podobny do praktyki w programowaniu, gdzie stosowanie wielu małych funkcji, które się powtarzają, jest bardziej eleganckie niż tworzenie pojedynczej, dużej funkcji.

Rozważmy teraz bardziej zaawansowany przykład: składnię listy numerowanej. W tej gramatyce musimy wziąć pod uwagę różne elementy, takie jak numery, kropki, teksty oraz znaki nowej linii:

go
Copy code
list ::= *

item ::= '.' '\n'
number ::= '0' | '1' | ... | '9'
text ::= .*

Warto zauważyć, że w gramatyce pojawiają się symbole specjalne, takie jak „...” i „.”. Symbol „...” oznacza, że lista terminali jest kontynuowana w sposób domyślny, a „.” wskazuje na dowolny terminal, jak w wyrażeniach regularnych.

Przekształcając te reguły na bardziej zrozumiałą formę w języku angielskim, możemy stwierdzić, że:

1. Lista składa się z zero lub więcej elementów.

2. Element to liczba, kropka, tekst i znak nowej linii.

3. Liczba to jedna lub więcej cyfr.

4. Cyfra to jeden z znaków od 0 do 9.

5. Tekst to dowolny ciąg znaków.

Jednakże zauważamy jeden istotny problem: liczba z wiodącymi zerami, na przykład 0020, jest dopuszczona, a to może być niepożądane w kontekście numerowanej listy. Takie sytuacje wymagają rozwiązania, aby gramatyka była bardziej sensowna w kontekście rzeczywistego zastosowania.

Powyższe przykłady odnoszą się do tzw. gramatyki bezkontekstowej. Oznacza to, że każda reguła produkcji jest niezależna od kontekstu, w jakim pojawia się dany nieterminalny symbol. Każda produkcja może być rozwinięta w sposób samodzielny, bez potrzeby uwzględniania innych symboli wokół. Gramatyka bezkontekstowa jest w tym sensie „czysta” i dość uniwersalna, co sprawia, że jest łatwa do zastosowania w różnych kontekstach.

go
Copy code
❶  ::= '\n' | 'REM' .* '\n'
❷  ::= 'PRINT' | 'IF' 'THEN' | 'GOTO' | 'LET' '=' | 'GOSUB' | 'RETURN'
❸  ::= ( | ) (',' ( | <expression>))*
❹  ::= ('+' | '-')*
❺  ::= ('*' | '/')*
❻  ::= ('-' | ε) | | | '('')'
digit ::= '0' | '1' | ... | '9'

letter ::= 'a' | 'b' | ... | 'z' | 'A' | 'B' | ... | 'Z'

Jednym z nowych elementów w pełnej gramatyce NanoBASIC jest symbol epsilon (ε), który oznacza „nic” lub „pustkę”. Pojawia się w kontekście alternatyw, sugerując, że w danym miejscu może występować coś, ale równie dobrze może tego nie być. NanoBASIC, mimo że bardziej rozbudowany niż wcześniejsze przykłady, nadal jest stosunkowo prosty do zrozumienia.

Na przykład, reguły produkcji w języku NanoBASIC mogą wyglądać następująco:

1. Linia może składać się z numeru linii i instrukcji lub komentarza.

2. Instrukcja jest jednym z kilku typów (PRINT, IF, GOTO, LET, GOSUB, RETURN).

3. Lista wyrażeń to lista rozdzielona przecinkami ciągów lub wyrażeń.

4. Wyrażenie może obejmować operacje arytmetyczne, takie jak dodawanie lub odejmowanie.

5. Wyrażenie składa się z terminów, które obejmują mnożenie i dzielenie.

Dzięki takiej gramatyce możemy teraz przejść do implementacji interpreterów języków programowania. W przypadku NanoBASIC, jak w każdym interpreterze, mamy do czynienia z trzema głównymi komponentami: tokenizatorem (lexer), parserem i właściwym wykonaniem kodu. Tokenizator dzieli kod źródłowy na najmniejsze jednostki rozpoznawane przez interpreter, parser analizuje te jednostki i tworzy tzw. drzewo składniowe, które reprezentuje hierarchię operacji w kodzie. To drzewo jest następnie wykorzystywane do obliczeń w trakcie wykonywania programu.

Warto pamiętać, że sama składnia gramatyki nie nadaje sensu poszczególnym elementom języka. To rola interpretera, który nadaje znaczenie poszczególnym wyrażeniom, instrukcjom i wartościom. Gramatyka jest zatem tylko fundamentem do zbudowania funkcjonalnego języka programowania.

Jak generować sztukę przypominającą dzieła ludzkie za pomocą algorytmu?

Program opracowany w tym rozdziale bazuje na prostym, lecz potężnym algorytmie mającym na celu stworzenie abstrakcyjnego obrazu na podstawie fotografii. Cały proces polega na stopniowym nakładaniu losowo dobranych kształtów na pustą płaszczyznę, a następnie ocenie, jak bardzo dany kształt przybliża wygląd obrazu do oryginału. Z każdą iteracją wybieramy kształty, które najbardziej pasują do fotografii, co w rezultacie prowadzi do powstania swego rodzaju impresjonistycznego dzieła sztuki.

Wszystko opiera się na tym, jak "podobny" jest obraz do oryginału. Aby ocenić to podobieństwo, algorytm stosuje różne metody wyboru kolorów kształtów: od losowego do bardziej zaawansowanego podejścia, jak metoda "najczęstszego koloru", co ma na celu uzyskanie wyraźniejszych, mniej zblendowanych kolorów w poszczególnych kształtach. Na przykład, w przypadku obrazu przedstawiającego balon na gorące powietrze, wykorzystanie elips w jego odwzorowaniu może nadać obrazowi wygląd przypominający witraż, co daje bardzo ciekawe efekty wizualne.

Metodą, która została zastosowana w przypadku balonu na gorące powietrze, jest użycie 540 elips, które rozmieszczono na obrazie w 100,000 iteracjach przez 104 sekundy na laptopie. Dla porównania, ten sam obraz, wykonany za pomocą 307 trójkątów, nie wyglądał równie atrakcyjnie, ponieważ kształty te nie pasowały do zakrzywionych linii balonu. Jednak trójkąty sprawdzają się o wiele lepiej w przypadku innych obrazów, jak np. wizerunków motyli, gdzie wykorzystanie 573 trójkątów przez 1 milion iteracji dało świetny efekt.

Jeśli chodzi o obrazki bardziej szczegółowe, jak np. portrety ludzi, tu pojawia się wyzwanie. Dla takiej fotografii, użycie większej liczby prostych kształtów może sprawić, że obraz stanie się zbyt abstrakcyjny, by rozpoznać postacie. Z drugiej strony, zbyt duża liczba szczegółów prowadzi do zbliżenia się do dosłownej kopii oryginału, co z kolei pozbawia obraz artystycznego charakteru. Balans między abstrakcją a rozpoznawalnością jest trudny do uzyskania, zwłaszcza w przypadku portretów ludzi.

Jednak dla portretów program doskonale sprawdza się, gdy używa się linii, które ze względu na swoją cienkość pozwalają na wygenerowanie większej liczby szczegółów. Przykładem może być obraz przedstawiający prezydenta Johna F. Kennedy'ego podczas jego słynnego przemówienia w Berlinie. Został on odwzorowany za pomocą 16,633 linii w 10 milionach iteracji, co zajęło 6,957 sekund na laptopie. Ciekawym aspektem tego obrazu jest to, że wynikowy obraz ma wyższą rozdzielczość niż oryginał, co jest możliwe dzięki zastosowaniu grafiki wektorowej, gdzie matematyka decyduje o ostatecznym wyglądzie obrazu, a nie same piksele.

Istnieje również wiele innych czynników, które wpływają na wynik końcowy. Używanie większej liczby kształtów oraz przeprowadzanie większej liczby iteracji może znacząco poprawić jakość finalnego dzieła. Warto jednak pamiętać, że algorytm opiera się na procesie stochastycznym, co oznacza, że wyniki mogą się różnić nawet przy tych samych ustawieniach i dla tej samej fotografii. W związku z tym, choć algorytm może stworzyć dzieło, które wygląda bardzo dobrze, to zawsze trzeba pamiętać o zmienności wyników, która jest cechą tego typu technologii.

Program stworzony do generowania takich "impressji" jest bardzo konfigurowalny. Wybór różnych parametrów, jak np. liczba iteracji, kształt używanych elementów, czy metoda doboru kolorów, pozwala na tworzenie różnorodnych artystycznych efektów. Do dyspozycji są różne opcje, jak np. możliwość generowania grafiki wektorowej lub animowania procesu tworzenia obrazu w postaci GIF-a. Dzięki temu użytkownicy mogą eksperymentować z ustawieniami, aby stworzyć swoje własne, unikalne wersje obrazów.

Ważne jest, aby pamiętać, że proces ten ma swoje ograniczenia. Im bardziej szczegółowy obraz, tym dłużej trwa jego generowanie. Dla przykładu, obraz z wizerunkiem JFK zajął prawie dwie godziny na moim laptopie, co może się różnić w zależności od specyfikacji komputera. Jednak nawet mimo długiego czasu generowania, efekty końcowe mogą być naprawdę spektakularne, oferując zupełnie nową perspektywę na klasyczne fotografie i obrazy.

Jak tworzymy obraz impresjonistyczny przy użyciu algorytmów?

W procesie tworzenia obrazu impresjonistycznego opisanego w algorytmie, kluczową rolę odgrywa zestaw parametrów, które są precyzyjnie zdefiniowane na początku programu. Najpierw musimy zaimportować podstawowe biblioteki, takie jak PIL, które pozwalają na manipulację obrazami, oraz niezbędne klasy i funkcje pomocnicze, umożliwiające stworzenie odpowiednich struktur danych. Kluczowym celem jest generowanie obrazu, który przypomina styl impresjonistyczny poprzez wykorzystanie podstawowych kształtów geometrycznych, takich jak elipsy, trójkąty czy linie, i nadanie im odpowiednich kolorów na podstawie analizy wejściowego obrazu.

Algorytm rozpoczyna się od zdefiniowania kilku typów, które określają sposób pracy z danymi wejściowymi. Zmienna ColorMethod pozwala określić metodę wyboru koloru dla rysowanych kształtów, a ShapeType ustala, jakie kształty będą używane do tworzenia obrazu. Choć na razie program rysuje tylko jeden rodzaj kształtu w każdej iteracji, możliwe jest rozbudowanie go o możliwość tworzenia obrazów z różnymi typami figur w jednej próbie.

Dzięki tym podstawowym definicjom program będzie mógł kontrolować różne aspekty tworzonego dzieła. Na przykład, zmienna MAX_HEIGHT ogranicza wysokość przetwarzanego obrazu do 256 pikseli, co pozwala zoptymalizować czas obliczeń, szczególnie w przypadku bardzo dużych plików. Pomimo iż teoretycznie moglibyśmy również określić maksymalną szerokość, w praktyce obrazy, które są wyjątkowo szerokie, rzadko mają taką proporcję, aby sama wysokość wystarczała do ich zredukowania.

Główna funkcjonalność algorytmu opiera się na metodzie get_most_common_color(), która analizuje obraz i wybiera najczęściej występujący kolor. Wykorzystuje ona metodę getcolors() z biblioteki Pillow, która zwraca wszystkie kolory występujące w obrazie oraz ich liczność. Funkcja ta za pomocą wbudowanej funkcji max() wybiera najczęstszy kolor, który później zostanie przypisany do odpowiednich kształtów na obrazie.

Kiedy obraz jest już przygotowany, następuje jego przeskalowanie, aby jego wysokość nie przekraczała określonego limitu, co przyspiesza proces dalszej analizy. W celu zachowania proporcji obrazu, jego szerokość jest skalowana odpowiednio do wysokości. Kolejnym etapem jest obliczenie średniego koloru obrazu, który posłuży jako tło nowo generowanego obrazu. Technologia Pillow pozwala na łatwe uzyskanie tej średniej wartości poprzez klasę ImageStat, która przetwarza dane RGB wszystkich pikseli i zwraca ich średnią wartość.

Następnie tworzony jest obraz o średnim kolorze, który stanie się tłem dla dalszej pracy algorytmu. Na tym etapie również tworzymy zmienne do śledzenia postępu procesu, jak np. zmienną best_difference, która przechowuje najlepszy wynik uzyskany do tej pory. Dzięki temu będziemy w stanie śledzić postęp generowania obrazu i jego stopniową poprawę w porównaniu z oryginałem.

Po przygotowaniu niezbędnych elementów, algorytm przechodzi do kluczowego etapu, czyli iteracji, podczas której generowane są kształty. Funkcja trial() sprawdza, czy wstawienie nowego kształtu poprawia wynik algorytmu, który jest oceniany na podstawie podobieństwa do oryginalnego obrazu. Cały proces generowania kształtów jest powtarzany określoną liczbę razy, a każde kolejne wstawienie kształtu zmienia wynikowy obraz, zmierzony przy pomocy funkcji difference(), która ocenia, jak bardzo obecny obraz różni się od oryginału.

Funkcja difference() wykorzystuje moduł ImageChops z biblioteki Pillow, który umożliwia obliczenie różnicy między dwoma obrazami na poziomie poszczególnych pikseli. Każda różnica jest obliczana w trzech kanałach RGB, a następnie średnia różnica dla całego obrazu jest normalizowana do wartości od 0 do 1, gdzie 0 oznacza pełną zgodność, a 1 – maksymalną różnicę. Celem algorytmu jest minimalizacja tej różnicy, co skutkuje uzyskaniem obrazu jak najbardziej podobnego do oryginału.

Na końcu algorytmu generowany obraz jest zapisywany na dysku za pomocą funkcji create_output(), która umożliwia zapisanie rezultatu w formie pliku graficznego. Ważnym aspektem procesu jest także czas trwania algorytmu, który może być monitorowany za pomocą funkcji mierzących czas wykonania, takich jak timer() z biblioteki timeit.

Ważnym aspektem, który warto zrozumieć, jest fakt, że algorytm ten nie ma na celu jedynie technicznego odtworzenia obrazu w stylu impresjonistycznym, ale raczej stworzenie pewnego rodzaju „wrażenia”, które jest zgodne z ideą impresjonizmu. Działa to na zasadzie wyodrębnienia podstawowych kształtów i kolorów, które w swojej prostocie i losowości tworzą iluzję obrazu, który mógłby zostać namalowany przez artystę impresjonistycznego. Dlatego też kluczową rolę odgrywa metoda wyboru koloru oraz kształtu, które odpowiadają za dynamikę całego procesu twórczego.

Jak działa algorytm KNN w klasyfikacji danych?

W naszym przypadku, każda jednostka danych to obiekt klasy, który reprezentuje przykład z konkretnego zbioru danych. Algorytm KNN wymaga, by dane te były przechowywane w odpowiedni sposób, umożliwiający łatwe porównanie z danymi nieznanymi. Przykładem takiej struktury może być klasa DataPoint, która przechowuje dane w postaci atrybutów takich jak waga, długość, szerokość czy inne cechy charakterystyczne.

Jednym z pierwszych kroków przy używaniu KNN jest załadowanie danych z plików CSV. W klasie KNN stosujemy metodę _read_csv(), która korzysta z wbudowanego modułu csv Pythona do załadowania zawartości pliku i zamiany każdej linii w obiekt typu DataPoint lub jego podklasy. Taka struktura pozwala na elastyczne ładowanie różnych zbiorów danych, co jest kluczowe przy rozwiązywaniu zróżnicowanych problemów klasyfikacyjnych.

Mimo że takie podejście jest efektywne w kontekście niewielkich zbiorów danych, to jednak dla dużych zbiorów może stać się nieoptymalne. Operacja sortowania ma złożoność O(n log n), gdzie n to liczba punktów danych w zbiorze. W przypadku ogromnych baz danych, taka operacja może stanowić istotne wąskie gardło w algorytmie. Istnieje wiele sposobów na poprawienie wydajności, takich jak zastosowanie bardziej zaawansowanych struktur danych do przechowywania punktów lub użycie technik przybliżonych wyszukiwań, które ograniczają przestrzeń poszukiwań do reprezentatywnych podzbiorów danych.

Kiedy już mamy wybrane k najbliższych punktów, czas na klasyfikację. W tym celu stosujemy technikę głosowania, polegającą na zliczeniu, jak często każda klasa występuje wśród sąsiadów, a następnie przypisaniu etykiety klasy, która pojawiła się najczęściej. Zastosowanie do tego wbudowanej w Pythonie klasy Counter pozwala na szybkie zliczenie częstotliwości poszczególnych klas i wybranie tej, która dominuje.

Po zaimplementowaniu algorytmu KNN, warto przejść do jego zastosowań w rzeczywistych problemach. Przykład zastosowania algorytmu KNN w klasyfikacji ryb na podstawie wymiarów przedstawiony w książce doskonale obrazuje, jak algorytm może działać w praktyce. Dane dotyczące wymiarów i wagi ryb są używane do trenowania modelu, który później jest w stanie przypisać odpowiednią klasę (gatunek ryby) do nieznanych próbek.

Zbiór danych w tym przykładzie pochodzi z badania Pekki Brofeldta z 1917 roku i zawiera informacje o rybach z jeziora w Finlandii. Zawiera on takie cechy jak waga, długość, wysokość oraz szerokość ryb, które mogą być użyte do ich klasyfikacji. Po załadowaniu tych danych, tworzymy podklasę Fish, która reprezentuje pojedynczą rybę i zawiera metodę distance(), obliczającą odległość między dwoma rybami na podstawie ich wymiarów.

Dodatkowo, warto zwrócić uwagę na to, że KNN nie wymaga zaawansowanego modelowania statystycznego czy skomplikowanych obliczeń, co sprawia, że jest idealnym algorytmem do zastosowań w przypadkach, gdzie liczy się szybkość implementacji i prostota. Dzięki temu, jest to świetny wybór do początkowych projektów związanych z klasyfikacją danych.