На одной из конференций я наблюдал, как наши коллеги реализовывали тернарный оператор в Go с помощью комментариев. Доклад длился всего минут 10, и, честно говоря, я не смог уловить ничего внятного, кроме того, что ребята явно хорошо повеселились. Однако это вдохновило меня разобраться, как работает компилятор Go под капотом. А лучший способ разобраться — это попробовать написать что-то своё.

Самым простым и понятным для меня в этом плане показалась реализация цикла while. В этой статье я покажу, что у меня получилось выяснить. Вот примерный результат, к которому мы придём:

alek.dmitriev@alek-dmitriev src % cat ../../main.go
package main

import ("fmt")

func main() {
        x := 0

        while x < 10 {
                fmt.Println(x)
                x++
        }
}

alek.dmitriev@alek-dmitriev src % ../bin/go run ../../main.go
0
1
2
3
4
5
6
7
8
9

Немного теории о компиляторах

Дисклеймер: Я не профессиональный разработчик компиляторов и не преподаватель информатики. Я monkey-кодер на Go, который решил разобраться в теме и поделиться своими находками. Если в статье вы найдёте неточности или ошибки, пожалуйста, дайте знать в комментариях — я буду рад исправить их и не ввести никого в заблуждение. В конце концов, мы все здесь учимся!

Компиляторы — это программы, которые переводят исходный код, написанный на языке программирования высокого уровня, в машинный код или промежуточное представление, которое может быть выполнено компьютером. Процесс компиляции обычно состоит из нескольких этапов, каждый из которых выполняет определённую задачу:

Основные этапы работы компилятора Go

1. Лексический анализ (Lexical Analysis)
   Компилятор начинает с разбиения исходного кода на токены — минимальные значимые элементы, такие как ключевые слова (if, for, func), идентификаторы (имена переменных и функций), операторы (+, -, =) и т.д. Например, строка x := 10 + y разбивается на токены: x, :=, 10, +, y.

2. Синтаксический анализ (Parsing)
   На этом этапе токены преобразуются в абстрактное синтаксическое дерево (AST). AST — это древовидная структура, которая отражает логическую структуру программы. Например, выражение x := 10 + y превращается в дерево, где := — корневой узел, x — левый потомок, а + — правый потомок с дочерними узлами 10 и y.

3. Семантический анализ (Semantic Analysis)
   Компилятор проверяет, корректна ли программа с точки зрения языка: правильно ли используются типы данных, объявлены ли переменные, соответствуют ли вызовы функций их сигнатурам и т.д. Например, если вы попытаетесь сложить строку и число, компилятор выдаст ошибку.

4. Генерация промежуточного представления (Intermediate Representation, IR)
   Go использует собственное промежуточное представление, называемое SSA (Static Single Assignment). SSA — это низкоуровневое представление кода, где каждая переменная присваивается только один раз. Это упрощает оптимизацию и анализ кода. Например, цикл for может быть преобразован в последовательность инструкций SSA.

5. Оптимизация
   На этом этапе компилятор пытается улучшить код, чтобы он работал быстрее или использовал меньше ресурсов. Go применяет множество оптимизаций, таких как удаление мёртвого кода (dead code elimination), инлайнинг функций (inlining) и упрощение выражений. Например, если компилятор видит, что переменная не используется, он может удалить её из кода.

6. Генерация машинного кода
   Финальный этап — преобразование промежуточного представления в машинный код, специфичный для целевой платформы (например, x86, ARM). Go компилятор генерирует нативный код, который может быть напрямую выполнен процессором. Это делает программы на Go быстрыми и эффективными.

7. Сборка и линковка
   После генерации машинного кода компилятор создаёт исполняемый файл, объединяя скомпилированный код с необходимыми библиотеками (например, стандартной библиотекой Go).

Обычно компилятор разделяют на две основные части: frontend и backend.

