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


Rambler's Top100


Абстрактный визуальный синтаксис
© Мартин Эрвиг (Martin Erwig)

Источник: http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#TVL97
Перевод: Александр Яшин (escander@ulstu.ru)

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

1. Что такое абстрактный визуальный синтаксис.

Существует множество формализмов для определения синтаксиса визуальных языков (Для сравнения [MM96]). Большинство из существующих подходов используют в своей основе конкретный синтаксис, и лишь некоторые авторы затрагивают абстрактный синтаксис [AER96]. Что странно, ведь в текстовых языках использование абстрактного синтаксиса показало себя с положительной стороны и оказалось полезным во многих ситуациях, в том числе и при построении компиляторов, преобразовании программ и определении семантики. Одна из причин, на мой взгляд, состоит в том, что оптимальный уровень абстракции синтаксиса для визуальных языков еще не найден. Мы же предполагаем, что он может быть "более абстрактным" нежели в текстовом случае.

Покажем это на простом примере. Рассмотрим текстовую грамматику, описывающую часть конкретного синтаксиса "выражений".

expr ::= n-expr | b-expr | if-expr
n-expr::= term | n-expr + term
term ::= factor | term * factor
factor ::= id | ( n-expr )
b-expr ::= id | b-expr ∨ b-expr | ...
if-expr ::= if b-expr then expr else expr

Соответствующий абстрактный синтаксис мог бы игнорировать множество таких деталей, как выбор ключевых слов, правила грамматики для определения ассоциативности операторов, или правила ограничивающие набор операций [Mos90].

expr ::= id | expr op expr | if ( expr , expr , expr )
op ::= + | * | ∨ | ...

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

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

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

Определение 1.
Ориентированным помеченным мультиграфом (α, β) называют пятерку G = (V, E, ι, ν, ε), состоящую из множества узлов V и множества дуг E, где ι: E → V ╳ V - полное отображение, определяющее для каждой дуги инцидентные вершины. Частичные отображения ν: V → α, ε: E → β приписывают метки узлам и дугам.

Для графа G, V(G) и E(G) обозначают множество узлов и дуг графа G. Мы будем использовать сокращения V и E в тех случаях, когда G строго определен. Так же для краткости утверждение "узел (дуга) x помечена как l" будем записывать в виде x:l.

Начало дуги e ∈ E ι(e)=(v, w) определяется как σ(e)=v, а конец дуги e как τ(e) = w. Маршрут в графе G - это чередующаяся последовательность узлов и дуг p = [v1, e1, v2, e2 : vn, en, vn+1], (eiE(G), 1≤i≤n), таких что для : σ(ei) = vi и τ(ei) = vi+1. В частности пустой маршрут - это последовательность, состоящая лишь из одной вершины [v1]. Если каждая дуга идентифицируется vi и vi+1, маршрут можно записать проще [v1, v2, : vn+1]

Мы расширим определение функций τ и υ: τ(p)=v1 и υ(p) = vi+1. Множество маршрутов обозначим как P(G). Заметьте, что P(G) не включает ни простые маршруты, ни циклы, ни маршруты, в которых одни и те же дуги встречаются несколько раз.

Типы меток могут быть как просто множеством символов, так и некоторыми сложными структурами, которые дают возможность помечать узлы или дуги термами или семантическими переменными. Множество графов (α, β) обозначают как Γ(α, β).

Определение 2.
Визуальный язык (α, β) это множество графов VL⊆Γ(α, β).

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

Существует еще один фактор, влияющий на абстрактность - выбор связей. Представления, основанные на элементарных отношениях, таких как "касается" или "содержит", более объемны по сравнению с представлениями, в которых дуги символизируют отношения типа "соединяется стрелкой с меткой x". Подробная иллюстрация дается во 2м разделе. Там же - сравнение нашего подхода с уже существующими. Индуктивное определение графов и метод их сравнения с образцом - в 4м разделе статьи, а демонстрация использования абстрактного синтаксиса - в 5м.

2. Обзор работ

Использование графов для описания диаграмм - широко распространенный подход. Однако, существует всего несколько основных моделей, которые активно применяются в графовых языках. Например Hi-графы [Har88] и теория графовых грамматик [Cou90].

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

