Урок 1: Постановка задачи

Вступление

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

Это введение для первого семестра цикла уроков, в нём мы научимся создавать лицевую часть компилятора, предназначенную для разбора текста программы и трансляции его в представление, пригодное для дальнейшей компиляции. В качестве представлений у нас будут:

Цикл сделан таким образом чтобы читатели с различным уровнем подготовки могли найти его полезным для себя. В первую очередь курс будет полезен студентам, желающим глубже изучить построение компиляторов и попробовать свои силы на практике. Также он будет полезен преподавателям чтобы дополнить свой курс различными деталями. Наконец, курс будет полезен интересующимся специалистам, которые смогут на его основе создать свой предметно-ориентированный язык.

Уроки построены таким образом чтобы в конце каждого к проекту добавлялась небольшая (на сколько это возможно) часть функций, выполняемых компилятором. Чтобы изучать заметки было интересно как начинающим, так и опытным специалистам, они все будут состоять из трёх частей. Во вступлении будет рассказываться что предполагается сделать в рамках данного урока. В итоге будет показываться как должен работать результат. Опытным разработчикам этого вполне достаточно чтобы самостоятельно выполнить всю практическую часть. Для тех кто не знаком с темой компиляторов и инструментами их разработки, в части выполнения будут показаны основные моменты. В конце статьи всегда будет ссылка на эталонный код, однако я рекомендую смотреть в него либо после выполнения задания либо если решение задачи совсем зашло в тупик.

Итак, предлагаю переходить от слов к делу и набросать эскиз языка и вообще понять что мы собираемся делать.

Требования к проекту

Первое что надо сделать перед выполнением проекта - понять что вообще мы собираемся делать. В рамках первого семестра мы делаем лицевую часть компилятора (frontend, англ.), задача которой прочитать текст подаваемой программы, убедиться в его правильности и перевести его в формат, пригодный для дальнейшей компиляции. Если в программе выявлена ошибка, то следует вывести адекватное сообщение, из которого пользователь поймёт где и в чём была проблема.

Язык программирования должен обладать конструкциями сравнений, циклов, вызовов функций. В рамках языка можно использовать целочисленные, логические и символьные данные. Кроме того, необходима поддержка массивов.

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

Выполнение

Общее описание языка

Мы сформулировали требования к создаваемому языку программирования, теперь попробуем неформально представить как будут выглядеть наши программы. Условимся что названием языка программирования будет X. Формальное определение языка мы дадим во время написания синтаксического анализа, а пока что введём основные понятия для общего представления о том что мы делаем.

Программы на языке X состоят из модулей. Модулем будет отдельный файл, в котором могут содержаться объявления и определения функций. Объявление функции - это просто сигнатура функции без её определения (т.е. тела). Оно нужно для того чтобы мы могли использовать вызов функции ещё до того как напишем её содержимое. Определение функции - это непосредственно код функции. Приведём простой пример объявления и определения функций в модуле:

void f1();

void f2(){}

В этом примере функция f1 содержит только объявление, а функция f2 содержит только определение (хотя она ничего не делает).

Далее, поговорим о типах данных в нашей программе. У нас будут допустимы следующие примитивные типы:

Типы данных нужны для объявления переменных и указания типа возврата функций. Рассмотрим их на примерах:

int f1();

bool f2(int a, int b);

void f3() {int c = 0;}

В целом объявления переменных и функций аналогичны таковым в языке Си. От примитивных типов перейдём к составным. В нашем случае составным типом будет являться только массив, для него мы примем следующий синтаксис:

int[10][10] matr; /* Создание двумерного массива 10x10 */

int[][] matr2 = foo(); /* Функция foo возвращает созданный массив, и он записывается в matr2 */

int[][] foo(int[][] a, int[][] b); /* Объявление функции foo, возвращающей созданный массив */

matr[0][0] = 0; /* Присваиваем элементу массива значение */

delete matr; /* Удаляем массив */

В примере мы видим сразу много особенностей работы с массивами, поэтому разберём их. В нашем языке массивы будут всегда динамические. Это означает что программист обязан удалять их самостоятельно при помощи ключевого слова delete. Массивы можно создавать либо сразу с указанием размера, либо как возвращаемое из функции значение. Синтаксис чтения/записи элементов массива идентичен таковому в языке Си.

В качестве управляющей конструкции у нас будет конструкция if-elif-else в различных комбинациях. Выглядеть это будет следующим образом:

if( a == 1 )
{
  smth1();
} elif( b == 2 )
{
  smth2();
} else
{
  smth3();
}

При этом допустимы комбинации if-elif, if-else и просто if. Кроме того в отличие от Си мы не допускаем отсутствия фигурных скобок (и в Си советую его не допускать).

Переходим к циклам. Для циклов мы выполним только конструкцию for, её хватает с избытком, с ней придётся повозиться, но зато это будет весело и удобно.

for(int i = 0; i < 10; i = i + 1)
{
  smth();
}

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

Запускаться программа будет классически из функции main, также мы будем поддерживать комментарии в стиле Си: /* */. В целом это всё неформальное описание языка, которое можно выполнить на бумажке, возможно по ходу работы что-то будет добавляться или меняться.

Итог

Основной итог этого урока - набросок основных конструкций языка и идей на бумажке. Наверное, это самый простой урок, от качественного выполнение которого, тем не менее, зависит сколько работы нам предстоит выполнить в дальнейшем (лично я несколько раз с почти нуля всё переписывал). С большим интересом жду дорогих читателей на следующем уроке!