vCGG:一種基于虛結(jié)點(diǎn)的空間圖文法形式框架*

2021-02-25 12:15:32劉禹鋒

軟件學(xué)報(bào) 2021年12期

劉禹鋒,楊帆

(南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院,江蘇南京 210046)

作為一種豐富的信息描述手段,可視化語言(可視化圖)是軟件系統(tǒng)概念設(shè)計(jì)階段中重要的人機(jī)交互工具,例如數(shù)據(jù)庫(kù)系統(tǒng)概念設(shè)計(jì)階段的 E-R(entity-relationship)圖、面向?qū)ο笙到y(tǒng)中的 UML(unified modeling language)圖以及描述離散并行系統(tǒng)的Petri 網(wǎng).可視化語言研究的重點(diǎn)之一是如何使用有效而又規(guī)范的方式去描述各種不同類型的可視化語言.一部分研究者嘗試使用一維字符文法描述可視化語言,然而,由于圖的二維性以及非線性特點(diǎn),字符文法在描述可視化語言時(shí)有著表達(dá)能力不足以及直觀性較差等問題.基于形式語言理論,圖文法是一種使用產(chǎn)生式(圖重寫規(guī)則)進(jìn)行圖語言定義與分析的二維化形式化工具.使用圖文法對(duì)各種可視化語言語法結(jié)構(gòu)的描述、操縱和分析,具有直觀明了和簡(jiǎn)便的優(yōu)點(diǎn).至今,圖文法已被廣泛地應(yīng)用于各種可視化語言的配置與分析中,例如圖語言定義與轉(zhuǎn)換[1]、圖模型的動(dòng)態(tài)分析[2].不僅如此,圖文法還被廣泛地應(yīng)用于軟件系統(tǒng)建模[3,4]、信息可視化[5]、模式識(shí)別[6-8]等領(lǐng)域.

作為二維或三維空間上最重要的特征之一,空間語義信息在可視化語言的空間拓?fù)浣Y(jié)構(gòu)描述以及空間知識(shí)呈現(xiàn)上是不可或缺的關(guān)鍵因素之一.然而,大多數(shù)圖文法在面向空間語義處理需求時(shí)存在諸多困難之處.Stiny和Gips 從描述空間元素形狀的角度出發(fā),提出了形狀文法SG(shape grammar)[9,10].SG 將形狀定義為一系列空間元素的有限排列,例如線段、點(diǎn)、矩形.SG 的文法直觀易懂,可以被廣泛地應(yīng)用于建筑圖像分析[11]、繪圖設(shè)計(jì)[12]等領(lǐng)域.根據(jù)事先定義的規(guī)則,SG 可以通過迭代地使用形狀替換操作來生成各種各樣的設(shè)計(jì).然而,由于只支持單方向的工作流,SG 更側(cè)重于完成不同類型圖形的生成繪制工作,而在圖形分析處理能力上有所欠缺.Kong 等人[13,14]在上下文相關(guān)圖文法RGG(reserved graph grammar)[15]形式框架中加入了空間信息處理機(jī)制,提出了一種空間圖文法——SGG(spatial graph grammar).SGG 對(duì)空間語義信息采用定性研究方法進(jìn)行描述,包括6 種拓?fù)潢P(guān)系、4 種方向關(guān)系、順序距離關(guān)系以及7 種對(duì)齊關(guān)系.基于定性分析方法,SGG 可以較為直觀靈活地分析各種可視化語言的語法與語義結(jié)構(gòu),在網(wǎng)頁描述及模式驗(yàn)證[16,17]領(lǐng)域取得了較好的應(yīng)用效果.然而,SGG 也有存在一些不足之處:首先,由于對(duì)空間語義信息缺少定量描述能力,SGG 在對(duì)空間關(guān)系進(jìn)行配置時(shí)缺乏相應(yīng)的精準(zhǔn)性;其次,SGG 中使用額外的語義函數(shù)描述空間語義關(guān)系,并通過執(zhí)行操作代碼實(shí)現(xiàn)語義變換,較大程度地增加了SGG 在實(shí)際應(yīng)用中的復(fù)雜性.針對(duì)SG 與SGG 文法框架的局限性,本文作者在前期研究中提出了一種坐標(biāo)圖文法框架——CGG(coordinate graph grammar)[18],將空間語義信息的定量和定性描述機(jī)制整合在一個(gè)理論框架內(nèi),并利用圖形元素之間的坐標(biāo)關(guān)系設(shè)計(jì)了相對(duì)低時(shí)間開銷的圖柄查找算法,為空間語義信息提供了相對(duì)靈活的配置方案.表1 給出了CGG 與SG、SGG 這兩種具有代表性的空間文法框架的對(duì)比,CGG 在保持SG 和SGG優(yōu)點(diǎn)的同時(shí)彌補(bǔ)了兩者的不足,為空間語義配置提供了一個(gè)更全面的形式化框架.目前,CGG 已被應(yīng)用在UML類圖定義與布局[19]、流程圖生成與檢測(cè)[18]等實(shí)際案例中.然而,CGG 是在EGG(edge based graph grammar)[20]的理論框架的基礎(chǔ)上加入空間語義機(jī)制而構(gòu)建的圖文法形式框架,因此,EGG 的部分缺陷延伸到了CGG 中:首先,CGG 中懸邊圖的概念不符合圖論中點(diǎn)邊圖的定義,使得圖柄結(jié)構(gòu)的規(guī)范性有所欠缺;其次,在CGG 的歸約操作中,懸邊的匹配需要考慮圖柄排列問題,導(dǎo)致大量冗余圖柄的出現(xiàn),在一定程度上增加了歸約執(zhí)行步數(shù),也導(dǎo)致大量無效歸約的產(chǎn)生;最后,CGG 產(chǎn)生式中使用懸邊描述上下文信息,通過減少上下文信息的匹配提高文法的抽象程度,卻在某種程度上影響了文法的直觀性以及表達(dá)能力.針對(duì)上述問題,本文在前期研究的基礎(chǔ)上,通過定義虛結(jié)點(diǎn)的概念,構(gòu)建一個(gè)新的空間圖文法框架vCGG(virtual node based coordinate graph grammar).該框架在文法中保留上下文結(jié)點(diǎn)的同時(shí),維持CGG 產(chǎn)生式的抽象能力,從而為圖的空間語義提供更加直觀而全面的形式化描述與分析手段.

Table 1 Comparison among SG,SGG and CGG[18]表1 CGG 與SG、SGG 的對(duì)比[18]

本文第1 節(jié)介紹CGG 的理論框架.第2 節(jié)在CGG 基礎(chǔ)上構(gòu)建一個(gè)新的空間圖文法框架vCGG,包括框架的基本概念與文法操作.第3 節(jié)對(duì)vCGG 與幾種具有代表性的空間圖文法進(jìn)行對(duì)比分析.第4 節(jié)給出總結(jié)及展望.

1 CGG 形式框架

1.1 基本概念

