Общая характеристика системы

Учебно-исследовательская система конструирования формальных языков (ФЯ) "Грамматика" предназначена для автоматизированной разработки предметно-ориентированных языков. Система предлагает методологию и набор программных средств, позволяющих существенно сократить объем работ по программированию при создании трансляторов. В учебном процессе система может быть полезна при изучении теории формальных языков и грамматик, теории компиляции, а также в приобретении практических навыков разработки языков. Данные методические указания содержат описание компонент системы "Грамматика" и принципов ее использования. Основы теории формальных языков и грамматик и теории компиляции изложены в [1,2,3,4,5,6].

Разработанная система основана на использовании синтаксически-управляемых процессов редактирования текстов, оформленных на ФЯ. В основе таких процессов лежит принцип сопоставления фразовых структур (строк текста) с образцом (см. рис. 1).

"Образцом" является грамматика ФЯ, полностью описывающая множество разнообразных фразовых структур, которые могут быть использованы в "Описании".

Анализатор в этой схеме является универсальной программой, функционирующей с использованием любого Образца. Смена Образца формально приводит к определению нового ФЯ.

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

Если рассматривать Описание как программу на ФЯ, то План будет определять результат трансляции этой программы.

Описание, Образец и План определяют структуры соответствующих файлов.

Описанная упрощенная схема реализуется в системе "Грамматика" следующими компонентами:

• подсистемой спецификации ФЯ,

• подсистемой анализа описаний на ФЯ и формирования результатов такого анализа.

Подсистема спецификации ФЯ включает в себя:

• метаязык, позволяющий специфицировать формальные языки на уровне лексики, синтаксиса, а также связывать с синтаксисом внешние семантические процедуры,

• анализатор корректности спецификации формального языка. Подсистема анализа описаний на ФЯ включает в себя:

• лексический анализатор предложения,

• синтаксический анализатор предложения.

2. СПЕЦИФИКАЦИЯ ФОРМАЛЬНОГО ЯЗЫКА

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

Грамматика образуется конечным множеством продукций, каждая из которых состоит из имени и тела и представляется в следующем виде:

имя_продукции::= тело_продукции **

Здесь имя_продукции - идентификатор, определяющий уточняемое понятие (нетерминал),

::= - метасимвол, разделяющий имя и тело продукции, тело_продукции - описание (уточнение) нетерминала. Тело продукции определяет синтаксическую структуру множества фраз конструируемого языка (сентенциальную форму), ** - метасимвол, означающий конец продукции.

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

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

А::=...<_ В _>...**

В::=....**

Могут быть два исключения из этого правила:

1) Имя первой продукции (аксиомы грамматики) не используется в других продукциях.

2) Используемый в теле продукции нетерминал является предопределенным, т.е. внесенным в библиотеку уточняемых понятий системы.

В качестве ключевого слова языка может выступать любой идентификатор, принадлежащий конструируемому языку. Он определяется последовательностью букв латинского и/или русского алфавита, арабских цифр, символа пробела, начинающейся с буквы, например procedure, begin, end. Идентификатор может иметь любую длину, однако отметим, что описываемая система анализирует только первые 32 символа, прописные буквы равнозначны строчным.

Разделителем является последовательность символов, не являющихся буквами латинского или русского алфавитов, цифрами, символами пробела, табуляции, конца строки. К разделителям относятся, например,:;, >= <> =! @. Система различает разделители по первым 8 символам.

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

<_ и _> - скобки нетерминала. Любой текст, используемый внутри скобок нетерминала, интерпретируется системой как имя продукции, например, <_Список_параметров_>.

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

{_ и _} - скобки итеративного элемента, т.е. элемента, который может повторяться в описании на ФЯ 0,1 или более раз. Например, элемент {_ <_АВС _> _} означает, что образец (ABC) может последовательно использоваться для анализа фрагмента описания 0, 1, 2,... раз. Другими словами, этот элемент допускает следующие строки фрагмента описания:

-пустая строка

-(ABC)

-(ABC) (ABC)

-(ABC) (ABC) (ABC)

?_ и _|_ и _? - скобки и разделитель списка альтернатив. Данная конструкция используется при анализе строки описания на соответствие одному из указанных вариантов. Например, конструкция?_ + _|_ - _|_ * _|_ / _? означает символ + или - или * или /.

