【摘要】：句法分析是結(jié)構(gòu)模式識(shí)別系統(tǒng)的重要組成部分之一。然而,傳統(tǒng)上句法分析單元的實(shí)現(xiàn)方式是通過編寫專門的過程語(yǔ)言的代碼。當(dāng)應(yīng)用領(lǐng)域需要識(shí)別的文法規(guī)模十分龐大時(shí),編寫出能夠快速對(duì)樣本進(jìn)行識(shí)別的程序,并不容易。 本文嘗試通過將句法分析算法與關(guān)系代數(shù)模型緊密集成,利用關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)能夠組織和快速檢索海量數(shù)據(jù)的特點(diǎn),增強(qiáng)句法分析單元處理復(fù)雜文法樣本的能力,同時(shí)減輕用戶的編碼負(fù)擔(dān)。 我們給出了Earley (?)(?)法分析算法的擴(kuò)展關(guān)系模型。在此框架中,任意部分推導(dǎo)樹集合可對(duì)應(yīng)表示為關(guān)系代數(shù)中一個(gè)關(guān)系；部分推導(dǎo)樹之間的運(yùn)算被表示為關(guān)系代數(shù)運(yùn)算；語(yǔ)法分析算法被對(duì)應(yīng)表示為一條遞歸查詢語(yǔ)句；過程語(yǔ)言描述的運(yùn)算過程與遞歸查詢的查詢執(zhí)行在單個(gè)運(yùn)算、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)三個(gè)方面存在對(duì)應(yīng)關(guān)系。 依據(jù)此框架,我們給出一種新的Earley語(yǔ)法分析關(guān)系代數(shù)算法,及其公用表表達(dá)式(CTE)實(shí)現(xiàn)和存儲(chǔ)過程的實(shí)現(xiàn)。并通過原型系統(tǒng)驗(yàn)證了該方法的可行性。 屬性文法兼有決策理論方法和結(jié)構(gòu)方法兩者的特點(diǎn),所以在模式識(shí)別領(lǐng)域中受到廣泛的注意。因此進(jìn)一步本文嘗試將基于關(guān)系代數(shù)的方法推廣應(yīng)用于屬性文法的語(yǔ)義分析問題,給出一種基于關(guān)系代數(shù)的Earley綜合屬性語(yǔ)法制導(dǎo)翻譯算法。將其應(yīng)用于一個(gè)基本的綜合屬性計(jì)算問題——算術(shù)表達(dá)式求值問題,算法可在讀入表達(dá)式詞法分析結(jié)果的同時(shí),計(jì)算出表達(dá)式的值。從而驗(yàn)證了該方法的可行性。 已知了Earley語(yǔ)法分析算法與關(guān)系數(shù)據(jù)庫(kù)間存在的這些對(duì)應(yīng)關(guān)系,在今后的算法設(shè)計(jì)中就可以全部或部分地利用這些關(guān)系,有選擇地將句法分析問題全部或部分轉(zhuǎn)化為數(shù)據(jù)庫(kù)查詢問題,借助關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)處理海量數(shù)據(jù)的優(yōu)勢(shì),增強(qiáng)句法分析單元處理復(fù)雜文法樣本的能力。此外,借助本文給出的擴(kuò)展關(guān)系代數(shù)運(yùn)算,可以方便地表達(dá)Earley語(yǔ)法分析算法運(yùn)算過程中產(chǎn)生的語(yǔ)法分析項(xiàng)目或部分推導(dǎo)樹之間的關(guān)系。 理論方面,由于已知這些對(duì)應(yīng)關(guān)系,對(duì)于一個(gè)領(lǐng)域的某些問題,通過類比,有可能從另一個(gè)領(lǐng)域獲得啟發(fā)。例如,我們可以通過比較二者,發(fā)現(xiàn)相對(duì)查詢執(zhí)行而言,過程語(yǔ)言所描述的算法在某些方面具有更高執(zhí)行效率的原因。這些無疑是數(shù)據(jù)庫(kù)查詢處理可以借鑒的。
[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.
【學(xué)位授予單位】：大連交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：H043

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

4 孫浩鵬;;基于SQL的高校科研管理平臺(tái)[J];長(zhǎng)春工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2010年01期

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

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

7 李長(zhǎng)文;余春昊;周軍;李國(guó)軍;劉復(fù)屏;;測(cè)井處理解釋一體化軟件平臺(tái)的設(shè)計(jì)[J];測(cè)井技術(shù);2011年04期

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

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

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

相關(guān)會(huì)議論文 前3條

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

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

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

相關(guān)博士學(xué)位論文 前6條

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

2 楊林;支持多模式的復(fù)合交通網(wǎng)絡(luò)模型及關(guān)鍵技術(shù)研究[D];中國(guó)地質(zhì)大學(xué);2008年

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

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

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

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

相關(guān)碩士學(xué)位論文 前10條

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

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

3 王強(qiáng);高校綜合人力資源管理系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)[D];中國(guó)海洋大學(xué);2010年

4 申冠楠;百貨店庫(kù)存管理信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];中國(guó)海洋大學(xué);2010年

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

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

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

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

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

10 程歲歲;面向XML文檔的細(xì)粒度訪問控制研究及應(yīng)用[D];東華大學(xué);2011年

本文編號(hào)：2241788