• Backend занимается генерацией машинного кода, оптимизацией программы и выбором инструкций процессора. Это включает преобразование промежуточного представления (например, SSA) в машинный код, применение различных оптимизаций (например, удаление мёртвого кода или инлайнинг функций) и адаптацию кода под конкретную архитектуру процессора.

• Frontend отвечает за разбор и анализ исходного кода. Сюда входят лексический и синтаксический анализ, построение абстрактного синтаксического дерева (AST), а также семантический анализ. Фронтенд проверяет, корректно ли написан код с точки зрения языка, и подготавливает его для дальнейшей обработки. Т.e. все до 4-го пункта включительно. Он-то нам и нужен.

Следовательно примерно как-то так будет выглядить наше AST c циклом while:

func main() {
    var a, b int
  
    while b != 0 {
        if a > b {
            a = a - b
        } else {
            b = b - a
        }
    }

    return a
}

Краткий план:

Исходя из теории о работе компилятора написанной выше, вот план, что нужно сделать, чтобы добавить оператор while в Go:

1. Добавить токен while для лексического анализа

2. Добавить поддержку while в синтаксический анализатор (parser)

3. Добавим семантический анализ для while

4. Преобразуем while в промежуточное представление (SSA)

5. Скомпилируем и протестируем.

Но для начала прежде чем его реализовывать давайте склонируем себе компилятор Go и переключимся на актуальную версию, для этого введем:

git clone https://github.com/golang/go.git
git checkout release-branch.go1.24

Реализация компилятора GO находится в src/cmd/compile/internal относительно корня репозитория. Переходим туда, все пути будут указаны относительно этой директории:

cd go/src/cmd/compile/internal

1. Добавляем токен while для лексического анализа. (/syntax)

Для добавления токена while переходим в /syntax тут лежит логика для работы с лексическим анализом. Все что нам нужно от этого пакета, чтобы он понял наш новый синтаксис. Добавим токен, прописав его в /syntax/tokens.go:

	_For         
	_While       // while
	_Func        
	_Go         

Комментарий справа важен, так как он используется для идентификации токена в коде программы. Это становится возможным благодаря процессу кодогенерации. Пакет stringer автоматически генерирует методы String() для типов, что позволяет преобразовывать значения токенов в их строковое представление:

go install golang.org/x/tools/cmd/stringer

И перегенерируем /syntax/token_string.go:

go generate tokens.go

Мы должны увидеть в нем примерно следующее:

	_ = x[_For-31]
	_ = x[_While-32] -> While сгенерировался
	_ = x[_Func-33]
	_ = x[_Go-34]

2. Добавляем поддержку токена в синтаксический анализатор.

Nodes.go

Теперь, когда мы добавили токен while, нужно создать структуру (ноду), которая будет представлять этот новый синтаксический элемент в абстрактном синтаксическом дереве (AST). Для этого мы можем взять за основу структуру цикла for и адаптировать её под while. Переходим в файл /syntax/nodes.go и пишем структуру:

	WhileStmt struct {
		Init SimpleStmt
		Cond Expr
		Post SimpleStmt
		Body *BlockStmt
		stmt
	}

• Cond — это условие, которое проверяется на каждой итерации цикла.

• Body — это блок кода, который выполняется, пока условие истинно.

• Init и Post оставлены для совместимости с существующими структурами, хотя в while они обычно не используются.

Parser.go

Теперь, когда у нас есть структура WhileStmt, нужно добавить функцию в парсер, которая будет распознавать и разбирать цикл while. Для этого мы переходим в файл /syntax/parser.go и добавляем новую функцию whileStmt.

1. Добавляем функцию whileStmt

Эта функция будет вызываться, когда парсер встречает ключевое слово while. Она создаёт экземпляр WhileStmt и заполняет его поля.

func (p *parser) whileStmt() Stmt {
	if trace {
		defer p.trace("whileStmt")()
	}

	s := new(WhileStmt)
	s.pos = p.pos()

	s.Init, s.Cond, _ = p.header(_While)
	s.Body = p.blockStmt("while clause")

	return s
}

2. Интеграция с парсером

