Jak działa tokenizer w interpreterze NanoBASIC?

Tokenizacja to kluczowy etap w procesie przetwarzania źródłowego kodu w interpreterze, który przygotowuje go do dalszego przetwarzania przez parser i interpreter. Na przykład, jeśli interpreter Pythona napotka token „a”, a następnie „+” i „2”, stworzy węzeł wyrażenia arytmetycznego i połączy go z węzłami reprezentującymi „a” oraz „2”. Następnie środowisko wykonawcze przechodzi przez te węzły w drzewie składniowym (AST), wykonując odpowiednie operacje na ich podstawie. Dla naszego węzła „a + 2” oznacza to odczytanie wartości zmiennej „a” i dodanie do niej liczby 2.

Podstawowym zadaniem tokenizer-a w interpreterze NanoBASIC jest przekształcenie tekstu źródłowego w odpowiednie tokeny, które będą używane w kolejnych etapach przetwarzania. Tokeny te stanowią najmniejsze jednostki programu, które mogą zostać przetworzone. Każdy token odpowiada określonemu elementowi w języku programowania, takiemu jak zmienne, operatory, słowa kluczowe czy liczby. W NanoBASIC, jak i w wielu innych językach, te jednostki są ściśle związane z gramatyką, która je definiuje.

Kluczowym elementem przy budowie tokenizer-a jest precyzyjne określenie kolejności wyszukiwania wzorców. Często zdarza się, że jedno wyrażenie regularne może pasować do różnych tokenów, co sprawia, że kolejność ich dopasowywania ma istotne znaczenie. Na przykład, wzorzec dla nazwy zmiennej może również pasować do słowa kluczowego „PRINT”. W takiej sytuacji wyszukiwanie zmiennych odbywa się dopiero po rozpoznaniu wszystkich słów kluczowych.

W naszym przypadku dla NanoBASIC definiujemy klasy tokenów przy pomocy typu wyliczeniowego (enum). Każdy typ tokenu jest związany z odpowiednim wzorcem wyrażenia regularnego. Ponadto, niektóre tokeny mogą zawierać wartości użytkownika, jak na przykład nazwa zmiennej lub liczba. Oto przykład klasy tokenów:

python
Copy code
class TokenType(Enum):

    COMMENT = (r'rem.*', False)
    WHITESPACE = (r'[\t\n\r]', False)
    PRINT = (r'print', False)
    IF_T = (r'if', False)
    THEN = (r'then', False)
    LET = (r'let', False)
    GOTO = (r'goto', False)
    GOSUB = (r'gosub', False)
    RETURN_T = (r'return', False)
    COMMA = (r',', False)
    EQUAL = (r'=', False)
    NOT_EQUAL = (r'<>|><', False)
    LESS_EQUAL = (r'<=', False)
    GREATER_EQUAL = (r'>=', False)
    LESS = (r'<', False)
    GREATER = (r'>', False)
    PLUS = (r'\+', False)
    MINUS = (r'-', False)
    MULTIPLY = (r'\*', False)
    DIVIDE = (r'/', False)
    OPEN_PAREN = (r'\(', False)
    CLOSE_PAREN = (r'\)', False)
    VARIABLE = (r'[A-Za-z_]+', True)
    NUMBER = (r'-?[0-9]+', True)
    STRING = (r'".*"', True)

Każdy typ tokenu jest skojarzony z wyrażeniem regularnym, które pozwala na jego wykrycie w tekście źródłowym. Istotnym elementem jest także fakt, że oprócz samego typu tokenu, przechowywana jest również jego lokalizacja w pliku źródłowym. Umożliwia to późniejsze raportowanie błędów składniowych i precyzyjne wskazanie miejsca, w którym wystąpił problem.

Tokeny, które zawierają wartości, takie jak zmienne czy liczby, mają dodatkowe pole associated_value, które przechowuje tę wartość. Na przykład, token dla zmiennej będzie zawierał jej nazwę, a token dla liczby – jej wartość liczbową.