CGG 是在上下文相關(guān)圖文法EGG 中引入空間語義機(jī)制擴(kuò)展而來的空間圖文法形式框架,通過在傳統(tǒng)連續(xù)坐標(biāo)的基礎(chǔ)上定義離散坐標(biāo)的概念,使用兩個(gè)子框架cCGG(continuous coordinate graph grammar)和dCGG (discrete coordinate graph grammar),為分別空間語義提供定量與定性描述粒度.以下給出CGG 中的基本概念.

定義1.1.G=(N,E)是一個(gè)定義在標(biāo)號(hào)集L上的空間語義圖,當(dāng)且僅當(dāng):

?N是一個(gè)結(jié)點(diǎn)集,并且可以進(jìn)一步被分為兩個(gè)子集合:終結(jié)點(diǎn)集NT和非終結(jié)點(diǎn)集NNT;

?E?N×N是一個(gè)有向邊集.

為了方便語法語義操作,CGG 定義了以下幾個(gè)函數(shù).

?fNL:N→L是一個(gè)從結(jié)點(diǎn)n∈N到標(biāo)號(hào)l∈L的映射,即fNL(n)=n.l;

?fNC:N→R×R是一個(gè)從結(jié)點(diǎn)n∈N到坐標(biāo)c∈R×R的映射;

定義1.2.給定一個(gè)空間語義圖G,結(jié)點(diǎn)n∈G.N的離散坐標(biāo)是(rx,ry),當(dāng)且僅當(dāng):

?rx和ry分別是fNC(n).x和fNC(n).y在G.N中所有結(jié)點(diǎn)坐標(biāo)值中的反向排名數(shù)值.

對(duì)于一個(gè)給定的圖,結(jié)點(diǎn)的離散坐標(biāo)抽象自連續(xù)坐標(biāo),表示結(jié)點(diǎn)的橫坐標(biāo)與縱坐標(biāo)在當(dāng)前圖所有結(jié)點(diǎn)中的反向排名,反映了該結(jié)點(diǎn)在圖中的相對(duì)空間位置.例如,圖1 是一個(gè)空間圖連續(xù)坐標(biāo)的離散化過程,結(jié)點(diǎn)a橫坐標(biāo)與縱坐標(biāo)在圖中所有的結(jié)點(diǎn)中反向排名為2,3,因此,結(jié)點(diǎn)a在當(dāng)前圖中的離散坐標(biāo)為(2,3).

Fig.1 Mapping between continuous coordinates and discrete coordinates圖1 連續(xù)坐標(biāo)與離散坐標(biāo)之間的映射

定義1.3.圖G與圖Q是同構(gòu)關(guān)系,記作G≈Q,其中,G和Q之間存在兩個(gè)雙射:fNN:G.N?Q.N和fEE:G.E?Q.E,并滿足以下條件.

滿足同構(gòu)關(guān)系的兩個(gè)圖有著一一對(duì)應(yīng)的結(jié)點(diǎn)和邊,其中,對(duì)應(yīng)結(jié)點(diǎn)擁有相同的標(biāo)號(hào),并且對(duì)應(yīng)邊的起始結(jié)點(diǎn)和結(jié)束結(jié)點(diǎn)也需符合該對(duì)應(yīng)關(guān)系.

定義1.4.圖Q是一個(gè)包含懸邊的圖的核圖,記作Q=,當(dāng)且僅當(dāng):

定義1.5.如果圖Q是一個(gè)給定主圖G的子圖并可能帶有懸邊,并且圖是一個(gè)產(chǎn)生式的左圖或右圖,圖Q是圖在主圖G中的圖柄,記作,當(dāng)且僅當(dāng):存在兩個(gè)雙射:fNN:Q.N?.N和fEE:Q.E?.E,并滿足以下條件.

在CGG 中,圖柄不僅要求與某個(gè)產(chǎn)生式圖形成同構(gòu)關(guān)系,還需滿足空間上的語義匹配要求.根據(jù)不同的粒度描述選擇,子框架cCGG 要求產(chǎn)生式圖中任意兩個(gè)結(jié)點(diǎn)和它們?cè)趫D柄Q中對(duì)應(yīng)的結(jié)點(diǎn)具有完全相等的坐標(biāo)差值;而dCGG 要求產(chǎn)生式圖和圖柄Q具有等價(jià)的空間拓?fù)浣Y(jié)構(gòu),即中任意一個(gè)結(jié)點(diǎn)和它在圖柄Q中對(duì)應(yīng)的結(jié)點(diǎn)具有完全相等的離散坐標(biāo)值.

在圖文法的推導(dǎo)或歸約工作流中,在根據(jù)一個(gè)產(chǎn)生式圖找到其在主圖中的圖柄后,便可以對(duì)圖柄執(zhí)行圖轉(zhuǎn)換操作.根據(jù)不同的配置粒度,cCGG 和dCGG 中圖轉(zhuǎn)換操作的具體步驟如下.

1) 根據(jù)當(dāng)前產(chǎn)生式生成一個(gè)產(chǎn)生式實(shí)例;

? cCGG:將圖柄中的任意結(jié)點(diǎn)n與其在產(chǎn)生式圖中的對(duì)應(yīng)節(jié)點(diǎn)n′的坐標(biāo)差值,即n.c-n′.c,作為偏移量平移產(chǎn)生式的另一端;

3) 從主圖中刪除圖柄;

圖2 是一個(gè)CGG 中R-application 的例子,其中,圖2(a)是一個(gè)給定主圖,圖2(b)和圖2(c)分別是一個(gè)cCGG產(chǎn)生式和dCGG 產(chǎn)生式.對(duì)于cCGG 產(chǎn)生式,產(chǎn)生式實(shí)例的左圖使用偏移量(0,1.5)進(jìn)行平移,該偏移量是圖2(a)中虛線框內(nèi)所示圖柄與產(chǎn)生式右圖之間匹配結(jié)點(diǎn)的坐標(biāo)差值.而對(duì)于dCGG 產(chǎn)生式,首先在產(chǎn)生式右圖中選擇具有最大“Y”坐標(biāo)值的結(jié)點(diǎn)“stat1”,然后將圖柄中的對(duì)應(yīng)結(jié)點(diǎn)與結(jié)點(diǎn)“stat1”的坐標(biāo)差值(-1,0)作為偏移量,平移產(chǎn)生式左圖.在該例中,使用cCGG 產(chǎn)生式和dCGG 產(chǎn)生式對(duì)圖柄進(jìn)行R-application 操作,得到的是兩個(gè)不同的主圖,如圖2(d)、圖2(e)所示.

Fig.2 An example of CGG R-application圖2 CGG 中R-application 實(shí)例

1.2 框架缺陷

