любой тёмный рыцарь когда-то с чего-то обязательно начался. в случае компиляторов начало, сердце, печень, почки, да и весь прочий ливер — это разбор выражений. и кодогенерация, конечно.
методов для разбора выражений есть куча. много, то есть. мы будем использовать простейший — потому что это… ну, просто. чтобы показать, что я знаю ещё и другие умные слова, упомяну про очень изящный , например, который удобен для создания грамматик в рантайме. или вот ещё забавный , который удобен для преобразования инфиксных выражений в постфиксные.
но нам это всё нафиг не упёрлось (вместе с тяжёлой артиллерией типа flex/bison, или lemon, или peg), диды без этого всего жили, мы тоже проживём.
итак. поскольку мы не будем делать , а будем сразу петь, чо увидим, то всё, что нам надо — это знать, в какой стековый слот (помните прошлый пост? я дальше буду вместо слова «регистр» употреблять слово «слот», он же «стековый слот») в итоге приземлилось наше значение. давайте сначала посмотрим на выхлоп самого глупого кодогенератора для случая, например, «2+3*4»:
Lit r1,2
Lit r2,3
Lit r3,4
Mul r4,r2,r3
Add r5,r1,r4
кодогенератор наш глупый, он не пытается повторно использовать слоты, и не пытается даже делать constant folding. к этому мы вернёмся попозже, а пока пусть будет так.
так вот. как видим, в итоге всей магии результат выражения у нас живёт в слоте r5. также можно заметить, что как только парзер встречает какое-нибудь число (в дальнейшем это может быть переменная, или что-нибудь ещё сложнее), он сразу же выделяет для него слот, и суёт это туда. потому что никаких других вещей кроме «значение из слота N» он не знает. это неоптимально, зато просто в реализации.
итак. выбраный нами парзер весь очень рекурсивный, и его реализация обычно выглядит примерно так:
Value parseExpr () {
return parsePlusMinus();
}
// ничего особенного, просто зовём парзер следующего уровня приоритетов для обоих операндов (если они есть)
Value parsePlusMinus () {
Value lhs = parseMulDiv();
while (token.delim("+") || token.delim("-")) {
OpCode opc = (token.delim("+") ? OpCode.Add : OpCode.Sub);
skipToken();
Value rhs = parseMulDiv();
Value res = allocTempSlot();
emitCode(VMOp(opc, res, lhs, rhs));
lhs = res;
}
return lhs;
}
// и тут то же самое; и во всём коде для двухоперандных операторов то же самое; много, много копипасты
Value parseMulDiv () {
Value lhs = parseUnary();
while (token.delim("*") || token.delim("/")) {
OpCode opc = (token.delim("*") ? OpCode.Mul : OpCode.Div);
skipToken();
Value rhs = parseUnary();
Value res = allocTempSlot();
emitCode(VMOp(opc, res, lhs, rhs));
lhs = res;
}
return lhs;
}
// а вот тут уже интересней
Value parseUnary () {
// просто число
if (token.number) {
Value res = allocTempSlot();
emitLoadLiteral(res, token.ival);
skipToken();
return res;
}
// здесь же обрабатываем скобки
if (token.delim("(")) {
skipToken();
Value res = parseExpr();
if (!token.delim(")")) compileError("')' expected");
skipToken();
return res;
}
// и всякие унарные операции, например "!"
if (token.delim("!")) {
skipToken();
Value rhs = parseUnary(); // а потому что все они имеют одинаковый приоритет, например
Value res = allocTempSlot();
emitCode(VMOp(OpCode.LogNot, res, rhs));
return res;
}
// также тут можно (и нужно) обрабатывать всякие переменные, а также "." и "[]", но это потом
compileError("unexpected shit in expression"); // увы
}
для простоты — поскольку мы не будем повторно использовать слоты — `allocTempSlot()` может просто использовать обычный счётчик слотов, тупо его каждый раз инкрементируя. это у нас, кстати, почти SSA получился, потому что значение в каждый слот заносится ровно один раз. «почти» — потому что вся красота сломается при появлении переходов, где в SSA принято вставлять фиты. но это просто лирическое отступление.
ах, да. `Value` на этом этапе может быть просто синонимом `int`, потому что больше мы в нём ничего не храним. но будем сразу использовать красивый новый тип: попозже мы основательно его расширим, превратив очень плохой кодогенератор в просто плохой.
вы можете сразу в это не поверить, но мы только что написали самую важную часть любого компилятора. почти всё, что мы будем делать в дальнейшем — это обвешивать наш простой и красивый парзер выражений всякими свистелками и перделками, пока он не превратится в монстра, которому будут завидовать финальные боссы из resident evil.
в случае AST мы тут вместо кодогенерации создавали бы AST nodes. в принципе, это лучше в плане того, что парзер проверяет исключительно синтаксис, а всякие там типы и нюансы кодогенерации выделены в отдельную часть. то есть, сначала проверили синтаксис и построили дерево, потом запустили на дереве семантический анализатор, который прописал нужные типы (и проверил на правильность-совместимость типов), а потом — отдельно — кодогенератор на уже заведомо валидном дереве.
именно потому, что части красиво отделены друг от друга, и практически независимы, все нормальные люди делают компиляторы именно с использованием AST. но если бы мы были нормальные, то не сидели бы тут — так что мы будем делать плохо и сложно. потому что хорошо и просто вас научит кто угодно, а плохо и сложно только я (и ещё половина интернетов, но это неважно).
спасибо, что были с нами. оставайтесь на нашем канале, дальше будет только хуже.
дальше она у тебя поднимется ещё больше. потому что будет как я пообещал: хуже и хуже. специфика компилятора без AST — всё перемешано и посредине ананас лежит.
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}
