Kompilator

Proces kompilacji w MicroPython obejmuje następujące etapy:

  • Analizator leksykalny (lexer) konwertuje strumień tekstu tworzący program MicroPython na tokeny.

  • Następnie parser konwertuje tokeny na abstrakcyjną składnię (drzewo rozbioru).

  • Później na podstawie drzewa rozbioru emitowany jest bytecode lub kod natywny.

Na potrzeby tej dyskusji dodamy prostą funkcję językową add1, której można użyć w Pythonie w następujący sposób:

>>> add1 3
4
>>>

Instrukcja add1 przyjmuje liczbę całkowitą jako argument i dodaje do niej 1.

Dodawanie reguły gramatycznej

Gramatyka MicroPython opiera się na gramatyce CPython i jest zdefiniowana w py/grammar.h. Ta gramatyka jest wykorzystywana do parsowania plików źródłowych MicroPython.

Istnieją dwa makra, które musisz znać, aby zdefiniować regułę gramatyczną: DEF_RULE i DEF_RULE_NC. DEF_RULE pozwala zdefiniować regułę z powiązaną funkcją kompilacji, natomiast DEF_RULE_NC nie posiada funkcji kompilacji (NC).

Prosta definicja gramatyczna z funkcją kompilacji dla naszej nowej instrukcji add1 wygląda następująco:

DEF_RULE(add1_stmt, c(add1_stmt), and(2), tok(KW_ADD1), rule(testlist))

Drugi argument c(add1_stmt) jest odpowiadającą funkcją kompilacji, którą należy zaimplementować w py/compile.c, aby przekształcić tę regułę w kod wykonywalny.

Trzeci wymagany argument może mieć wartość or lub and. Określa on liczbę węzłów powiązanych z instrukcją. Na przykład w tym przypadku nasza instrukcja add1 jest podobna do ADD1 w języku asemblera. Przyjmuje ona jeden argument numeryczny. Dlatego add1_stmt ma dwa powiązane z nią węzły. Jeden węzeł odpowiada samej instrukcji, tj. literałowi add1 odpowiadającemu KW_ADD1, a drugi jej argumentowi, regule testlist, która jest regułą wyrażenia najwyższego poziomu.

Informacja

Reguła add1 jest tutaj tylko przykładem i nie stanowi części standardowej gramatyki MicroPython.

Czwartym argumentem w tym przykładzie jest token powiązany z regułą, KW_ADD1. Token ten powinien zostać zdefiniowany w analizatorze leksykalnym poprzez edycję py/lexer.h.

Zdefiniowanie tej samej reguły bez funkcji kompilacji uzyskuje się przy użyciu makra DEF_RULE_NC oraz pominięciu argumentu funkcji kompilacji:

DEF_RULE_NC(add1_stmt, and(2), tok(KW_ADD1), rule(testlist))

Pozostałe argumenty zachowują to samo znaczenie. Reguła bez funkcji kompilacji musi być obsługiwana jawnie przez wszystkie reguły, które mogą mieć ją jako węzeł. Takie reguły NC są zwykle używane do wyrażenia podczęści skomplikowanej struktury gramatycznej, której nie można wyrazić w pojedynczej regule.

Informacja

Makra DEF_RULE i DEF_RULE_NC przyjmują również inne argumenty. Aby dogłębnie zrozumieć obsługiwane parametry, zobacz py/grammar.h.

Dodawanie tokenu leksykalnego

Każda reguła zdefiniowana w gramatyce powinna mieć powiązany z nią token, który jest zdefiniowany w py/lexer.h. Dodaj ten token, edytując wyliczenie _mp_token_kind_t:

typedef enum _mp_token_kind_t {
    ...
    MP_TOKEN_KW_OR,
    MP_TOKEN_KW_PASS,
    MP_TOKEN_KW_RAISE,
    MP_TOKEN_KW_RETURN,
    MP_TOKEN_KW_TRY,
    MP_TOKEN_KW_WHILE,
    MP_TOKEN_KW_WITH,
    MP_TOKEN_KW_YIELD,
    MP_TOKEN_KW_ADD1,
    ...
} mp_token_kind_t;

Następnie zedytuj również py/lexer.c, aby dodać tekst literału nowego słowa kluczowego:

static const char *const tok_kw[] = {
    ...
    "or",
    "pass",
    "raise",
    "return",
    "try",
    "while",
    "with",
    "yield",
    "add1",
    ...
};

Zwróć uwagę, że słowo kluczowe jest nazywane w zależności od tego, jak chcesz je nazwać. Dla zachowania spójności utrzymuj odpowiednio standard nazewnictwa.

Informacja

