Copyright: Crimson Help ©2001 By A. Zenchenko


Visual Yacc 2.1
Visual Yacc 2.1	Copyright © 2002

Программа Visual Yacc 2.1 предназначена для визуального проектирования распознавателей языков, грамматика которых является грамматикой LR(1) класса.  Распознаватели конструируются для Borland C++ Builder.

Функциональные возможности программы:

Содержание

1. Создание лексем;

2. Настройка лексем;

3. Создание правил в БНФ нотации;

4. Настройка правил;

5. Определение текста С++ фрагментов свертки правил;

6. Верификация грамматики на соответствие LR(1) классу;

7. Генерирование С++ кода программы распознавателя (парсера);

8. Использование парсера в прикладной программе;

Разработчики:

Глухов Д.О., к.т.н., ст. преп. кафедры технической кибернетики Полоцкого государственного университета.

Глухов А.О., к.т.н., ст. преп. кафедры технической кибернетики Полоцкого государственного университета.


Создание лексем

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

Встроенные лексемы используют встроенные алгоритмы, оптимизированные по скорости выполнения, для распознавания следующих регулярных выражений:

•	Логические переменные ( enum { false, true } );

•	Целые числа ( int );

•	Числа с плавающей запятой ( double );

•	Текстовые строки ( “\tНекоторый текст \n\x00” );

•	Текстовые имена ( _start_009 ).

По правилам языка C++!

Для создания дополнительных лексем, определяющих ключевые слова языка, используется пункт контекстного меню на свободном поле листа Add lexem.

 Вновь созданная лексема имеет вид

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

Содержание.


Настройка лексем

Настройка лексемы выполняется в утилите Lexem Properties для выделенной щелчком мыши лексемы.

•	Имя лексемы должно быть уникальным в пространстве имен лексем и правил. Имя лексемы совсем необязательно должно совпадать с введенным регулярным выражением.

•	Ассоциативность лексемы привлекается для разрешения конфликтов свертка-переход. Для операторов с левой ассоциативностью при возникновении подобной коллизии выполняется свертка, для право-ассоциативных операторов - переход.

левая ассоциативность op: 	a op b op c => (a op b) op c

правая ассоциативность op: 	a op b op c => a op (b op c)

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

•	Регулярное выражение в настоящей версии есть константная строка.

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

Содержание.


Создание правил в БНФ нотации

Нотация Бекуса-Наура является очень распространенной нотацией описания широкого класса грамматик формальных языков. В частности для грамматик LR(1). Левая часть правила выступает в дальнейшем в качестве нетерминального символа формального языка, а правая определяет последовательность терминальных и нетерминальных символов. Кроме этого допускаются аннулирующие нетерминальные символы.

Создание правила выполняется аналогично созданию лексемы по пункту контекстного меню для пустого поля редактора.

Правило также обладает уникальным именем. Правило имеет один обязательный вариант правила Error необходимы для реализации перехватчиков ошибочных ситуаций.

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

Причем если в альтернативе присутствует только один токен, то операция удаления токена будет заблокирована.

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

Содержание.


Настройка правил

Настройка правил выполняется в окне Rule Properties. Данное окно активизируется при выделении любого составляющего элемента правила и показывает настройки правила в целом.

•	На имя правила распространяются те же ограничения, что и на имя лексемы. Оно должно быть уникальным в пространстве имен лексем и правил.

•	Флажок Start rule for the parsing указывает, что разбор начинается с данного правила, оно является корнем дерева разбора. Стартовое правило выделяется розовым цветом его левой части.

•	Флажок Stop parsing while error указывает на необходимость прервать разбор в случае несоответствия текста грамматике языка.

•	Поле Will be converted to указывает тип переменной в семантическом стеке. Допускаются все встроенные типы, а также имеется возможность определить свой тип данных (класс). Инициализация соответствующего объекта данного класса, создаваемого парсером с использованием его конструктора по умолчанию автоматически, должна быть выполнена в С++ фрагменте, закрепляемом за сверткой каждого альтернативного правила данного правила.

•	Поле Custom class служит для указания имени собственного типа данных.

Содержание.


Определение текста С++ фрагментов свертки правил

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

BOOL INT DOUBLE STRING NAME regular expression	bool int double AnsiString AnsiString AnsiString

Тип нетерминальных элементов задается при разработке правил и программист сам «сворачивает» правила в переменные заданного типа. Далее при попадании нетерминальных элементов в другие правила в семантическом стеке будут размещены переменные пользовательского типа данных.

Каждому альтернативному варианту правила может соответствовать свой отдельный код.

Для добавления кода на выделенном любом объекте альтернативного правила применяется пункт контекстного меню Add CPP code.

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

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

Содержание.


Верификация грамматики на соответствие LR(1) классу

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

Верификация выполняется через меню Run \ Verify LR(1) grammar или по горячим клавишам Ctrl-V.

Содержание.


Генерирование С++ кода программы распознавателя (парсера)

Сгенерировать С++ код класса парсера можно, воспользовавшись опцией меню Run \ Generate CPP code. Далее потребуется ввести имя класса парсера и будут сгенерированы файлы CPP и H с таким же именем.

Взаимодействие полученных классов и прикладной программы можно проиллюстрировать на следующей схеме:

.

Содержание.


Использование парсера в прикладной программе

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

class Parser{

  public:

 	bool noerror;

    	int line;

    	AnsiString errorText;

  public:

    	Parser();

    	bool write(char *filename);

    	bool read(char *filename);

    	void init();

    	bool parse(AnsiString as);

};

Приведем пример использования класса парсера.

// Обязательный шаг создания парсера

  Parser p;

// Обязательный шаг загрузки грамматики

  p.read("c:\\temp\\calc.vyp");

// Обязательный шаг инициализации

  p.init();

// Разбор текста и вывод ошибки в случае неудачи

  if(!p.parse(text->Text)) {

  	MessageBox(NULL,p.errorText.c_str(),"",0);

  }