由于延續(xù)了EGG 的懸邊機(jī)制,CGG 存在一個(gè)較為明顯的表達(dá)能力上的缺陷——Lcf圖語言問題[21].如圖3所示,圖語言Lcf是由一對(duì)“fork”,“join”結(jié)點(diǎn)以及它們之間的任意數(shù)量(不小于2)“stat”分支組成的一類流程圖.對(duì)于這一類圖語言,無法通過有限數(shù)量的EGG 或CGG 產(chǎn)生式描述所有可能情形下的Lcf圖.其原因在于:如果要描述任意一個(gè)Lcf,由于“stat”分支的數(shù)量是未知的,無法在產(chǎn)生式設(shè)計(jì)階段窮舉所有分支,從而無法在產(chǎn)生式中確定“fork”與“join”結(jié)點(diǎn)所連接的懸邊數(shù)量.Lcf圖語言問題可以通過定義額外的通配懸邊加以解決,然而通配懸邊的處理在一定程度上增加了產(chǎn)生式以及文法操作的復(fù)雜性.相比之下,圖文法LGG 和RGG 則不存在這個(gè)問題.在產(chǎn)生式設(shè)計(jì)階段,LGG 可以將出入邊數(shù)量未知的結(jié)點(diǎn)(例如“fork”和“join”結(jié)點(diǎn))作為上下文結(jié)點(diǎn),在匹配時(shí)不需要考慮上下文結(jié)點(diǎn)的出入度;RGG 使用雙層結(jié)構(gòu)結(jié)點(diǎn)中標(biāo)記的頂點(diǎn)來關(guān)聯(lián)上下文,在匹配時(shí)不需要考慮頂點(diǎn)所連接邊的數(shù)量.

Fig.3 An example of the graphical language Lcf圖3 一個(gè)圖語言Lcf 的例子

懸邊機(jī)制帶來的另一個(gè)問題是懸邊映射問題.在EGG 和CGG 的工作流中,當(dāng)一個(gè)主圖子圖與產(chǎn)生式圖符合圖柄匹配條件時(shí),若產(chǎn)生式圖中存在一個(gè)結(jié)點(diǎn)連接了兩條及兩條以上同方向的懸邊,需根據(jù)這些懸邊在主圖中不同映射情況生成多個(gè)圖柄進(jìn)行處理[20].如圖4 所示,左側(cè)主圖虛線框內(nèi)的子圖與產(chǎn)生式p1 與p2 的右圖之間均滿足圖柄匹配條件.由于產(chǎn)生式p1 的右圖結(jié)點(diǎn)“stat”連接了兩條同方向的懸邊“1”、懸邊“2”,兩條懸邊與主圖中對(duì)應(yīng)結(jié)點(diǎn)“stat”所連接的邊(stat,a-branch),(stat,b-branch)之間存在兩種雙射,而在不同雙射情況下進(jìn)行R- application 會(huì)產(chǎn)生兩種具有不同結(jié)構(gòu)的主圖,因此,兩種雙射情況下的圖柄應(yīng)當(dāng)被視為不同的圖柄.這種規(guī)定可以保證圖轉(zhuǎn)換結(jié)果的唯一性,然而該規(guī)定在一些場(chǎng)景下并不是必要的.例如:對(duì)于圖4 中的產(chǎn)生式p2,在任意一種雙射情況下對(duì)主圖進(jìn)行R-application 所產(chǎn)生的新主圖均具有相同的結(jié)構(gòu).原因在于:懸邊“1”、懸邊“2”在產(chǎn)生式p2 的左圖中只與一個(gè)結(jié)點(diǎn)“stat2”相連接,在進(jìn)行子圖替換的過程中,主圖的余圖只能與該結(jié)點(diǎn)進(jìn)行連接,因而不會(huì)出現(xiàn)兩種圖轉(zhuǎn)換結(jié)果.在這種情況下,如果按照上述規(guī)定進(jìn)行歸約,則容易因圖柄集規(guī)模擴(kuò)大而導(dǎo)致多余回溯的出現(xiàn),產(chǎn)生不必要的分析時(shí)間開銷.

2 vCGG 形式框架

2.1 基本概念

針對(duì)空間圖文法存在的問題,本章在繼承CGG 形式框架空間語義機(jī)制的前提下構(gòu)建新的空間圖文法框架vCGG,該框架引入虛結(jié)點(diǎn)作為上下文結(jié)點(diǎn),描述圖柄與產(chǎn)生式之間語法結(jié)構(gòu)與空間語義上的關(guān)系,在保留文法抽象性的同時(shí),增加文法的表達(dá)能力與分析效率.由于CGG 使用兩個(gè)子框架dCGG 與cCGG 分別處理定性與定量空間語義關(guān)系,vCGG 根據(jù)空間語義的不同粒度描述分為vdCGG(virtual-node based discrete coordinate graph grammar)與vcCGG(virtual-node based continuous coordinate graph grammar),以下是vCGG 形式框架中基本概念的定義.

Fig.4 Examples of dangling-edges mapping problem圖4 懸邊映射問題的例子

定義2.1.G=(N,E)是一個(gè)定義在標(biāo)號(hào)集L上的空間語義圖,當(dāng)且僅當(dāng):

?L=Lv∪Lr,Lv∩Lr=?,其中,Lv是虛結(jié)點(diǎn)的標(biāo)號(hào)集,Lr是實(shí)結(jié)點(diǎn)的標(biāo)號(hào)集;

?Lr=LT∪LNT,LT∩LNT=?,其中,LT是終結(jié)點(diǎn)的標(biāo)號(hào)集,LNT是非終結(jié)點(diǎn)的標(biāo)號(hào)集;

?N是一個(gè)結(jié)點(diǎn)集并且可以被分為兩個(gè)子集合:虛結(jié)點(diǎn)集Nv、實(shí)結(jié)點(diǎn)集Nr,其中,實(shí)結(jié)點(diǎn)集Nr可以進(jìn)一步分為終結(jié)點(diǎn)集NT和非終結(jié)點(diǎn)集NNT;

?E?N×N是一個(gè)有向邊集.

為了方便于語法語義操作,CGG 定義了以下幾個(gè)函數(shù).

?fNL:N→L是一個(gè)從結(jié)點(diǎn)n∈N到標(biāo)號(hào)l∈L的映射,即fNL(n)=n.l;

?fNC:N→R×R是一個(gè)從結(jié)點(diǎn)n∈N到坐標(biāo)c∈R×R的映射;

? :EN→ 是一個(gè)從有向邊e∈E到它的起始結(jié)點(diǎn)的映射;

在vCGG 中,圖中包含的結(jié)點(diǎn)根據(jù)分配的標(biāo)號(hào)被分成了兩類:虛結(jié)點(diǎn)和實(shí)結(jié)點(diǎn),其中,實(shí)結(jié)點(diǎn)可以進(jìn)一步地分為終結(jié)點(diǎn)與非終結(jié)點(diǎn).實(shí)結(jié)點(diǎn)的標(biāo)號(hào)集定義與CGG 相同,而虛結(jié)點(diǎn)的標(biāo)號(hào)主要用于區(qū)分不同虛結(jié)點(diǎn)標(biāo)記,不包含其他語義信息,因此,主圖中虛結(jié)點(diǎn)在通常情況下其標(biāo)號(hào)集為空,即主圖的所有結(jié)點(diǎn)都是實(shí)結(jié)點(diǎn).虛結(jié)點(diǎn)的主要作用是描述主圖與產(chǎn)生式的語法結(jié)構(gòu)與空間語義關(guān)系,下面給出vCGG 產(chǎn)生式的定義.

定義2.2.產(chǎn)生式是兩個(gè)圖GL和GR組成的形如GL:=GR的表達(dá)式,在GL和GR之間存在一個(gè)雙射fNN:GL.Nv?GR.Nv,并滿足以下條件.

