А. И.Толкачёв

Республика Беларусь. Гомель. Гомельский Государственный университет имени Франциска Скорины.

тел. +(375) 232-578256. e-mail: tolkachyov@gsu.unibel.by
Unisan parser generator was developed in Gomel State University. It is based on SLL¹(k) parser. Unisan is used in some research projects held in Gomel State University, which concern with embedded systems design software development. The software can be used for training courses on parser and translator design. The grammar description format is not complicated and the grammar strength is great. It makes possible to easily describe high-level programming languages grammars. Syntactic tree construction routines can be inserted in the grammar description. The parser can be used from any win32 application. It is implemented in C++ and designed as a dynamic link library. This paper describes the structure of Unisan parser generator and the grammar description language.
Введение

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

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

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

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

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

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

В Гомельском государственном университете разработан программно – технологический комплекс (ПТК) Unisan [1-7], позволяющий автоматизировать процесс разработки трансляторов. Распознаватель позволяет работать с SLL¹(k), k  1 - грамматиками, которые являются подмножеством LL(k). Объём памяти и время, затрачиваемое для работы и построения распознавателя для SLL¹(k) – грамматики, линейно зависит от k, что позволяет эффективно использовать грамматики при k>1. Кроме этого, используется эвристический алгоритм факторизации синтаксических диаграмм, позволяющий в ряде случаев уменьшить k или даже привести грамматику к виду SLL¹(k), если она не являлась такой в исходном виде. Из дополнительных возможностей отметим наличие механизма, позволяющего управлять потоком лексем во время разбора. Эта возможность упрощает реализацию, например, макроподстановок или включения файла в исходный текст (директива #include препроцессора языка С). ПТК Unisan реализован на языке C++. На данный момент имеется версия для платформы Win32, хотя, при необходимости, возможен его перенос на другие платформы.

Для генерации промежуточного представления программы в ПТК Unisan реализован механизм, позволяющий в описание грамматики включать конструкции, описывающие синтаксическое дерево.

Для сохранения отладочной информации разработан формат ESDI, обеспечивающий высокую скорость сохранения и загрузки программы и явлюяющийся универсальным для различных платформ. Реализована библиотека для работы с этим форматом. Формат ESDI поддерживается средой проектирования и отладки программного обеспечения встроенных систем Winter [8-9] и средой высокоуровневого проектирования цифровых устройств HLCCAD [10].

ПТК Unisan может быть использован в учебном процессе для обучения студентов основам проектирования трансляторов.
Схема использования ПТК Unisan

П

Рисунок 1 - структура программы, использующей Unisan .Unisan содержит функции лексического и синтаксического анализа, внешняя программа задаёт исходный текст и принимает построенное синтаксическим анализатором промежуточное представление информации.

ПТК Unisan позволяет автоматизировать разработку лексического и синтаксического анализаторов. На рис. 1 изображена структура программы, использующей Unisan. Unisan состоит из двух модулей – исполняемый файл bnfc.exe и динамически подключаемая библиотека parser.dll. Генератор распознавателей (bnfc.exe) используется для построения детерминированного распознавателя по заданному файлу с формальным описанием грамматики с помощью РБНФ (далее – bnf-файл). Построенный распознаватель сохраняется в бинарном файле с расширением ‘.arr‘ (далее – arr-файл).

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

Для управления распознавателем и получения информации в ходе разбора внешняя программа должна содержать реализацию методов интерфейса IMessageSystem.

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

Bnf-файл имеет следующую структуру (полужирным шрифтом выделены строки, присутствующие в bnf-файле, обычным шрифтом – строки, используемые для описания формата файла, блоки, заключённые в квадратные скобки, могут отсутствовать):
опции распознавателя

lexer // описание лексического анализатора

{

опции лексического анализатора

[ @terminals

{ описание обычных лексем

};

]

[ @literals

{ описание литералов

};

]

правила лексического анализатора

}

parser // описание синтаксического анализатора

{

опции синтаксического анализатора

правила синтаксического анализатора

}
После каждой опции или правила должен стоять символ ; (точка с запятой).

В правила синтаксического анализатора могут быть включены конструкции, описывающие построение синтаксического дерева.

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

Рассмотрим это на примере (фрагмент описания синтаксиса для калькулятора выражений языка C):

Нетерминал expr1 описывает синтаксис оператора присваивания, expr2 – выражение из операторов, приоритет которых ниже оператора присваивания. Выражение #0:expr2 обозначает дерево, построенное при распознавании правила для нетерминала expr2, #1 используется для идентификации этого дерева. Аналогично выражения #1: Assignment_operator и #2: expr1 обозначают деревья, построенные для соответствующих нетерминалов.

Выражение #0: #(#1 #0 #2) описывает создание дерева с корнем #1 и потомками #0 и #2. Созданное дерево обозначается идентификатором #0.

Идентификаторы, используемые для обозначения деревьев, состоят из символа # и номера, например, #0, #1, #12. Рекомендуется использовать минимальное количество идентификаторов и нумеровать их последовательно, начиная и нуля.

В выражении создания дерева #(…) используется Lisp – нотация (см. п.1.1.3), позволяющая описывать произвольное дерево. Например:
#( OPasgn #( OPplus #0 #1) #(OPminus #2 #3))
Идентификаторы #0, #1, #2, #3, используются для обозначения деревьев, остальные (OPasgn, OPplus, OPminus) обозначают типы узлов. Если для выражения не указан идентификатор получаемого дерева, то подразумевается #0, например, выражение #(OPplus) эквивалентно #0:#(OPplus).

Для нетерминала может быть указано, какое дерево ему соответствует, например:

Разработанный ПТК Unisan может быть использован как в процессе обучения, так и для выполнения реальных проектов. В Гомельском государственном университете Unisan используется в научно-исследовательских работах, связянных с проектированием инструментов для совместной разработки программного и аппаратного обеспечения встроенных систем.

1. 
   Толкачёв А.И. Универсальный синтаксический анализатор // Материалы XXVI научной конференции по естественным, техническим и гуманитарным наукам. Гомель, 1997, с.27-28.
   
2. 
   Толкачёв А.И. Универсальный синтаксический анализатор и построение компиляторов на его основе // Новые компьютерные технологии в науке, технике, производстве и индустрии развлечений, Материалы республиканской научно-технической конференции, 9-13 марта 1998г. ГГУ им. Ф. Скорины.
   
3. 
   Толкачёв А.И. Универсальный синтаксический анализатор и примеры его апробации // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях, Материалы II Республиканской научно-технической конференции студентов и аспирантов 15-20 марта 1999г.
   
4. 
   Толкачёв А.И. Универсальный синтаксический анализатор // Творчество молодых ‘99 Cборник научных работ студентов и аспирантов Гомельского Государственного университета им. Ф. Скорины. Гомель, 1999, с.13-14.
   
5. 
   Толкачёв А.И. Языки программирования и описания аппаратуры : универсальный синтаксический анализатор. // Труды международной конференции "Информационные технологии в бизнесе, образовании и науке" Минск, 1999.
   
6. 
   Толкачёв А.И. Разработка компилятора и отладчика языка Vhdl. // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях, Материалы III Республиканской научной конференции студентов и аспирантов 13-18 марта 2000г.
   
7. 
   Толкачёв А.И. Универсальный синтаксический анализатор. // Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях, Материалы IV Республиканской научной конференции студентов и аспирантов 19-22 марта 2001г., с. 194-196.
   
8. 
   Ермолаев И.Ю. Технология создания интегрированной среды разработки программ для произвольного микроконтроллера // Электроника. 2000г. N2 c.20-26.
   
9. 
   Ермолаев И.Ю. Настраиваемые на целевую архитектуру средства отладки программ // Тезисы V Республиканской научной конференции студентов и аспирантов Беларуси (НИРС-2000) 25-27 апреля 2000 года (г. Гродно).
   
10. 
    Литвинов В.А. Система высокоуровневого проектирования цифровых устройств (HLCCAD - High Level Chip Computer-Aided Design) // Труды международной конференции "Информационные технологии в бизнесе, образовании и науке", Минск, 1999, с. 179-182.