(_ и _) - скобки семантики. Между скобками должно быть указано целое число в диапазоне 0..65535, означающее номер семантической процедуры, например, (_15_). Сведения, необходимые для разработки набора этих процедур, реализующего семантический анализ текста на ФЯ, изложены в разделе "Анализ текста на формальном языке".

(* и *) - скобки комментария. Текст, заключенный между этими скобками в грамматике ФЯ, при анализе игнорируется.

Терминалы, или терминальные символы грамматики, - это любые символьные строки ФЯ, которые не требуют определения в продукциях грамматики ФЯ. Ключевые слова и разделители являются разновидностями терминалов.

Система содержит три предопределенных нетерминала: Name, Numb, Real, порождающих соответственно множество идентификаторов произвольной длины с 32 первыми значащими символами, множество целых чисел без знака в диапазоне от 0 до 65535, множество вещественных чисел без знака в диапазоне от 2.9е-39 до 1.7е38.

Оформление грамматики должно учитывать специфику используемых в системе алгоритмов сопоставления с образцом. Алгоритмы нисходящего рекурсивного анализа (рекурсивного спуска), реализованные в системе, накладывают два дополнительных ограничения на грамматику ФЯ.

1) Отсутствие левосторонней рекурсии.

Продукции видов

А::=<_А_>... **,

А::= [ _<_А_>... и т.п.

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

А::=?_ <_ А_> а _|_ а_? **

может быть заменена эквивалентной продукцией, свободной от "левой" рекурсии:

А::=а{_а_}** Возможны и другие эквивалентные преобразования.

2) Упорядочение альтернатив.

Рассмотрим грамматику:

А::= [_<_B_> _] <_С_> **

В::= abc **

С::= abc **

Если применить ее к анализу строки "abc", то результатом будет FALSE - "строка не соответствует грамматике". Это обусловлено тем, что факультатив [_ <_ В _> _] эквивалентен альтернативе с пустой второй частью:?_ <_ В _> _|_ _?. Использование такой грамматики при анализе строки "abc" приводит к заключению:

(<_ В _>_"_abc_" = TRUE) AND (<_ С _>_{" "} = FALSE) = FALSE; (здесь "" - пустая строка). Если же заменить продукцию

A::=[_<_B_>_] <_C_> ** на эквивалентную (только для этого примера!)

А::=<_С_>[_<_В_>_]** то результатом сопоставления строки "abc" с образцом А будет

(<_ С _>_"abc" = TRUE) AND (<_ В _>_{" "} = TRUE) = TRUE. Такие коллизии возникают при использовании альтернатив с идентичными начальными частями вариантов. Например,

А::=?_ ab _|_ abc _|_ abce _? d **

Анализ входной строки "abcd" по этой продукции приведет к результату FALSE, поскольку первый вариант альтернативы (ab) дает результат TRUE, а оставшаяся подстрока "cd" дает результат FALSE при сопоставлении с образцом d. Переупорядочение вариантов по принципу "длинные вперед" приведет к правильному результату.

Любая правильно оформленная грамматика должна быть проверена на корректность. Анализ грамматики на корректность связан с выявлением ошибок в спецификации языка. Простейшие из них:

1) неопределенные нетерминалы (нетерминалы, не принадлежащие к предопределенным и не имеющие эквивалентов среди имен продукций);

2)недостижимые нетерминалы (имя нетерминала не используется в телах продукций);

3)ошибки следования метасимволов.

Контроль грамматики по желанию пользователя может сопровождаться демонстрацией грамматики в отдельном окне, указанием текущего обрабатываемого символа, а также протоколированием - фиксированием в отдельном файле и окне последовательности решений анализатора. Файл протокола имеет имя, совпадающее с именем грамматики, и расширение "gap".

По результатам анализа грамматики система выдает следующие сообщения:

1) для корректной грамматики перечисляются нетерминальные символы, ключевые слова и разделители языка;

2) для некорректной грамматики выдается список выявленных ошибок.

Ниже приводится пример грамматики, определяющей простой паскалеподобный язык.

Программа::= program <_Name_>;

[_ <_ Константы _> _]

[_ <_ Переменные _> _] begin

{_ <_ Операция _> _} end. **

Константы::= const {_ <_Name_> = <_Число_>; _} **

Переменные::= var {_ <_Name_> {_,<_Name_>_}:.

<_Стандартный_тип_>; _} **

Число::=?_ <_Numb_> _|_ <_Real_> _? **