Обзор современных инструментальных средств разработки компиляторов

Зайцева Л.В., Сафонов П.В. (peter@shelkovo.comcor.ru)
Московский государственный институт электроники и математики, ИТАС

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

Классификация инструментальных средств разработки компиляторов позволяет выделить следующие типы средств:

1. Генераторы лексических анализаторов. Генераторы строят лексические анализаторы, на основе правил записанных в виде регулярных выражений. Построенные генераторами анализаторы работают по принципу конечных автоматов. Как правило, такие системы формируют код, который может быть использован программами, построенными генераторами синтаксических анализаторов. Типичным примером таких систем является lex.
2. Генераторы синтаксических анализаторов. Эти системы генерируют код синтаксических анализаторов, на основе правил записанных в БНФ. Построенные генераторами анализаторы обычно реализуют алгоритм восходящего разбора, основанный на LR-грамматиках (например, yacc, bison). Ядром LR-анализатора является таблица синтаксического анализа. Генераторами yacc и bison для построения таблицы используется метод LALR (lookahead LR - LR-анализ с заглядыванием вперед).

   Можно встретить системы, которые строят анализаторы, реализующие алгоритм нисходящего разбора, основанного на работе предикативного анализатора (например, RDP, LISA). Для построения однозначных таблиц анализа синтаксис языка должен быть описан LL-грамматикой, которая не может быть неоднозначной или леворекурсивной.

3. Средства синтаксически управляемой трансляции. Такие системы позволяют создавать наборы программ, которые осуществляют проход по дереву разбора и генерируют промежуточный код. В качестве примера таких систем можно привести Kimwitu, The Memphis Tree Builder & Tree Walker Tool.
4. Автоматические генераторы кода. Эти системы получают набор правил, определяющие способ трансляции каждой операции промежуточного языка в машинный язык. Примерами таких систем являются BEG, IBURG, MBURG, TWIG.
5. Генераторы анализаторов потока данных и оптимизаторов. Такие системы позволяют создавать программы, осуществляющие анализ потока данных, необходимых для получения оптимизированного кода. Примерами таких систем являются Berkeley ANalysis Engine, OPTIMIX, PAG.
6. Наборы программ создания компиляторов. Такие наборы, как правило, включают в себя почти все перечисленные выше инструментальные средства разработки компиляторов. Например, набор PCCTS состоит из следующих программ:
   • DLG - генератор лексических анализаторов;
   • ANTLR - генератор синтаксических анализаторов;
   • SORCERER - генератор программ, осуществляющих проход по дереву разбора.
7. Системы создания сред разработки. Такие системы кроме компилятора позволяют построить редактор, ориентированный на определенный язык. В качестве примера такой системы можно привести The Synthesizer Generator, разработанной для среды X11 Window System, которая входит в состав различных коммерческих версий ОС Unix (Sun Solaris, HP-UX, IBM AIX и др.). Эта система позволяет построить среду разработки приложений, обладающую редактором, который позволяет обнаружить синтаксические ошибки до компиляции, а также реализующую синтаксически-управляемую трансляцию, осуществляющую компиляцию или интерпретацию исходной программы.

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

1. Построение лексического и синтаксического анализаторов.
2. Организация синтаксически управляемой трансляции.
3. Построение генераторов и оптимизаторов целевого кода.

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

Литература

1. Ахо А. В., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструменты.
2. http://catalog.compilertools.net/ - Catalog of Compiler Construction Tools