Янушкевич Вадим Александрович

Факультет компьютерных наук и технологий

Кафедра компьютерной инженерии

Специальность «Системное программирование»

Как создать свой простой компилятор

Архитектура современных компиляторов

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

Я не буду рассматривать сложные концепции, но эта статья претендует быть хорошим началом для изучения темы компиляторов и интерпретаторов. После изучения изложенного материала у Вас больше не будет желания писать сколь-нибудь сложный парсер на императивных языках программирована (таких как С++ или Java), и более-того, Вы сможете писать парсеры не только для языков программирования, но и для других данных, например для своего собственного формата конфигурационного файла (если вам такой вдруг понадобится).

И так, что же такое современный компилятор? Рассмотрим его сначала как черный ящик. На входе компилятору поступает файл с некоторыми (обычно текстовыми) данными – описание программы на исходном языке компилятора. На выходе компилятор выдает файл с другими данными – описание той же программы, но уже на другом языке – зачастую в машинном коде, или на языке ассемблера. То есть, компилятор можно рассматривать как переводчик программ с одного машинного языка на другой. Тут возникает проблема масштабируемости. Сейчас существует множество языков и множество целевых платформ (не забываем так же про виртуальные процессоры, такие как JVM, CLR, Parrot и т.д.). Когда создается новый язык программирования, Появляется необходимость использовать его на разных архитектурах, а как следствие приходится писать множество компиляторов. Эту проблему достаточно быстро осознали, и перешли к 3х этапной модели компиляции программ [1].

Компилятор разделили на 3 относительно независимые части:

Парсер, генератор дерева синтаксического разбора
Оптимизатор промежуточного представления кода
Генератор кода из промежуточного представления в целевую платформу

Такая архитектура позволила уменьшить объем работы, связанный с созданием новых языков программирования, позволала переносить программы на новые платформы(кто бы мог подумать, есть способы конвертации С++ кода в JavaScript!), а так же упростила разработку и отладку компилятора в целом.

LLVM как библиотека для разработки компиляторов

Ярким примером такой системы компиляторов является Low Level Virtual Machine (LLVM). На рисунке наглядно показано, как с помощью LLVM реализуется компиляция различных языков.

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

%char = type i8
%int = type i32

@msg = internal constant [13 x %char] c"Hello World!\00"

declare %int @puts(%char*)

define %int @main() {
  call %int @puts(%char* getelementptr inbounds ([13 x %char]* @msg, %int 0, %int 0))
  ret %int 0
}

Лексический и грамматический анализ исходного кода

И так, перейдем непосредственно к написанию парсера. Какой бы не были язык программирования, сразу в голову приходят однотипные действия. Нужно как-то вычленять лексемы, искать выражения, области видимости и т.д. Много работы было проведено в исследовании парсеров, и в итоге на данный момент была сформирована следующая концепция: сначала исходный текст разбивается на лексемы лексическим анализатором. Лексемами могут являться ключевые слова слова, имена переменных, пробелы, числа, специальные символы. Ниже приведен пример некого выражения на JSON- подобдном языке и его разбор лексическим анализатором.

После лексического разбора, лексемы и исходный текст отдаются синтаксическому анализатору. Синтаксический анализатор собирает вместе лексемы, формируя более сложные выражения. А из них в свою очередь еще более сложные. В итоге вся программа представляется парсером как одно выражение, и оно называется деревом синтаксического разбора. Этим деревом легко манипулировать, например на его основе можно сделать простой интерпретатор или компилятор. Причем, единственное отличие компилятора от интерпретатора только в том, что компилятор записывает в выходной поток соответствующую команду, а интерпретатор эту команду непосредственно исполняет [2].

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

Так сложилось, что я предпочитаю С/С++, поэтому для примеров буду использовать flex для получения набора токенов и bison для построения дерева разбора.