Теперь нужно обновить логику парсера, чтобы он вызывал функцию whileStmt при встрече токена While. Для этого находим в парсере место, где обрабатываются операторы (например, if, for, switch), и добавляем проверку на While.

func (p *parser) stmtOrNil() Stmt {
    case _While:
  		return p.whileStmt()
  
  ...

}

Positions.go

В компиляторе Go важно отслеживать позиции элементов в исходном коде для корректной обработки ошибок, отладки и генерации кода. Для этого используется структура Pos и методы, такие как EndPos(n Node), которые позволяют определить начальную и конечную позицию узла в AST.

В EndPos реализуем кейс с While, который вернет конец структуры, т.e. Body:

func EndPos(n Node) Pos {

  ...

    case *WhileStmt:
			m = n.Body

  ...

}

Walk.go

В компиляторе Go обход абстрактного синтаксического дерева (AST) выполняется с помощью функции walk. Этот механизм используется для анализа и преобразования узлов AST, например, для проверки типов, оптимизации или генерации кода. Чтобы добавить поддержку нового оператора while, нужно обновить логику обхода AST в файле syntax/walk.go.

func (w walker) node(n Node) {
  ,,,
    case *WhileStmt:
		if n.Init != nil {
			w.node(n.Init)
		}
		if n.Cond != nil {
			w.node(n.Cond)
		}
		if n.Post != nil {
			w.node(n.Post)
		}
		w.node(n.Body)
  ...
  }

На этом этапе мы успешно завершили работу с лексическим анализатором. Теперь наш кастомный компилятор умеет распознавать ключевое слово while в исходном коде и преобразовывать его в соответствующий токен. Следующий шаг — проверка семантики языка, чтобы убедиться, что новый синтаксис корректно интегрируется в существующие правила и не нарушает их.

2.5 Подготовка к семантическому анализу(/noder)

Пакет /noder отвечает за преобразование AST (абстрактного синтаксического дерева) в универсальное представление, которое используется для дальнейшего анализа и генерации кода. Основные задачи /noder:

• Преобразование AST в узлы (nodes)
  AST, созданное парсером, может быть специфичным для конкретного синтаксиса. Пакет /noder преобразует его в более универсальное представление, которое легче анализировать и оптимизировать.

• Подготовка к семантическому анализу
  Пакет /noder подготавливает AST для проверки типов и других семантических правил, которые выполняются в пакете /types2.

• Интеграция с /ir
  После семантического анализа AST передаётся в пакет /ir для преобразования в промежуточное представление (SSA)

reader.go

Файл noder/reader.go в пакете noder отвечает за чтение и преобразование AST в универсальное представление, которое используется для дальнейшего анализа и генерации кода. Это ключевой компонент, который связывает парсер (создающий AST) с семантическим анализатором (/types2) и генератором промежуточного представления (/ir). Напишем код, который будет отвечать за чтение и преобразование while в IR:

func (r *reader) whileStmt(label *types.Sym) ir.Node {
	r.Sync(pkgbits.SyncForStmt)

	r.openScope()

	if r.Bool() {
		pos := r.pos()
		rang := ir.NewRangeStmt(pos, nil, nil, nil, nil, false)
		rang.Label = label

		names, lhs := r.assignList()
		if len(lhs) >= 1 {
			rang.Key = lhs[0]
			if len(lhs) >= 2 {
				rang.Value = lhs[1]
			}
		}
		rang.Def = r.initDefn(rang, names)

		rang.X = r.expr()
		if rang.X.Type().IsMap() {
			rang.RType = r.rtype(pos)
		}
		if rang.Key != nil && !ir.IsBlank(rang.Key) {
			rang.KeyTypeWord, rang.KeySrcRType = r.convRTTI(pos)
		}
		if rang.Value != nil && !ir.IsBlank(rang.Value) {
			rang.ValueTypeWord, rang.ValueSrcRType = r.convRTTI(pos)
		}

		rang.Body = r.blockStmt()
		rang.DistinctVars = r.Bool()
		r.closeAnotherScope()

		return rang
	}

	pos := r.pos()
	init := r.stmt()
	cond := r.optExpr()
	post := r.stmt()
	body := r.blockStmt()
	perLoopVars := r.Bool()
	r.closeAnotherScope()

	if ir.IsConst(cond, constant.Bool) && !ir.BoolVal(cond) {
		return init // simplify "for init; false; post { ... }" into "init"
	}

	stmt := ir.NewWhileStmt(pos, init, cond, post, body, perLoopVars)
	stmt.Label = label
	return stmt
}

