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

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

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

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

Идентификатор (id) — имя некоей области памяти программы, например, переменной, константы, функции. В нашем языке идентификатором будет считаться любое слово, начинающее не с цифры и состоящее из букв и цифр.
Например:
Лексемы — неделимые единицы языка, такие как идентификаторы, зарезервированные слова, управляющие символы, литералы.
Например:
Токены — единицы, построенные из лексем на фазе лексического анализа для передачи синтаксическому анализатору. Для примеров приведённых выше:

Пробелы, разделяющие лексемы в нашем языке значащими являться не будут — выражения
и
будут в нашем языке идентичны

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

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

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

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

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

Открыть спойлер

Закрыть спойлер

[копировать] [скачать]

1. line -> stmt |
2.     functioncall |
3.     if_condition |
4.     cycle_for |
5.     cycle_while |
6.     closingbracket
7. stmt -> id = expr
8. expr -> val |
9. val op_binary expr
10. val ->  id |
11. number
12. number -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
13. op_binary -> + | - | * | /
14. functioncall -> id ( args )
15. args -> ∅ |
16.  val |
17.  val , args
18. if_condition -> if ( condition ) {
19. condition -> val | val binary_bool condition
20. binary_bool -> & | | | == | != | < | > | <= | >=
21. cycle_for -> for ( stmt ; condition ; stmt ) {
22. cycle_while -> while ( condition ){
23. closingbracket -> }

Небольшой пример на нашем языке:

Открыть спойлер

Закрыть спойлер

[копировать] [скачать]

1. println ("Hey")
2. //This is a comment
3. e = 3 * 9 + 2
4. if (true == true){              //Can that even not be true?
5.     println("all hail britannia" )
6.     e = 2.71//Not a precise value, of course
7. }
8. println (e)