Czym jest AST i dlaczego parsery to coś więcej niż nudna teoria

Czym jest AST i dlaczego parsery to coś więcej niż nudna teoria

Studia informatyczne, jak wiele innych kierunków inżynierskich, składają się z dwóch typów przedmiotów do studiowania. Niektóre z nich to teoria której wykorzystania w praktyce nie potrafimy zrozumieć, a inne to coś, nad czym możemy spędzać setki godzin bo widzimy ich bezpośrednie przełożenie na naszą przyszłość. Niestety, z powodu braku dostatecznej wiedzy, te podziały o których mowa bardzo często nie mają nic wspólnego z rzeczywistością, a przedmioty z gatunku “przeżyć i zapomnieć” okazują się dostarczać wiedzy której braku możemy po prostu żałować. Na własnym przykładzie – człowieka który dość wcześnie postanowił skupić się na “robieniu apek” – widzę, że przedmioty oparte na tej nudnej z pozoru teorii są tymi, wobec których każdy świadomy programista / student informatyki po prostu nie może przejść obojętnie.

Przecież nigdy nie stworzę kolejnego języka programowania…

…myśli sobie student uczęszczający na zajęcia z kompilatorów, parserów czy struktur danych. Patrząc na samego siebie oraz na studentów których miałem okazję poznać widzę, że większość z nas w okresie studiów nakręca się dość naiwnym “dążeniem do praktyki”. Przez praktykę rozumiemy oczywiście tworzenie gier, aplikacji i wszelkiego typu projektów.

To dążenie do realizacji kolejnych projektów motywuje nas do poznawania sprawdzonych w boju języków programowania, popularnych biblioteki i frameworków. Jeśli chodzi o czas spędzony na poznawaniu podstaw… no tutaj bywa różnie. Mówimy o językach programowania wysokiego poziomu, kolejnych abstrakcjach wprowadzanych przez nowe biblioteki i innych tego typu ułatwieniach które mają być odpowiedzią na to, że wiedza o kompilatorach nikomu z nas nie przyda się w praktyce.

Niedawno przekonałem się jednak, że tylko dzięki teorii którą miałem okazję wstępnie poznać na studiach, a ostatnio świadomie pogłębiać, mogłem rozwiązać pewien konkretny problem związany z projektem który tworzę. Rozwiązanie to jest wyciągnie wprost ze świata kompilatorów, a pomogło mi w znaczący sposób poprawić jakość kodu który można teraz rozwijać o wiele szybciej (czyt. taniej).

Operacje na kodzie źródłowym

Projekt o którym mowa opisywałem niedawno w jednym z ostatnich postów – to create-angular-template, czyli narzędzie przyśpieszające proces migracji aplikacji opartych o framework AngularJS.

Najważniejszą funkcjonalnością tego narzędzia jest transformacja template’ów (tworzonych przy użyciu HTML) poszczególnych komponentów front-endowych w taki sposób, żeby składnia poszczególnych elementów (a konkretnie dyrektyw) była zgodna z nową składnią wprowadzoną w Angularze 2+. Spis podstawowych transformacji można znaleźć na oficjalnej stronie Angulara, ale w skrócie polega to na tym, że poszczególne atrybuty zmieniają nieco swoją formę (np. *ngIf zamiast ng-if, *ngFor zamiast ng-repeat, itd.). Koniec końców narzędzie wczytuje string (template), transformuje go i zwraca kolejny string (zawierający zaktualizowaną składnię).

Gdyby napisać test jednostkowy sprawdzający takie narzędzie, mógłby on wyglądać tak:

Test sprawdza czy pozbyliśmy się fragmentu “ng-repeat” na rzecz “*ngFor” – oczywiście to tylko przykład, jednak dość dobrze ilustruje podstawową funkcjonalność.

Naiwnym podejściem do takiego zadania – co zresztą zrobiłem na początku – była praca na surowych stringach. Poszczególne elementy zamieniałem przy użyciu wyrażeń regularnych, co do których miałem dodatkową satysfakcję – w końcu wykorzystam je w praktyce! Od jednego wyrażenia do drugiego, przez trzecie i czwarte – prace posuwały się do przodu.

Niestety, bardzo szybko okazało się, że wyrażenia regularne i HTML nie idą ze sobą w parze – podstawowe przykłady (i moja happy-path) sprawdzały się znakomicie, jednak praca na bardziej skomplikowanych stringach i wszystkie występujące tam wyjątki okazały się barierą nie do przeskoczenia. Tagi samo-zamykające się, apostrofy, cudzysłowy – wszystko to powodowało, że wymyślone przez mnie reguły wzbogacały się o kolejne wyjątki.