Графовые грамматики представляют ясную модель визуальных языков. Обладая значительной мощностью, они в основном применяются для трансформации графов. Графовые грамматики основываются на объемной теоретической базе и используют, в некотором смысле, индуктивное определение графов. В таком случае справедливо задаться вопросом: зачем нам еще одна графовая модель? Основная сложность графовых грамматик в том, что они полагают обрабатываемые графы глобальными переменными, при преобразовании которых могут возникнуть ошибки. Это означает, что правила грамматики безоговорочно изменяют граф, и, таким образом, декларативная обработка запрещена. Еще более усложняет ситуацию тот факт, что семантика графовой грамматики - скорее комплекс сложных внутренних недетерминированных правил. В противоположность этому, индуктивное определение графа, изложенное в 4м разделе, трактует граф как явный параметр преобразования.

Спецификации синтаксиса визуальных языков используют алгебраический инструментарий [WL93] и несколько логических формализмов [MMW96]. Например, в [WL93] диаграмма представляется множеством терминальных символов, генерируемых на основе некоторой сигнатуры, входящей в сигнатуру визуального языка. При логическом подходе диаграмма представляется в виде множества фактов, что не особо отличается от предыдущего подхода. Интересно отметить, что эти формализмы работают с конкретным синтаксисом, хотя возможно, в принципе, получение более абстрактного представления путем определения соответствующих предикатов. В любом случае, возможна трансформация логического описания в граф и наоборот.

Идея абстрактного визуального синтаксиса детально изложена в публикациях: [AER96], [RS95], [RS96]. Несмотря на то, что авторы отметили необходимость разделения конкретного и абстрактного синтаксиса, они все же не довели до конца это разделение, хотя для их задач требовались однозначные соотношения между обоими уровнями абстракций.

3. Примеры: Диаграммы состояний и VEX

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

На диаграмме состояний круги представляют собой состояния, а стрелки - переходы между ними. Одна из стрелок помечается специальным символом start. Круг, в который она заходит, считается начальным состоянием автомата. Все другие стрелки, соединенные своими началами и концами с кругами помечаются с помощью множества символов из некоторого алфавита А и символом ◊, означающим пустое слово. Конечное состояние автомата представляется с помощью двойного кружка.

Автомат на диаграмме 1 принимает строки из символов "a" и "b", соединяющиеся парой символов "a" или "b".

Диаграмма 1. Конечный автомат для языка (a ∪ b)*(aa ∪ bb)(a ∪ b)*

Какова структурная информация диаграммы состояний? Диаграмма состояний состоит из следующих объектов: круги, двойные круги, символы алфавита A, стрелки, специальный символ start. Следовательно, типы узлов графа: {○, ⓞ, →, start} ∪ A. Связи: соединение стрелкой с (двойным) кругом и пометка стрелки символом. Теперь мы можем определиться с метками дуг: {src, tgt, lab}, где src, tgt - метки дуг, представляющие соединение стрелок началом и концом соответственно. Получившийся абстрактный синтаксический граф расположен на диаграмме 2.

Диаграмма 2. Абстрактный синтаксический граф для автомата

Теперь, проигнорировав структурную составляющую, ясно, что визуальный язык задается графом типа { {○, ⓞ, →, start, ◊} ∪ A,{src, tgt, lab} }, что фактически является супермножеством корректно оформленных диаграмм состояний.

Интересно, что в графе, представляющим синтаксически корректные диаграммы состояний встречаются одни и те же повторяющиеся элементы. Например, все вершины "→" (за исключением одной) обладают двумя исходящими дугами, соединенными с кругами, и одной входящей, соединенной с узлом-символом. Одна из исходящих дуг помечена src, другая tgt. Входящая дуга помечена lab. В таком случае возможна безопасная замена (замена без потери какой-либо значимой информации) этого подграфа более абстрактным отношением. Оно будет представлено дугой, начало которой в конце дуги src, конец - в конце дуги tgt, а метка - символы узла, в который входила дуга lab. Теперь необходимо решить, что делать со стрелками, которые помечены более чем одним символом. Для удобства каждой метке отведем по дуге. После этого, можно избавиться от узлов-символов, которые теперь изолированы и не являются частью какого-либо отношения. Наконец, мы можем избавиться от маршрута [u:start, v:, w:○], помечая последний узел маршрута как стартовый. В результате, мы имеем три вида меток узлов (так как есть еще и конечная вершина): только стартовый узел S, только конечный узел F, и стартовый и конечный узел SF. Все другие узлы могут быть непомечены. Теперь мы располагаем более лаконичным абстрактным синтаксисом диаграмм состояний: граф { {S, F, SF}, A ∪ {◊} } (см. диаграмму 3).

