基于RTN的藏文句法分析器研究與實(shí)現(xiàn)

多拉 安見才讓

摘? 要： 句法分析是藏文信息處理的一個(gè)基礎(chǔ)環(huán)節(jié)，也是智能化藏文信息處理的關(guān)鍵所在。遞歸轉(zhuǎn)移網(wǎng)絡(luò)是在有限狀態(tài)轉(zhuǎn)移網(wǎng)絡(luò)的基礎(chǔ)上發(fā)展而來的，也稱之為RTN算法，與有限狀態(tài)轉(zhuǎn)移網(wǎng)絡(luò)不同。文章利用遞歸轉(zhuǎn)移網(wǎng)絡(luò)算法來分析藏文語(yǔ)法規(guī)則是否合法，為藏文句法分析后期提供了較好的研究思路及探索價(jià)值。

關(guān)鍵詞： RTN算法; 語(yǔ)法規(guī)則; 句法分析; 有限狀態(tài)轉(zhuǎn)移網(wǎng)絡(luò)

中圖分類號(hào)：TP39? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? 文章編號(hào)：1006-8228（2019）02-12-03

Research and implementation of RTN based Tibetan syntactic analyzer

Duo La， Anjian Cairang

（school of computing， Qinghai University for Nationalities， Xining， Qinghai 810007， China）

Abstract： Syntactic analysis is a basic part of Tibetan information processing， and it is also the key to intelligent Tibetan information processing. The recursive transfer network， which is also called RTN algorithm， is based on the finite state transfer network， but it is different from the finite state transfer network. In this paper， recursive transfer network algorithm is used to analyze the legality of Tibetan grammatical rules， which provides a better research thinking and exploration value for the latter stage of Tibetan syntactic analysis.

Key words： RNT algorithm; grammatical rule; syntactic analysis; finite state transfer network

0 引言

隨著計(jì)算機(jī)技術(shù)迅速發(fā)展，人們?cè)絹碓綗崆械仄谂斡米匀徽Z(yǔ)言同計(jì)算機(jī)進(jìn)行交流，讓計(jì)算機(jī)承擔(dān)大量人的工作，自然語(yǔ)言處理領(lǐng)域的研究涵蓋了詞、短語(yǔ)、句、句群，以及篇章的輸人、輸出、識(shí)別、分析、理解、生成等多層面信息加工處理任務(wù)[1]。但是藏語(yǔ)信息處理還處于萌芽或初始階段，需解決人與計(jì)算機(jī)接口，系統(tǒng)問答等一系列重要問題。

目前藏文句法分析有喬姆斯基語(yǔ)法作為理論依據(jù)的規(guī)則系統(tǒng)，這些系統(tǒng)都采用了正則表達(dá)式的方法[2]。后來為了克服限狀態(tài)語(yǔ)法的缺陷，喬姆斯基提出了上下文無(wú)關(guān)文法[3]。上下文無(wú)關(guān)文法， 也叫做上下文無(wú)關(guān)的短語(yǔ)結(jié)構(gòu)語(yǔ)法或者叫做短語(yǔ)結(jié)構(gòu)語(yǔ)法。往往一個(gè)句子是由一個(gè)或很多個(gè)短語(yǔ)構(gòu)成的，所以上下無(wú)關(guān)文法解決不了很多句法的結(jié)構(gòu)，因此我們利用遞歸的方法解釋一個(gè)句子的結(jié)構(gòu)，一個(gè)句子可以分為好幾個(gè)短語(yǔ)，也就是說一個(gè)句子可以利用幾個(gè)上下文無(wú)關(guān)文法，這樣一來，就可以用遞歸轉(zhuǎn)移網(wǎng)絡(luò)。

1 RTN算法的基本策略

遞歸轉(zhuǎn)移網(wǎng)絡(luò)是在有限狀態(tài)轉(zhuǎn)移網(wǎng)絡(luò)的基礎(chǔ)上發(fā)展而來[4]，但與有限狀態(tài)轉(zhuǎn)移網(wǎng)絡(luò)不同。第一，RTN的弧可以標(biāo)識(shí)詞、詞類或語(yǔ)法類，一般，詞和詞類是終結(jié)符，語(yǔ)法類是非終結(jié)符。第二，RTN是由一個(gè)或多個(gè)網(wǎng)絡(luò)組成。第三，RTN中弧上標(biāo)的語(yǔ)法類，是另一個(gè)網(wǎng)絡(luò)的名稱，這造成了可遞歸的調(diào)用條件。

在遍歷圖的過程中，如果弧的標(biāo)識(shí)是終結(jié)符且匹配成功，那么控制就轉(zhuǎn)移到網(wǎng)的下一個(gè)狀態(tài);如果是一個(gè)非終結(jié)符，即另一個(gè)RTN，則控制轉(zhuǎn)移到該RTN，直到到達(dá)該RTN的終結(jié)狀態(tài)，控制才返回高層。

