Написать компилятор на C# или C++ или Python? — rpilot62.ru

Написать компилятор на C# или C++ или Python?

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

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

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

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

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

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

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

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

И так, что же такое современный компилятор? Рассмотрим его сначала как черный ящик. На входе компилятору поступает файл с некоторыми (обычно текстовыми) данными – описание программы на исходном языке компилятора. На выходе компилятор выдает файл с другими данными – описание той же программы, но уже на другом языке – зачастую в машинном коде, или на языке ассемблера. То есть, компилятор можно рассматривать как переводчик программ с одного машинного языка на другой. Тут возникает проблема масштабируемости.

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

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

  1. Парсер, генератор дерева синтаксического разбора
  2. Оптимизатор промежуточного представления кода
  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 оборотов в минуту!

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

Список используемых источников

  1. GridStack ­— Пример практического применения flex+bison
  2. Writing Your Own Toy Compiler Using Flex, Bison and LLVM

Похожие работы на портале магистров

  1. Тимофеев М.А. — Генерация исходного кода из спецификации методологии IDEF0
  2. Другобицкий А. Ю. — Исследование возможностей функциональных языков для создания генераторов программ.

Компиляция / Компилятор

Компиляция — это процесс преобразования исходной программы в исполняемую. Процесс компиляции состоит из двух этапов. На первом этапе выполняется проверка текста программы на отсутствие ошибок, на втором — генерируется исполняемая программа (ехе-файл).

После ввода текста функции обработки события и сохранения проекта можно из меню Project выбрать команду Compile и выполнить компиляцию. Процесс и результат компиляции отражаются в диалоговом окне Compiling (РИС. В38). В это окно компилятор выводит ошибки (Errors), предупреждений (warnings) и подсказок (Hints).

Сами сообщения об ошибках, предупреждения и подсказки отображаются в нижней части окна редактора кода (рис. В39).

Примечание

Если во время компиляции окна Compiling на экране нет, то выберите из меню Tools команду Environment options и на вкладке Preferences установите во включенное состояние переключатель Show compiler progress.

Компилятор

Компилятор

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

Как работает компилятор?

Создание компилятора – обычная практика для студентов IT-специальностей западных стран: это умение помогает учащемуся глубже понять технологию создания системного программного обеспечения, заглянув за рамки пользовательского интерфейса ОС.

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

К сожалению, в российском обучении такой подход не практикуется, что и приводит к тому, что российского компьютерного софта существует так мало.

Компилятор – это программа, которая превращает исходный текст, созданный на языке программирования, в машинный код, способный к выполнению процессором.

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

Как правило, компилятор состоит из нескольких стандартных частей: парсера, лексического анализатора, кодогенератора, оптимизатора. Парсер следит за правильностью структуры программы, лексический анализатор выделяет из потока парсера лексемы, определяет их и составляет внутренние таблицы переменных, вызовов процедур и т.д. Если компилятор является однопроходным, то в процессе анализа лексем может работать кодогенератор, формируя выходной машинный код. Так как компьютеры сейчас очень быстрые, то имеет смысл разработка многопроходных компиляторов: в этом случае вся программа переводится в промежуточный код – к примеру, пи-код. Пи-код интересен тем, что позволяет оптимизировать программу еще на начальном этапе, а кодогенератор способен преобразовать ее не только в коды данного компьютера, но и в выходной код другой платформы. Таким образом можно получить многоплатформенный компилятор, работающий, скажем, под DOS/DOS32/Windows и Linux.

Перед созданием компилятора разумно документировать язык программирования так, чтобы его можно было описать на формальном графическом языке БНФ. БНФ язык не привязан к конкретному языку и лишь описывает правила составления блоков и условий в программе. Сейчас существуют специальные генераторы, которые лишь по БНФ могут построить каркас для нового компилятора, включив в него большую часть модулей для анализа исходного текста.

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

Как создать свой язык программирования: теория, инструменты и советы от практика

.

Добавить комментарий

Закрыть меню