writer.go

Файл noder/writer.go отвечает за генерацию кода или сериализацию универсального представления программы. Чтобы добавить поддержку while, добавим обработку кейсов:

func (w *writer) stmt1(stmt syntax.Stmt) {
    case *syntax.WhileStmt:
		w.Code(stmtFor)
		w.whileStmt(stmt)
}

И реализацию функции:

func (w *writer) whileStmt(stmt *syntax.WhileStmt) {
	w.Sync(pkgbits.SyncForStmt)
	w.openScope(stmt.Pos())

	if rang, ok := stmt.Init.(*syntax.RangeClause); w.Bool(ok) {
		w.pos(rang)
		w.assignList(rang.Lhs)
		w.expr(rang.X)

		xtyp := w.p.typeOf(rang.X)
		if _, isMap := types2.CoreType(xtyp).(*types2.Map); isMap {
			w.rtype(xtyp)
		}
		{
			lhs := syntax.UnpackListExpr(rang.Lhs)
			assign := func(i int, src types2.Type) {
				if i >= len(lhs) {
					return
				}
				dst := syntax.Unparen(lhs[i])
				if name, ok := dst.(*syntax.Name); ok && name.Value == "_" {
					return
				}

				var dstType types2.Type
				if rang.Def {
					// For `:=` assignments, the LHS names only appear in Defs,
					// not Types (as used by typeOf).
					dstType = w.p.info.Defs[dst.(*syntax.Name)].(*types2.Var).Type()
				} else {
					dstType = w.p.typeOf(dst)
				}

				w.convRTTI(src, dstType)
			}

			keyType, valueType := types2.RangeKeyVal(w.p.typeOf(rang.X))
			assign(0, keyType)
			assign(1, valueType)
		}

	} else {
		if stmt.Cond != nil && w.p.staticBool(&stmt.Cond) < 0 { // always false
			stmt.Post = nil
			stmt.Body.List = nil
		}

		w.pos(stmt)
		w.stmt(stmt.Init)
		w.optExpr(stmt.Cond)
		w.stmt(stmt.Post)
	}

	w.blockStmt(stmt.Body)
	w.Bool(w.distinctVarsWhile(stmt))
	w.closeAnotherScope()
}

func (w *writer) distinctVarsWhile(stmt *syntax.WhileStmt) bool {
	lv := base.Debug.LoopVar
	fileVersion := w.p.info.FileVersions[stmt.Pos().Base()]
	is122 := fileVersion == "" || version.Compare(fileVersion, "go1.22") >= 0
	return is122 || lv > 0 && lv != 3
}

3. Проверка семантики (/types2)

Семантический анализ нашего кода происходит в /types2 директории. Переходим в файл /types2/stmt.go и находим функцию stmt, она отвечает за проверку корректности statements (операторов) в Go. Добавим сюда наш While:

// stmt typechecks statement s.
func (check *Checker) stmt(ctxt stmtContext, s syntax.Stmt) {
  ...
	case *syntax.WhileStmt:
		inner |= breakOk | continueOk

		check.openScope(s, "while")
		defer check.closeScope()

		check.simpleStmt(s.Init)
		if s.Cond != nil {
			var x operand
			check.expr(nil, &x, s.Cond)
			if x.mode != invalid && !allBoolean(x.typ) {
				check.error(s.Cond, InvalidCond, "non-boolean condition in while statement")
			}
		}
		check.stmt(inner, s.Body)
  ...
}