Postanowiłem więc sprawdzić, czy to moja wiedza dotycząca RegExpów kuleje, czy może z moim podejściem jest coś nie tak. Odpowiedź dał mi StackOverflow, a konkretnie to pytanie i odpowiedź do niego. Jeśli chcesz pozostać zdrowy na umyśle, to nie podchodź do HTMLa wyrażeniami regularnymi.

Użyj parsera.

Wracamy na studia?

Użycie parsera wydawało się być tym, co rozwiąże moje problemy związane z wyrażeniami regularnymi. Zamiast pracy na surowych stringach miałbym teraz do dyspozycji drzewo reprezentujące strukturę mojego kodu, na którego węzłach mogę wykonywać konkretne operacje. Wiedza ze studiów do wykorzystania w praktyce? Brzmi nieźle!

Będę z wami szczery – nie jest to pomysł który wpadł mi do głowy ot tak, ponieważ będąc front-endowcem w obszarze twoich zainteresowań może być chociażby Babel, który opiera dokładnie na takich samych podstawach. Ba, można założyć, że prawie każde rozsądne narzędzie modyfikujące twój kod będzie posługiwało się bardziej zaawansowanymi strukturami danych niż string.

Na początku warto wyjaśnić czym różni się podejście z wykorzystaniem parsera od podejścia polegającego na pracy na stringach.

Można powiedzieć, że w przypadku operacji na kodzie źródłowym, string zawiera zdecydowanie za mało informacji do realizacji poszczególnych zadań i transformacji. Tak naprawdę jedyne co o wiemy o danym stringu to jego długość i zawartość. Dzięki tym informacjom nie wiemy jednak czy aktualnie (w przypadku HTMLa) modyfikujemy atrybut, tag, albo wartość atrybutu. Nie wiemy w którym węźle jesteśmy, albo jakiego rodzaju tag aktualnie modyfikujemy. Nie wiemy czy tag posiada w sobie inne tagi, czy np. surowy tekst.

Co ciekawe, string w naszym przypadku zawiera też w pewnym sensie… za dużo informacji – informacje o tym, że atrybuty są otoczone średnikami lub apostrofami, a dany element zaczyna się na miejscu o indeksie 10 a dana linijka zaczyna się znakiem tabulacji to szum który przeszkadza w realizacji naszego głównego zadania – chcemy przekształcić atrybut z jednej postaci w drugą.

AST i życie staje się lepsze

Informacje w odpowiedniej formie otrzymamy dopiero po przeparsowaniu naszego kodu, w wyniku czego w nasze ręce wpadnie struktura zwana AST (abstract syntax tree).

AST to drzewiasta struktura danych która reprezentuję strukturę składni danego fragmentu kodu w sposób abstrakcyjny (umowny, niezwiązany z konkretnym językiem).

W przypadku kodu HTML, AST wygenerowany z poprzedniego fragmentu HTMLa może wyglądać w sposób następujący:

Zamiast stringa możemy się teraz posługiwać obiektem który reprezentuje strukturę naszego kodu. Czy nie wygląda to o klasę lepiej w porównaniu do wyrażeń regularnych które metodą prób i błędów próbuje skleić realizując dane zadanie?

Mając nasze nowo utworzone AST i chcąc się dowiedzieć jakie atrybuty zawiera poszczególny tag, wystarczy, że sprawdzimy zawartość tablicy ‘attrs’:

Wystarczy teraz, że nazwę “class” zamienimy np. na “poznajprogramowanie”, a po serializacji AST do stringa nasz tag będzie wyglądał następująco:

Tak – to takie proste!

W ramach poszerzenia tematu dodam, że inne przykłady drzew składniowych możecie zobaczyć w praktycznie każdym projekcie który dotyczy analizy bądź modyfikacji kodu źródłowego – tutaj np. SharpLab i C#:

Ogromną zaletą takiej struktury jak AST jest to, jak łatwo można się nią posługiwać – większość programistów potrafi przecież operować na obiektach lub drzewach. Pobieranie wartości i iterowanie po poszczególnych elementach nie wydaje się być czymś szczególnie trudnym w porównaniu do wyrażeń regularnych. Do tego uzyskujemy logiczną separację naszego kodu jako “wartości samej w sobie” w postaci stringa, od struktury na której wykonujemy operacje. Struktura ta jest przystosowana do modyfikacji poszczególnych elementów kodu, a do tego jej serializacja i deserializacja pozostaje z naszej perspektywy po stronie zewnętrznych bibliotek, które w tych operacjach się specjalizują. Warto też pamiętać o rozmaitych algorytmach dotyczących drzew, które mogą nam znacznie usprawnić niektóre operacje z nimi związane.

