Компиляция. 1: лексер

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

Первые посты серии уже подготовлены, и бета-тестировались в одном маленьком и наглухо закрытом сообществе. Тем не менее, я буду продолжать их править с учётом пожеланий почтенной хабрапублики.

Далее в посте:

1. С какой стати писать компиляторы?
2. Общий план
3. Анализ текста
4. Практический пример
5. Как это работает?

С какой стати писать компиляторы?

Разве не все нужные языки программирования уже написаны? Кому в наш просвещённый век может понадобиться писать собственный компилятор?

Everything that can be invented has been invented.
--Charles H. Duell, Director of U.S. Patent Office, 1899 (attributed)

Что было, то и будет; и что делалось, то и будет делаться, и нет ничего нового под солнцем.
--Екклесиаст 1:9 (ок. 3 в. до н.э.)

Во-первых, языки постоянно создаются и развиваются. Из ныне популярных, Ruby, PHP, Java и C# были созданы на нашей памяти, а бурно применяться начали несколько лет назад. Прямо сейчас Майкрософт проталкивает новый язык F#, и он — учитывая мощь Майкрософт — наверняка также войдёт в число общеупотребимых.
До сих пор остаются ниши для новых языков: например, не прекращаются попытки придумать удобный императивный язык для параллельного программирования.

Во-вторых, используемые в компиляции приёмы (в первую очередь, парсинг по грамматике) имеют массу других приложений. Часто есть потребность в преобразованиях source-to-source (рефакторинг, перевод кода на другой язык, и т.п.), когда нужно разобрать текст на языке программирования, обработать его, и вывести обработанный текст (на том же или на другом языке).

Безусловно, компиляция — довольно экзотичное занятие для программиста, где-нибудь в одном ряду с программированием огромных боевых человекоподобных роботов. Однако у всего этого есть практические применения, в отличие от многих других экстравагантных программистских хобби.

Общий план

Процесс компиляции, в принципе, состоит из двух основных этапов:

1. Анализ текста на исходном языке
2. Генерация машинного кода

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

Самая challenging часть компилятора — оптимизация кода; на первом этапе выполняется высокоуровневая оптимизация, на уровне узлов дерева (например, разворачиваются циклы, вживляются inline-функции); на втором — низкоуровневая, на уровне потока команд (например, переупорядочиваются так, чтобы полнее нагрузить конвейеры конкретного процессора). До оптимизаций, по традиции, в вузовских курсах дело никогда не доходит; но самые простые (copy elimination, constant propagation) мы в нашем примере постараемся реализовать.

Старые посты на тему синтаксического разбора я на Хабре видел; но к генерации кода, вроде бы, авторы не приближались ни разу.

Анализ текста

Когда начинающий программист пытается написать парсер текста, его естественный подход — рекурсивное углубление: найти начало конструкции (например, {); найти её конец (например, } на том же уровне вложенности); выделить содержимое конструкции, и пропарсить её рекурсивно.

Проблемы с таким подходом — во-первых, избыточная сложность (по одному и тому же фрагменту текста гуляем взад-вперёд); во-вторых, неудобство поддержки (синтаксис языка оказывается рассредоточен по килобайтам и килобайтам ветвистого кода).

Синтаксис языка можно задать декларативно; например, всем знакомы регулярные выражения. Идеально было бы написать стопочку регэкспов для всех конструкций языка, напротив каждого — определение узла, который должен создаться в дереве программы; «универсальный парсер» бы просто подставлял программу в один регэксп за другим, и создавал узлы согласно описанию, один за другим.

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

Практический пример

