Abstrakcyjne drzewa składniowe w programowaniu: kompletny przewodnik

Informatec Digital » Zasoby » Abstrakcyjne drzewa składniowe w programowaniu: kompletny przewodnik

Abstrakcyjne drzewa składniowe w programowaniu to jedna z tych koncepcji, które początkowo brzmią bardzo teoretycznie, ale gdy już się z nimi oswoisz, zdasz sobie sprawę, że są one wszechobecne: w kompilatorach, interpreterach , narzędziach do analizy kodu, narzędziach do refaktoryzacji, a nawet w językach zapytań do danych strukturalnych. Są one w zasadzie sposobem, w jaki maszyna „rozumie” strukturę programu wykraczającą poza zwykły tekst.

Choć czasami mylone z klasycznymi drzewami składniowymi, abstrakcyjne drzewa składniowe (AST) rządzą się swoimi własnymi zasadami. Abstrakcyjne drzewo składniowe to nie tylko ładny rysunek: to zwarta i dobrze zaprojektowana struktura danych, która eliminuje wszystko, co zbędne w konkretnej składni (nawiasy, przecinki, zbędne słowa kluczowe itp.) i koncentruje się na tym, co najważniejsze: jakie operacje są wykonywane, na jakich wartościach i w jakiej kolejności.

Czym właściwie jest abstrakcyjne drzewo składniowe (AST)?

W teorii języków programowania abstrakcyjne drzewo składniowe (AST) to struktura przypominająca drzewo, która reprezentuje składnię programu, ale w uproszczonej formie w porównaniu z konkretnym drzewem parsowania. Zawiera ono te same podstawowe informacje co drzewo parsowania, ale zorganizowane w bardziej zwarty i łatwy w zarządzaniu sposób.

Drzewo składniowe zawiera wszystkie produkcje gramatyki oraz wszystkie symbole końcowe, w tym nawiasy, przecinki, średniki i inne elementy czysto składniowe. AST natomiast usuwa szczegóły, które nie wnoszą znaczenia semantycznego, zachowując jedynie logiczną strukturę wyrażeń i zdań.

Pod względem implementacji AST zwykle składa się z obiektów węzłów , których typ wskazuje na rodzaj konstrukcji składniowej (stała, identyfikator, zastosowanie funkcji, operator binarny itd.), a także dodatkowe właściwości opisujące ich zawartość: wartość, nazwa, elementy podrzędne, lista argumentów itd.

Zaletą AST jest to, że ułatwia późniejsze fazy kompilatora lub interpretera, takie jak sprawdzanie typów, optymalizacja czy generowanie kodu , ponieważ oferuje przejrzysty widok struktury programu bez szumu składniowego.

Różnica między drzewem składniowym konkretnym a drzewem składniowym abstrakcyjnym

Aby w pełni zrozumieć, co wnosi AST, warto najpierw porównać konkretne drzewo parsowania z abstrakcyjnym. Wyobraź sobie prostą gramatykę rozpoznającą wyrażenia arytmetyczne, takie jak „a + 4 * 5” . Konkretne drzewo parsowania dokładnie odzwierciedla zastosowanie każdej reguły gramatycznej: symboli nieterminalnych, terminali, nawiasów, operatorów itp.

To konkretne drzewo jest zazwyczaj głębokie i ma wiele węzłów pośrednich, które służą jedynie do utrzymania formalnej struktury gramatyki. Na przykład, mogą istnieć węzły dla „Wyrażenia”, „Terminu”, „Czynnika”, a następnie symbole końcowe, takie jak „+” , „*” , identyfikatory i liczby. Każda produkcja staje się gałęzią drzewa, zwiększając złożoność strukturalną.

Z drugiej strony, abstrakcyjne drzewo składniowe dla tego samego wyrażenia ogranicza się do reprezentowania rzeczywistych operacji i operandów . Zatem zamiast kilku poziomów „Wyrażenia” i „Termu”, moglibyśmy mieć węzeł główny reprezentujący dodawanie, z dwoma potomkami: po lewej stronie identyfikatorem a, a po prawej węzeł mnożenia, którego potomkami są wartości 4 i 5. Czysto gramatyczne węzły znikają, a części struktury ulegają reorganizacji lub kondensacji.

