IBMForever,
Что такое AST.Как работают однопроходные компиляторы (на примере моей реализации).Однопроходный компилятор - самый простой по своему устройству. Он проходит по исходнику, превращает его в массив токенов (это делает лексер), а затем проходится по этому массиву и генерирует машинный код (или байт-код), записывая его в файл (парсер).
Токен - это стуктура, состоящая из двух полей: типа и значения.
Разберём работу компилятора на простенькой программе.
- Код: Выделить всё
typedef enum TokenType {
LCALL, // вызов нативной функции, @
NUMBER, // число
STRING, // строка
ID, // например, имя переменной и т.д.
ASSIGN, // =
LPAREN, // {
RPAREN, // }
LBRACE, // (
RBRACE, // )
... // и т.д. и т.п.
};
typedef struct {
TokenType type;
char *value;
} Token;
Например, есть у нас такая программка:
- Код: Выделить всё
@println(123)
После лексера массив токенов:
type=LCALL, value="@"
type=ID, value="println"
type=LBRACE, value="("
type=NUMBER, value="123"
type=RBRACE, value=")"
То есть лексер, как бы обезличивает исходый код и превращает его в плотный массив токенов, над которым собственно парсер уже спокойно работает, и парсеру уже не надо возиться с пробелами, отсупами и прочим.
Затем по этому массиву токенов проходит парсер.
Он видит токен с типом LCALL, получает следующий токен (ID), записывает его в образ кучи, получает следующий токен, убеждается, что он является LBRACE, (если нет - опять-таки ошибка), увеличивает указатель на текущий токен, он указывает уже на 5, затем он вызывает функцию par_parExpr(), которая парсит арифметические выражения, результат уже лежит в байт-коде, и осталось только добавить в массив байт-кода вызов нативной функции.
Делается это так:
- Код: Выделить всё
par_render(a, (Vm){CALL, selszu(АДРЕС_ИМЕНИ_НАТИВНОЙ_БИБЛИОТЕКИ_И_ФУНКЦИИ_В_НЕЙ_В_КУЧЕ), АДРЕС_ИМЕНИ_НАТИВНОЙ_БИБЛИОТЕКИ_И_ФУНКЦИИ_В_НЕЙ_В_КУЧЕ);
Ну а потом парсер завершает свою работу и начинает работать функция par_free(), которая уже записывает в .cvm-файлик весь массив байт-кода одним махом. ПОтом файлик закрывается, вызывается free() для всего, что надо очистить, и компилятор завершается. Свою работу он сделал.
А теперь разберём, как работает AST.Первый проход - построение синтаксического дерева. Для этой программы оно будет выглядеть так:
- Код: Выделить всё
Program
|--- Statement (CALL)
|--- FunctionName: "println"
|--- Arguments:
|--- Expression (Literal)
|--- Value: "123"
|--- Type: Integer
Второй проход - это генерация байт-кода.
Главная функция - codegen().
Она видит узел Program и... вызывает сама себя на его единственного "ребёнка" - Statement.
Она записывает в кучу FunctionName, сохраняет его смещение в куче... но пока не пишет CALL в байт-код, а вызывает сама себя на Arguments.
В Arguments она снова вызывает сама себя на Expression, а потом рендерит в байт-код:
- Код: Выделить всё
PUSH INT|1 123
(1 - это минимальное количество байт, необходимых для умещения этого числа. В данном случае, 123 входит в диапазон -128 - 127 и поэтому ей хватает одного байта).
После чего эта функция завершается и...
Вспомните: а кто её вызывал?
Правильно, она сама, при обработке Arguments. Потом она так же входит из Arguments, попадает в Statement, и тут-то и рендерится вызов нативки.
Потом она выходит в Program, и... всё! Работа парсера окончена!
P.S. Насчёт подпрограмм на Си - AST с этим никак не связан. Нет.
Но можно написать динамическую библиотеку с функциями (т.е. как раз подпрограммами) на Си, добавить её в imports-table.txt и вызывать через
- Код: Выделить всё
@ИМЯ_ФУНКЦИИ(АРГУМЕНТЫ)
