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


Rambler's Top100


Алгоритм анализа диаграммных языков на базе автоматной RV-грамматики
Шаров О. Г.

Растущий, в последнее время, интерес к диаграммным (графовым) языкам определяет необходимость реализации алгоритмов их анализа. Существует ряд методик анализа диаграммных языков имеющих свои достоинства и недостатки.
Например, авторский формализм автоматной RV - грамматики характеризуется линейными временными затратами на анализ диаграмм и двухкратным сокращением требуемой памяти по сравнению с существующими аналогами.
Алгоритм анализа основан на базе распознающего RV - автомата с внутренней памятью, команда которого имеет вид , где - квазитерм алфавита , - - арное отношение, определяющее вид операции над внутренней памятью (чтение, запись, сравнение); - оператор модификации, задающий различные сочетания отношений ; - имя комплекса продукции - приемника. В качестве внутренней памяти используются стеки, очереди и эластичные ленты, ячейки которых могут работать в режиме счетчика целых положительных чисел.
Распознавание принадлежности диаграммы языку L, заданному RV - грамматикой, сводится к проверке вхождения первого квазитерма проверяемой цепочки левой части какой - либо продукции (команды) комплекса , в то время как последующие квазитермы должны встречаться в левой части текущего комплекса продукций - приемников, а последний квазитерм цепочки обязательно должен принадлежать продукции с в левой части.
Ниже представлена система команд (распознающий автомат) для графической схемы алгоритмов (ГСА).

Анализ диаграммы начинается с элемента , далее должна следовать связь (), на третьем шаге допустимо присудствие любого из элементов , переход в следующее состояние осуществим при условии выполнения соответствующей операции над внутренней памятью и т.д.
В настоящее время разработанны RV - грамматики визуальных языков сетей Петри, ГСА и параллельных ГСА (ПГСА) [2]. Для последних двух существуют программные реализации алгоритма.

Литература
1. Контроль информации в системах автоматизации проектирования / А. Н. Афанасьев, А. А. Гужавин, О. Г. Кокаев и др. - Саратов: Изд-во Саратовского университета, 1985.- 136 с.
2. Шаров О.Г. Автоматная графическая грамматика (RV - грамматика) http://gg.ulstu.ru


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