W projekcie create-angular-template podejście oparte o AST było – co teraz mogę już przyznać z całą pewnością – słusznym podejściem do problemu. Operacje na atrybutach to teraz operacje na faktycznych obiektach reprezentujących atrybuty, a zmiana klasy danego elementu to zmiana wartości atrybutu “class”, zamiast podmiany fragmentu stringa z użyciem wyrażenia regularnego. Taki sposób pracy z template’ami uporządkował kod mojego narzędzia oraz pozwolił rozbudowywać go bez wprowadzania niepotrzebnego bałaganu.

Dla wszystkich, którzy stoją przed podobnym wyzwaniem związanym z operacjami na HTMLu polecam Parse5 – http://inikulin.github.io/parse5/index.html. Jest to parser zgodny z HTML5, który w moim przypadku sprawdził się znakomicie. Do tego, jak czytamy na stronie dokumentacji, wykorzystywany jest w takich projektach jak js-doc, Polymer oraz Angular, co samo w sobie powinno mówić o jego jakości. Mając pod ręką takie narzędzia jak parser nie przyjdzie nam już do głowy praca na czystym stringu – jest to po prostu zbyt kosztowne oraz podatne na błędy.

Jak to jest z tą nudną teorią?

Zapewne zabrzmi to banalnie, ale pochopne ocenianie przedmiotów na które uczęszczamy jest bardzo często powodowane ignorancją. Wiemy o danej dziedzinie niewiele, ale nie przeszkadza nam to oceniać jej poszczególnych elementów. Kompilatory – nie, parsery – nie, struktury danych  – nie. Przecież chcę tworzyć aplikacje i tylko to mnie interesuje!

Problem z tym podejściem jest taki, że nieświadomie zamykamy sobie a) ścieżki rozwoju zanim ścieżka zawodowa w ogóle się zaczęła b) możliwe rozwiązania problemu, o którym jeszcze nawet nie wiemy, że może się pojawić! Właśnie dlatego nasze umiejętności – nawet pomimo określonej specjalizacji – powinniśmy rozwijać w szerokim zakresie. Być może przez 95% swojej programistycznej kariery nie będziesz wykorzystywał konkretnego algorytmu ani parserów, ale kiedy sytuacja będzie tego wymagać to znane ci narzędzia zadziałają jak koło ratunkowe. Nawet jeśli zdecydujesz na drogę “programisty tworzącego produkty” to kto powiedział, że grupą docelową projektu którzy tworzysz nie mogą być inni programiści?

Odnośnie uczenia się o strukturach danych to dodam jeszcze, że spostrzeżenia o których dzisiaj piszę pojawiły się u mnie w głowie w momencie, kiedy zacząłem bliżej poznawać mechanizmy stojące za takimi bibliotekami jak chociażby React czy narzędziami pokroju GITa. Praktyka pokazuje – niezależnie od tego czy się z tym zgodzisz czy nie – że odpowiednie wykorzystanie odpowiednich struktur danych i algorytmów to coś, co podbija twój “programistyczny exp” o kolejne kilka punktów. Na front-endzie, którym zajmuję się na codzień, to widoczne również w przypadku poruszania się po DOMie, który również jest drzewem z węzłami reprezentującymi poszczególne elementy danej strony czy aplikacji.

Jeśli do tej pory tematyka którą poruszam w tym poście wydawała się dla ciebie nudna lub mało atrakcyjna to zachęcam cię do poświęcenia jej kilku godzin i do spróbowania połączenia teorii z praktyką – wielu z was pozytywnie się zaskoczy a przy okazji dołoży bardzo wartościowy punkt do swojego pakietu umiejętności związanych z programowaniem. Powodzenia!

Powiązane

Studia informatyczne – 120% możliwości Poszedłeś na studia informatyczne, żeby nauczyć się programowania? Studia zazwyczaj przedstawialiśmy z trochę gorszej strony, mimo że ja oraz Przemek ...
O migracji do Angulara, czyli debiut w świecie ope... Niedawno pracując przy jednym z projektów które współtworzę natrafiłem na zadanie wymagające żmudnej, manualnej pracy powtarzanej w ten sam sposób...
Enhance your development workflow with npm link npm is the most popular package manager in JavaScript ecosystem. I'm sure that huge number of our readers may be familiar with this tool, because ...
Jak wykorzystać tryb offline do zwiększenia możliw... Niedawno pisaliśmy na naszym blogu o PWA, czyli nowej fali aplikacji webowych które sposobem działania przypominają to, co znamy z natywnych aplikacji...