Oznacza to, że drzewo składniowe AST i drzewo składniowe zawierają te same informacje semantyczne , ale to pierwsze prezentuje je w znacznie bardziej bezpośredniej i zwartej formie. Ta kondensacja jest kluczowa dla efektywnej pracy z kodem w narzędziach analitycznych lub wykonawczych.

Drzewa i alfabety z funkcją arności

Aby sformalizować te drzewa z matematycznego punktu widzenia, zazwyczaj stosuje się koncepcję alfabetu z funkcją arności . Zamiast prostego zestawu symboli, definiuje się alfabet, w którym każdy symbol jest powiązany z liczbą wskazującą, ile potomków może mieć na drzewie.

Alfabet z funkcją arności to, nieformalnie, para składająca się ze skończonego zbioru symboli i funkcji, która przypisuje każdemu symbolowi liczbę naturalną (w tym zero). Liczba ta wskazuje na arność symbolu: jeśli jest równa 0, symbol zachowuje się jak liść; jeśli jest równa 1, zachowuje się jak węzeł unarny; jeśli jest równa 2, jest binarny; i tak dalej. Powszechne jest również dopuszczanie symboli o zmiennej arności dla operatorów jako list argumentów.

Symbole o arności 0 odpowiadają liściom drzewa (na przykład stałym lub identyfikatorom). Symbole o arności 1 są używane dla konstrukcji, które obejmują pojedyncze wyrażenie potomne. Symbole o arności 2 reprezentują klasyczne operacje binarne, takie jak dodawanie, mnożenie, przypisanie itp. Symbole o zmiennej arności umożliwiają modelowanie konstrukcji akceptujących nieokreśloną liczbę poddrzew, na przykład wywołanie funkcji z wieloma parametrami.

Z tego alfabetu z arnością można zdefiniować zbiór wszystkich możliwych drzew: zaczynając od drzewa pustego (jeśli rozważamy), dodając wszystkie symbole arności 0 i zmiennej, a następnie rozszerzając je indukcyjnie: jeśli symbol jest k-arny, można go umieścić jako węzeł nadrzędny k już skonstruowanych poddrzew. W ten sposób otrzymujemy język drzewa (lub termin) powiązany z alfabetem.

Język drzew i pojęcie węzła

Zbiór wszystkich drzew utworzonych z alfabetu i jego funkcji arności nazywany jest w tym kontekście językiem drzew lub językiem terminów . Jest to odpowiednik, z wyjątkiem struktur drzewiastych, tego, czym jest domknięcie Kleenego dla ciągów znaków.

Tak jak analizując ciągi znaków, używamy terminu „tokeny” w odniesieniu do wystąpień symboli alfabetu w sekwencji, tak pracując z drzewami, zazwyczaj używamy terminu „węzły” . Węzeł to w zasadzie konkretne wystąpienie symbolu alfabetu z arnością, zlokalizowane w określonej pozycji w drzewie.

Z tej perspektywy język drzewa jest dla węzłów tym, czym zbiór ciągów znaków dla tokenów. Każde drzewo jest interpretowane jako struktura budowana krok po kroku z alfabetu, a węzły to poszczególne elementy, które fizycznie materializują jego symbole.

Ten sposób patrzenia na to jest bardzo użyteczny przy projektowaniu parserów i generatorów AST , ponieważ pozwala na rozumowanie o regułach konstrukcji tych drzew w sposób analogiczny do gramatyki łańcuchowej, ale pracując bezpośrednio na strukturach hierarchicznych.

Arność węzłów w konkretnym AST: przypadek Egg

Przechodząc od teorii do praktycznych przykładów, wiele materiałów dydaktycznych wykorzystuje język Egg do zilustrowania konstrukcji i manipulacji AST. W tym kontekście używa się kilku głównych typów węzłów, z których każdy ma dobrze zdefiniowaną arność , co ułatwia manipulację.

W typowym kodzie AST Egg węzły VALUE są traktowane jako liście: reprezentują literały, takie jak ciągi znaków lub liczby. Nie mają potomków; przechowują jedynie wartość. Podobnie węzły WORD , używane do identyfikatorów (nazw zmiennych, nazw funkcji itp.), są również traktowane jako liście z właściwością przechowującą nazwę.

Kluczowym węzłem w Egg jest typ APPLY , który reprezentuje zastosowanie funkcji lub operatora. Ten typ węzła ma dwa koncepcyjne elementy potomne: element potomny OPERATOR , który wskazuje na stosowane wyrażenie; oraz element potomny ARGS , który jest w rzeczywistości specjalnym węzłem ARRAY odpowiedzialnym za utrzymywanie zbioru poddrzew, po jednym dla każdego argumentu.

