Дизайн компилятора — наука о создании компиляторов

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

Генерация и оптимизация кода:

Генерация кода — это процесс преобразования программы, написанной на языке высокого уровня, в машинный код. Это также известно как компиляция, и это в основном то, что делают компиляторы.

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

Процесс оптимизации иногда называют оптимизацией программы или оптимизацией программного обеспечения.

Инструменты, которые используются для оптимизации программ, варьируются от одного языка к другому, а также от одной платформы к другой. Например, программисты Java обычно используют javac и виртуальную машину Java (JVM) для компиляции своих программ, тогда как программисты C/C++ используют GCC или clang и коллекцию компиляторов GNU (GCC).

Компилятор Java (javac), входящий в состав JDK, можно использовать как для компиляции, так и для оптимизации ваших программ. Это инструмент командной строки, который вызывается путем передачи имени исходного файла для компиляции в качестве аргумента. Например, если у вас есть исходный файл с именем «MainClass.java», вы можете скомпилировать его в байт-код с помощью следующей команды: javac MainClass.java Помимо компиляции ваших программ, javac также выполняет некоторые базовые оптимизации, такие как устранение мертвого кода.

Однако эти оптимизации применяются только тогда, когда они строго необходимы, и не окажут никакого влияния на вашу программу, если они не нужны. Например, JVM автоматически встроит небольшие методы (состоящие менее чем из дюжины строк кода), а это означает, что javac также не нужен для этого.

Моделирование в разработке и реализации компилятора

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

Моделирование также может применяться на разных уровнях: вы можете захотеть применить некоторую форму формализма, например исчисление или алгебраическую логику, при проектировании потока управления вашего компилятора, но опять же, вы можете захотеть что-то более неформальное, например, форму Бэкуса-Наура (БНФ) при написании вашего кода. лексический анализатор. У вас будут разные варианты в зависимости от того, какой уровень абстракции лучше всего соответствует вашим потребностям на каждом этапе создания вашей системы. Одним из преимуществ моделирования является то, что оно может помочь вам выявить потенциальные проблемы в вашем проекте раньше, тем самым сэкономив время и деньги. Вы также можете обнаружить, что, используя такой формализм, как БНФ, который имеет четко определенный синтаксис и семантику, вы можете излагать свои идеи более четко, чем если бы вы использовали простой английский язык.

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

Алгоритмы разбора (распознавания):

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

Парсеры сверху вниз:

Нисходящий синтаксический анализатор начинает со структур самого высокого уровня в исходном коде и продвигается вниз к более низким уровням, пока не найдет что-то, что соответствует его набору правил для синтаксического анализа (например, грамматика «если упражняться, то»). Оттуда он пробует все возможные комбинации, пока одна из них не совпадет или не сработает из-за лексических ошибок или несоответствия входных типов/значений (например, грамматика «если упражнение, то» дает сбой при вводе неверных данных, таких как «кошка съела мою домашнюю работу»). Нисходящие синтаксические анализаторы обычно используются, когда вам нужна 100% точность, потому что они требуют гораздо больше усилий, чем другие методы, но не жертвуют скоростью, поскольку во время выполнения не происходит возврата.

Восходящие парсеры:

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

Направленный синтаксис перевод:

Перевод, управляемый синтаксисом, — это метод перевода языка программирования высокого уровня в какую-либо другую форму машинного языка. Впервые он был представлен Джоном Бэкусом в 1959 году и с тех пор стал наиболее широко используемым подходом к компиляции для многих языков, включая C, Fortran и COBOL.

Транслятор, управляемый синтаксисом (SDS), преобразует исходный код из одного формата в другой, преобразовывая каждую строку в маркеры, которые представляют следующий шаг выполнения или переход состояния, требуемый этой строкой. Полученный исполняемый код называется промежуточным представлением (IR).

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

Генератор грамматик и семантических действий：

Чтобы понять, как работают компиляторы и интерпретаторы, необходимо сначала разобраться в различных типах грамматик. Грамматика — это набор правил, описывающих то, что можно сказать на языке. Эти правила позволяют нам анализировать наши исходные программы на правильно сформированные части, которые мы затем используем для семантического анализа или генерации кода.

В традиционных компиляторах синтаксический анализ выполнялся на абстрактном синтаксическом дереве, полученном путем анализа каждого исходного файла в его соответствующем промежуточном представлении (IR). Затем семантические действия взяли этот IR и каким-то образом изменили его перед созданием другого IR на основе модели семантики вашего целевого языка для конкретного приложения; эти модификации включают такие оптимизации, как встроенный ассемблер (функция компилятора, при которой инструкции появляются непосредственно внутри других инструкций), устранение мертвого кода (удаление переменных, на которые нет ссылок) и так далее!

Оптимизация кода:

Оптимизация кода — это процесс изменения исходного кода программы с целью повышения его эффективности.

Оптимизация может улучшить скорость программы, использование памяти или другие атрибуты. Процесс оптимизации часто включает преобразование исходного кода в форму, в которой меньше инструкций и/или меньше места для хранения данных, чем в исходной форме. Оптимизации могут выполняться автоматическим компилятором или интерпретатором (который преобразует программы во время их выполнения) или вручную программистом, который их написал; это различие важно, потому что разные типы оптимизации могут лучше подходить для одного типа системы, чем для другого.

Роль тестирования:

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

Наш подход использует инструменты разработки программного обеспечения: системы контроля версий (Git), серверы непрерывной интеграции (Jenkins) и инструменты автоматического доказательства теорем, такие как HOL Light от Исследовательского центра Майкрософт в Кембридже, чтобы достичь высоких стандартов качества для нашего конечного продукта: компиляторов для языки программирования, такие как Java или C#/.NET Framework.

Код MDL и код C так же важны, как и распознавание допустимых входных данных в дизайне компилятора.

Код MDL и код C так же важны, как и распознавание допустимых входных данных при проектировании компилятора. Каждый раздел компилятора имеет точную спецификацию, которая должна быть проверена, по возможности автоматически. Язык для написания спецификаций и тестов один и тот же: языки на основе ML или BNF.

Вывод

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