Hacker News Digest

Краткий обзор компилятора C на 500 строк Python

Автор бросил себе вызов — написать компилятор C за 500 строк Python. Получилось трудно, но рабочий результат.

Архитектура

• Однопроходный: парсинг и генерация кода идут одновременно. AST не строится, экономим строки.
• Цель — WebAssembly: выбор странный (goto нет, стек-VM), но интересный. Пришлось реализовать собственный стек в памяти, т.к. стек WASM нельзя адресовать.

Что вырезали

• switch, do/while, goto, break/continue, enum, union, typedef, const/volatile, static, inline, sizeof, float, double, long, long long, void *, массивы, указатели на функции, структуры в структурах, varargs, макросы, #include, стандартную библиотеку.

Лексер

Регулярки разбивают исходник на токены: ключевые слова, идентификаторы, числа, операторы, строки и символы.

Парсер

Рекурсивный спуск. Пример префиксного ~:

elif lexer.try_next("~"):
    meta = load_result(prefix())
    emit("i32.const 0xffffffff")
    emit("i32.xor")
    mask_to_sizeof(meta.type)
    return meta

Семантика типов

Поддержаны int, char, short, int *, char *, struct. Все сводится к 32-битным целым. Структуры выравниваются по 4 байта.

Управление памятью

• Локальные переменные кладутся в стек.
• Глобальные — в секцию data.
• malloc/free нет, но можно вызвать внешнюю malloc из JS.

Циклы for

Из-за отсутствия goto пришлось генерировать вложенные блоки WebAssembly и использовать br_if для break/continue.

Функции

• Поддерживаются int аргументы и возвращаемые значения.
• Вызовы через call.
• Рекурсия работает.

Сборка и запуск

python compiler.py input.c > output.wat
wat2wasm output.wat -o output.wasm
node run.js output.wasm

Итог

500 строк Python компилируют подмножество C в WASM. Код читаемый, эксперимент удался.