Tablice są zatem naturalnym sposobem wprowadzenia zmiennej arności do AST: APPLY zawsze ma dwa komponenty (operator i listę argumentów), ale ta wewnętrzna lista może zawierać zero, jedno lub wiele poddrzew w zależności od konkretnego reprezentowanego wywołania.

Szczegółowa anatomia węzłów AST w jajku

Na poziomie implementacji węzły AST w Egg są zazwyczaj reprezentowane jako obiekty z właściwościami , co idealnie pasuje do języków takich jak JavaScript. Wszystkie węzły mają wspólną właściwość: `type` , która identyfikuje typ węzła (VALUE, WORD, APPLY, ARRAY itd.), a tym samym strukturę, jaką będzie miała reszta obiektu.

Węzły VALUE są używane do stałych literałowych . Zawierają one właściwość, często nazywaną wartością , w której przechowywana jest liczba lub ciąg znaków, który reprezentują. Nie mają żadnych dodatkowych potomków, ponieważ ich zawartość jest w całości opisana przez ten literał.

Węzły słów są zarezerwowane dla identyfikatorów : nazw zmiennych, nazw funkcji, nazw parametrów i tym podobnych. Zazwyczaj mają właściwość `name` , która przechowuje identyfikator jako ciąg znaków. Podobnie jak węzły VALUE, pełnią one funkcję liści w drzewie, ponieważ ich jedynym celem jest podanie tej nazwy.

Węzły Apply reprezentują aplikacje lub wywołania. Zawierają one właściwość operatora , która wskazuje na stosowane wyrażenie (inny węzeł), oraz właściwość args , która łączy się z węzłem ARRAY. Ten ostatni jest konkretnym węzłem w AST, którego celem jest przechowywanie listy argumentów aplikacji .

Węzeł ARRAY można rozumieć jako ustrukturyzowany kontener dla innych węzłów, reprezentujący sekwencję poddrzew. Z punktu widzenia arności, wprowadza on elastyczność, ponieważ pozwala na wywołania bez argumentów, z jednym argumentem lub z wieloma argumentami w ramach tej samej instrukcji APPLY, bez konieczności zmiany definicji głównego typu węzła.

Przykład AST: prosta aplikacja z jedną wartością

Aby zwizualizować powyższe, pomyślmy o reprezentacji prostej instrukcji, takiej jak zastosowanie funkcji X z pojedynczym argumentem 5. Kod AST wygenerowany przez parser odpowiada terminowi skonstruowanemu za pomocą węzłów VALUE, WORD i APPLY zgodnie z regułami Egg.

Na poziomie koncepcyjnym mielibyśmy węzeł APPLY w korzeniu. Jego właściwość operator wskazywałaby na węzeł WORD o nazwie X, a jego właściwość args odnosiłaby się do węzła ARRAY zawierającego pojedynczy element: węzeł VALUE o wartości liczbowej 5. W ten sposób struktura jasno odzwierciedla, do kogo i do czego jest stosowana.

Gdybyśmy chcieli wyraźnie określić wszystkie atrybuty, moglibyśmy napisać bardziej szczegółową notację, pokazującą typ, operator, argumenty, nazwę i wartość. Ta bardziej szczegółowa notacja jest bardzo przydatna do debugowania parsera lub do zrozumienia, jak wyrażenie tekstowe jest tłumaczone na obiekt drzewa w interpreterze.

W rzeczywistych implementacjach drzewo to jest zazwyczaj serializowane jako JSON , co ułatwia przechowywanie, przesyłanie i inspekcję. W rzeczywistości narzędzia i moduły, takie jak pakiet evm2term w ekosystemie npm, zapewniają zwartą reprezentację tych AST, co ułatwia analizę i transformację.

Przykład AST: zagnieżdżone dodawanie i mnożenie

Innym typowym przypadkiem jest nieco bardziej złożone wyrażenie, takie jak „+(a, *(4, 5))” . Mamy tu operację dodawania, której pierwszym argumentem jest identyfikator a, a drugim wynik mnożenia 4 przez 5. Kod AST wynikający z tego wyrażenia odzwierciedla tę zagnieżdżoną strukturę.