Диаграмма 3. Более абстрактный синтаксический граф для автомата

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

Примером может послужить язык VEX, служащий визуальной нотацией лямбда-исчислений [CHZ95]: пустые окружности обозначают идентификаторы, непустые - абстракции, а комбинации (применения функции к аргументу) изображаются двумя соприкасающимися окружностями со стрелкой, проведенной через точку касания от функции к аргументу. Каждая окружность-идентификатор, соединена прямой линией с так называемой корневой вершиной, которая касается окружности-абстракции, находящуюся внутри нее. В этом случае корневая вершина представляет параметр абстракции. Если корневая вершина находится снаружи другой окружности, она обозначает свободную переменную. Пример VEX для лямбда выражения λy.((λx.yx)z) см. на диаграмме 4.

Диаграмма 4. Простая VEX диаграмма

Как и в других случаях, абстрактный синтаксис может быть получен на различных уровнях абстракции. Во-первых, можно просто заменить линии и стрелки дугами def и apply, а внутренние и внутренние с касанием отношения дугами body и par соответственно. Метки узлов не нужны совсем, так как узлы-абстракции отличаются от узлов-переменных наличием инцидентных дуг. Таким образом, абстрактный синтаксис VEX может быть представлен в виде графа типа {∅, {def, apply, par, body}} (см. левую часть диаграммы 5).

С другой стороны, мы можем представить VEX диаграмму с помощью АТД, чтобы облегчить лаконичное описание семантики [Erw97b]. Такое представление содержит узлы-комбинации, узлы-абстракции и узлы-переменные с соответствующими метками вершин: @, λ, ○ (не помеченная). @-узел имеет исходящие дуги fun и arg, ведущие к функции и аргументу соответственно. Этот абстрактный синтаксис для VEX представляется графом типа {{@, λ}, {fun, arg, par, body}} (см. правую часть диаграммы 5).

Диаграмма 5. Абстрактный синтаксис VEX
4. Индуктивное определение графа

Мы можем определять граф в стиле алгебры, заимствованной в функциональных языках программирования: граф или пустой или составлен из графа g и нового узла v, соединенного исходящими дугами с последующими узлами в графе g и входящими дугам с предшествующими узлами в графе g. Используя этот подход, можно составить граф с помощью конструктора Empty, конструктора N от трех аргументов (pred-spec, node, succ-spec), называющихся контекстом узла, и расширяющегося графа g. Здесь node-spec - идентификатор узла, еще не содержащегося в g, с вероятно следующей за ним меткой. Например, v:S или y:F. pred-spec (succ-spec) - список предшествующих (следующих) узлов и расширенных (по возможности) меткой дуг, которые приходят из (следуют в) эти узлы. Например, [x>a, w>b] обозначают список из двух предшествующих узлов x и w, приходящие дуги из которых помечены a и b соответственно. Подобно этому [a>y, b>y] означают одиночный последующий элемент y, в который входят две различные дуги. Граф, показанный на диаграмме 3, можно представить следующими выражениями:

(N ([x>a, w>b], v:S, [a>w, b>x])
(N ([], w, [a>y]) (N ([], x, [b>y]) (N ([], y:F, [a>y, b>y]) Empty)))

Здесь v, w, x и y - произвольные идентификаторы узлов, которые попарно различны. В дальнейшем будем использовать два сокращения: (1) пустые последовательности могут быть опущены, и (2) каскады из N-конструкторов заменяются одним N*-конструктором. Используя эти сокращение, вышеуказанный терм может быть приведен к:

N* ([x>a, w>b], v:S, [a>w, b>x]) (w, [a>y]) (x, [b>y]) (y:F, [a>y, b>y]) Empty

Индуктивные графовые выражения не обязательно уникальны. В частности, порядок, в котором вершины появляются, может произвольно меняться (однако предшествующие и последующие элементы должны быть представлены соответствующе). К тому же индуктивным графовым выражением может быть представлен помеченный мультиграф (см. Erw97a - там же дается определение формальной семантике графов этого типа и графовых конструкторов).

В основном подобные конструкторы в контексте данной работы применяются не для построения новых графов, а для применения в алгоритме сравнения графов с шаблоном. Особенно полезна концепция активных шаблонов [Erw96]: как известно из практики сравнения с шаблоном над типами данных, сравнение с образцом, подобное N (p, v:l, s) g, над графовым выражением связывает последнюю вставленную вершину контекста с p, v, l и s и остальным графом g. Однако, в процессе обхода графа, необходимо сравнивать контекст и текущий узел. Это возможно, если v уже связан со сравниваемым узлом. В таком случае контекст v связывается с остальными переменными. Например, сравнивая шаблон N (p, y:l, s) g с предыдущими графовыми выражениями, получаем связи:

P → [w>a, x>b]), l → F, s → [a>y, b>y], g → "rest-graph"