python
Copy code
@dataclass(frozen=True)

class Token:
    kind: TokenType
    line_num: int
    col_start: int
    col_end: int
    associated_value: str | int | None

Warto zauważyć, że w tokenizatorze wykorzystujemy funkcję re.match(), aby dopasować odpowiedni wzorzec w danym wierszu tekstu. Kiedy wzorzec zostanie znaleziony, obliczamy kolumnę, na której występuje dany token, oraz zapisujemy go w liście tokenów, chyba że jest to komentarz lub białe znaki, które są ignorowane. Oto fragment funkcji tokenize, która przetwarza kod źródłowy:

python
Copy code
def tokenize(text_file: TextIO) -> list[Token]:

    tokens: list[Token] = []
    for line_num, line in enumerate(text_file.readlines(), start=1):
        col_start: int = 1
        while len(line) > 0:
            found: re.Match | None = None
            for possibility in TokenType:
                found = re.match(possibility.pattern, line, re.IGNORECASE)
                if found:
                    col_end: int = col_start + found.end() - 1
                    if (possibility is not TokenType.WHITESPACE and possibility is not TokenType.COMMENT):

                        associated_value: str | int | None = None

                        if possibility.has_associated_value:
                            if possibility is TokenType.NUMBER:
                                associated_value = int(found.group(0))
                            elif possibility is TokenType.VARIABLE:
                                associated_value = found.group()
                            elif possibility is TokenType.STRING:
                                associated_value = found.group(0)[1:-1]
                        tokens.append(Token(possibility, line_num, col_start, col_end, associated_value))

Dzięki tej funkcji możemy rozbić każdy wiersz kodu na tokeny, które są później wykorzystywane w dalszych etapach procesu interpretacji.

Na tym etapie należy zrozumieć, że tokenizer to tylko początek długiego procesu przetwarzania kodu. Po rozbiciu kodu na tokeny, kolejnym krokiem jest ich analiza przez parser, który buduje drzewo składniowe, a następnie interpreter wykonuje operacje wynikające z tej struktury. Ważne jest także to, że tokeny muszą być traktowane w kontekście całego kodu, aby zapewnić ich właściwą interpretację i obsługę błędów.

Jak efektywnie zaimplementować instrukcje procesora 6502: Automatyczne tworzenie tabeli i implementacja metod

Implementowanie procesora 6502 to zadanie, które na pierwszy rzut oka może wydawać się żmudne i pełne powtórzeń. Niezwykle czasochłonne byłoby ręczne tworzenie tabeli dla wszystkich możliwych instrukcji, szczególnie gdy chodzi o złożone zestawy opcji, które trzeba obsłużyć. W takim przypadku warto sięgnąć po automatyzację – tworzenie skryptu do generowania takiej tabeli z publicznych źródeł stanowi prostą, ale bardzo skuteczną metodę oszczędzania czasu. Skrypt taki, mimo że jest „brudnym hackiem” stworzonym w pośpiechu, może zaoszczędzić masę pisania kodu.

Tabele instrukcji procesora 6502 są wykorzystywane w wielu emulacjach, a stworzenie ich ręcznie, na podstawie dokumentacji, wymaga ogromnej precyzji. Proces automatyzacji w tym przypadku okazał się wyjątkowo przydatny. Dodatkowo pozwala na szybkie testowanie, modyfikowanie i iterowanie nad kodem, co jest istotne w projektach wymagających wysokiej precyzji.

Instrukcje procesora 6502 to mnemoniki, które odpowiadają za konkretne operacje arytmetyczne, logiczne czy sterujące. Każda z nich posiada określony kod operacji (opcode), tryb pamięci, liczbę cykli potrzebnych do wykonania oraz różne flagi, które mogą zostać zmienione po wykonaniu instrukcji. Na przykład, instrukcja AND wykonuje operację logicznego AND pomiędzy wartością w akumulatorze a danymi z pamięci, a jej wynik zapisuje z powrotem do akumulatora. Istnieje wiele takich prostych, ale wymagających odpowiedniego zaimplementowania metod, które należy rozbić na mniejsze kroki.

