Пишем компилятор — Введение

от
Java

Компиляторы — вещь сложная, но принципы его работы достаточно просты.
1. Лексемный разбор — разбор входящего потока символов на лексемы и передача их следующему этапу в виде токенов.
2. Синтаксический разбор — разбор лексем, полученных в предыдущей стадии на синтаксические конструкции
3. Трансляция — формирование кода более низкого уровня из синтаксического дерева, полученного на предыдущей стадии

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

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

Идентификатор (id) — имя некоей области памяти программы, например, переменной, константы, функции. В нашем языке идентификатором будет считаться любое слово, начинающее не с цифры и состоящее из букв и цифр.
Например:
  1. kolyastronk, geegeeMyFriend, secretcode123, p24369ze5

Лексемы — неделимые единицы языка, такие как идентификаторы, зарезервированные слова, управляющие символы, литералы.
Например:
  1. if, kolyastronk, } , “Hey, this is a text, it consists of many spaces and }, (, )

Токены — единицы, построенные из лексем на фазе лексического анализа для передачи синтаксическому анализатору. Для примеров приведённых выше:
  1. <ID, if>, <ID, kolyastronk>, <CLOSING_BRACKET, }>, <QUOTAGE, “Hey, this…”>

Пробелы, разделяющие лексемы в нашем языке значащими являться не будут — выражения
  1. if(     56 +25> 1)      {
и
  1. if (56 + 25 > 1) {
будут в нашем языке идентичны

Выражением в нашем языке будет являться строчка (ниже line). Одна строчка — одно выражение. Язык будет иметь глобальную видимость переменных, позволять определять и вызывать функции, а также иметь базовые управляющие структуры (циклы, условия).

Для простоты разработки в языке не будут поддерживаться некоторые конструкции (например, вычисление выражений внутри условий),которые несложно реализовать самостоятельно.

Комментарии начинаются с символов ‘//’ и продолжаются до конца строчки.

В контекстно-независимой грамматике, которая используется для описания синтаксиса языков программирования используются так называемые продукции. К примеру данная продукция описывает конструкцию if-else в языке Java:
  1. stmt -> if ( expr ) stmt else stmt

Опишу синтаксическую структуру языка:
Открыть спойлер

Небольшой пример на нашем языке:
Открыть спойлер
+9   10   1
2374