June 23rd, 2009

with Cat The Cat

Мысль вслух.

Я тут думал насчёт атрибутных грамматик. Они, в основном, определены над деревом, иерархически описывающим основные стороны проблемы.

Для графов такие грамматики распространены гораздо меньше.

Здесь, конечно же, надо упомянуть DiaGen: DiaGen uses hypergraph grammars to specify diagram languages. Таким образом, из гиперграфа мы получаем, хаха, опять же иерархическое описание в виде абстрактного синтаксического дерева.

Куда ни кинь, всюду клин.

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

Контрпримеров пока придумал немного, это повествование в общем смысле: музыка, литература, кино.

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

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