U korzenia drzewa ponownie mielibyśmy węzeł APPLY reprezentujący operację dodawania. Jego operatorem byłby węzeł WORD o nazwie „+”, a jego argumenty znajdowałyby się w węźle ARRAY z dwoma elementami: pierwszym, WORD o nazwie „a”, a drugim, kolejnym węzłem APPLY reprezentującym mnożenie.

Drugie polecenie APPLY miałoby jako operator WORD o nazwie „*”, a jako argumenty TABLICĘ z dwoma węzłami VALUE: jednym o wartości 4 i drugim o wartości 5. Patrząc na tę strukturę jako całość, wyraźnie widać, że kolejność oceny polega na pomnożeniu 4 przez 5, a następnie dodaniu wyniku do a.

Jeśli rozszerzymy notację o wszystkie atrybuty, zobaczymy typy wszystkich węzłów, ich nazwy lub konkretne wartości oraz relacje między nimi. Ten jawny opis odpowiada rzeczywistej implementacji w interpreterze Egg, gdzie każdy węzeł jest obiektem o wyżej wymienionych właściwościach.

Gramatyka drzewiasta i gramatyka parsera

Sposób generowania tych AST nie jest arbitralny: opiera się na tzw. gramatyce drzewa . W typowym sformułowaniu taką gramatykę definiuje się jako czwórkę złożoną z alfabetu z arnością, skończonego zbioru zmiennych składniowych (nieterminalnych), skończonego zbioru reguł produkcji oraz symbolu początkowego.

W każdej regule produkcyjnej zmienna jest zastępowana drzewem, którego korzeniem jest symbol alfabetu z arnością, a którego elementami potomnymi są zmienne lub już zdefiniowane drzewa. Struktura ta przypomina klasyczne gramatyki regularne lub bezkontekstowe, ale jest dostosowana do bezpośredniego generowania drzew zamiast ciągów symboli.

Z tą bardziej formalną definicją wiąże się konkretna gramatyka, której parser Egg używa do generowania drzew. Gramatyka ta, zazwyczaj prezentowana nieformalnie w dokumentacji, dokładnie opisuje, jakie kombinacje słów kluczowych, operatorów, nawiasów itd. są akceptowane w języku i jak przekładają się one na węzły typu VALUE, WORD, APPLY i ARRAY.

Tę gramatykę drzewiastą można postrzegać jako szczególny przypadek tego, co w literaturze nazywa się regularną gramatyką drzewiastą . Ideą jest posiadanie ściśle zdefiniowanych reguł konwersji sekwencji tokenów wejściowych na ustrukturyzowany kod AST, który następnie można zinterpretować lub skompilować.

Notacja Deweya: współrzędne w drzewie

Gdy mamy już AST, często musimy odwoływać się do konkretnych poddrzew : na przykład drugiego argumentu funkcji, operatora wyrażenia itd. Bardzo eleganckim sposobem na zrobienie tego jest tzw. notacja dziesiętna Deweya, która zapożycza schemat używany do numerowania sekcji i podsekcji w dokumentach.

W tej notacji, zaczynając od drzewa t, poddrzewo jest oznaczane ciągiem liczb rozdzielonych kropkami . Każda liczba wskazuje pozycję dziecka (zwykle zaczynającą się od 1), a sekwencja ciągnie się w dół drzewa. Zatem wyrażenie takie jak t/2.1.3 odnosi się do trzeciego dziecka pierwszego dziecka drugiego dziecka drzewa t.

Indukcyjna definicja tej notacji jest prosta: pusty ciąg odnosi się do całego drzewa; jeśli ciąg składa się z liczby, po której następują kolejne liczby oddzielone kropkami, interpretuje się go najpierw poprzez wzięcie poddrzewa potomnego odpowiadającego wskazanemu indeksowi, a następnie rekurencyjne zastosowanie tej samej logiki do reszty ciągu.

Na przykład, jeśli mamy drzewo t reprezentujące wyrażenie takie jak „+(a, *(4,5))”, z węzłem głównym APPLY dla dodawania, słowem potomnym WORD o nazwie „+” i kolejnym słowem potomnym APPLY dla mnożenia, możemy zidentyfikować konkretne pozycje. Zatem t/1 może być węzłem WORD z operatorem „+”, t/2.1 identyfikatorem „a”, a t/2.2.2.1 węzłem VALUE o wartości 4, jeśli odpowiednio ponumerujemy dzieci.

