Графические грамматики


Rambler's Top100


Задачи нейтрализации ошибок в RV-грамматиках
Шаров О. Г.

Для графических языков, как и для текстовых, задача нейтрализации синтаксических ошибок является одной из важных.

От анализатора ожидают:
1. Точного указания места ошибки.
2. Продолжения анализа после обнаружения первой ошибки с целью обнаружения остальных [1].

Для текстовых языков первое требование не всегда выполнимо, поскольку результат ошибки может сказаться не обязательно в том месте, где эта ошибка была допущена. RV - анализатор обнаруживает синтаксически неправильную конструкцию на первом недопустимом графическом объекте или в случае отсутствия ожидаемого графического объекта [2].

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

Для решения этой задачи в RV - грамматиках вводятся вершины - продолжатели, которые используются для продолжения анализа в случае обнаружения ошибки. Понятно, что меняется и методика построения RV - грамматики, но незначительно.
1. На фазе синтеза добавляется этап определения списка типов вершин - продолжателей анализа. В качестве таковых, например, для языка графических схем алгоритмов, могут выступать: логическое условие и объединение взаимоисключающих ветвей.
2. Расширяется квазитермальный алфавит. Вводятся квазитермы вершин - продолжателей и квазитерм проверки наличия вершин - продолжателей.

Квазитермы вершин - продолжателей необходимы для "первичного" и "вторичного" анализа вершины. Эти события возникают из-за наличия двух типов перехода к графическому объекту во время анализа:
* естественного перехода от связи к графическому объекту;
* выбора данного объекта в качестве продолжателя анализа.

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

Литература
1. Хантер Р. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232 с., ил.
2. Шаров О.Г. Автоматная графическая грамматика (RV - грамматика) http://gg.ulstu.ru


Информатика, системы искусственного интеллекта и моделирование технических систем. Труды международной конференции "Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике . КЛИН . 2005" (17-19 мая 2005 г.) / под общей редакцией Л.И. Волгина. Ульяновск: УлГТУ, 2005 г. . Том.2 . 209с.
Шаров Олег, © 2002 - 2007