MathTextOntology-pasek

 

 

     W tym wpisie opiszę na prostym przykładzie ;-) w jaki sposób wygenerować własny parser za pomocą antlr. Po zainstalowaniu i skonfigurowaniu zgodnie z instrukcją na stronie ( różne tam systemowe aliasy żeby wszystko się uruchamiało ze ścieżek bezszmerowo), uzyskujmy trzy elementy w systemie: zainstalowany program antlr o którym za chwilę napiszę więcej, program grun – a właściwie spreparowany alias systemowy pewnego złożonego polecenia pozwalający na uruchamianie kodu generowanego przez antlr ( o czym za chwilę) oraz oczywiście zainstalowaliśmy stosowną wersję java, jak napisano w instrukcji instalacji. Jak ktoś chce wykonać własnoręcznie to co opisałem poniżej, musi mieć zainstalowane wszystkie trzy komponenty. Nie będę opisywał tych szczegółów bo są dobrze ujęte na stronie antlr, a ponadto dla prostej nauki można użyć AntlrWorks który nie wymaga żadnych szczególnych konfiguracji i dostarcza „wszystko w jednym” i to dla rozmaitych systemów operacyjnych, a na dodatek obok tego co opisałem poniżej, sprawdza poprawności, koloruje i wyświetla diagramy składniowe dla podanej gramatyki.

    Przejdźmy do samego antlr. Wpis omawia antlr w wersji 4, czyli antlr4. W stosunku do antlr3 są spore różnice, in plus, więc kwestie antlr3 zostawmy na boku, zaznaczając tylko, że jak ktoś czyta gdziekolwiek artykuł o antlr powinien zadać sobie jako pierwsze pytanie o jakiej wersji mowa bo różnice sa spore.

    Antlr jest narzędziem które na wejściu przyjmuje definicję gramatyki języka i na jej podstawie generuje kod programu który potrafi ten język analizować. Nie będę wnikał tu zbyt głęboko w temat, ale właściwie mamy tu do czynienia z definicją gramatyki w postaci BNF zapisaną w specyficzny dla antlr sposób. Pominę także detale związane z poprawnością gramatyki i ograniczeniami jakie niesie antlr – szczegóły sa do odnalezienia w dokumentacji – antlr pozwala na gramatyki wprost lewo rekurencyjne – jak w przykłądzie poniżej, ale nie pozwala na gramatyki niejawnie lewo rekurencyjne ( generacja kodu kończy sie błędem).
Jako przykład niech posłuży nam gramatyka wyrażeń numerycznych obejmujących liczby naturalne oraz ich dodawanie, odejmowanie, mnożenie i dzielenie, oraz nawiasy. Definicja takiej gramatyki ma postać pliku .g4 który wygląda następująco ( numery na początku wierszy nie są częścią pliku):

