Kompilátor

Proces kompilace v MicroPythonu zahrnuje následující kroky:

  • Lexer převádí proud textu, který tvoří program v MicroPythonu, na tokeny.

  • Parser poté převede tokeny na abstraktní syntaxi (syntaktický strom).

  • Následně je na základě syntaktického stromu vygenerován bytecode nebo nativní kód.

Pro účely tohoto výkladu přidáme jednoduchou jazykovou konstrukci add1, kterou lze v Pythonu použít takto:

>>> add1 3
4
>>>

Příkaz add1 přijímá jako argument celé číslo a přičte k němu 1.

Přidání gramatického pravidla

Gramatika MicroPythonu vychází z gramatiky CPythonu a je definována v souboru py/grammar.h. Tato gramatika se používá k parsování zdrojových souborů MicroPythonu.

K definici gramatického pravidla je třeba znát dvě makra: DEF_RULE a DEF_RULE_NC. DEF_RULE umožňuje definovat pravidlo s přidruženou kompilační funkcí, zatímco DEF_RULE_NC žádnou kompilační (NC) funkci nemá.

Jednoduchá definice gramatiky s kompilační funkcí pro náš nový příkaz add1 vypadá takto:

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

Druhý argument c(add1_stmt) je odpovídající kompilační funkce, která by měla být implementována v souboru py/compile.c, aby toto pravidlo převedla na spustitelný kód.

Třetí povinný argument může být or nebo and. Ten určuje počet uzlů přidružených k příkazu. Například v tomto případě je náš příkaz add1 podobný instrukci ADD1 v jazyce symbolických adres. Přijímá jeden číselný argument. Proto má add1_stmt přidruženy dva uzly. Jeden uzel je pro samotný příkaz, tj. literál add1 odpovídající tokenu KW_ADD1, a druhý pro jeho argument, pravidlo testlist, což je výrazové pravidlo nejvyšší úrovně.

Poznámka

Pravidlo add1 zde slouží pouze jako příklad a není součástí standardní gramatiky MicroPythonu.

Čtvrtým argumentem v tomto příkladu je token přidružený k pravidlu, KW_ADD1. Tento token by měl být definován v lexeru úpravou souboru py/lexer.h.

Definice téhož pravidla bez kompilační funkce se provede pomocí makra DEF_RULE_NC a vynecháním argumentu s kompilační funkcí:

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

Zbývající argumenty mají stejný význam. Pravidlo bez kompilační funkce musí být explicitně zpracováno všemi pravidly, která mohou toto pravidlo mít jako uzel. Taková NC-pravidla se obvykle používají k vyjádření dílčích částí složité gramatické struktury, kterou nelze vyjádřit jediným pravidlem.

Poznámka

Makra DEF_RULE a DEF_RULE_NC přijímají i další argumenty. Pro podrobné pochopení podporovaných parametrů viz py/grammar.h.

Přidání lexikálního tokenu

Každé pravidlo definované v gramatice by mělo mít přidružený token, který je definován v souboru py/lexer.h. Tento token přidáte úpravou výčtu _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;

Poté také upravte soubor py/lexer.c a přidejte text nového klíčového slova jako literál:

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

Všimněte si, že klíčové slovo je pojmenováno podle toho, jak je chcete mít. Kvůli konzistenci dodržujte odpovídajícím způsobem konvenci pojmenování.

Poznámka

Pořadí těchto klíčových slov v souboru py/lexer.c musí odpovídat pořadí tokenů ve výčtu definovaném v souboru py/lexer.h.

Parsování

Ve fázi parsování parser přebírá tokeny vyprodukované lexerem a převádí je na abstraktní syntaktický strom (AST) neboli syntaktický strom. Implementace parseru je definována v souboru py/parse.c.

Parser také udržuje tabulku konstant pro použití v různých aspektech parsování, podobně jako to dělá tabulka symbolů.

Během této fáze je provedeno několik optimalizací, jako je skládání konstant u celých čísel pro většinu operací, např. logických, binárních, unárních atd., a optimalizační vylepšení u závorek kolem výrazů, spolu s některými optimalizacemi u řetězců.

