基于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.