Упомянутый «универсальный парсер», конечно же, давно реализован, и не одиножды. Классическая реализация — lex — принимает описания действий для каждого регэкспа на Си. В стандартные утилиты GNU входит flex, совместимый с lex, — его мы и будем использовать для примеров. (Есть аналогичные утилиты для C#, Java и пр.)

По традиции, первым примером станет написание калькулятора:

%{
    #include <stdio.h>
    int reg = 0;
    char op = '+';
    int unmin = 0;
%}

%option main
%option yylineno

%%

[/][/].*\n      ; // comment
[0-9]           { int opnd = atoi(yytext);
                  if (unmin) opnd =- opnd; unmin=0;
                  switch(op) {
                    case '+': reg += opnd; break;
                    case '-': reg -= opnd; break;
                    case '*': reg *= opnd; break;
                    case '/': reg /= opnd; break;
                  }
                  op = 0;
                }
[-+*/]          { if (op) {
                    if (*yytext=='-')
                      unmin = 1;
                    else {
                      printf("Unexpected operator in line %d\n", yylineno);
                      exit(1);
                    }
                  } else
                    op = *yytext;
                }
[;]             { if (op) {
                    printf("Unexpected semicolon in line %d\n", yylineno);
                    exit(1);
                  }
                  printf("=%d\n", reg);
                  reg = 0;
                  op = '+';
                }
[ \t\r\n]       ; // whitespace
.               { printf("Syntax error in line %d\n", yylineno); exit(1); }
%%

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

Скомпилируем наш калькулятор, и попробуем с ним поиграть:
[tyomitch@home ~]$ lex 1.lex
[tyomitch@home ~]$ cc lex.yy.c
[tyomitch@home ~]$ ./a.out
2+2;
=4
2+2*2;
=8
2 + // hello
- 3
;
=-1
2 / /
Unexpected operator in line 6


Разбор кода

• Вверху, в тегах %{ %}, идёт код, который скопируется напрямик в парсер. Объявляем три переменные: reg («регистр») для промежуточного результата, op для набранной операции, и unmin — флаг, что был набран минус после знака операции, и он должен трактоваться как знак второго операнда.
• %option main указывает, что нас устроит стандартная main (которая читает с stdin до EOF). %option yylineno создаёт в парсере переменную int yylineno, где будет храниться номер текущей строки входного текста: он пригодится для диагностических сообщений.
• %% разделяет область объявлений и область собственно правил языка
• В каждом правиле слева пишется регэксп, справа — код на Си. В первом регэкспе код пуст; т.е. такая конструкция (а это коммментарий) будет просто игнорироваться. Аналогично, предпоследнее правило предписывает игнорировать пробелы и переводы строк между распознаваемыми конструкциями.
• Во втором правиле пользуемся переменной yytext: в ней хранится совпавший с регэкспом текст (в нашем случае, число-операнд)
• В третьем правиле — пример обработки ошибки в тексте программы (используем yylineno в тексте сообщения)
• Правила пробуются в порядке их появления, от первого к последнему. Если ни одно не подошло, парсер просто напечатает текущий символ в stdout. Вместо этого, мы добавляем последним правилом . — оно подойдёт к любому символу, и напечатает сообщение об ошибке.

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

Как это работает?

У математиков есть понятие ДКА (детерминированный конечный автомат) — штука, которая может находиться в одном из N состояний; которая читает из входного потока символ за символом; и у которой есть таблица: для каждого сочетания текущего состояния и прочитанного символа — в которое состояние перейти. Работа flex заключается в том, что он строит ДКА по заданному набору регэкспов; в некоторых состояниях этот ДКА не только переходит в следующее, но вдобавок вызвает наши правила.

Увидеть построенный ДКА можно, заглянув внутрь сгенерированного парсера lex.yy.c. Потребовалось 15 состояний. Для экономии места, таблица переходов хранится не в явном виде (размером 15х256), а разбитая на мудрёные накладывающиеся списки. Чтобы увидеть её в наиболее наглядной форме, скомпилируем парсер с опцией -Cef («отключить сжатие таблиц»):

static yyconst short yy_nxt[][8] =
    {
    {    0,    0,    0,    0,    0,    0,    0,    0    },
    {    3,    4,    5,    6,    7,    8,    9,   10    },
    {    3,    4,    5,    6,    7,    8,    9,   10    },
    {   -3,   -3,   -3,   -3,   -3,   -3,   -3,   -3    },
    {    3,   -4,   -4,   -4,   -4,   -4,   -4,   -4    },
    {    3,   -5,   -5,   -5,   -5,   -5,   -5,   -5    },
    {    3,   -6,   -6,   -6,   -6,   -6,   -6,   -6    },
    {    3,   -7,   -7,   -7,   -7,   -7,   -7,   -7    },
    {    3,   -8,   -8,   -8,   -8,   11,   -8,   -8    },
    {    3,   -9,   -9,   -9,   -9,   -9,   12,   -9    },
    {    3,  -10,  -10,  -10,  -10,  -10,  -10,  -10    },
    {    3,   13,   13,   14,   13,   13,   13,   13    },
    {    3,  -12,  -12,  -12,  -12,  -12,   12,  -12    },
    {    3,   13,   13,   14,   13,   13,   13,   13    },
    {    3,  -14,  -14,  -14,  -14,  -14,  -14,  -14    },
    } ;

static yyconst short int yy_accept[15] =
    {   0,
        0,    0,    8,    6,    5,    5,    3,    3,    2,    4,
        0,    2,    0,    1
    } ;

Символы здесь разбиты на 8 классов, идентичных с точки зрения парсера (например, все цифры объединены в один класс). Отдельный массив static yyconst int yy_ec[256] ставит каждому символу в соответствие класс.

Основной цикл работы парсера весьма незамысловат:

yy_match:
   while ( (yy_current_state = yy_nxt[yy_current_state][yy_ec[(unsigned char)(*yy_cp)]]) > 0 )
       {
       if ( yy_accept[yy_current_state] )
           {
           yy_last_accepting_state = yy_current_state;
           yy_last_accepting_cpos = yy_cp;
           }

         yy_cp;
       }

   yy_current_state = -yy_current_state;

Положительные числа в таблице переходов означают «перейти в состояние и продолжить читать»; отрицательные — «перейти в состояние и выполнить действие». Номер действия, которое должно выполняться по приходу в состояние, хранится в yy_accept.

Рассмотрим пример: для цифр номер «класса символа» — 6.
В начальном состоянии (1) по символу 6 видим в таблице переходов 9. Переходим, читаем дальше.
В состоянии 9, если есть ещё одна цифра (6), переходим в состояние 12 и читаем дальше.
Из состояния 12, если есть ещё одна цифра, просто читаем дальше. (В таблице стоит 12)
Если увидели не-цифру (любой символ, кроме 6), нужно выполнить действие: видим в 9-ой строчке ряд из -9, и в 12-ой строчке ряд из -12.
Проверяем yy_accept: в обоих случаях применяем правило 2. (Вспомним, что правило, распознающее числа, в нашем парсере действительно второе.)
Непонятно, зачем flex решил разделить состояния 9 и 12, если в обоих делает одно и то же самое. Но он бездушная железяка, ему виднее.

Замечательно то, насколько готовый парсер прост: вместо ветвистого распознавания разных конструкций, у нас одна большая таблица, и цикл из десяти строк. Но есть существенная проблема. Вернёмся к примеру из самого начала поста: «найти начало конструкции (например, {); найти её конец (например, } на том же уровне вложенности)...» Как регэкспом обозначить условие «на том же уровне вложенности»?

Математики и тут постарались: доказали, что невозможно. Значит, для парсинга языков, поддерживающих вложенные конструкции (а это все языки сложнее BAT-файлов), нам потребуется более мощный инструмент, чем регэкспы. В следующий раз — о нём.