Każda instrukcja jest w zasadzie jednym małym fragmentem kodu. Na przykład operacja AND wyglądałaby następująco:

python
Copy code
def AND(self, instruction: Instruction, data: int):

    src = self.read_memory(data, instruction.mode)
    self.A = self.A & src
    self.setZN(self.A)

W tym przypadku używamy metody self.read_memory(), która odpowiedzialna jest za odczytanie danych z pamięci. Następnie, wynik operacji logicznego AND między akumulatorem a danymi jest zapisany z powrotem do akumulatora. Na końcu wywoływana jest metoda self.setZN(), która ustawia odpowiednie flagi w rejestrach procesora.

Następnie, warto zapoznać się z metodami pomocniczymi, które już istnieją w klasie CPU, jak na przykład te związane z manipulowaniem stosem, odczytem i zapisem do pamięci. Wiele instrukcji jest bardzo prostych, jak np. operacja DEX, która po prostu dekrementuje wartość rejestru X, ale nawet te prostsze operacje wymagają odpowiedniej obsługi flag, co oznacza konieczność utworzenia metod takich jak self.setZN().

Podstawowe operacje arytmetyczne i logiczne są łatwe do zaimplementowania dzięki operatorom bitowym w Pythonie. Ważne jest zrozumienie, jak te operatory działają, ponieważ wiele instrukcji procesora 6502 wymaga manipulacji na poziomie bitów. Na przykład operacja SBC (subtraction with borrow) jest odpowiedzialna za odejmowanie z uwzględnieniem pożyczki i wygląda następująco:

python
Copy code
def SBC(self, instruction: Instruction, data: int):

    src = self.read_memory(data, instruction.mode)
    result = self.A - src - (1 if self.C == 0 else 0)
    self.A = result & 0xFF
    self.setZN(self.A)
    self.setCarry(result)

Podobnie jak inne operacje, wynik jest zapisywany w akumulatorze, a odpowiednie flagi są ustawiane na podstawie rezultatu operacji. Ważnym aspektem jest również obsługa flagi przeniesienia (carry), która jest niezbędna w przypadku operacji takich jak SBC.

Z kolei bardziej złożone instrukcje, takie jak te wymagające odczytu lub zapisu z wykorzystaniem trybów pośrednich (np. pośrednia indeksacja) muszą być zaimplementowane zgodnie z zasadami tych trybów pamięci, co również znajduje swoje odzwierciedlenie w kodzie.

Dodatkowo, ważnym krokiem jest testowanie każdej z metod za pomocą emulatora lub dedykowanego środowiska. Również w przypadku implementacji bardziej zaawansowanych instrukcji należy zwrócić uwagę na sposób, w jaki operują one na pamięci i jakie efekty wywołują w rejestrach procesora. Testowanie pomaga również w wychwyceniu błędów związanych z obsługą cykli, które mogą wystąpić w przypadku złożonych operacji, takich jak INC, DEC, czy instrukcje zmieniające stan flag.

Warto pamiętać, że proces implementacji 6502 to także doskonała okazja do nauczenia się szczegółów architektury komputerów oraz zasady działania procesorów w kontekście niskopoziomowego programowania. Dzięki dobrej dokumentacji oraz metodycznemu podejściu do implementacji instrukcji, zadanie to staje się znacznie prostsze i bardziej przejrzyste.

Jak kontynuować naukę informatyki po przeczytaniu tej książki?