Где "rest-graph" - произвольное представление сравниваемого графа без узла y и инцидентных ему дуг. Например:

N* ([x>a, w>b]), v:S, [a>w,b>x] (w) (x) Empty

Шаблоны в будущем можно ограничить добавлением меток, представленных как замена списка переменных s или p более конкретным списком шаблонов. Например, x::l сравнивает любой непустой список и связывает x с его головой, а l - с его хвостом. Есть возможность сравнивать списки так же и определенной длины. В процессе этого можно игнорировать связи между всеми элементами, просто опуская соответствующие части шаблона. Например, мы можем, сравнивая узел v, связать узлы, в которые входят дуги a и b, с переменными i и j, используя шаблон: N (v, [a>i, b>j]) g. В результате i и j будут связаны с вершинами w и x соответственно. Однако в этом примере не указано что-либо относительно предшествующих узлов, поэтому связей с ними мы не получим. Если мы формулируем требование, что у узла не должно быть предшествующей вершины, мы можем изменить шаблон на N ([], v, [a>i, b>j]) g. Однако в таком виде этот шаблон не даст возможность сравнивать графы из наших примеров. В подобных случаях справляется шаблон, изложенный чуть далее по тексту (описанный в виде функции).

Рассмотрим сравнение каскадного шаблона N* c1, c2 : cn g с графом g`. Допустим g1,:, gn - вспомогательные переменные для связывания промежуточных составных графов. Таким образом, N c1 g1, сопоставляясь с g`, дает связь, в которой узел связывается с c1 и остальным графом g1. Эта связь участвует в сравнении N* c2:cn g с графом g1, то есть N c2 g2 сравнивается c g1, N c3 g3 сравнивается против g2 и так далее, до тех пор, пока N cn gn не сопоставится c gn-1. Тогда g будет связано с gn. Таким образом, N* шаблон фактически может быть использованным для удобного поиска маршрута (фиксированной длины) в графе.

Используем дополнительный конструктор ребер E (v>l>w) g, который просто вставляет дугу с меткой l между двумя узлами v и w (v и w должны присутствовать в графе). E конструктор играет вспомогательную функцию и может быть выражен в терминах N: например, сравнивая узел v, и вставляя его заново с l>w как узел, следующий за текущим.

E (v>l>w) (N (p, v:m, s) g) := N (p, v:m, (l>w)::s) g

В некоторых случаях E более удобен, нежели вложенные конструкции N.

5. Применение абстрактного синтаксиса

Покажем, как определить семантику для диаграмм состояний, используя второй из полученных абстрактных синтаксисов. Затем продемонстрируем, как индуктивное определение графа может быть использовано для преобразования между различными уровнями визуального синтаксиса. (Использование индуктивного графа для определения семантики: [Erw97b])

5.1 Маршрутные семантики диаграмм состояний

Семантика диаграмм состояний заключается в маршрутах абстрактного синтаксического графа в соответствии со словами из алфавита A. Фактически, это происходит в два шага: во-первых, определяется множество маршрутов диаграмм состояний, которые соответствуют поведению автомата, когда слово принято. Эти маршруты (простые и непростые) - все конечны. Их начальный узел помечен как S (или SF), конечный - как F (или SF). Затем множество допустимых слов извлекается путем концентрирования меток каждого такого маршрута.

agg (f, u) [v] := u
agg (f, u) [v1, e1, v2, :, vn+1] := f(ε(e1), agg(f, u) [v2, :, vn+1])

Запись означает, что пустой маршрут отобразится в u, а отображение непустого маршрута состоит из агрегации метки первой дуги с агрегацией остальной части графа путем вызова функции f (agg - это фактически аналогия оператора "свертка/сдвиг" в функциональных языках). Теперь слово, представленное маршрутом в графе автомата, может быть извлечено путем агрегирования маршрута с u, являющимся пустым словом, и f, определяющим соединение символа a перед словом s. Это обычно выражается как a∙s, где ◊∙s = s∙◊ = s

