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


Rambler's Top100


Исследование и классификация графических грамматик
Шаров О. Г.

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

Многообразие существующих графических грамматик большинство исследователей делит на 4 типа [1]:
* Грамматики обработки изображений. Грамматики данного типа предназначены для разбора цифровых изображений состоящих из пикселей. Эти грамматики обнаруживают структуру визуального предложения, составляя индивидуальные пиксели в визуальные элементы (линия, дуга и т.д.). Этот подход используется, когда системе необходимо распознать пиктограммы с определенным допустимым уровнем ошибок (например, рукописные числа).
* Грамматики предшествования. Эти грамматики пространственного разбора могут использоваться для анализа двухмерных математических выражений и анализа печатных полос. Грамматики предшествования наиболее подходят для синтаксического анализа визуальных предложений из элементарных пиктограмм и пиктограммых операций. Деревья разбора строятся сравнением операторов предшествования в шаблоне и погружением шаблона в один или более подшаблон.
* Контекстно . свободные и контекстно . зависимые грамматики. Эти грамматики используются для спецификации композиций визуальных предложений хорошо известных формализмов, поэтому много стандартных методов разбора таких грамматик применимы.
* Графовые грамматики. Они, безусловно, самые мощные спецификации визуальных языков. Эти формализмы обеспечивают большинство методов установления контекстных отношений.
Последние два типа грамматик находят применение в САПР СВТ и CASE . средствах. Так, на базе позиционных грамматик реализована система VLCC [2] (компилятор компилятора визуального языка) для автоматической генерации окружения визуального программирования. Грамматики отношений использовались при создании средства проектирования моделей последовательности технологических операций, названного ShowBiz [4].

Большинство контекстно . свободных и контекстно . зависимых грамматик развивались на формализме плекс . структур [6], которые были предложены Федером. Позиционные грамматики [2] вобрали в себя все достоинства и недостатки плекс . грамматик. В грамматиках отношений [4] формализм, предложенный Федером, расширен и реализована возможность использования графических объектов, содержащих динамически изменяемое количество входов или выходов. Причем для каждого элемента, имеющего более одного выхода, должен быть элемент, .собирающий. все его потоки.

Графовые грамматики являются частным случаем веб . грамматик предложенных Пфальцем и Розенфельдом [6]. Любая графовая грамматика . это кортеж (А, Р), где А . не пустой начальный граф (аксиома) и Р . множество продукций графовой грамматики. Каждая продукция имеет два графа, называемых левым и правым графом. А . специальный случай продукции с пустой левой частью. Наиболее известными представителями данного класса грамматик являются многоуровневая графовая грамматика [3] и сохраняющая графовая грамматика [5].

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

Следует отметить, что для графических грамматик характерно полиномиальное или экспоненциальное время разбора.

Литературы
1. Boshernitsan M., Downes M. Visual programming languages: A survey. . 1997. http://citeseer.ist.psu.edu/boshernitsan97visual.html

2. Costagliola G., Lucia A. D., Orefice S., Tortora G. Positional grammars: a formalism for LR-like parsing of visual languages. http://www.dmi.unisa.it/people/costagliola/www/home/papers/tvl96.ps.gz

3. Rekers J., Schurr A. Defining and parsing visual languages with layered graph grammars// Journal of Visual Languages and Computing. . 1997. . Vol. 8, no. 1. . pp. 27 . 55. http://citeseer.ist.psu.edu/rekers97de_ning.html

4. Wittenburg K. Relational grammars: Theory and practice in a visual language interface for process modeling. . 1996. http://citeseer.ist.psu.edu/wittenburg96relational.html

5. Zhang D.-Q., Zhang K., Cao J. A context-sensitive graph grammar formalism for the specification of visual languages // The Computer Journal. . 2001. . Vol. 44, no. 3. . pp. 186 . 200. http://citeseer.ist.psu.edu/zhang01contextsensitive.html

6. Фу К. Структурные методы в распознавании образов. . М.: Мир, 1977. . 319 с.


По материалам магистерской диссертации, 2004 г.
Шаров Олег, © 2002 - 2007