vCGG 將虛結(jié)點(diǎn)引入產(chǎn)生式結(jié)構(gòu)中.在一個(gè)產(chǎn)生式圖中,虛結(jié)點(diǎn)表示上下文結(jié)點(diǎn),而實(shí)結(jié)點(diǎn)代表非上下文結(jié)點(diǎn),也可稱為產(chǎn)生式內(nèi)部結(jié)點(diǎn).為了圖轉(zhuǎn)換操作的可執(zhí)行性,vCGG 規(guī)定:同一個(gè)產(chǎn)生式兩端的虛結(jié)點(diǎn)集之間需存在一個(gè)雙射,并且對(duì)應(yīng)的結(jié)點(diǎn)擁有相等的標(biāo)號(hào)與坐標(biāo).此外,為了圖嵌入過程中不產(chǎn)生歧義,同一個(gè)圖中的每一個(gè)虛結(jié)點(diǎn)具有唯一的標(biāo)號(hào),可以用唯一的整數(shù)表示.例如,圖5 是一個(gè)合法的vCGG 產(chǎn)生式,其中,虛線圓框代表虛結(jié)點(diǎn),實(shí)線圓框代表實(shí)結(jié)點(diǎn).

Fig.5 vCGG production圖5 vCGG 產(chǎn)生式

由圖5 可見:產(chǎn)生式左圖與右圖之間存在一個(gè)雙射,并且對(duì)應(yīng)結(jié)點(diǎn)具有相同的標(biāo)號(hào)“1”、標(biāo)號(hào)“2”以及相等的坐標(biāo)(1,3),(1,1).

定義2.3.圖G與圖Q是同構(gòu)關(guān)系,記作G≈Q,其中,G和Q之間存在兩個(gè)雙射:fNN:G.N?Q.N和fEE:G.E?Q.E,并滿足以下條件.

在判定一對(duì)圖是否滿足同構(gòu)條件時(shí),虛結(jié)點(diǎn)比實(shí)結(jié)點(diǎn)具有更高的抽象程度,可以匹配任意標(biāo)號(hào)的結(jié)點(diǎn).圖6是一個(gè)vCGG 中圖同構(gòu)的例子,其中,所有結(jié)點(diǎn)和邊在滿足雙射關(guān)系的.其中,實(shí)結(jié)點(diǎn)“stat”和對(duì)應(yīng)結(jié)點(diǎn)必須具有相同的標(biāo)號(hào),而虛結(jié)點(diǎn)“1”、虛結(jié)點(diǎn)“2”可以匹配任何標(biāo)號(hào)的結(jié)點(diǎn)(圖6 中為“begin”“end”).

Fig.6 Theisomorphic graphs in vCGG圖6 vCGG 中具有同構(gòu)關(guān)系的圖

其中,fNL和是Q和GL|R的結(jié)點(diǎn)標(biāo)號(hào)映射,fNC和分別是Q和GL|R的結(jié)點(diǎn)坐標(biāo)映射.

基于不同的空間語義描述粒度,vCGG 兩個(gè)子框架vcCGG 與vdCGG 的圖柄定義有所不同.在滿足同構(gòu)關(guān)系的前提下,vcCGG 要求圖柄和產(chǎn)生式圖需要滿足坐標(biāo)關(guān)系的完全匹配,產(chǎn)生式圖中任意兩個(gè)結(jié)點(diǎn)與它們?cè)谥鲌D中對(duì)應(yīng)結(jié)點(diǎn)具有相等的坐標(biāo)差,即產(chǎn)生式圖通過平移可以與圖柄完全重合.與vcCGG 相比,vdCGG 空間語義匹配條件按照虛結(jié)點(diǎn)和實(shí)結(jié)點(diǎn)分為兩個(gè)層次:在第1 層,圖柄和產(chǎn)生式圖的對(duì)應(yīng)結(jié)點(diǎn)需要在各自空間內(nèi)部具有相等的離散坐標(biāo);在第2 層,虛節(jié)點(diǎn)之間的定量坐標(biāo)關(guān)系需要和對(duì)應(yīng)主圖結(jié)點(diǎn)完全一致,即所有虛結(jié)點(diǎn)可以同時(shí)通過平移與其在圖柄中的對(duì)應(yīng)結(jié)點(diǎn)完全重合.匹配要求的劃分使vCGG 既能對(duì)產(chǎn)生式內(nèi)部結(jié)點(diǎn)提供定性與定量的拓?fù)潢P(guān)系描述,也能維持上下文結(jié)點(diǎn)的一致性.例如:圖7(a)是一個(gè)主圖,若根據(jù)圖7(b)中產(chǎn)生式右圖在主圖中查找圖柄時(shí),在vcCGG 和vdCGG 中的任何一個(gè)子框架下,該產(chǎn)生式右圖都符合圖柄的匹配條件;而當(dāng)在主圖中查找圖7(b)中產(chǎn)生式右圖的圖柄時(shí),在vcCGG 框架下產(chǎn)生式右圖與主圖的任何一個(gè)子圖都不符合坐標(biāo)匹配條件,而在vdCGG 框架下則可以成功查找到所需圖柄.此外,vCGG 要求圖柄中實(shí)結(jié)點(diǎn)在主圖中的出入度與產(chǎn)生式圖中對(duì)應(yīng)結(jié)點(diǎn)完全相等,保證了圖柄中所有與產(chǎn)生式圖中實(shí)結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)在主圖中只能與虛結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)相連接,在圖轉(zhuǎn)換過程中避免了懸邊的出現(xiàn).

Fig.7 The redex matching in vCGG圖7 vCGG 中的圖柄匹配

2.2 文法操作

圖文法的主要工作流是圖推導(dǎo)與歸約,分別面向?qū)嶋H應(yīng)用中圖的生成與分析需求.推導(dǎo)與歸約工作流的基本構(gòu)成要素是圖轉(zhuǎn)換操作.圖轉(zhuǎn)換操作根據(jù)其執(zhí)行方向可以分為 L-application 與 R-application,其中,L- application 是指用產(chǎn)生式右圖替換左圖在主圖中圖柄的操作,而R-application 用產(chǎn)生式左圖替換右圖在主圖中圖柄.L/R application 中的一個(gè)重要問題是如何避免轉(zhuǎn)換后的新主圖中產(chǎn)生懸邊,即嵌入問題.在vCGG 中,由于在產(chǎn)生式使用虛結(jié)點(diǎn)作為上下文結(jié)點(diǎn),可以使用粘合的方式解決嵌入問題.根據(jù)不同的配置粒度要求,vcCGG 和vdCGG 中L/R application 的具體步驟如下.

1) 根據(jù)當(dāng)前產(chǎn)生式生成一個(gè)產(chǎn)生式實(shí)例;

2) 平移產(chǎn)生式實(shí)例的右圖或左圖GR|L.

? vcCGG:將圖柄中的任意結(jié)點(diǎn)n與其在產(chǎn)生式圖GL|R中的對(duì)應(yīng)節(jié)點(diǎn)n′的坐標(biāo)差值,即n.c-n′.c,作為偏移量平移產(chǎn)生式的另一端GR|L;

