【摘要】：句法分析是結(jié)構(gòu)模式識別系統(tǒng)的重要組成部分之一。然而,傳統(tǒng)上句法分析單元的實現(xiàn)方式是通過編寫專門的過程語言的代碼。當應用領域需要識別的文法規(guī)模十分龐大時,編寫出能夠快速對樣本進行識別的程序,并不容易。 本文嘗試通過將句法分析算法與關系代數(shù)模型緊密集成,利用關系數(shù)據(jù)庫系統(tǒng)能夠組織和快速檢索海量數(shù)據(jù)的特點,增強句法分析單元處理復雜文法樣本的能力,同時減輕用戶的編碼負擔。 我們給出了Earley (?)(?)法分析算法的擴展關系模型。在此框架中,任意部分推導樹集合可對應表示為關系代數(shù)中一個關系；部分推導樹之間的運算被表示為關系代數(shù)運算；語法分析算法被對應表示為一條遞歸查詢語句；過程語言描述的運算過程與遞歸查詢的查詢執(zhí)行在單個運算、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)三個方面存在對應關系。 依據(jù)此框架,我們給出一種新的Earley語法分析關系代數(shù)算法,及其公用表表達式(CTE)實現(xiàn)和存儲過程的實現(xiàn)。并通過原型系統(tǒng)驗證了該方法的可行性。 屬性文法兼有決策理論方法和結(jié)構(gòu)方法兩者的特點,所以在模式識別領域中受到廣泛的注意。因此進一步本文嘗試將基于關系代數(shù)的方法推廣應用于屬性文法的語義分析問題,給出一種基于關系代數(shù)的Earley綜合屬性語法制導翻譯算法。將其應用于一個基本的綜合屬性計算問題——算術表達式求值問題,算法可在讀入表達式詞法分析結(jié)果的同時,計算出表達式的值。從而驗證了該方法的可行性。 已知了Earley語法分析算法與關系數(shù)據(jù)庫間存在的這些對應關系,在今后的算法設計中就可以全部或部分地利用這些關系,有選擇地將句法分析問題全部或部分轉(zhuǎn)化為數(shù)據(jù)庫查詢問題,借助關系數(shù)據(jù)庫系統(tǒng)處理海量數(shù)據(jù)的優(yōu)勢,增強句法分析單元處理復雜文法樣本的能力。此外,借助本文給出的擴展關系代數(shù)運算,可以方便地表達Earley語法分析算法運算過程中產(chǎn)生的語法分析項目或部分推導樹之間的關系。 理論方面,由于已知這些對應關系,對于一個領域的某些問題,通過類比,有可能從另一個領域獲得啟發(fā)。例如,我們可以通過比較二者,發(fā)現(xiàn)相對查詢執(zhí)行而言,過程語言所描述的算法在某些方面具有更高執(zhí)行效率的原因。這些無疑是數(shù)據(jù)庫查詢處理可以借鑒的。
[Abstract]:Syntactic analysis is one of the important components of structural pattern recognition system. Traditionally, however, syntactic parsing units are implemented by writing specific procedural language codes. When the scale of grammar recognition in application field is very large, it is not easy to write a program that can recognize samples quickly. This paper attempts to integrate the syntactic parsing algorithm with the relational algebra model, and make use of the characteristics of the relational database system to organize and quickly retrieve the massive data, so as to enhance the ability of the syntactic analysis unit to deal with complex grammar samples. At the same time reduce the user's coding burden. We gave Earley (?) The extended relational model of the algorithm is analyzed by the method. In this framework, any set of partial derivation trees can be represented as a relation in relational algebra, the operations between partial derivation trees can be represented as relational algebraic operations, and the syntax analysis algorithm can be represented as a recursive query statement. The operation process described by the procedure language has corresponding relations with the query of recursive query in three aspects: single operation, control structure and data structure. According to this framework, we present a new Earley syntax parsing relational algebra algorithm, and the realization of common table expression (CTE) and stored procedure. The feasibility of the method is verified by the prototype system. Attribute grammar has both the characteristics of decision theory and structural method, so it has been paid more and more attention in the field of pattern recognition. Therefore, this paper attempts to extend the relational algebraic approach to the semantic analysis of attribute grammars, and presents a Earley Synthetical attribute Grammar guidance Translation algorithm based on relational algebra. It is applied to a basic comprehensive attribute evaluation problem, the arithmetic expression evaluation problem. The algorithm can calculate the expression value while reading the result of the expression lexical analysis. The feasibility of the method is verified. These corresponding relations between Earley parsing algorithm and relational database are known, which can be fully or partially utilized in future algorithm design. The syntactic parsing problem is transformed into database query problem in whole or in part selectively, and the ability of syntactic analysis unit to deal with complex grammar samples is enhanced by using the advantage of relational database system to deal with massive data. In addition, with the help of the extended relational algebraic operation presented in this paper, it is easy to express the relationship between the parse items or partial derivation trees produced in the operation of the Earley parsing algorithm. Theoretically, because these corresponding relations are known, it is possible to draw inspiration from another domain for some problems in one domain by analogy. For example, by comparing the two, we can find the reason why the algorithms described in the procedure language are more efficient in some aspects than query execution. These are undoubtedly database query processing can be used for reference.
【學位授予單位】：大連交通大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：H043