———————-Expr.g4—————–
(1) grammar Expr;
(2) progr: (expr NEWLINE)*
(3) ;
(4) expr: expr (‚*’|’/’) expr
(5)          | expr (‚+’|’-‚) expr
(6)          | INT
(7)          | ‚(‚ expr ‚)’
(8)          | expr NEWLINE
(9) ;
(10) NEWLINE : [\n]+ ;
(11) INT : [0-9]+ ;
—————————————

    Opiszmy jaki jest cel użycia takiej gramatyki i co z nią potrafi zrobić antlr, a przy okazji wyjaśnimy znaczenie poszczególnych linii pliku. Gramatyka pokazana powyżej nazywa sie Expr, co definiuje linia (1) pliku. Opisuje ona reguły interpretacji pewnego rodzaju tekstu – czyli zespołów znaków tekstowych. Wyrażenia te, jeśli są prawidłowo zbudowane, powinny dać sie zinterpretować w kontekście tej gramatyki, dla siebie powiedzielibyśmy że jako wyrażenia arytmetyczne, a dla programu – jako zgodne z gramatyką ciągi znaków. Wyrażenie takie to progr który jest pewną liczbą wyrażeń expr zakończonych znakami NEWLINE ( linie (2)-(3) pliku). Wyrażenie expr zdefiniowane w liniach (4)-(9) składa sie z wyrażeń typu expr NEWLINE – ( mamy tu jawnie lewą rekurencję)   lub   „nawias” expr „nawias” lub INT lub expr  ( „+” lub „-„ ) expr itp. Kreski pionowe na początku linii (5) i następnych oznaczają alternatywy. Na końcu w liniach (10) i (11) zdefiniowano co znaczy NEWLINE i INT w składni przypominającej wyrażenia regularne. Przykłady bardziej – niekiedy znacznie bardziej – złożonych gramatyk można znaleźć na tej stronie. Polecam zwłaszcza zerknięcie na gramatykę jakiegoś języka programowania jak choćby java czy python, oraz gramatykę opisująca plik csv.

    Program komputerowy analizujący wyrażenie zgodne z powyższą gramatyką, na przykład „(5*(3+4) -12)/(2+3*(6-3))”, powinien prawidłowo rozpoznać elementy wyrażenia, takie jak „(3+4)”, określić ich „znaczenie” i poprawność. Nazwijmy taki program analizatorem. Proces tworzenia analizatora który będzie dokonywał interpretacji takich wyrażeń ma wiele uniwersalnych cech, niezależnych od szczegółów gramatyki zdefiniowanej powyżej. Elementy te powtarzają się zarówno przy budowie analizatorów dla wyrażeń jak „(3+4)” jak i w przypadku analizatorów języka naturalnego, języka SQL, analizatorów sprawdzających konstrukcje języka C++ lub pliki xml. Twórcy antlr stworzyli narzędzie które w oparciu o definicję gramatyki, buduje szkielet programu, w jednym z kilku dostępnych języków, który programista może zmodyfikować dostosowując je w trakcie pracy do własnych potrzeb. Antlr jest zatem programem który generuje programy ( a raczej programem który generuje źródła innych programów). Tego rodzaj programów nazywa sie generatorami kodu, a w tym konkretnie przypadku mamy do czynienia z programem generującym analizatory ( sa oczywiście inne generatory, programy mogą generować szkielety stron www, szkielety GUI, szkielety baz danych i inne. Właściwie każdy IDE który posiada pewnego rodzaju wbudowaną „automatyzację” tworzenia kodu – na przykład dopisuje szkielety klas języka itp. jest tego rodzaju generatorem. Całkiem spora część kodu jest tym samym generowana). Program wygenerowany przez antlr ( domyślnie w java), nasz analizator, składa sie z dwu podstawowych elementów logicznych. Pierwszy z nich nazywa się lekserem. Lekser to program który dzięki wbudowanej gramatyce, takiej jak ta powyżej, jest w stanie prawidłowo rozpoznać elementy języka, zwane tokenami. Tokeny w naszym przykładzie to: złożone wyrażenia progr i expr, symbole operacji logicznych „+,-,*,/”, wyrażenie INT – reprezentowane w prostym tutaj przykładzie jako dowolnej długości ciąg znaków 0,1,2…9 = [0-9]+, oraz wyrażenie NEWLINE, obejmujące znaki nowej linii [\n]+ w dowolnej ilości. Lekser przegląda zatem strumień znaków jaki program analizuje i wykrzykuje z radością – „o! expr! „, „o! progr!”, „o! nawias!”.

     Lekser rozpoznaje ciągi znaków i przekazuje je do kolejnego elementu analizatora – parsera. Parser otrzymuje od leksera, z powodów nazwijmy to technicznych, numer pozycji w wyrażeniu gdzie zaczyna i kończy się dany element języka. Wtedy parser sprawdza czy spełnione sa reguły gramatyki. Prosta gramatyka jaką tu omawiam, nie ma zbyt wielu skomplikowanych aspektów, ale jednym z śladów złożoności z jaką musi poradzić sobie parser jest kwestia poprawnego otwarcia i domknięcia nawiasów. Parser zatem dokona sprawdzenia czy zgodnie z regułami gramatyki zapisanymi w linii o numerze (7) każdy nawias który został otwarty został także prawidłowo zamknięty, czy każdy operator „+” zawiera dwa wyrażenia expr z swojej prawej i lewej strony itp. Parser mówi „nawias mówisz? a gdzie drugi?”.

    Podsumujmy – lekser rozpoznaje, parser sprawdza.

    Jak używać antlr? Zapisujemy definicje gramatyki w pliku o nazwie zgodnej z nazwą gramatyki – w naszym przypadku będzie to plik Expr.g4. Najlepiej całą operację przeprowadzić w stworzonym uprzednio katalogu, gdyż antrl wygeneruje kilka plików z kodem i katalog zapełni się plikami. Następnie generujemy pareser/lexer poleceniem