一個(gè)上下文無(wú)關(guān)文法轉(zhuǎn)換成一個(gè)遞歸轉(zhuǎn)移網(wǎng)絡(luò)（RTN）的方法是這樣的：每一個(gè)非終結(jié)符為左部的所有規(guī)則縮合成一個(gè)小網(wǎng)，它們有共同的開始狀態(tài)結(jié)點(diǎn)，每一個(gè)規(guī)則的右部對(duì)應(yīng)為從開始狀態(tài)結(jié)點(diǎn)到某個(gè)終結(jié)狀態(tài)結(jié)點(diǎn)的路徑，右部的每個(gè)語(yǔ)法符號(hào)對(duì)應(yīng)一條邊，每條邊對(duì)應(yīng)于一個(gè)轉(zhuǎn)移動(dòng)作結(jié)點(diǎn)狀態(tài)[5]。每個(gè)狀態(tài)結(jié)點(diǎn)的出邊按語(yǔ)法符號(hào)排序，終結(jié)符排在前邊，非終結(jié)符排在后邊。

2 RTN算法的實(shí)現(xiàn)

給定輸入字符串W=W1，W2，…，Wn，其詞性標(biāo)注為T=T1，T2，…，Tn。

⑴ 開始：設(shè)Current為RTN中S對(duì)應(yīng)的開始狀態(tài)，String=T1，T2，…，Tn，Contral=空集，Trace=空集。

⑵ 如果Current不是終止?fàn)顟B(tài)。

如果Current有多個(gè)出邊，則取出current的所有出邊中還未遍歷的第一個(gè)出邊，并設(shè)當(dāng)前回溯點(diǎn)Trace。

① 如果Current出邊的標(biāo)識(shí)為終結(jié)符Wt，并且Wt與String所指的字符相等，則構(gòu)造子樹，設(shè)Current為當(dāng)前出邊的后續(xù)狀態(tài)，String指針指向下一個(gè)符號(hào);

② 如果Current出邊的標(biāo)識(shí)為終結(jié)符Wt，并且Wt與String所指的字符不相等，則如果Trace不為空，取出Trace的棧頂元素，返回⑵。否則，分析失敗，算法結(jié)束。

③ 如果Current出邊的標(biāo)識(shí)為非終結(jié)符X，把Current出邊的后續(xù)狀態(tài)壓入棧Contral中，同時(shí)設(shè)Current為網(wǎng)絡(luò)X的開始狀態(tài)。

⑶ 如果Current是終止?fàn)顟B(tài)而且不是S網(wǎng)的終止?fàn)顟B(tài)，則取出Stack的棧頂作為Current。

⑷ 如果Current是S網(wǎng)的終止?fàn)顟B(tài)：

若Contral已空且String指針指向句子結(jié)尾，則分析成功，算法結(jié)束;否則，如果Trace不為空，取出棧頂，返回⑵。

如果Trace為空，分析失敗，算法結(jié)束。

⑸ 返回⑵。

3 分析器模塊設(shè)計(jì)

本分析器在windo7操作系統(tǒng)上用C#來開發(fā)，整體模塊設(shè)計(jì)和運(yùn)行結(jié)果圖如下，如圖2和圖3所示。

⑴ 首先在大量的語(yǔ)料庫(kù)中識(shí)別句子邊界并抽取句子。

⑵ 已抽取句子用RTN算法進(jìn)行分析。

⑶ 如果分析成功，生產(chǎn)句法過程。

4 結(jié)束語(yǔ)

本文對(duì)現(xiàn)代藏語(yǔ)的單句用短語(yǔ)結(jié)構(gòu)語(yǔ)法來建立一套語(yǔ)法規(guī)則，在此基礎(chǔ)上，用RTN算法來分析句子結(jié)構(gòu)是否合法，用計(jì)算機(jī)程序來實(shí)現(xiàn)藏文句法分析器。這對(duì)進(jìn)一步處理藏語(yǔ)句法分析的研究具有重要意義。由于本文的句法規(guī)則庫(kù)還不完善，所以存在歧義的句子尚未處理，這會(huì)影響分析的結(jié)果，對(duì)此需進(jìn)一步研究與完善。

參考文獻(xiàn)（References）：

[1] 才讓加.上下無(wú)關(guān)文法與藏文句法分析[J].自然科學(xué)版，2013.2.

[2] 安見才讓.藏文信息處理原理與技術(shù)實(shí)現(xiàn)[M].青海民族出版社，2017.

[3] 萬(wàn)瑪扎西.藏文句法分析的研究與實(shí)現(xiàn)[J].中國(guó)知網(wǎng)，2013.

[4] 吉太加.藏文句法研究青海民族出版社[M].中國(guó)藏學(xué)出版社，2016.

[5] 華卻才讓等.基于判別式的藏語(yǔ)依存句法分析[J].計(jì)算機(jī)工程，2013.

[6] 扎西加.上下文無(wú)關(guān)文法與藏語(yǔ)句法分析[J].西藏大學(xué)學(xué)報(bào)（自然科學(xué)版），2013.

[7] 當(dāng)增卓瑪?shù)?自動(dòng)識(shí)別藏文整句的方法研究[J].信息與電腦（理論版），2013.