Interpreter, nad którym pracowaliśmy w pierwszej części książki, był prosty, ale zawierał wszystkie kluczowe elementy rzeczywistego interpretera (tokenizer, parser, środowisko wykonawcze). Dzięki temu możesz teraz stworzyć interpreter bardziej zaawansowanego języka, bez konieczności dalszego studiowania. Trudności pojawiają się dopiero wtedy, gdy chcesz uczynić ten język bardziej wydajnym. Może to wymagać zastosowania bardziej zaawansowanych technik, takich jak implementacja maszyny wirtualnej lub kompilatora, czy też dodanie optymalizacji wykonania w czasie rzeczywistym. Choć w tej książce omawialiśmy jedynie podstawy, możesz zacząć pisać własne interpretery już teraz. Jeśli kiedykolwiek chciałeś stworzyć własny język programowania, teraz masz do tego narzędzia. Nie twierdzę, że koniecznie powinieneś to zrobić, ale teraz jest to w zasięgu ręki.

W czwartej części książki postawiliśmy pierwsze kroki w kierunku uczenia maszynowego. Algorytm KNN to najprostszy algorytm w sztucznej inteligencji. Działa świetnie w odpowiednich zastosowaniach, ale aby w pełni zrozumieć, kiedy go użyć, warto poznać kilka innych technik. Dzięki temu, że zaczęliśmy od bardzo prostych podstaw, mam nadzieję, że obszar ten, który często wydaje się przerażający, stał się dla Ciebie bardziej przystępny. Dziś, dostęp do algorytmów sztucznej inteligencji jest już jedynie kwestią wywołania odpowiednich bibliotek. Nie musisz być ekspertem, aby używać tych technik, ale kluczowe jest, by wiedzieć, jakich narzędzi użyć w danej sytuacji.

Zrealizowanie projektów zawartych w książce to dopiero początek w tych czterech obszarach. To, co dalej zrobisz, zależy już od Ciebie — możesz rozpocząć własne projekty lub kontynuować naukę.

Dalsza nauka informatyki wcale nie wymaga formalnego wykształcenia akademickiego. Jak widzisz, książka ta była świetnym wstępem. Jak w przypadku niemal każdej dziedziny, wszystko, czego potrzebujesz, znajdziesz w bibliotekach i internecie, wystarczy tylko poświęcić czas na naukę i praktykę. Sam jestem osobą, która lubi rozumieć, jak rzeczy działają na poziomie podstawowym, i wiem, że wielu ludziom właśnie to jest potrzebne, by poczuć się pewnie w tej dziedzinie. Nawet jeśli nie masz takich skłonności, przekonam Cię, dlaczego warto poznać podstawy informatyki i zrozumieć, jak działają systemy "pod maską".

Informatyka to szeroka dziedzina, ale nie ma się czego bać. Dla osób, które chciałyby kontynuować naukę, polecam kilka książek, które doskonale uzupełniają tę książkę:

• „Grokking Algorithms, 2nd Edition” autorstwa Adity Y. Bhargavy — książka o algorytmach, niezwykle przystępna, z przykładami w Pythonie, doskonała dla osób szukających mniej matematycznego podejścia do tej tematyki.

• „Classic Computer Science Problems in Python” autorstwa Davida Kopeca — książka traktująca o klasycznych problemach z zakresu informatyki, prezentująca algorytmy w sposób praktyczny, szczególnie polecana dla tych, którzy chcą nauczyć się algorytmów od podstaw.

Jeśli chodzi o temat interpretatorów, polecam dwie książki, które są uznawane za doskonałe w tym temacie:

• „Crafting Interpreters” autorstwa Roberta Nystroma — świetna książka zarówno pod względem pedagogicznym, jak i kodowania. Doskonała dla osób, które chcą napisać większe interpretery po zapoznaniu się z projektami z książki.

• „Writing an Interpreter in Go” autorstwa Thorstena Balla — książka bardziej zwięzła, ale dobrze napisana, szczególnie dla programistów Go.

Sztuka komputerowa i techniki związane z tworzeniem obrazów komputerowych również rozwijają się dynamicznie, więc warto poszukać dodatkowych materiałów w internecie, jeśli ten temat Cię zainteresował.