Программа на языке LEX состоит из 3х частей, первая часть – это обычный код на С, заключенный в символы %{ … }%. Второй блок, это список регулярных выражений, и соответствующий им код на С. Каждый раз, когда лексер будет встречать что-то во входном потоке, подходящее под регулярное выражение, он будет исполнять соответствующий ему код на С. 3я часть программы, это тоже код на С, в данном примере она не требуется и потому отсутствует. Пример простейшей программы с использованием генератора lex:

%{
#include <stdio.h>
%}

%%
[0123456789]+           printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*    printf("WORD\n");
%%

Откомпилировать и запустить программу можно так:

$ lex example.l 
$ cc lex.yy.c -o example -lfl
$ ./example
foo
WORD

bar
WORD

123
NUMBER

bar123
WORD

123bar
NUMBER
WORD

После чего вы получите программу, которая читает входной поток с клавиатуры, и при каждой встрече числа выводит слово «NUMBER», а каждый раз, когда встречает слово, выводит «WORD»

Грамматический анализ

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

power on
        Двигатель включен!
power off
        Двигатель выключен!
set speed 100
        Задана новая скорость вращения!

Необходимо распознавать следующие токены: power, on/off (состояние STATE), set, speed и числа (NUMBER). Lex-анализатор выглядит следующим образом

%{
#include  <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval=atoi(yytext, 10); return NUMBER;
poer                    return TOKPOWER;
on|off                  yylval=!strcmp(yytext,"on"); return STATE;
set                     return TOKSET;
speed                   return TOKSPEED;
\n                      /* игнорируем символ конца строки */;
[ \t]+                  /* игнорируем пробелы и символы табуляции */;
%%

В этом примере нужно отметить некоторые изменения, по сравнению с предыдущим примером. Во-первых, был подключен файл 'y.tab.h', во-вторых, на экран больше ничего не выводится, а лишь возвращаются имена токенов. Это изменение нужно потому, что поток токенов отдается на вход YACC, которому неважно, что выводится на экран. В файле y.tab.h как раз находятся определения этих токенов.

Теперь про сам файл y.tab.h. Он генерируется парсером BISON из файла грамматики, который мы сейчас напишем. Наш язык очень прост,такой же простой будет и его грамматика:


%token NUMBER TOKPOWER STATE TOKSET TOKSPEED


commands: /* empty */
        | commands command
        ;

command:
        power_switch
        |
        set_speed
        ;

power_switch:
        TOKPOWER STATE
         {
                if($2) // вместо $2 будет подставлено yylval из lex файла для токена STATE
                        printf("\Двигатель включен!\n");
                else
                        printf("\tДвигатель выключен!\n");
        }
        ;

set_speed:
        TOKSET TOKSPEED NUMBER
        {
                printf("\tЗадана новая скорость вращения - %d оборотов в минуту!\n", $3);
        }
        ;

Первая часть грамматики означает, что имеются "команды" (commands), и эти команды состоят из отдельных "команд" (command). Как нетрудно заметить, это определение рекурсивно, ведь оно содержит в себе само себя. Благодаря рекурсии, программа способна постепенно сокращать набор команд одну за одной. Второе правило определяет, что из себя представляет команда. Предпологается лишь два типа команд - power_switch (вкл/выкл двигателя) и set_speed (установка скорости). Здесь используется знак ИЛИ - | . В целом правило означает: "command может быть power_switch или set_speed". Правило power_switch состоит из токена POWER (это просто слово "power"), после которого идет состояние (оно определено в Lex-файле как "on" или "off"). Немного более сложным является последнее правило set_speed, состоящее из токена SET (слово "set"), токена SPEED (слово "speed") и числа.

пример работы программы:

$ yacc -d example2.y
$ lex example2.l
$ cc lex.yy.c y.tab.c -o example2
$ ./example2
power on
        Двигатель включен!
power off
        Двигатель выключен!
set speed 100
        Задана новая скорость вращения - 100 оборотов в минуту!

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