Грамматика формы

Грамматики форм в вычислениях представляют собой особый класс систем производства , которые генерируют геометрические формы. Обычно формы являются 2- или 3-мерными, поэтому грамматики форм являются способом изучения 2- и 3-мерных языков. Грамматики форм были впервые представлены в основополагающей статье Джорджа Стини и Джеймса Гипса в 1971 году. ^[1] Математические и алгоритмические основы грамматик форм (в частности, для линейных элементов в двух измерениях) были разработаны в "Изображениях и формальных аспектах форм и грамматик форм" (Birkhäuser Basel, 1975) Джорджа Стини. Приложения грамматик форм были впервые рассмотрены в "Грамматиках форм и их использовании" (Birkhäuser Basel, 1975) Джеймса Гипса. Эти публикации также содержат две независимые, хотя и эквивалентные, конструкции, показывающие, что грамматики форм могут имитировать машины Тьюринга .

Определение

Грамматика формы состоит из правил формы и механизма генерации , который выбирает и обрабатывает правила. Правило формы определяет, как существующая (часть) формы может быть преобразована. Правило формы состоит из двух частей, разделенных стрелкой, указывающей слева направо. Часть слева от стрелки называется левой стороной (LHS). Она изображает состояние в терминах формы и маркера. Часть справа от стрелки называется правой стороной (RHS). Она изображает, как должна быть преобразована форма LHS и где расположен маркер. Маркер помогает найти и сориентировать новую форму.

Грамматика формы как минимум состоит из трех правил формы: начального правила , как минимум одного правила преобразования и правила завершения . Начальное правило необходимо для начала процесса генерации формы. Правило завершения необходимо для остановки процесса генерации формы. Самый простой способ остановить процесс — применить правило формы, которое удаляет маркер. Грамматики формы отличаются от грамматик Хомского в важном отношении: правила производства могут применяться последовательно (как в грамматиках Хомского) или параллельно (не допускается в грамматиках Хомского ), аналогично тому, как «производства» выполняются в L-Systems .

Система грамматики формы дополнительно имеет рабочую область, где отображается созданная геометрия. Механизм генерации проверяет существующую геометрию, часто называемую Текущей рабочей формой (CWS), на наличие условий, которые соответствуют LHS правил формы. Правила формы с совпадающими LHS допускаются к использованию. Если применяется более одного правила, механизм генерации должен выбрать, какое правило применять. В альтернативном сценарии механизм сначала выбирает одно из правил грамматики, а затем пытается найти все совпадения LHS этого правила в CWS. Если совпадений несколько, механизм может (в зависимости от его конфигурации/реализации)

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

Грамматики форм наиболее полезны, когда они ограничены небольшой, четко определенной проблемой генерации, такой как планировка жилья и уточнение структуры. Поскольку правила форм обычно определяются для небольших форм, грамматика форм может быстро содержать много правил. Грамматика форм палладианских вилл, представленная Уильямом Митчеллом ^[2], например, содержит 69 правил, которые применяются на протяжении восьми этапов.

Параметрические грамматики формы являются расширением грамматик формы. ^[3] Новая форма в правой части правила формы определяется параметрами , чтобы она могла учитывать больше контекста уже существующих форм. Это обычно влияет на внутренние пропорции новой формы, чтобы можно было создать большее разнообразие форм. Таким образом, предпринимаются попытки заставить грамматики формы реагировать на структурные условия, например, ширину балок в конструкциях крыши, которая зависит от пролета.

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

Приложения

Грамматики форм были первоначально представлены для живописи и скульптуры ^[1], но изучались в частности в архитектуре ( компьютерное архитектурное проектирование ), поскольку они обеспечивают формализм для создания новых проектов. Другими важными областями, в которых применялись грамматики форм, являются декоративно-прикладное искусство, промышленный дизайн и инженерия. ^[4]

Прототипы программного обеспечения

Это список прототипов программного обеспечения, доступных в Интернете (некоторые из них, строго говоря, представляют собой довольно устоявшиеся системы грамматики ^[5]^[6] ):

Грамматическая среда
ВИНОГРАД
СД2
Интерпретатор грамматики форм
Shaper2D
шлепок
SubShapeDetector
Генератор здания Инцзао моди
СорталGI

Литература

Стини, Г. и Гипс, Дж. (1972). Грамматики форм и генеративная спецификация живописи и скульптуры. В Information Processing 71, 1460–1465. North-Holland Publishing Company. ссылка на статью
Стини, Г. (1975). Иллюстрированные и формальные аспекты формы и грамматики формы. Birkhäuser Basel. ссылка на книгу
Стини, Г. (1980). Введение в форму и грамматику формы. Окружающая среда и планирование B: Планирование и дизайн 7(3), 343-351.
Найт, TW (1994). Трансформации в дизайне: формальный подход к стилистическим изменениям и инновациям в изобразительном искусстве. Cambridge University Press.
Стини, Г. (2006). Форма: разговоры о видении и действии. MIT Press, Кембридж, Массачусетс. Ссылка на книгу

Смотрите также

Ссылки

^ ab Стини, Г. и Гипс, Дж. (1972). Грамматики форм и генеративная спецификация живописи и скульптуры. В Information Processing 71, 1460–1465. North-Holland Publishing Company.
^ Митчелл, У. (1990). Логика архитектуры. MIT Press, Лондон.
^ Стини, Г. (1980). Введение в форму и грамматику формы. Окружающая среда и планирование B: Планирование и дизайн 7(3), 343-351.
^ Cagan, J. (2001). Инженерные грамматики форм: где мы были и куда идем?. В: Antonsson, EK & Cagan, J. (ред.). Формальный синтез инженерного проектирования. Cambridge University Press, Кембридж, Великобритания.
^ Маккей, А.; Чейз, СК; Ши, К.; Чау, ХХ (2012). Реализация пространственной грамматики: от теории к пригодному к использованию программному обеспечению. AI EDAM (Искусственный интеллект для инженерного проектирования, анализа и производства) 26(02), 143-159.
^ Стини, Г. (1982). Пространственные отношения и грамматики. Окружающая среда и планирование B: Планирование и дизайн 9(1), 113–114.

Внешние ссылки

www.shapegrammar.org (последний снимок в интернет-архиве (2019))
Грамматика и моделирование стиля формы (список литературы)
Реализация грамматики форм: от теории к пригодному для использования программному обеспечению (обзор подходов к вычислительной реализации по состоянию на 2010 г.)
Семинар по достижениям в области грамматики форм по состоянию на 2016 год

[stiny1972-1] Стини, Г. и Гипс, Дж. (1972). Грамматики форм и генеративная спецификация живописи и скульптуры. В Information Processing 71, 1460–1465. North-Holland Publishing Company.

[2] Митчелл, У. (1990). Логика архитектуры. MIT Press, Лондон.

[3] Стини, Г. (1980). Введение в форму и грамматику формы. Окружающая среда и планирование B: Планирование и дизайн 7(3), 343-351.

[4] Cagan, J. (2001). Инженерные грамматики форм: где мы были и куда идем?. В: Antonsson, EK & Cagan, J. (ред.). Формальный синтез инженерного проектирования. Cambridge University Press, Кембридж, Великобритания.

[5] Маккей, А.; Чейз, СК; Ши, К.; Чау, ХХ (2012). Реализация пространственной грамматики: от теории к пригодному к использованию программному обеспечению. AI EDAM (Искусственный интеллект для инженерного проектирования, анализа и производства) 26(02), 143-159.

[6] Стини, Г. (1982). Пространственные отношения и грамматики. Окружающая среда и планирование B: Планирование и дизайн 9(1), 113–114.