Taki sposób podawania „współrzędnych” w AST jest bardzo przydatny do wskazywania konkretnych lokalizacji podczas zgłaszania błędów, nawigowania po drzewie lub stosowania lokalnych przekształceń do konkretnych węzłów bez żadnych niejasności.

Równoważne notacje w programowaniu i narzędziach

Idea, na której opiera się notacja Deweya, nie jest charakterystyczna wyłącznie dla teorii drzew. W rzeczywistości pojawia się wielokrotnie w wielu praktycznych notacjach , których używamy na co dzień w programowaniu i obsłudze danych strukturalnych, nawet jeśli nie zawsze jesteśmy tego świadomi.

Kiedy piszemy wyrażenia z operatorem kropki w języku programowania , takie jak object.property.subproperty, robimy coś bardzo podobnego: przechodzimy przez drzewo zagnieżdżonych obiektów, wybierając obiekt potomny na każdym kroku według nazwy, a nie numeru pozycji. Zaczynając od węzła głównego, schodzimy do węzłów bardziej wewnętrznych.

Ten sam schemat pojawia się w systemach plików typu Unix, gdzie do oddzielania katalogów używa się operatora ukośnika (/) : /src/js/tutu.js opisuje ścieżkę od katalogu głównego systemu plików do określonego zasobu, przechodząc kolejne poziomy struktury drzewa.

W świecie dokumentów strukturalnych języki takie jak XPath używają bardzo podobnych notacji do wybierania węzłów w drzewie XML. Zapytanie takie jak „A//B/*” wybiera pierwsze dziecko (niezależnie od jego nazwy) każdego elementu B, będącego potomkiem elementu A, w odpowiedniej pozycji względem bieżącego kontekstu, używając pojedynczych i podwójnych ukośników do wskazania poziomów głębokości.

Inne znane narzędzie, język JQ , wykorzystuje system równoległy do ​​nawigacji po strukturach JSON, umożliwiając wybór podobiektów za pomocą ścieżek złożonych, filtrów i wyrażeń. Wszystkie te notacje to po prostu różne sposoby wyrażania ścieżek w drzewie , bardzo zbliżone do notacji dziesiętnej Deweya, ale dostosowane do ich odpowiednich dziedzin.

Drzewa parsowania w językoznawstwie i programowaniu

Poza światem kompilatorów, drzewa składniowe są również wykorzystywane w językoznawstwie do reprezentacji struktury zdań. Nazywa się je tam drzewami derywacyjnymi lub drzewami parsowania, które pokazują, jak zdanie jest rozbijane na frazy, słowa i kategorie gramatyczne.

W tych drzewach, podobnie jak w programowaniu, znajdujemy trzy podstawowe typy węzłów: węzeł główny , który reprezentuje całe zdanie lub strukturę globalną; węzły wewnętrzne lub rozgałęzione, które pełnią funkcję węzłów nadrzędnych i grupują podzbiory zdania; oraz węzły liściowe, które zwykle odpowiadają konkretnym słowom pojawiającym się w ciągu wejściowym.

Węzeł główny jest wyjątkowy: cała struktura drzewa jest na nim zawieszona. Węzły rozgałęziające znajdują się bezpośrednio pod korzeniem lub innymi węzłami nadrzędnymi i służą do hierarchicznej organizacji części zdania lub programu. Węzły liściowe natomiast znajdują się na najniższym poziomie drzewa i nie mają żadnych potomków, zamykając w ten sposób strukturę rozgałęziającą.

Drzewa te są uważane za potężne narzędzia dydaktyczne, ponieważ pomagają rozbić złożone zdania na łatwe do opanowania elementy. To samo dotyczy programowania: dobrze skonstruowany kod AST pozwala na pierwszy rzut oka zobaczyć, które operacje są ze sobą powiązane, które wyrażenia są zagnieżdżone i jak przebiega ewaluacja.

W zależności od celu analizy, możemy wyróżnić różne rodzaje drzew analitycznych . Niektóre kładą nacisk na zależności między słowami lub składnikami (na przykład, kto od kogo zależy w zdaniu), podczas gdy inne koncentrują się na grupowaniu w frazy lub elementy, co prowadzi do powstania dwóch głównych rodzin.

Drzewa składniowe według zależności i według składni

