Формальная грамматика — HiSoUR История культуры

Грамматики формы в вычислении — это особый класс производственных систем, которые генерируют геометрические формы. Обычно формы являются 2- или 3-мерными, поэтому грамматики формы являются способом изучения 2- и 3-мерных языков. Основа грамматики формы была определена в оригинальной статье Джорджа Стини и Джеймса Гипса в 1971 году.

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

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

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

Формальная грамматика формально определяется как 4- кортеж ${\ displaystyle G = (V_ {T}, V_ {M}, R, I)}$ ,

$V_T$ является конечным набором символов,
${\ displaystyle V_ {M}}$ является конечным набором символов, поэтому ${\ displaystyle V_ {T} * \ Cap V_ {M} = \ Sigma}$ ,
$р$ — конечный набор правил производства
$я$ является исходной фигурой, состоящей из элементов ${\ displaystyle V_ {T} *}$ а также ${\ displaystyle V_ {M}}$ ,

Элементы толпы ${\ displaystyle V_ {T} *}$ являются конечным расположением любого числа элементов $V_T$ с любым масштабированием или ориентацией.

Элементы ${\ displaystyle V_ {T} *}$ что в правиле $(U, v)$ вне $р$ , или в $я$ события называются терминальными цифрами.

Элементы $V_T$ являются так называемыми нетерминальными цифрами или маркерами. элементы $(U, v)$ вне $р$ называются правилами формы или производственными правилами и находятся в форме ${\ displaystyle u-> v}$ записан.

Левая сторона $U$ представляет собой фигуру, состоящую из элемента ${\ displaystyle V_ {T} *}$ в сочетании с одним элементом $V_T$ ,

Правая сторона $v$ представляет собой фигуру и состоит из одного и того же элемента ${\ displaystyle V_ {T} *}$ это в $U$ происходит тот же самый элемент ${\ displaystyle V_ {T} *}$ в $U$ , в сочетании с элементом ${\ displaystyle V_ {M}}$ , или тот же элемент ${\ displaystyle V_ {T} *}$ в $U$ , с дополнительным элементом ${\ displaystyle V_ {T} *}$ в сочетании с элементом ${\ displaystyle V_ {M}}$ ,

$я$ является исходной фигурой, состоящей из элементов ${\ displaystyle V_ {T} *}$ а также ${\ displaystyle V_ {M}}$ , Он обычно состоит по крайней мере из одного элемента, который как $U$ в правиле $(U, v)$ в $р$ имеет место.

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

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

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

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

Грамматика формы генерирует фигуру путем рекурсивного применения правил формы, начиная с начальной фигуры.Результатом применения правила к существующему рисунку всегда является новая фигура, состоящая из существующей фигуры, с появлением левой части правила, при замене новой фигуры на фигуре справа от правила.

Грамматика формы минимально состоит из трех правил производства (= правила формы). Исходное правило, по крайней мере одно правило преобразования и правило завершения. Для запуска процесса генерации требуется правило запуска, в то время как правило планирования необходимо для завершения генерации. Самый простой способ остановить процесс — удалить маркер (= nonterminals). В отличие от грамматик Хомского, правила производства в граммах Shape могут применяться не только последовательно, но и параллельно, подобно последовательности L-систем.

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

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

Параметрические грамматические символы являются расширением грамматики формы. Вместо правил производства, схема правил формы ( ${\ displaystyle \ alpha -> \ beta}$ ), которые состоят из параметрических фигур. Вводя конкретные значения в переменные $\альфа$ а также $\бета$ определены новые правила формы, которые затем используются обычным способом для создания новых фигур. Благодаря этому обобщению может быть создано большее изменение фигур.

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

Подобно архитектуре, грамматики формы становятся все более важными в компьютерной графике в последние десятилетия. Грамматика формы используется в основном для процедурного моделирования зданий или городов (например, для фильмов или видеоигр). Форма Граммары составляют основу для многих развитых систем, которые используют правила производства для создания различных 3D-моделей. Как реалистично выглядящие уличные планы, так и фасады или интерьеры зданий могут быть созданы процедурно с использованием форм-грамматик.

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

Программные прототипы
Это список прототипов программного обеспечения, доступных в Интернете (некоторые из них, строго говоря, задают грамматические системы):

Грамматическая среда
GRAPE
SD2
Грамматический переводчик формы
Shaper2D
spapper
SubShapeDetector
Генератор здания Yingzao fashi