【共引文獻】

相關期刊論文 前10條

1 李用江,回雁雁;基于ADO.NET的海洋經(jīng)濟生物MIS系統(tǒng)[J];安陽師范學院學報;2004年05期

2 徐潔;許永昌;于亞婁;金衛(wèi)東;;數(shù)據(jù)庫技術在測井資料分析中的應用[J];吉林大學學報(地球科學版);2007年S1期

3 劉萌萌;;基于B/S、C/S的混合模式在網(wǎng)絡數(shù)據(jù)庫中的應用[J];成都信息工程學院學報;2006年02期

4 孫浩鵬;;基于SQL的高�？蒲泄芾砥脚_[J];長春工程學院學報(自然科學版);2010年01期

5 向宏;唐旭;胡海波;魯先志;李樂樂;;大量并發(fā)環(huán)境下的緩沖異步處理模型[J];重慶工學院學報(自然科學版);2009年01期

6 王建民;曹慶芳;金衛(wèi)東;;巖石物理實驗數(shù)據(jù)庫網(wǎng)絡系統(tǒng)的建立[J];測井技術;2006年03期

7 李長文;余春昊;周軍;李國軍;劉復屏;;測井處理解釋一體化軟件平臺的設計[J];測井技術;2011年04期

8 王紅藝;李冠峰;楊春蕾;普杰信;;實例教學在數(shù)據(jù)庫原理教學中的應用[J];電腦知識與技術(學術交流);2007年05期

9 王木林;;基于關聯(lián)規(guī)則數(shù)據(jù)挖掘技術在教學管理中的應用[J];電腦知識與技術(學術交流);2007年08期

10 張立;;數(shù)據(jù)庫管理系統(tǒng)及其實現(xiàn)問題研究[J];電腦知識與技術;2010年16期

相關會議論文 前3條

1 殷旭;田英愛;;高校計算機專業(yè)數(shù)據(jù)庫課程教學改革研究與探討[A];著力提高高等教育質(zhì)量，，努力增強高校創(chuàng)新與服務能力——北京市高等教育學會2007年學術年會論文集（上冊）[C];2008年

2 吳秀娟;方愛平;;基于SQL Server的測繪儀器檢定數(shù)據(jù)處理系統(tǒng)的VC++實現(xiàn)[A];2009年全國測繪儀器綜合學術年會論文集[C];2009年

3 許世峰;高軍;楊冬青;王騰蛟;;基于穿行次數(shù)的大規(guī)模圖數(shù)據(jù)路徑查詢[A];第26屆中國數(shù)據(jù)庫學術會議論文集（A輯）[C];2009年

相關博士學位論文 前6條

1 于寶琴;成套電器企業(yè)異構(gòu)數(shù)據(jù)整合及其物流系統(tǒng)的研究[D];天津大學;2006年

2 楊林;支持多模式的復合交通網(wǎng)絡模型及關鍵技術研究[D];中國地質(zhì)大學;2008年

3 趙春宇;高性能并行GIS中矢量空間數(shù)據(jù)存取與處理關鍵技術研究[D];武漢大學;2006年

4 向軍;移動實時數(shù)據(jù)庫系統(tǒng)服務質(zhì)量管理[D];華中科技大學;2008年

5 胡茂勝;基于數(shù)據(jù)中心模式的分布式異構(gòu)空間數(shù)據(jù)無縫集成技術研究[D];中國地質(zhì)大學;2009年

6 戴露;煤礦地測數(shù)據(jù)的地理本體與網(wǎng)絡服務研究[D];中國礦業(yè)大學;2010年

相關碩士學位論文 前10條

1 任萌;鮑店煤礦輔助運輸信息管理系統(tǒng)設計與實現(xiàn)[D];山東科技大學;2010年

2 宋小波;基于Flex的內(nèi)容管理系統(tǒng)（CMS）的設計與實現(xiàn)[D];湘潭大學;2010年

3 王強;高校綜合人力資源管理系統(tǒng)的設計和實現(xiàn)[D];中國海洋大學;2010年

4 申冠楠;百貨店庫存管理信息系統(tǒng)的設計與實現(xiàn)[D];中國海洋大學;2010年

5 李秀雯;基于WebGIS的河南工業(yè)經(jīng)濟監(jiān)測預警系統(tǒng)設計[D];河南工業(yè)大學;2010年

6 劉娟;基于.NET的小區(qū)物業(yè)管理系統(tǒng)的設計與實現(xiàn)[D];華東師范大學;2010年

7 胡建鈞;浙江商職院網(wǎng)絡評審系統(tǒng)的設計與實現(xiàn)[D];華東師范大學;2010年

8 陳潔敏;電子運維系統(tǒng)中作業(yè)管理模塊的設計和實現(xiàn)[D];華南理工大學;2010年

9 吳東;網(wǎng)上人才信息管理系統(tǒng)[D];南昌大學;2010年

10 程歲歲;面向XML文檔的細粒度訪問控制研究及應用[D];東華大學;2011年

本文編號：2241788