多拉 安見才讓

摘? 要： 句法分析是藏文信息處理的一個基礎(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ò)算法來分析藏文語法規(guī)則是否合法，為藏文句法分析后期提供了較好的研究思路及探索價(jià)值。

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

中圖分類號：TP39? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? 文章編號：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ā)展，人們越來越熱切地期盼用自然語言同計(jì)算機(jī)進(jìn)行交流，讓計(jì)算機(jī)承擔(dān)大量人的工作，自然語言處理領(lǐng)域的研究涵蓋了詞、短語、句、句群，以及篇章的輸人、輸出、識別、分析、理解、生成等多層面信息加工處理任務(wù)[1]。但是藏語信息處理還處于萌芽或初始階段，需解決人與計(jì)算機(jī)接口，系統(tǒng)問答等一系列重要問題。

目前藏文句法分析有喬姆斯基語法作為理論依據(jù)的規(guī)則系統(tǒng)，這些系統(tǒng)都采用了正則表達(dá)式的方法[2]。后來為了克服限狀態(tài)語法的缺陷，喬姆斯基提出了上下文無關(guān)文法[3]。上下文無關(guān)文法， 也叫做上下文無關(guān)的短語結(jié)構(gòu)語法或者叫做短語結(jié)構(gòu)語法。往往一個句子是由一個或很多個短語構(gòu)成的，所以上下無關(guān)文法解決不了很多句法的結(jié)構(gòu)，因此我們利用遞歸的方法解釋一個句子的結(jié)構(gòu)，一個句子可以分為好幾個短語，也就是說一個句子可以利用幾個上下文無關(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)識詞、詞類或語法類，一般，詞和詞類是終結(jié)符，語法類是非終結(jié)符。第二，RTN是由一個或多個網(wǎng)絡(luò)組成。第三，RTN中弧上標(biāo)的語法類，是另一個網(wǎng)絡(luò)的名稱，這造成了可遞歸的調(diào)用條件。

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

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

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

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

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

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

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

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

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

③ 如果Current出邊的標(biāo)識為非終結(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所示。

⑴ 首先在大量的語料庫中識別句子邊界并抽取句子。

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

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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