Stojí za zmínku, že docstringy jsou zahozeny a nejsou kompilátoru přístupné. Na docstringy se nevztahují ani optimalizace jako internování řetězců.

Průchody kompilátoru

Stejně jako mnoho kompilátorů kompiluje MicroPython veškerý kód do bytecodu MicroPythonu nebo do nativního kódu. Funkčnost, která toho dosahuje, je implementována v souboru py/compile.c. Nejdůležitější metoda, kterou byste měli znát, je tato:

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);
}

Kompilátor kompiluje kód ve čtyřech průchodech: rozsah platnosti (scope), velikost zásobníku, velikost kódu a emise. Každý průchod spouští stejný C kód nad stejnou datovou strukturou AST, přičemž se pokaždé počítají jiné věci na základě výsledků předchozího průchodu.

První průchod

V prvním průchodu se kompilátor dozví o známých identifikátorech (proměnných) a jejich rozsahu platnosti, ať už globálním, lokálním, uzavřeném (closed over) atd. Ve stejném průchodu emitor (bytecodu nebo nativního kódu) také vypočítá počet návěští potřebných pro vygenerovaný kód.

// 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);
            }
        }
    }
    ...
}

Druhý a třetí průchod

Druhý a třetí průchod zahrnují výpočet velikosti Python zásobníku a velikosti kódu pro bytecode nebo nativní kód. Po třetím průchodu se velikost kódu již nesmí měnit, jinak budou návěští skoků nesprávná.

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);
    }

    ...
}

Těsně před druhým průchodem dochází k výběru typu kódu, který se má vygenerovat, jímž může být buď nativní kód, nebo 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;
}

Volba bytecodu je výchozí, ale u volby nativního kódu stojí za zmínku jedna specifická věc, a to že existuje další možnost prostřednictvím VIPER. Více podrobností o anotacích viper najdete v sekci Generování nativního kódu.

K dispozici je také podpora inline assembleru, kde se instrukce assembleru zapisují jako volání Python funkcí, ale jsou generovány přímo jako odpovídající strojový kód. Tento assembler má pouze tři průchody (rozsah platnosti, velikost kódu, emise) a používá odlišnou implementaci, nikoli funkci compile_scope. Více podrobností najdete v referenci inline assembleru.

Čtvrtý průchod

Čtvrtý průchod generuje finální kód, který lze spustit, buď jako bytecode ve virtuálním stroji, nebo jako nativní kód přímo procesorem.

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);
    }
}

Generování bytecodu

Příkazy v Python kódu obvykle odpovídají vygenerovanému bytecodu, například a + b generuje „push a“, poté „push b“ a poté „binary op add“. Některé příkazy nic negenerují, ale místo toho ovlivňují jiné věci, jako je rozsah platnosti proměnných, například global a.

Implementace funkce, která generuje bytecode, vypadá podobně jako tato:

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 příklad zde používáme výrazy s unárními operátory, ale podrobnosti implementace jsou pro ostatní příkazy/výrazy podobné. Metoda emit_write_bytecode_byte() je obal kolem hlavní funkce emit_get_cur_to_write_bytecode(), kterou musí pro generování bytecodu volat všechny funkce.

Generování nativního kódu

Podobně jako se generuje bytecode, měla by pro každý příkaz kódu existovat odpovídající funkce v souboru 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]);
     }
}

Rozdíl zde spočívá v tom, že musíme zpracovat viper typování. Anotace viper nám umožňují zpracovávat více než jeden typ proměnné. Ve výchozím nastavení jsou všechny proměnné Python objekty, ale s viperem může být proměnná deklarována také jako strojově typovaná proměnná, například nativní celé číslo nebo ukazatel. Na viper lze nahlížet jako na nadmnožinu Pythonu, kde se běžné Python objekty zpracovávají jako obvykle, zatímco nativní strojové proměnné se zpracovávají optimalizovaným způsobem pomocí přímých strojových instrukcí pro dané operace. Viper typování může narušit ekvivalenci s Pythonem, protože například celá čísla se stávají nativními celými čísly a mohou přetéct (na rozdíl od Python celých čísel, která se automaticky rozšiřují na libovolnou přesnost).