>antlr4 Expr.g4

Wykonanie tego polecania powoduje że w katalogu w którym je wykonaliśmy pojawi się sporo plików z kodem java.
Kompilujemy owe kody ( w katalogu gdzie to wszystko jest):
>javac *.java

    I już. Powstał nam prosty parser, który potrafi rozpoznać i sprawdzić poprawność wyrażeń arytmetycznych na liczbach naturalnych. Oczywiście od takiej prostej generacji do użytecznych działań daleka droga, ewentualny rozwój aplikacji ( prostego kalkulatora ?) wymagałby od nas grzebania po kodzie jaki wygenerował antlr i dostosowywania tego kodu do naszych potrzeb. W szczególności musielibyśmy napisać kod który zinterpretuje wyrażenia które rozpoznał lekser i sprawdził parser ( ale jeśli ktoś poda nam złe wyrażenie, np. nie domknie nawiasu – obsługę błędów już mamy!). Interpretacja oznacza w ostatnim zdaniu przejście od tego, że program rozumie iż (3+4) to prawidłowe wyrażenie w którym 3 i 4 to elementy INT, + to operator „+” zaś „(” i „)” to nawiasy, do użycia w miejsce + operatora dodawania zaś w miejsce 3 i 4 liczb integer. Antlr bowiem parsuje, czyli przetwarza, pliki tekstowe, i wszystko co sprawdza to znaki w takich plikach, po prostu napisy.

    Sprawdźmy jak to działa. stworzyłem plik tekstowy example.txt o następującej zawartości:

———–example.txt—————–
((2+7*(13-10/7)/8)*12 -3*(5+7))/5
((2+7*(13-10/7)/8)/12 -3*(5+7))/6
———————————————

i za pomocą polecenia:
>grun Expr prog -gui example.txt

wygenerowałem następujący obrazek:

antlr4_parse_tree

    Jak widać w ostatnim poleceniu wskazałem jawnie że wierzchołek parsowania ma postać dyrektywy progr z gramatyki ( jak się wskaże co innego drzewo wygląda inaczej – i jest błędne dla podanego przykładu – co jak rozumiem oznacza, że przykład nie spełnia założenia, czyli że jest czym innym niż elementem, progr. ), czego kod wygenerowany z antlr sam nie rozpozna.

    Antlr generuje kod w java który zawiera lekser i parser. Programy te nie tylko wykonują to co opisaliśmy powyżej – to rola leksera i parsera – ale także reprezentują dostarczony strumień znaków w postaci drzewa jakie widzimy ma obrazku powyżej – jest to tak zwane drzewo parsowania. W drzewie tym, reguły złożone gramatyki, takie jak progr i expr reprezentowane są jako korzenie drzewa, zaś tokeny proste, jak NEWLINE, INT i nawiasy – są liśćmi. Obok leksera i parsera antlr generuje także kod walkera i listenera. Walker potrafi przeglądać drzewo – od lewej do prawej, i generować zdarzenia których oczekuje lekser i potrafi je zinterpretować. Na przykład walker trafiając na wyrażenie „3+4” wygeneruje zdarzenia „wchodzę w wyrażenie „+”, końcowy liść – „3”, końcowy liść „4”, wychodzę z wyrażenia”. Listener może zinterpretować te sygnały i wykonać operację arytmetyczną na koniec wypisując „wynik: 7”, ale może także zamienić nasze wyrażenie do postaci: „wyrażenie to: trzy plus cztery”. Oba te zachowania, i wiele innych, są możliwe, relatywnie łatwe do wykonania, wymagają jednak modyfikacji kodu czego nie będę tu pokazywał – odsyłam do strony antlr. Warto wszakże zwrócić uwagę, że choć z ludzkiego punktu widzenia pierwszy rodzaj działania to wyliczanie, czyli ewaluacja, a drugi to „tłumaczenie na język pisany”, to w sensie koncepcyjnym nie ma tu właściwie żadnej różnicy – zamieniamy symbole jednego rodzaju na symbole innego rodzaju. W taki sam sposób właściwie działa kompilator, translator i interpreter i koloryzator składni.  Antlr jest używany także przy analizie składni zapytań w wyszukiwarkach np. Twitter.

 

Jeśli słomiany zapał mi nie opadnie – wpis będzie miał kontynuację..