本文關(guān)鍵詞：上下文相關(guān)圖文法及其應(yīng)用研究

  更多相關(guān)文章： 上下文相關(guān)圖文法 形式框架 表達(dá)能力 產(chǎn)生式上下文 語(yǔ)法分析算法

【摘要】：可視化語(yǔ)言提供了一種可視、直觀與抽象的方式去描述復(fù)雜對(duì)象的結(jié)構(gòu)與構(gòu)成的方法,已廣泛應(yīng)用于計(jì)算機(jī)相關(guān)領(lǐng)域�？梢暬Z(yǔ)言研究的最基本問(wèn)題之一是如何描述可視化語(yǔ)言。與形式文法用于描述文本語(yǔ)言類(lèi)似,圖文法是描述可視化語(yǔ)言的自然選擇。由于上下文無(wú)關(guān)圖文法在易用性和表達(dá)能力上均存在明顯不足,上下文相關(guān)圖文法的研究成為必然。然而,已有上下文相關(guān)圖文法在形式框架的完備性上尚多有不足,諸多關(guān)鍵問(wèn)題研究仍面臨挑戰(zhàn),具體表現(xiàn)為：(1)在表達(dá)能力上,對(duì)于已有形式框架表達(dá)能力的理論分析有所欠缺;(2)在產(chǎn)生式形式上,隱式的形式框架普遍存在因產(chǎn)生式中上下文缺失而導(dǎo)致的直觀性差的問(wèn)題；(3)在語(yǔ)法分析算法上,已有的兩類(lèi)算法存在分析效率低下或適應(yīng)范圍過(guò)窄的問(wèn)題。本文提出了一個(gè)一般性的上下文相關(guān)圖文法的概念框架,并在此基礎(chǔ)上對(duì)上述問(wèn)題進(jìn)行了較為系統(tǒng)性的研究,主要工作如下：1.在分析與歸納已有上下文相關(guān)圖文法形式框架的基本特征基礎(chǔ)上,通過(guò)構(gòu)造不同形式框架圖文法實(shí)例之間的轉(zhuǎn)換算法,揭示并證明了這些形式框架的表達(dá)能力之間的關(guān)系。一方面,這些結(jié)論揭示了已有上下文相關(guān)圖文法形式框架的表達(dá)能力之間關(guān)系,補(bǔ)充并完善了圖文法的表達(dá)能力之間關(guān)系的理論。另一方面,這些算法也為不同形式框架圖文法實(shí)例之間的轉(zhuǎn)換提供了一種可行的方法,使上下文相關(guān)圖文法的應(yīng)用不再拘泥于一個(gè)形式框架,而是可以在不同形式框架之間選擇適當(dāng)?shù)拿枋鲂问脚c分析算法,從而提高了這些形式框架的易用性。2.針對(duì)隱式上下文相關(guān)圖文法形式框架中普遍存在的因產(chǎn)生式中上下文缺失所導(dǎo)致的直觀性差的問(wèn)題,以RGG形式框架為基礎(chǔ),提出了一種上下文的形式定義與計(jì)算方法來(lái)揭示產(chǎn)生式中所隱含的上下文。在產(chǎn)生式之間的偏前驅(qū)關(guān)系與全前驅(qū)關(guān)系概念基礎(chǔ)上,形式化定義了產(chǎn)生式的上下文,刻畫(huà)了上下文的基本特征與上下文存在的一個(gè)充分條件,并構(gòu)建了上下文與上下文實(shí)例之間的關(guān)聯(lián)。在此基礎(chǔ)上構(gòu)造了一組算法來(lái)計(jì)算產(chǎn)生式的上下文。對(duì)原本隱含在產(chǎn)生式中的上下文的發(fā)掘增強(qiáng)了產(chǎn)生式形式的直觀性,從而有助于圖文法的理解與設(shè)計(jì)。而且,此方法還可以推廣到其它隱式上下文相關(guān)圖文法形式框架。3.針對(duì)已有上下文相關(guān)圖文法的語(yǔ)法分析算法中存在的問(wèn)題,提出了兩類(lèi)相應(yīng)的改進(jìn)方法。一、針對(duì)僅適用于合流圖文法的語(yǔ)法分析算法的適用范圍過(guò)窄的問(wèn)題,以RGG形式框架為例,提出了兩種轉(zhuǎn)換算法,將非合流的產(chǎn)生式集轉(zhuǎn)換為生成相同圖語(yǔ)言的合流產(chǎn)生式集,從而拓寬了這類(lèi)算法的適用范圍。第一種算法基于擴(kuò)充的RGG形式框架XRGG,將非合流的RGG產(chǎn)生式轉(zhuǎn)換成合流的XRGG產(chǎn)生式；第二種算法基于產(chǎn)生式上下文,將非合流的RGG產(chǎn)生式轉(zhuǎn)換成合流的裝配了裁剪過(guò)的1層上下文及其派生上下文的RGG產(chǎn)生式。兩種算法的適用情形有所不同。二、針對(duì)通用語(yǔ)法分析算法效率低下的問(wèn)題,提出了一種上下文匹配方法,用產(chǎn)生式的上下文去匹配主圖中圖柄的上下文來(lái)進(jìn)一步鑒別待替換圖柄,以盡可能地排除不必要?dú)w約,從而提高了通用算法的分析效率。4.研究了上下文相關(guān)圖文法在程序并行性分析中的應(yīng)用。針對(duì)并行性分析往往需要先從程序代碼中抽取出控制與數(shù)據(jù)流圖或其它依賴(lài)圖的問(wèn)題,基于RGG形式框架,定義了一種任務(wù)級(jí)的并行編程圖語(yǔ)言GPPL來(lái)直接描述順序或并行程序的控制與數(shù)據(jù)流圖,并提出了相應(yīng)的并行性分析算法以挖掘GPPL圖程序的并行性特征,從而使并行性挖掘避免了從程序中抽取出相應(yīng)依賴(lài)圖的過(guò)程。與已有方法相比,GPPL圖的形式更為簡(jiǎn)潔與直觀和更具表達(dá)能力,而且算法的并行性挖掘能力也更強(qiáng)。5.設(shè)計(jì)并部分實(shí)現(xiàn)了一個(gè)上下文相關(guān)圖文法支撐系統(tǒng),以支持基于上下文相關(guān)圖文法的圖語(yǔ)言設(shè)計(jì)、分析及應(yīng)用。系統(tǒng)提供了可視化的用戶(hù)操作界面,其主要功能涵蓋圖文法編輯與語(yǔ)法檢查、產(chǎn)生式上下文計(jì)算、以及在圖文法合流判定基礎(chǔ)上的對(duì)于主圖的語(yǔ)法分析。而且,在此支撐系統(tǒng)上實(shí)現(xiàn)了對(duì)GPPL圖語(yǔ)言的定義和一個(gè)GPPL圖的語(yǔ)法分析。
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：TP391.1
，

本文編號(hào)：1266694