Kolejność tych słów kluczowych w py/lexer.c musi odpowiadać kolejności tokenów w wyliczeniu zdefiniowanym w py/lexer.h.

Parsowanie

Na etapie parsowania parser pobiera tokeny wytworzone przez analizator leksykalny i konwertuje je na abstrakcyjne drzewo składniowe (AST) lub drzewo rozbioru. Implementacja parsera jest zdefiniowana w py/parse.c.

Parser utrzymuje również tablicę stałych do wykorzystania w różnych aspektach parsowania, podobnie do tego, co robi tablica symboli.

W tej fazie wykonywanych jest kilka optymalizacji, takich jak zwijanie stałych na liczbach całkowitych dla większości operacji, np. logicznych, binarnych, jednoargumentowych itd., oraz usprawnienia optymalizacyjne dotyczące nawiasów wokół wyrażeń, wraz z pewnymi optymalizacjami na łańcuchach znaków.

Warto zauważyć, że docstringi są odrzucane i nie są dostępne dla kompilatora. Nawet optymalizacje takie jak internowanie łańcuchów znaków nie są stosowane do docstringów.

Przebiegi kompilatora

Podobnie jak wiele kompilatorów, MicroPython kompiluje cały kod do bytecode’u MicroPython lub kodu natywnego. Funkcjonalność realizująca to zadanie jest zaimplementowana w py/compile.c. Najważniejsza metoda, którą warto znać, jest następująca:

mp_obj_t mp_compile(mp_parse_tree_t *parse_tree, qstr source_file, bool is_repl) {
    // Create a context for this module, and set its globals dict.
    mp_module_context_t *context = m_new_obj(mp_module_context_t);
    context->module.globals = mp_globals_get();

    // Compile the input parse_tree to a raw-code structure.
    mp_compiled_module_t cm;
    cm.context = context;
    mp_compile_to_raw_code(parse_tree, source_file, is_repl, &cm);

    // Create and return a function object that executes the outer module.
    return mp_make_function_from_proto_fun(cm.rc, cm.context, NULL);
}

Kompilator kompiluje kod w czterech przebiegach: zakres, rozmiar stosu, rozmiar kodu oraz emisja. Każdy przebieg uruchamia ten sam kod w języku C na tej samej strukturze danych AST, przy czym za każdym razem obliczane są różne rzeczy na podstawie wyników poprzedniego przebiegu.

Pierwszy przebieg

W pierwszym przebiegu kompilator poznaje znane identyfikatory (zmienne) i ich zakres: globalny, lokalny, domknięty (closed over) itd. W tym samym przebiegu emiter (bytecode’u lub kodu natywnego) oblicza również liczbę etykiet potrzebnych dla emitowanego kodu.

// Compile pass 1.
comp->emit = emit_bc;
comp->emit_method_table = &emit_bc_method_table;

uint max_num_labels = 0;
for (scope_t *s = comp->scope_head; s != NULL && comp->compile_error == MP_OBJ_NULL; s = s->next) {
    if (s->emit_options == MP_EMIT_OPT_ASM) {
        compile_scope_inline_asm(comp, s, MP_PASS_SCOPE);
    } else {
        compile_scope(comp, s, MP_PASS_SCOPE);

        // Check if any implicitly declared variables should be closed over.
        for (size_t i = 0; i < s->id_info_len; ++i) {
            id_info_t *id = &s->id_info[i];
            if (id->kind == ID_INFO_KIND_GLOBAL_IMPLICIT) {
                scope_check_to_close_over(s, id);
            }
        }
    }
    ...
}

Drugi i trzeci przebieg

Drugi i trzeci przebieg obejmują obliczenie rozmiaru stosu Pythona oraz rozmiaru kodu dla bytecode’u lub kodu natywnego. Po trzecim przebiegu rozmiar kodu nie może już się zmienić, w przeciwnym razie etykiety skoków będą nieprawidłowe.

for (scope_t *s = comp->scope_head; s != NULL && comp->compile_error == MP_OBJ_NULL; s = s->next) {
    ...

    // Pass 2: Compute the Python stack size.
    compile_scope(comp, s, MP_PASS_STACK_SIZE);

    // Pass 3: Compute the code size.
    if (comp->compile_error == MP_OBJ_NULL) {
        compile_scope(comp, s, MP_PASS_CODE_SIZE);
    }

    ...
}

Tuż przed drugim przebiegiem następuje wybór typu kodu, jaki ma zostać wyemitowany, którym może być kod natywny lub bytecode.

