基于RTN的藏文句法分析器研究與實現

多拉 安見才讓

摘? 要： 句法分析是藏文信息處理的一個基礎環節，也是智能化藏文信息處理的關鍵所在。遞歸轉移網絡是在有限狀態轉移網絡的基礎上發展而來的，也稱之為RTN算法，與有限狀態轉移網絡不同。文章利用遞歸轉移網絡算法來分析藏文語法規則是否合法，為藏文句法分析后期提供了較好的研究思路及探索價值。

關鍵詞： RTN算法; 語法規則; 句法分析; 有限狀態轉移網絡

中圖分類號：TP39? ? ? ? ? 文獻標志碼：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 引言

隨著計算機技術迅速發展，人們越來越熱切地期盼用自然語言同計算機進行交流，讓計算機承擔大量人的工作，自然語言處理領域的研究涵蓋了詞、短語、句、句群，以及篇章的輸人、輸出、識別、分析、理解、生成等多層面信息加工處理任務[1]。但是藏語信息處理還處于萌芽或初始階段，需解決人與計算機接口，系統問答等一系列重要問題。

目前藏文句法分析有喬姆斯基語法作為理論依據的規則系統，這些系統都采用了正則表達式的方法[2]。后來為了克服限狀態語法的缺陷，喬姆斯基提出了上下文無關文法[3]。上下文無關文法， 也叫做上下文無關的短語結構語法或者叫做短語結構語法。往往一個句子是由一個或很多個短語構成的，所以上下無關文法解決不了很多句法的結構，因此我們利用遞歸的方法解釋一個句子的結構，一個句子可以分為好幾個短語，也就是說一個句子可以利用幾個上下文無關文法，這樣一來，就可以用遞歸轉移網絡。

1 RTN算法的基本策略

遞歸轉移網絡是在有限狀態轉移網絡的基礎上發展而來[4]，但與有限狀態轉移網絡不同。第一，RTN的弧可以標識詞、詞類或語法類，一般，詞和詞類是終結符，語法類是非終結符。第二，RTN是由一個或多個網絡組成。第三，RTN中弧上標的語法類，是另一個網絡的名稱，這造成了可遞歸的調用條件。

在遍歷圖的過程中，如果弧的標識是終結符且匹配成功，那么控制就轉移到網的下一個狀態;如果是一個非終結符，即另一個RTN，則控制轉移到該RTN，直到到達該RTN的終結狀態，控制才返回高層。

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

2 RTN算法的實現

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

⑴ 開始：設Current為RTN中S對應的開始狀態，String=T1，T2，…，Tn，Contral=空集，Trace=空集。

⑵ 如果Current不是終止狀態。

如果Current有多個出邊，則取出current的所有出邊中還未遍歷的第一個出邊，并設當前回溯點Trace。

① 如果Current出邊的標識為終結符Wt，并且Wt與String所指的字符相等，則構造子樹，設Current為當前出邊的后續狀態，String指針指向下一個符號;

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

③ 如果Current出邊的標識為非終結符X，把Current出邊的后續狀態壓入棧Contral中，同時設Current為網絡X的開始狀態。

⑶ 如果Current是終止狀態而且不是S網的終止狀態，則取出Stack的棧頂作為Current。

⑷ 如果Current是S網的終止狀態：

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

如果Trace為空，分析失敗，算法結束。

⑸ 返回⑵。

3 分析器模塊設計

本分析器在windo7操作系統上用C#來開發，整體模塊設計和運行結果圖如下，如圖2和圖3所示。

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

⑵ 已抽取句子用RTN算法進行分析。

⑶ 如果分析成功，生產句法過程。

4 結束語

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

參考文獻（References）：

[1] 才讓加.上下無關文法與藏文句法分析[J].自然科學版，2013.2.

[2] 安見才讓.藏文信息處理原理與技術實現[M].青海民族出版社，2017.

[3] 萬瑪扎西.藏文句法分析的研究與實現[J].中國知網，2013.

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

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

[6] 扎西加.上下文無關文法與藏語句法分析[J].西藏大學學報（自然科學版），2013.

[7] 當增卓瑪等.自動識別藏文整句的方法研究[J].信息與電腦（理論版），2013.