? vdCGG:首先,在產(chǎn)生式圖GL|R中選擇任意一個(gè)虛結(jié)點(diǎn)n′,將圖柄中的對(duì)應(yīng)結(jié)點(diǎn)n與n′的坐標(biāo)差值n.c-n′.c作為偏移量平移另一個(gè)產(chǎn)生式圖GR|L;

3) 從主圖中刪除圖柄中所有的邊以及與GL|R中實(shí)結(jié)點(diǎn)匹配的結(jié)點(diǎn);

4) 按照產(chǎn)生式圖GL|R的虛節(jié)點(diǎn)與圖柄結(jié)點(diǎn)的映射關(guān)系,粘合產(chǎn)生式圖GR|L的虛結(jié)點(diǎn)與圖柄中對(duì)應(yīng)結(jié)點(diǎn),并在主圖中去除該虛標(biāo)號(hào).

vCGG 圖轉(zhuǎn)換的操作繼承了CGG 中的坐標(biāo)映射機(jī)制,即產(chǎn)生式局部坐標(biāo)與主圖全局坐標(biāo)的映射關(guān)系,區(qū)別在于:vdCGG 基于虛結(jié)點(diǎn)而計(jì)算獲得坐標(biāo)偏移量,而dCGG 的偏移量是基于最大“Y”值的結(jié)點(diǎn)而計(jì)算得出.相比之下,vdCGG 偏移量的可解釋性更好,產(chǎn)生式設(shè)計(jì)人員的學(xué)習(xí)曲線較為平緩.圖8 描述了使用圖7 中的產(chǎn)生式p1和p2 對(duì)圖7(a)中的主圖分別進(jìn)行R-application 生成的新主圖,其中,圖8(a)是使用圖7(a)中產(chǎn)生式p1 在vcCGG框架下生成的新主圖,圖8(b)是使用產(chǎn)生式p2 按照vdCGG 的R-application 步驟生成的主圖.

Fig.8 New host graphs generated by the productions in Fig.7圖8 使用圖7 中產(chǎn)生式進(jìn)行R-application 生成的新主圖

2.3 vCGG及其語言定義

定義2.5.vCGG 是一個(gè)四元組(λ,L,P,S),其中,

? λ是一個(gè)初始圖;

?L=Lv∪Lr,Lv∩Lr=?,其中,Lv是虛結(jié)點(diǎn)的標(biāo)號(hào)集,Lr是實(shí)結(jié)點(diǎn)的標(biāo)號(hào)集;

?Lr=LT∪LNT,LT∩LNT=?,其中,LT是終結(jié)點(diǎn)的標(biāo)號(hào)集,LNT是非終結(jié)點(diǎn)的標(biāo)號(hào)集;

?P是一個(gè)產(chǎn)生式集;

?S是一個(gè)由若干正實(shí)數(shù)組成的標(biāo)尺集,并且滿足關(guān)系:S?R+.

為了避免產(chǎn)生式的冗余,vCGG 的形式化定義中繼承了CGG 的標(biāo)尺集概念.類似于地圖標(biāo)尺,標(biāo)尺集中的每一個(gè)正實(shí)數(shù)代表著主圖對(duì)產(chǎn)生式的坐標(biāo)比例.標(biāo)尺的引入,可以有效地減少產(chǎn)生式的數(shù)量,尤其是那些結(jié)構(gòu)完全相同而互相之間坐標(biāo)成比例關(guān)系的產(chǎn)生式.每個(gè)產(chǎn)生式集P中的產(chǎn)生式都可以通過坐標(biāo)與標(biāo)尺的相乘得到多個(gè)實(shí)際使用的產(chǎn)生式,因此,標(biāo)尺集所包含正實(shí)數(shù)的數(shù)量對(duì)一個(gè)文法的實(shí)際表達(dá)能力有著重要的影響.

定義2.6.對(duì)于vCGG 的任意一個(gè)文法vcgg,其語言Γ(vcgg)是一個(gè)由空間語義圖組成的集合:

圖文法的語言是由初始圖經(jīng)過推導(dǎo)操作生成的只含有終結(jié)點(diǎn)的圖的集合.對(duì)一個(gè)只含有終結(jié)點(diǎn)的圖進(jìn)行歸約操作的過程,可以判斷該圖是否屬于相應(yīng)文法所定義的語言.vCGG 的推導(dǎo)工作流生成的是一個(gè)包含空間語義配置的圖,而歸約工作流可以在判斷給定圖的結(jié)構(gòu)語法的合法性的同時(shí),分析該圖的空間語義模型.

3 與已有文法的對(duì)比

本節(jié)對(duì)新構(gòu)建的vCGG 框架與幾種具有代表性的框架SGG、SG、CGG 進(jìn)行對(duì)比,其中,SGG 對(duì)空間語義采用定性描述,SG 根據(jù)文法定義的定量空間關(guān)系繪制圖形,CGG 使用離散坐標(biāo)和連續(xù)坐標(biāo)為空間語義提供基于不同粒度的配置.為了獲得全面而系統(tǒng)的比較結(jié)論,本節(jié)從形式化框架、文法表達(dá)能力、分析效率、以及文法應(yīng)用這4 個(gè)維度對(duì)這幾種框架進(jìn)行對(duì)比分析.

3.1 形式化框架

直觀性是衡量一個(gè)圖文法形式框架的關(guān)鍵特性之一,而上下文深度是評(píng)價(jià)文法框架直觀性的一個(gè)重要依據(jù).上下文深度是指產(chǎn)生式圖中內(nèi)部結(jié)點(diǎn)到上下文結(jié)點(diǎn)的最短路徑長(zhǎng)度,具體值等于最短路徑中結(jié)點(diǎn)(不包含起始結(jié)點(diǎn))和邊數(shù)量之和的二分之一.上下文深度大于等于1 的文法稱為顯式文法,而小于1 的文法稱為隱式文法.一般而言,顯式文法的直觀性高于隱式文法,而顯式文法的不足在于上下文結(jié)點(diǎn)描述的復(fù)雜性,在很多應(yīng)用場(chǎng)景下較難使用有限的上下文結(jié)點(diǎn)描述所有可能出現(xiàn)的上下文信息.例如:LGG 使用通配符描述上下文信息,當(dāng)通配符數(shù)量較大時(shí),產(chǎn)生式構(gòu)造變得過于復(fù)雜而難以設(shè)計(jì).對(duì)幾種框架的上下文深度進(jìn)行對(duì)比,如圖9 所示:SGG 將上下文信息以頂點(diǎn)形式內(nèi)嵌在結(jié)點(diǎn)的雙層結(jié)構(gòu)中,上下文深度為0;CGG 繼承了EGG 的懸邊機(jī)制,采用懸邊表示上下文連接,因此上下文深度為0.5;SG 在形式上沒有對(duì)上下文信息進(jìn)行描述,上下文深度為空;vCGG 在產(chǎn)生式中引入了虛結(jié)點(diǎn),上下文深度為1,并且虛結(jié)點(diǎn)在圖柄查找過程中不需要匹配其標(biāo)號(hào)語義信息,因此不需要考慮虛結(jié)點(diǎn)除空間坐標(biāo)之外的語義信息,相比LGG 具有更高的抽象性,產(chǎn)生式結(jié)構(gòu)也更為簡(jiǎn)潔而易于設(shè)計(jì).此外,與前身CGG 相比,由于不再需要定義懸邊圖作為圖柄,vCGG 中圖的形式與定義更加符合圖論的規(guī)范標(biāo)準(zhǔn).