1. Установка флагов breakOk и continueOk

inner |= breakOk | continueOk

• breakOk и continueOk — это флаги, которые указывают, что внутри текущего оператора допустимы break и continue.

• Для цикла while эти флаги устанавливаются, так как внутри цикла можно использовать break для выхода из цикла и continue для перехода к следующей итерации.

2. Открытие новой области видимости

check.openScope(s, "while")
defer check.closeScope()

• Каждый цикл while создаёт новую область видимости для переменных, объявленных внутри него.

• check.openScope открывает новую область видимости, а defer check.closeScope() гарантирует, что область видимости будет закрыта после завершения проверки цикла.

3. Проверка инициализации (если есть)

check.simpleStmt(s.Init)

• Если в цикле while есть инициализация (например, while x := 0; x < 10 { ... }), она проверяется с помощью check.simpleStmt.

• В случае while инициализация обычно отсутствует, поэтому s.Init чаще всего будет nil.

4. Проверка условия цикла

if s.Cond != nil {
    var x operand
    check.expr(nil, &x, s.Cond)
    if x.mode != invalid && !allBoolean(x.typ) {
        check.error(s.Cond, InvalidCond, "non-boolean condition in while statement")
    }
}

• Проверяется, что условие цикла (s.Cond) существует и является корректным выражением.

• check.expr анализирует выражение и записывает результат в переменную x типа operand.

• Если тип выражения x.typ не является булевым (!allBoolean(x.typ)), выводится ошибка: "non-boolean condition in while statement".

5. Проверка тела цикла

check.stmt(inner, s.Body)

• Тело цикла (s.Body) проверяется рекурсивно с помощью check.stmt.

• Внутри тела цикла могут быть другие операторы, включая вложенные циклы, условия и т.д.

4. Преобразование в IR (/ir)

node.go

В файле ir/node.go определяются типы узлов промежуточного представления (IR), которые используются компилятором Go для представления различных конструкций языка на этапе оптимизации и генерации кода. Добавление константы OWHILE и других необходимо для того, чтобы компилятор мог корректно обрабатывать соответствующие конструкции языка. Добавим OWHILE в ir/node.go:

	OFOR      // for Init; Cond; Post { Body }
	OWHILE    // while Init; Cond; Post { Body }
	OGOTO     // goto Label
	OIF       // if Init; Cond { Then } else { Else }

fmt.go

Файл ir/fmt.go отвечает за форматирование узлов IR в текстовый формат.  Добавим туда OWHILE:

	OFOR:              "for",
	OWHILE:            "while",
	OGE:               ">=",
	OGOTO:             "goto",

stmt.go

Создадим функцию NewWhileStmt в файле ir/stmt.go отвечает за создание нового узла промежуточного представления (IR) для цикла while. Этот узел используется компилятором Go для представления цикла while на этапе оптимизации и генерации кода.

// A WhileStmt is a non-range for loop: for Init; Cond; Post { Body }
type WhileStmt struct {
	miniStmt
	Label        *types.Sym
	Cond         Node
	Post         Node
	Body         Nodes
	DistinctVars bool
}

func NewWhileStmt(pos src.XPos, init Node, cond, post Node, body []Node, distinctVars bool) *WhileStmt {
	n := &WhileStmt{Cond: cond}
	n.pos = pos
	n.op = OWHILE
	if init != nil {
		n.init = []Node{init}
	}
	n.Body = body
	n.DistinctVars = distinctVars
	return n
}

node_gen.go

После внесения изменений в файл ir/node.go (например, добавление нового типа узла OWHILE для цикла while), необходимо обновить сгенерированный код, чтобы компилятор мог корректно работать с новыми изменениями. Для этого выполняются команды:

go generate node.go
go run mknode.go

После чего в файле ir/node.go мы можем найти функции для работы с нашим узлом while:

func (n *WhileStmt) Format(s fmt.State, verb rune) { fmtNode(n, s, verb) }
func (n *WhileStmt) copy() Node {
	c := *n
	c.init = copyNodes(c.init)
	c.Body = copyNodes(c.Body)
	return &c
}
func (n *WhileStmt) doChildren(do func(Node) bool) bool {
	if doNodes(n.init, do) {
		return true
	}
	if n.Cond != nil && do(n.Cond) {
		return true
	}
	if doNodes(n.Body, do) {
		return true
	}
	return false
}
func (n *WhileStmt) doChildrenWithHidden(do func(Node) bool) bool {
	if doNodes(n.init, do) {
		return true
	}
	if n.Cond != nil && do(n.Cond) {
		return true
	}
	if doNodes(n.Body, do) {
		return true
	}
	return false
}
func (n *WhileStmt) editChildren(edit func(Node) Node) {
	editNodes(n.init, edit)
	if n.Cond != nil {
		n.Cond = edit(n.Cond).(Node)
	}
	editNodes(n.Body, edit)
}
func (n *WhileStmt) editChildrenWithHidden(edit func(Node) Node) {
	editNodes(n.init, edit)
	if n.Cond != nil {
		n.Cond = edit(n.Cond).(Node)
	}
	editNodes(n.Body, edit)
}

5. Обход узлов IR (/walk)

Функция Walk в компиляторе Go используется для рекурсивного обхода узлов промежуточного представления (IR). Это важный механизм, который позволяет компилятору анализировать и преобразовывать IR на этапах оптимизации и генерации кода, поэтому давайте научим его взаимодействовать с нашей новой нодой. Переходим в walk/order.go и обрабатываем новый кейс с while в функции stmt которая гарантирует выполнение операторов в правильном порядке:

func (o *orderState) stmt(n ir.Node) {
  ...
    case ir.OWHILE:
		n := n.(*ir.WhileStmt)
		t := o.markTemp()
		n.Cond = o.exprInPlace(n.Cond)
		orderBlock(&n.Body, o.free)
		n.Post = orderStmtInPlace(n.Post, o.free)
		o.out = append(o.out, n)
		o.popTemp(t)
  ...
}

После чего идем в walk/stmt.go и добавляем кейс ноды While для прохода по IR и применения функции преобразования:

func walkStmt(n ir.Node) ir.Node {
  ...
	case ir.OWHILE:
		n := n.(*ir.WhileStmt)
		return walkWhile(n)
  ...
}

func walkWhile(n *ir.WhileStmt) ir.Node {
	if n.Cond != nil {
		init := ir.TakeInit(n.Cond)
		walkStmtList(init)
		n.Cond = walkExpr(n.Cond, &init)
		n.Cond = ir.InitExpr(init, n.Cond)
	}

	n.Post = walkStmt(n.Post)
	walkStmtList(n.Body)
	return n
}

Компиляция компилятора

Отлично! После всех манипуляций с кодом компилятора, мы готовы скомпилировать ваш кастомный компилятор Go и протестировать его. Кратко пройдёмся по шагам:

1. Переходим в директорию исходного кода Go:

   cd /go/src

2. Запускаем скрипт сборки

   ./make.bash

   Этот скрипт:

   • Скомпилирует ваш кастомный компилятор.

   • Соберёт стандартную библиотеку Go.

   • Установит компилятор в директорию go/bin/

Тестируем

Можем протестировать наш компилятор на программе из начала статьи

alek.dmitriev@alek-dmitriev src % cat ../../main.go
package main

import ("fmt")

func main() {
        x := 0

        while x < 10 {
                fmt.Println(x)
                x++
        }
}

alek.dmitriev@alek-dmitriev src % ../bin/go run ../../main.go
0
1
2
3
4
5
6
7
8

Итого

Хотя добавление цикла while в Go не имеет практического применения (ведь цикл for уже покрывает все необходимые сценарии), для меня этот эксперимент оказался крайне полезным. Он позволил глубже понять, как устроен компилятор Go, и разобраться в его внутренней работе.