形狀文法在計算機科學中是一種特定的生產系統,用於生成幾何形狀。通常,形狀是二維或三維的,因此形狀文法是研究二維和三維語言的一種方式。形狀文法最早由喬治·史坦尼(George Stiny)和詹姆斯·吉普斯(James Gips)於 1971 年在一篇開創性文章中提出。
形狀文法的數學和算法基礎(特別是針對二維線性元素)由喬治·史坦尼在其著作《圖形與形狀文法的形式方面》(Pictorial and Formal Aspects of Shapes and Shape Grammars)(Birkhäuser Basel,1975)中開發。形狀文法的應用最早由詹姆斯·吉普斯在其著作《形狀文法及其用途》(Shape Grammars and their Uses)(Birkhäuser Basel,1975)中進行了探討。這些出版物還包含兩種獨立但等效的構造,表明形狀文法可以模擬圖靈機。
一個形狀文法由形狀規則和一個選擇並處理規則的生成引擎組成。形狀規則定義了現有形狀(或其一部分)如何被轉換。形狀規則包含兩個部分,由一個從左到右的箭頭分隔。箭頭左側的部分稱為左側(LHS),它以形狀和標記的形式描述一個條件。箭頭右側的部分稱為右側(RHS),它描述了 LHS 形狀應如何被轉換以及標記的位置。標記有助於定位和定向新形狀。
一個形狀文法最少包含三個形狀規則:一個起始規則、至少一個轉換規則和一個終止規則。起始規則對於啟動形狀生成過程是必需的。終止規則對於使形狀生成過程停止是必需的。停止過程的最簡單方法是使用一個移除標記的形狀規則。形狀文法在一個主要方面與喬姆斯基文法不同:生產規則可以串行應用(如同喬姆斯基文法),也可以並行應用(喬姆斯基文法不允許),這類似於 L-系統中的「生產」方式。
形狀文法系統額外有一個工作區域,用於顯示創建的幾何圖形。生成引擎檢查現有的幾何圖形,通常稱為當前工作形狀(CWS),以尋找與形狀規則的 LHS 相匹配的條件。具有匹配 LHS 的形狀規則有資格被使用。如果有多個規則適用,生成引擎必須選擇要應用的規則。在另一種情況下,引擎首先選擇一個文法規則,然後嘗試在 CWS 中找到該規則 LHS 的所有匹配項。如果有多個匹配項,引擎可以(取決於其配置/實現)
當形狀文法被限制在一個小型、定義明確的生成問題中時,例如房屋佈局和結構細化,它們最為有用。由於形狀規則通常在小型形狀上定義,因此一個形狀文法可以很快包含大量規則。例如,威廉·米切爾(William Mitchell)提出的帕拉第奧別墅形狀文法(palladian villas shape grammar)包含 69 個規則,在八個階段中應用。
參數化形狀文法是形狀文法的一種擴展。RHS 中新形狀由參數定義,以便能夠考慮更多現有形狀的上下文。這通常會影響新形狀的內部比例,從而可以創建更多樣化的形式。通過這種方式,人們試圖使形狀文法響應結構條件,例如屋頂結構中梁的寬度取決於跨度。
儘管形狀文法在學術界很受歡迎且具有應用性,但它們並未在通用的計算機輔助設計(CAD)應用中得到廣泛應用。
形狀文法最初是為繪畫和雕塑提出的,但尤其在建築學(計算機輔助建築設計)中得到了研究,因為它們提供了一種創建新設計的形式系統。形狀文法應用的其他重要領域包括裝飾藝術、工業設計和工程學。
這是一個可在網路上找到的軟件原型列表(其中一些嚴格來說更像是集合文法系統):