Fig.9 Comparison between the productions of SGG,SG,CGG and vCGG圖9 SGG、SG、CGG、vCGG 產(chǎn)生式比較

形式化框架比較的另一個(gè)重點(diǎn)是子圖嵌入問題的解決方法,大致可以分為兩種:一種是使用嵌入規(guī)則進(jìn)行圖轉(zhuǎn)換操作,具體方法是在主圖中首先刪除圖柄,之后根據(jù)嵌入規(guī)則將產(chǎn)生式圖嵌入主圖中;另一種方法使用結(jié)點(diǎn)粘合的方式,首先在主圖中刪除圖柄中除了與上下文結(jié)點(diǎn)匹配的結(jié)點(diǎn)之外的部分,再根據(jù)產(chǎn)生式兩端上下文結(jié)點(diǎn)的雙射關(guān)系進(jìn)行結(jié)點(diǎn)粘合.總體而言:嵌入規(guī)則方法的形式上更加靈活,例如,用戶可以通過修改嵌入規(guī)則改變嵌入前邊的方向;粘合方法的規(guī)范性更好,可以確保文法操作中不會(huì)出現(xiàn)懸邊.相比之下,SG、SGG、CGG都是使用嵌入規(guī)則的方式進(jìn)行子圖嵌入操作,而vCGG 采用粘合方式將作為上下文結(jié)點(diǎn)的虛結(jié)點(diǎn)和其對(duì)應(yīng)結(jié)點(diǎn)進(jìn)行粘合并去除虛標(biāo)號(hào),從而得到合法的新主圖.

3.2 文法表達(dá)能力

圖文法形式框架的表達(dá)能力指的是文法能夠描述圖語言的范圍,如何增強(qiáng)圖文法的表達(dá)能力,是該領(lǐng)域中的一個(gè)重要研究話題.與CGG 相比,對(duì)于圖語言LCF問題,由于引入了虛結(jié)點(diǎn)機(jī)制,vCGG 可以將第1.2 節(jié)中圖3的結(jié)點(diǎn)“fork”,“join”放入產(chǎn)生式中作為虛結(jié)點(diǎn),直觀而簡(jiǎn)潔地描述所有形如Lcf圖語言的多分支結(jié)構(gòu)圖.從空間語義配置的全面性上對(duì)幾種框架進(jìn)行對(duì)比,vCGG 對(duì)圖語言空間語義的描述更加全面.vCGG 在產(chǎn)生式中引入了虛結(jié)點(diǎn)作為上下文結(jié)點(diǎn),虛結(jié)點(diǎn)在圖柄查找時(shí)不需考慮標(biāo)號(hào)語義,匹配的是虛結(jié)點(diǎn)與實(shí)結(jié)點(diǎn)之間的語法結(jié)構(gòu)以及空間語義關(guān)系,因此,vCGG 不僅可以描述產(chǎn)生式非公共子圖(不包含上下文結(jié)點(diǎn)的部分)的空間語義模型,也可以通過上下文結(jié)點(diǎn)的空間語義描述非公共子圖與主圖之間的坐標(biāo)方位關(guān)系.與之對(duì)比,SG、SGG 與CGG 的產(chǎn)生式只能描述非公共子圖內(nèi)部空間語義模型,缺乏對(duì)圖柄與主圖之間空間語義關(guān)系的描述能力,因此,空間語義配置的全面性不如vCGG.

3.3 分析效率

在文法分析效率方面,由于圖語言結(jié)構(gòu)的二維非線性特點(diǎn),文法分析過程中容易發(fā)生大量的回溯,造成了分析算法的最壞時(shí)間開銷通常為指數(shù)級(jí).繼承自RGG、SGG 可以使用一個(gè)時(shí)間開銷為多項(xiàng)式級(jí)的分析算法—— SFPA 算法(selection-free parsing algorithm)[15].然而,SFPA 算法對(duì)產(chǎn)生式提出了約束較高的選擇無關(guān)條件作為歸約前提,導(dǎo)致SFPA 的通用性有所不足.由于歸約中回溯的不可避免性,大多數(shù)圖文法分析算法的設(shè)計(jì)目標(biāo)是盡可能地降低圖柄查找過程的時(shí)間開銷.假設(shè)n是主圖的結(jié)點(diǎn)數(shù)量,m是產(chǎn)生式右圖的結(jié)點(diǎn)數(shù)量,n與m代表了主圖與產(chǎn)生式的規(guī)模,圖文法的圖柄查找時(shí)間開銷的時(shí)間復(fù)雜度在通常情況下為O()m nA,即在規(guī)模為n的主圖能夠查找到規(guī)模為m的不同結(jié)點(diǎn)順序子圖的最多數(shù)量.引入了空間語義機(jī)制后,由于產(chǎn)生式以及主圖中的結(jié)點(diǎn)可以按照其空間拓?fù)潢P(guān)系進(jìn)行排序,利用該順序指導(dǎo)子圖匹配過程可以有效縮小圖柄的查找空間,從而減少時(shí) 間開銷.因此,SGG 與CGG 的圖柄查找算法時(shí)間開銷位于[13,18]量級(jí),將傳統(tǒng)圖柄查找過程的排列問題轉(zhuǎn) 變成了典型的組合問題.繼承自CGG、vCGG 可以使用CGG 的圖柄查找算法,通過對(duì)結(jié)點(diǎn)排序而縮小圖柄的搜索空間,并且由于圖柄查找過程中不需要考慮懸邊的映射問題,vCGG 分析算法的實(shí)際時(shí)間開銷小于CGG.

圖文法分析性能的評(píng)價(jià)不僅體現(xiàn)在其時(shí)間開銷上,對(duì)非法語義關(guān)系與語法結(jié)構(gòu)作出判斷的及時(shí)性也是評(píng)價(jià)的一個(gè)重要依據(jù).與SG、SGG、CGG 相比,vCGG 產(chǎn)生式增加了上下文與產(chǎn)生式非公共子圖之間的空間關(guān)系約束,因此在分析過程中可以更早地發(fā)現(xiàn)錯(cuò)誤,即時(shí)停機(jī)從而減少無效歸約.例如,圖10(a)是一個(gè)任意給定的主圖,不滿足圖10(b)、圖10(c)中產(chǎn)生式對(duì)圖形元素的空間語義約束.在歸約時(shí),圖10(b)中CGG 產(chǎn)生式需要根據(jù)產(chǎn)生式p1,p2 對(duì)主圖進(jìn)行兩次歸約才可以判定出該語義錯(cuò)誤,而vCGG 產(chǎn)生式只需要圖10(c)中的一個(gè)產(chǎn)生式進(jìn)行一步歸約便可判斷出其空間語義關(guān)系的非法性,在一定程度上減少了無效歸約的數(shù)量.

Fig.10 Detection of invalid host graph in CGG and vCGG圖10 CGG 與vCGG 對(duì)不合法主圖的檢測(cè)

