Разработка транслятора искусственного языка на примере транслятора подмножества языка с языка ST на язык С

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

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

Лексический анализ – первый этап трансляции текста. Под ним следует понимать процесс аналитического разбора входной последовательности символов на лексемы с целью получения на выходе идентифицированных последовательностей, называемых токенами. Разбор текста на лексемы происходит в соответствии с определенными правилами, принятыми для данного языка.

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

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

В данной работе лексический анализатор текста на языке ST генерируется программой flex. На входе эта программа получает текст и правила выделения лексем в этом тексте, а на выходе выдаёт код лексического анализатора в виде функции на языке Си.

Правила хранятся в файле с расширением .l и задаются в виде пар регулярных выражений и строк кода на языке Си. Файл содержит три секции, отделяющиеся строкой «%%»: блок определений, блок правил и блок кода на Си. Определения содержат стартовые значения и определения, правила – сами выражения и соответствующие им действия; пользовательский код просто включается в вывод flex. Подробнее структура этого файла будет рассмотрена на примере реализованного транслятора.

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

В данном примере для генерации синтаксического анализатора используется программа GNU Bison. Она генерирует программу, которая получает на вход поток токенов, сформированный лексическим анализатором, и находит в этом потоке структурные элементы (нетерминальные токены) согласно заданной грамматике.

Грамматика языка содержится в файле с расширением .y, чья структура похожа на структуру файла .l, но отличается наполнением. Имеется три секции: пролог, куда помещается код на языке Си, необходимый для работы анализатора – здесь размещаются подключения заголовочных файлов и сигнатуры функций; объявления, где располагаются объявления токенов и типов данных, с которыми работает анализатор; правила грамматики, где содержится описание грамматики, и эпилог, куда можно помещать код на языке Си.

Для реализации транслятора искусственного языка ST в язык Си были созданы файлы, описывающие лексемы и грамматику исходного текста. На их основе посредством программ flex и bison были созданы лексический и семантический анализаторы, рассмотренные выше, и собранные вместе в единую программу-транслятор посредством компилятора GCC.

Лексемы текста на языке ST и их аналоги на языке Си представлены в файле l_file.l. Далее представлен его посекционный разбор.

На рисунке 1 представлен блок определений. Он используется для включения необходимых для работы анализатора библиотек языка Си, функции обработки ошибок и файла y.tab.h. Этот файл представляет собой набор операторов #define и позволяет использовать одни и те же лексемы в лексическом и синтаксическом анализаторах.

Рис. 1. Блок определений файла .l

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

Третий блок представлен одной функцией yywrap, которая возвращает единицу при обнаружении конца файла. После этого flex заканчивает свою работу.

Рис. 2. Блок правил файла .l

Результатом работы flex является файл lex.yy.c, содержащий программу лексического анализатора.

Грамматика, используемая Bison для анализа текста на языке ST, представлена в файле y_file.y. Он будет рассмотрен аналогичным образом.

На рисунке 3 показан блок определений. В прологе включены библиотеки, объявлены глобальные переменные – указатели на файлы ввода и вывода результата, объявлена и реализована функция вывода ошибок. Далее представлены терминальные и нетерминальные символы. Терминал – непосредственный объект языка, имеющий неизменяемое значение. Нетерминал – абстрактный объект, обозначающий некую сущность языка, не имеющую конкретного символьного значения.

Рис. 3. Блок объявлений файла .y

На рисунках 4–6 представлен фрагмент блока правил, где описана формальная грамматика преобразуемого языка. На основе этой грамматики анализатор формирует древо разбора, начиная с «листьев», то есть токенов. Большая часть секции опущена из-за ее длины.

Рис. 4. Блок правил файла .y

Рис. 5. Блок правил файла .y

Рис. 6. Блок правил файла .y

В закрывающей секции файла представлен код на Си (рис. 7). Здесь открывается файл с исходным текстом в режиме чтения, создается файл для записи результата. В этот файл «вручную» записываются первые строки кода – включение библиотек и объявление основной функции. Далее запускается анализатор, в файл записывается конец цикла, файлы закрываются.

Рис. 7. Эпилог файла .y

Результатом работы Bison является файл y.tab.c, содержащий программу синтаксического анализатора. После генерации программ лексического и синтаксического анализаторов их требуется собрать в единую программу посредством команды gcc lex.yy.c y.tab.c. Результатом является программа-транслятор a.exe.