// Choose the emitter type.
switch (s->emit_options) {
    case MP_EMIT_OPT_NATIVE_PYTHON:
    case MP_EMIT_OPT_VIPER:
        if (emit_native == NULL) {
            emit_native = NATIVE_EMITTER(new)(&comp->compile_error, &comp->next_label, max_num_labels);
        }
        comp->emit_method_table = NATIVE_EMITTER_TABLE;
        comp->emit = emit_native;
        break;

    default:
        comp->emit = emit_bc;
        comp->emit_method_table = &emit_bc_method_table;
        break;
}

Opcja bytecode’u jest domyślna, ale czymś unikalnym, co warto odnotować w przypadku opcji kodu natywnego, jest istnienie kolejnej opcji za pośrednictwem VIPER. Więcej szczegółów na temat adnotacji viper znajduje się w sekcji Emitowanie kodu natywnego.

Istnieje również wsparcie dla wbudowanego kodu asemblera (inline assembly), gdzie instrukcje asemblera są zapisywane jako wywołania funkcji Pythona, ale są emitowane bezpośrednio jako odpowiadający im kod maszynowy. Ten asembler ma tylko trzy przebiegi (zakres, rozmiar kodu, emisja) i wykorzystuje inną implementację, nie funkcję compile_scope. Więcej szczegółów znajduje się w dokumentacji wbudowanego asemblera.

Czwarty przebieg

Czwarty przebieg emituje ostateczny kod, który może zostać wykonany: bytecode w maszynie wirtualnej lub kod natywny bezpośrednio przez procesor.

for (scope_t *s = comp->scope_head; s != NULL && comp->compile_error == MP_OBJ_NULL; s = s->next) {
    ...

    // Pass 4: Emit the compiled bytecode or native code.
    if (comp->compile_error == MP_OBJ_NULL) {
        compile_scope(comp, s, MP_PASS_EMIT);
    }
}

Emitowanie bytecode’u

Instrukcje w kodzie Pythona zwykle odpowiadają emitowanemu bytecode’owi, na przykład a + b generuje „push a”, następnie „push b”, a potem „binary op add”. Niektóre instrukcje nie emitują niczego, lecz zamiast tego wpływają na inne rzeczy, takie jak zakres zmiennych, na przykład global a.

Implementacja funkcji emitującej bytecode wygląda podobnie do tej:

void mp_emit_bc_unary_op(emit_t *emit, mp_unary_op_t op) {
    emit_write_bytecode_byte(emit, 0, MP_BC_UNARY_OP_MULTI + op);
}

Jako przykład posługujemy się tutaj wyrażeniami z operatorem jednoargumentowym, ale szczegóły implementacyjne są podobne dla innych instrukcji/wyrażeń. Metoda emit_write_bytecode_byte() jest opakowaniem (wrapperem) wokół głównej funkcji emit_get_cur_to_write_bytecode(), którą wszystkie funkcje muszą wywołać, aby wyemitować bytecode.

Emitowanie kodu natywnego

Podobnie jak w przypadku generowania bytecode’u, dla każdej instrukcji kodu powinna istnieć odpowiadająca funkcja w py/emitnative.c:

static void emit_native_unary_op(emit_t *emit, mp_unary_op_t op) {
     vtype_kind_t vtype;
     emit_pre_pop_reg(emit, &vtype, REG_ARG_2);
     if (vtype == VTYPE_PYOBJ) {
         emit_call_with_imm_arg(emit, MP_F_UNARY_OP, op, REG_ARG_1);
         emit_post_push_reg(emit, VTYPE_PYOBJ, REG_RET);
     } else {
         adjust_stack(emit, 1);
         EMIT_NATIVE_VIPER_TYPE_ERROR(emit,
             MP_ERROR_TEXT("unary op %q not implemented"), mp_unary_op_method_name[op]);
     }
}

Różnica polega tutaj na tym, że musimy obsłużyć typowanie viper. Adnotacje viper pozwalają nam obsługiwać więcej niż jeden typ zmiennej. Domyślnie wszystkie zmienne są obiektami Pythona, ale dzięki viper zmienna może również zostać zadeklarowana jako zmienna typowana maszynowo, taka jak natywna liczba całkowita lub wskaźnik. Viper można traktować jako nadzbiór Pythona, w którym zwykłe obiekty Pythona są obsługiwane jak zazwyczaj, podczas gdy natywne zmienne maszynowe są obsługiwane w zoptymalizowany sposób poprzez wykorzystanie bezpośrednich instrukcji maszynowych dla operacji. Typowanie viper może naruszać równoważność z Pythonem, ponieważ na przykład liczby całkowite stają się natywnymi liczbami całkowitymi i mogą się przepełnić (w przeciwieństwie do liczb całkowitych Pythona, które automatycznie rozszerzają się do dowolnej precyzji).