3.4 文法應(yīng)用

通過上述對(duì)比,vCGG 不僅可以描述產(chǎn)生式圖內(nèi)部的空間語義模型,也可以將虛結(jié)點(diǎn)作為上下文結(jié)點(diǎn)直觀地描述產(chǎn)生式圖內(nèi)部與主圖的坐標(biāo)方位關(guān)系,提供了相對(duì)更全面的空間語義配置能力.因此,在空間圖文法的實(shí)際應(yīng)用中,vCGG 可以處理一部分SG、SGG 與CGG 較難應(yīng)對(duì)的實(shí)際應(yīng)用問題.以圖模型布局需求為例,圖11是一個(gè)簡(jiǎn)單的程序流程圖,其布局要求為:結(jié)點(diǎn)按從左到右的順序排列,每一個(gè)標(biāo)號(hào)為“if”或“while”的結(jié)點(diǎn)需位于前一結(jié)點(diǎn)(設(shè)為n)的正下方,而標(biāo)號(hào)為“Y-branch”或“endwhile”的結(jié)點(diǎn)需位于結(jié)點(diǎn)n的正右方.基于虛結(jié)點(diǎn)對(duì)上下文空間語義的顯式配置,使用vCGG 產(chǎn)生式可以較為容易地實(shí)現(xiàn)該布局要求.圖12 是一組用于繪制流程圖的vCGG 產(chǎn)生式.而使用該組產(chǎn)生式進(jìn)行推導(dǎo)操作即可繪制出滿足上述布局要求的程序流程圖,如圖13 所示.

Fig.12 A set of vCGG productions for the programming flowchart圖12 描述程序流程圖的一組vCGG 產(chǎn)生式

Fig.13 Derivation of the programming flowchart圖13 上述程序流程圖的推導(dǎo)過程

相比之下,SG、SGG 與CGG 只能配置產(chǎn)生式圖內(nèi)部的空間語義模型而缺乏對(duì)產(chǎn)生式與上下文之間的空間語義關(guān)系的描述.在面對(duì)上述需求時(shí),最直接的方法是將vCGG 產(chǎn)生式中的虛結(jié)點(diǎn)(即上下文結(jié)點(diǎn))引入產(chǎn)生式中作為普通實(shí)結(jié)點(diǎn).例如,圖14 是一個(gè)滿足上述關(guān)于“if”結(jié)點(diǎn)布局要求的CGG 產(chǎn)生式.然而,該方法存在著較大的弊端:首先,將虛結(jié)點(diǎn)引入產(chǎn)生式作為普通實(shí)結(jié)點(diǎn)需要窮舉該結(jié)點(diǎn)允許接受的標(biāo)號(hào)(如“statement”“endif”),而每種標(biāo)號(hào)都對(duì)應(yīng)著一個(gè)產(chǎn)生式,造成了產(chǎn)生式規(guī)模與數(shù)量的增長(zhǎng),尤其在需要引入多個(gè)虛結(jié)點(diǎn)作為實(shí)結(jié)點(diǎn)時(shí),產(chǎn)生式的數(shù)量隨之呈指數(shù)增長(zhǎng);其次,實(shí)結(jié)點(diǎn)的增加在一定程度上影響了產(chǎn)生式圖作為一個(gè)圖形單元的邏輯獨(dú)立性,例如,圖14 中產(chǎn)生式中出現(xiàn)了不屬于“if”選擇結(jié)構(gòu)的實(shí)結(jié)點(diǎn)“statement”;最后,在產(chǎn)生式中引入普通實(shí)結(jié)點(diǎn)還需考慮它們的上下文信息,進(jìn)一步增加了產(chǎn)生式的規(guī)模與數(shù)量,也使產(chǎn)生式的抽象程度有所下降.

Fig.14 CGG production under the layout requirements圖14 滿足布局需求的一個(gè)CGG 產(chǎn)生式

SG、SGG 與CGG 配置產(chǎn)生式與上下文之間空間語義關(guān)系的另一種方法是:根據(jù)圖柄結(jié)點(diǎn)在主圖中與余圖的坐標(biāo)關(guān)系,間接地設(shè)計(jì)嵌入圖結(jié)點(diǎn)的坐標(biāo)信息.圖15 是根據(jù)這種間接配置方法設(shè)計(jì)的CGG 產(chǎn)生式,其設(shè)計(jì)過程為:首先計(jì)算出產(chǎn)生式左圖結(jié)點(diǎn)“stat”的圖柄與主圖中上下文的坐標(biāo)差,再根據(jù)產(chǎn)生式右圖結(jié)點(diǎn)“if”與左圖結(jié)點(diǎn)之間的坐標(biāo)關(guān)系分配滿足布局要求的“if”結(jié)點(diǎn)坐標(biāo).然而,由于缺少產(chǎn)生式與上下文的空間關(guān)系的顯式描述,這種間接配置方法的直觀性有所不足,增加了設(shè)計(jì)人員繪制產(chǎn)生式的難度,尤其在那些坐標(biāo)計(jì)算較為復(fù)雜的應(yīng)用場(chǎng)景下.例如,部分圖模型布局算法要求相鄰結(jié)點(diǎn)之間需保持一個(gè)合適的距離,例如力引導(dǎo)布局算法[22]、Fruchterman-Reingold 算法[23]以及Kamada-Kawai 算法[24].圖16 描述了一個(gè)要求相鄰結(jié)點(diǎn)距離不小于2 的布局需求,其中,圖轉(zhuǎn)換后與上下文結(jié)點(diǎn)“a”,“b”相鄰的結(jié)點(diǎn)由結(jié)點(diǎn)“d”轉(zhuǎn)變?yōu)樾略鼋Y(jié)點(diǎn)“c”.

Fig.15 Indirect specification of the spatial relationship between production and context圖15 上下文與產(chǎn)生式之間空間關(guān)系的間接配置

Fig.16 Deficiency of the indirect specification of spatial semantics in intuitiveness圖16 間接空間語義配置在直觀性上的缺陷

以CGG 為例,由于產(chǎn)生式中缺少顯式的上下文結(jié)點(diǎn)“a”和“b”,導(dǎo)致在產(chǎn)生式設(shè)計(jì)階段結(jié)點(diǎn)“c”坐標(biāo)的計(jì)算復(fù)雜化且易出錯(cuò),也在一定程度上增加了產(chǎn)生式設(shè)計(jì)人員學(xué)習(xí)曲線的陡峭程度,不利于布局方法的推廣應(yīng)用.

4 結(jié)論與展望

針對(duì)空間圖文法形式框架存在的問題,本文對(duì)前期工作中構(gòu)建的坐標(biāo)圖文法CGG 進(jìn)行改進(jìn),通過引入虛結(jié)點(diǎn)描述產(chǎn)生式與主圖之間的語法結(jié)構(gòu)與空間語義關(guān)系,并構(gòu)建了一個(gè)新的空間圖文法形式框架vCGG 與幾種典型空間圖文法形式框架進(jìn)行對(duì)比分析,vCGG 具有以下幾個(gè)優(yōu)點(diǎn).

