基于Early算法的藏文句法分析研究与实现

德格加 安见才让

摘 要： 句法分析是自然语言处理中的关键一环，它连接更基础的词法分析和更高级的语义分析。文章通过厄尔利（Early）算法分析藏语句子的语法结构，并利用计算机程序实现藏文句子自动分析，生成句法分析树，对藏语句法分析的研究提供了较好的思路，具有探索价值。

关键词： 上下文无关文法； （Early）算法； 藏语句法分析； 句法分析树

中图分类号：TP391.1 文献标志码：A 文章编号：1006-8228（2018）09-08-03

Abstract： Syntactic analysis is a key part of natural language processing. It connects more basic lexical analysis and more advanced semantic analysis. This article analyzes the grammatical structure of Tibetan sentences through the Early algorithm， and uses computer programs to automatically analyze Tibetan sentences and generate syntactic analysis trees. It provides a good research idea for Tibetan syntax analysis and has exploration value.

Key words： Context-free grammar； （Early） algorithm； Tibetan syntax analysis； syntactic analysis tree

0 引言

句法分析作為自然语言处理中的基础性工作和关键技术，藏语句法分析的研究直接对进一步研究语义分析、信息检索语抽取、机器翻译和自动问答系统等藏语自然语言处理领域具有重要意义[1]。由于藏语自然处理起步晚，发展缓慢，至今在藏语句法分析领域仍未取得突破性进展。因此，藏语句法分析的研究和实现对藏语自然语言处理的发展颇具推进作用和现实意义[2]。

句法分析一般都依赖于某种语法体系，本文句法分析以乔姆斯基（N.Chomskyv）上下文无关文法为基本语法规则[3]。上下文无关文法是程序设计语言所使用的语法。它的特点是同样的字符串在不同的语境下，意思不变，即本文所研究的藏语句子皆为非歧义性句子。

1 藏语句法分析概述

句法分析也被称为句法剖析，就是利用语法规则和其他知识，将输入句子中的词与词之间的线性次序转化为一棵结构化的语法树。

句法分析可以简单地分为基于统计方法和基于规则的方法两大类，其中基于规则方法是利用所研究语言的语法知识和语法规则，用形式化的模型来描写语言内在的句法规律。对于任意一个字符串，根据规则可以推导出这个字符串的句法结构，根据句法结构又可以判断该字符串是否合法。而基于统计的方法是用概率统计的方法表示语言单位的语法规律，通过概率矩阵计算出某句子在特定的语言环境中出现的概率，根据概率判断该句子是否合法的可能性[4]。

自然语言是以句子为基本语义单位的，并都有自身的语法规律和特征，而句法分析的任务是按照给定的语法规则，通过计算机程序自动推导句子的结构规律，根据结构规律识别句子中的句法单位和彼此之间的关系，这种关系用一个层次分明，关系类型明确和主次明了的句法树来表示。

2 藏语句法分析算法策略

句法分析的过程就是将小的语法成分不断组合成大的语法成分的过程。虽然藏语句子的语法形式各异，但是在句法分析的过程中所采用的方法基本上是类似的，计算机根据形式化的语法规则判断和分析句子，确定句子的结构。

藏语句法分析系统可以用如下的三元组来表示：

其中S表示所要分析的藏语句子的非空集合；R表示产生藏语句子的规则的非空集合，即规则库；A表示该系统所采用的分析算法，本文中A为厄尔利（Earley）分析算法。

在自然语言处理中，常见的基于规则的分析算法有：自顶向下分析算法、递归转移网络（RNT算法）、CYK算法、厄尔利（Earley）算法、LR算法和富田胜算法等[5]。

2.1 厄尔利（Earley）算法及实现

厄尔利（Earley）算法是处理上下文无关文法算法，是一种自底向上的分析算法，厄尔利算法用项目来表示已经建成的完整或部分成分结构。

项目指在规则右部插入圆点的规则，圆点插入的部位，把规则的右部分为两半，直观上理解，左半部是输入字符串已经被该规则匹配好的，右半部是尚待匹配的[6]。为了更直观反映出与待分析字符串的哪些字符串匹配，厄尔利算法用字符间隔来记录匹配字符串的起始点和结束点。厄尔利算法的字符间隔从0开始。

软件运行截图如图4所示。

3 总结

本文对藏语句子的结构和语法规律进行深入研究的基础上，利用厄尔利（Earley）分析算法，对藏语句子进行结构分析，并通过计算机程序实现藏语句子自动分析推导和生成句法分析树。为藏语句法分析的研究和藏语句法分析系统的开发提供了宏观方法和具体做法。自然语言处理中藏语句法分析是其中的一个关键问题也是我们面临的瓶颈，仍需我们继续探索研究和不断突破。

参考文献（References）：

[1] 冯志伟.计算语言学基础[M].商务印书馆，2008.

[2] 扎西加.上下文无关文法与藏语句法分析[J].西藏大学学报（自然科学版），2013.2（28）：37-41

[3] 刘颖.计算语言学[M].清华大学出版社，2014.

[4] 冯志伟.语言与数学[M].世界图书出版公司北京公司，2011.

[5] 安见才让.基于规则的藏语句法分析研究[J].青海民族大学，2014.

[6] 高定国.藏文信息处理的原理与应用[M].西南交通大学出版社，2014.