Jednym z najbardziej znanych typów jest drzewo składniowe oparte na zależnościach . W tym wariancie wszystkie słowa w zdaniu lub wszystkie istotne elementy są traktowane jako węzły liściowe, a powiązania między nimi wskazują na bezpośrednie relacje zależności (na przykład czasownik główny i jego podmiot). W rezultacie często powstają drzewa z mniejszą liczbą węzłów niż w innych schematach.

Ta prostota sprawia, że ​​są one szczególnie wygodne dla początkujących i w przypadku niektórych zadań przetwarzania języka, ponieważ struktura koncentruje się na zależnościach między podmiotami, bez wprowadzania zbyt wielu węzłów pośrednich. W zastosowaniu do programowania, idea polega na skupieniu się tylko na podstawowych relacjach, pomijając gramatyczne ozdobniki.

Na drugim krańcu mamy drzewa składniowe oparte na elementach składniowych lub składnikach, które rozróżniają węzły główne, wewnętrzne węzły rozgałęzień i węzły liściowe, dzięki czemu wszystkie istotne grupy są widoczne. Drzewa te zazwyczaj zawierają więcej węzłów i bardziej szczegółowo odzwierciedlają hierarchiczną strukturę zdania lub programu.

Często spotykane szablony drzewa okręgów wyborczych wyświetlają długie zdania z licznymi węzłami liściowymi, kilkoma poziomami rozgałęzień i dobrze zdefiniowanym węzłem głównym. Są one szczególnie przydatne do analizy złożonych zdań lub programów z wieloma warstwami zagnieżdżonych struktur.

Zarówno w drzewach zależności, jak i okręgów wyborczych, przykłady i zasoby wizualne są dostępne w formie szablonów, co pozwala na proste wypełnienie węzłów pożądanymi informacjami. Oszczędza to czas i eliminuje konieczność projektowania diagramu od podstaw za każdym razem, gdy chcesz zilustrować strukturę.

Praktyczne zastosowania i narzędzia związane z AST

AST to nie tylko koncepcja teoretyczna: są one aktywnie wykorzystywane w wielu codziennych narzędziach przez każdego, kto pracuje z kodem. Kompilatory, interpretery, minifikatory, formatery kodu i analizatory statyczne niemal zawsze wykorzystują AST do wykonywania swoich funkcji.

Typowy kompilator pobiera kod źródłowy, tokenizuje go, analizuje i generuje abstrakcyjne drzewo składniowe. Następnie przeprowadza kontrole semantyczne (typy, zakres zmiennych, nieprawidłowe użycie konstrukcji) i stosuje optymalizację kodu poprzez przeszukiwanie i transformację AST przed wygenerowaniem kodu maszynowego, czyli kodu bajtowego.

Narzędzia takie jak lintery i formatery działają również na AST: analizują strukturę w celu wykrycia problematycznych wzorców, złych praktyk lub niespójności i proponują zmiany, które zachowują semantyczną strukturę drzewa, ale zmieniają prezentację kodu.

Przykładowo, w ekosystemie JavaScript istnieje wiele bibliotek, które udostępniają kod AST w formacie JSON, dzięki czemu inne narzędzia mogą łatwiej z niego korzystać w celu refaktoryzacji, generowania automatycznej dokumentacji lub tworzenia wizualizacji struktury złożonych programów.

Nawet w nieco bardziej wyspecjalizowanych dziedzinach, takich jak instrumentacja do pomiaru pokrycia testów czy transformacja kodu źródłowego do innych języków, AST stanowi fundament, na którym opiera się wiele nowoczesnych rozwiązań, gdyż pozwala na pracę na bardzo komfortowym poziomie abstrakcji między surowym tekstem a kodem maszynowym.

Podsumowując, abstrakcyjne drzewa składniowe stanowią kluczowy element łączący formalną gramatykę języka, jego wewnętrzną reprezentację w kompilatorze lub interpreterze oraz zaawansowane narzędzia, których używamy do bezpiecznego i wydajnego pisania, analizowania i transformowania kodu. Zrozumienie, jak są one zbudowane, jak się po nich poruszać (z uwzględnieniem takich pojęć jak notacja dziesiętna Deweya) oraz jakie typy węzłów są w nie zaangażowane (WARTOŚĆ, SŁOWO, ZASTOSOWANIE, struktury o stałej lub zmiennej arności itp.) pomaga nam znacznie wyraźniej zrozumieć, co tak naprawdę robi maszyna podczas przetwarzania programu.