Следовательно, семантика автомата представляется с помощью абстрактного синтаксического графа:

S[g] := {agg(∙,◊) p | pP(g) ∧ v(σ(p)) ∈ {S, SF} ∧ v(τ(p)) ∈ {F,SF}}

5.2 Трансформация синтаксиса

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

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

Первый применяется, когда узел u с меткой → существует, и когда этот узел имеет менее одного узла-предшественника x и два узла-последователя (v и w), соединенных с узлом u дугами src и tgt соответственно. В этом случае дуга из v в w с меткой l будет помещена в граф с помощью конструктора ребра E. Теперь включаем l, сравнивая x после u, используя каскадный шаблон. Заметьте, что конструктор E(v>l>w) не применен к g, составляющий граф без u и x. Вставка x заново необходима тогда, когда это будет использоваться метками других ребер, и вставка заново u вместе со всеми остальными предшественниками необходима для активизации вставки ребер для всевозможных других меток (дающихся p). Второй вариант простое удаление узлов →,не имеющих каких-либо меток, третий вариант - для завершения.

repl (N* (x::p,u:, [src>v, tgt>w]) (x:l,s) g) := E(v>l>w) (repl(N*(p,u:, [src>v, tgt>w]) (x:l,s) g))
repl (N ([],u:) g) := repl g
repl g := g

Удаление изолированных меток узлов реализуется функцией del.

del (N ([],v,[]) g) := del g
del g := g

Наконец замена стартового узла и изменение метки у финального состояния завершается функцией relab. Первый шаблон определяет маршрут из стартовой вершины через узел u с меткой → к актуальной стартовой вершине w автомата.

relab (N* (u:start,[v]) (v,[w]) (w:l,s) g) := N(u:if l = ⓞ then SF else S, s) (relab g)
relab (N (p,v:ⓞ,s) g) := N(p,v:F,s) (relab g)
relab g := g

Наконец, заканчиваем трансформацию простым вызовом:

transform g := relab(del(repl g))

6. Выводы

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

Литература
[AER96] Andries, M., Engels, G. & Rekers, J.: How to Represent a Visual Program?,Workshop on Theory of Visual Languages, 1996.
[CHZ95] Citrin, W., Hall, R. & Zorn, B.: Programming with Visual Expressions,IEEE Symp. on Visual Languages, pp. 294-301, 1995.
[Cou90] Courcelle, B.: Graph Rewriting: An Algebraic and Logic Approach, in J. van Leeuwen (ed.): Handbook of Theoretical Computer Science, Vol. B, Elsevier, pp. 193-242, 1990.
[Erw96] Erwig, M.: Active Patterns, 8th Int. Workshop on Implementation of Functional Languages, LNCS 1268, pp. 21-40, 1996.
[Erw97a] Erwig, M.: Functional Programming with Graphs,2nd ACM SIGPLAN Int. Conf. on Functional Programming, pp. 52-65, 1997.
[Erw97b] Erwig, M.: Semantics of Visual Languages, IEEE Symp. on Visual Languages, 1997. http://voss.fernuni-hagen.de/pi4/erwig/abstracts.html#VL97
[Har88] Harel, D.: On Visual Formalisms, Communications of the ACM, Vol. 31, No. 5, pp.514-530, 1988.
[MM96] Marriott, K., Meyer, B. & Wittenburg, K.: A Survey of Visual Language Specification and Recognition, Workshop on Theory of Visual Languages, 1996.
[MMW96] Marriott, K. & Meyer, B.: Towards a Hierarchy of Visual Languages, IEEE Symp. on Visual Languages, 1996.
[Mos90] Mosses, P.D.: Denotational Semantics, in J. van Leeuwen (ed.): Handbook of Theoretical Computer Science, Vol. B, Elsevier, pp. 575-631, 1990.
[RS95] Rekers, J. & Schьrr, A.: A Graph Grammar Approach to Graphical Parsing, IEEE Symp. on Visual Languages, pp. 195-202, 1995.
[RS96] Rekers, J. & Schьrr, A.: A Graph Based Framework for the Implementation of Visual Environments, IEEE Symp. on Visual Languages, 1996.
[WL93] Wang, D. & Lee, J.R.: Visual Reasoning: its Formal Semantics and Applications, Journal of Visual Languages and Computing 4, pp. 327-356, 1993.
Шаров Олег, © 2002 - 2007