(1) 在產(chǎn)生式中引入虛結(jié)點(diǎn)作為上下文結(jié)點(diǎn),上下文信息得到了顯式的描述,文法具有更好的直觀性;

(2) 采用粘合的方式進(jìn)行圖轉(zhuǎn)換操作,有效防止了轉(zhuǎn)換過程中出現(xiàn)懸邊,操作的規(guī)范性得以保證;

(3) 通過虛結(jié)點(diǎn)描述上下文與產(chǎn)生式之間的空間語義關(guān)系,在保留上下文抽象性的同時(shí),使文法具有更全面的空間語義配置性能;

(4) 使用虛結(jié)點(diǎn)代替懸邊描述上下文,在增強(qiáng)了文法表達(dá)能力的同時(shí),避免了CGG 中的懸邊映射問題;

(5) 在歸約的過程中,能夠通過較少的產(chǎn)生式更早地發(fā)現(xiàn)語法與語義錯(cuò)誤并及時(shí)停機(jī),減少了無效歸約的數(shù)量.

在今后的研究中,在圖文法理論研究方面,我們將進(jìn)一步改善空間圖文法形式框架,嘗試?yán)脠D形元素之間的空間拓?fù)潢P(guān)系進(jìn)一步縮小圖柄搜索空間,減小分析算法的時(shí)間開銷,使文法的實(shí)用性更強(qiáng).在圖文法應(yīng)用方面,我們考慮將圖形元素的空間特征作為關(guān)聯(lián)屬性,為產(chǎn)生式關(guān)聯(lián)語義動(dòng)作或條件謂詞作為屬性文法,在圖轉(zhuǎn)換過程中加入語法制導(dǎo)翻譯,嘗試將圖文法應(yīng)用在建筑外觀建模、工業(yè)設(shè)計(jì)與驗(yàn)證等領(lǐng)域中,并開發(fā)一個(gè)空間圖文法系統(tǒng)平臺(tái),為文法操作以及相關(guān)應(yīng)用的落地提供支撐.

References:

[1] Shi Z,Zeng XQ.Bidirectional transformation between BPMN and BPEL with graph grammar.Computers and Electrical Engineering,2016,51:304-319.

[2] Hibshman J,Sikdar S,Weninger T.Towards interpretable graph modeling with vertex replacement grammars.In: Proc.of the Int’l Conf.on Big Data.2019.372-376.

[3] Li C,Huang L,Chen L.Breeze graph grammar: A graph grammar approach for modeling the software architecture of big data—Oriented software systems.Software Practice & Experience,2015,45(8):1023-1050.

[4] Duarte M,Ribeiro L.Graph grammar extraction from source code.In: Proc.of the Brazilian Symp.on Formal Methods.2017.52-69.

[5] Miyadera Y,Murakami C,Anada K,et al.Attribute graph grammar method for research information collection and sharing.In: Proc.of the Int’l Conf.on Digital Information Management.2016.235-242.

[6] Chen Q,Shi D,Feng G,et al.On-line handwritten flowchart recognition based on logical structure and graph grammar.In: Proc.of the Int’l Conf.on Information Science & Technology.2015.424-429.

[7] Park S,Nie X,Zhu SC.Attribute and-or grammar for joint parsing of human pose,parts and attributes.IEEE Trans.on Pattern Analysis and Machine Intelligence,2017,1555-1569.

[8] Julcaaguilar F,Mouchère H,Viardgaudin C,et al.Top-down online handwritten mathematical expression parsing with graph grammar.In: Proc.of the BeroAmerican Congress on Pattern Recognition.2015.444-451.

[9] Stiny G,Gips J.Shape grammars and the generative specification of painting and sculpture.Proc.of the Workshop on Generalisation & Multiple Representation Leicester,1971,71:1460-1465.

[10] Stiny G.Pictorial and formal aspects of shape and shape grammars and aesthetic systems.Los Angeles: University of California,1975.

[11] Mamoli M.A shape grammar for the building-type definition of the ancient Greek and Roman library and the evaluation of library plans.In: Proc.of the Artificial Intelligence for Engineering Design Analysis and Manufacturing.2020.1-16.

[12] Li YN,Zhang K,Li DJ.Rule-based automatic generation of logo designs.Leonardo,2017,50(2):177-181.

[13] Kong J,Zhang K,Zeng XQ.Spatial graph grammars for graphical user interfaces.ACM Trans.on Computer-Human Interaction,2006,13(2):268-307.

[14] Kong J,Zhang K.Parsing spatial graph grammars.In: Proc.of the IEEE Symp.on Visual Languages & Human Centric Computing.2004.99-101.

[15] Zhang DQ,Zhang K,Cao J.A context-sensitive graph grammar formalism for the specification of visual languages.The Computer Journal,2001,44(3):186-200.

[16] Kong J,Barkol O,Bergman R,et al.Web interface interpretation using graph grammars.IEEE Trans.on Systems,Man,and Cybernetics—Part C: Applications and Reviews,2012,42(4):590-602.

[17] Roudaki A,Kong J,Zhang K.Specification and discovery of web patterns: A graph grammar approach.Information Sciences,2016,328:528-545.

[18] Liu YF,Zeng XQ,Zhang K,Zou Y.Coordinate graph grammar for the specification of spatial graphs (online publication).The Computer Journal,2020.

[19] Liu YF,Zeng XQ,Zhang K.Quantitative spatial semantics in a graph grammar formalism.In: Proc.of the Int’l Workshop on Interactive and Spatial Computing.Dallas: ACM,2018.1-7.

[20] Zeng XQ,Han XQ,Zou Y.An edge-based context-sensitive graph grammar formalism.Ruan Jian Xue Bao/Journal of Software,2008,19(8):1893-1901 (in Chinese with English abstract).http://www.jos.org.cn/jos/article/abstract/20080804?st=article_issue [doi: 10.3724/SP.J.1001.2008.01893]

[21] Zou Y,Lü J,Cao C,et al.On the expressiveness of context-sensitive graph grammars.Ruan Jian Xue Bao/ Journal of Software,2012,23(7):1635-1655 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4085.htm [doi: 10.3724/SP.J.1001.2012.04085]

[22] Eades PA.A heuristic for graph drawing.Congressus Numerantium,1984,42(42):149-160.

[23] Fruchterman TMJ,Reingold EM.Graph drawing by force-directed placement.Software: Practice and Experience,1991,21(11): 1129-1164.

[24] Kamada T,Kawai S.An algorithm for drawing general undirected graphs.Information Processing Letters,1989,31(1):7-15.

附中文參考文獻(xiàn):

[20] 曾曉勤,韓秀清,鄒陽.一種基于邊的上下文相關(guān)圖文法形式化框架.軟件學(xué)報(bào),2008,19(8):1893-1901.http://www.jos.org.cn/jos/ article/abstract/20080804?st=article_issue [doi: 10.3724/SP.J.1001.2008.01893]

[21] 鄒陽,呂建,曹春,等.上下文相關(guān)圖文法的表達(dá)能力分析.軟件學(xué)報(bào),2012,23(7):1635-1655.http://www.jos.org.cn/1000-9825/4085.htm [doi: 10.3724/SP.J.1001.2012.04085]