基于Early算法的藏文句法分析研究與實現(xiàn)

德格加 安見才讓

摘 要： 句法分析是自然語言處理中的關(guān)鍵一環(huán)，它連接更基礎(chǔ)的詞法分析和更高級的語義分析。文章通過厄爾利（Early）算法分析藏語句子的語法結(jié)構(gòu)，并利用計算機程序?qū)崿F(xiàn)藏文句子自動分析，生成句法分析樹，對藏語句法分析的研究提供了較好的思路，具有探索價值。

關(guān)鍵詞： 上下文無關(guān)文法； （Early）算法； 藏語句法分析； 句法分析樹

中圖分類號：TP391.1 文獻(xiàn)標(biāo)志碼：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 引言

句法分析作為自然語言處理中的基礎(chǔ)性工作和關(guān)鍵技術(shù)，藏語句法分析的研究直接對進(jìn)一步研究語義分析、信息檢索語抽取、機器翻譯和自動問答系統(tǒng)等藏語自然語言處理領(lǐng)域具有重要意義[1]。由于藏語自然處理起步晚，發(fā)展緩慢，至今在藏語句法分析領(lǐng)域仍未取得突破性進(jìn)展。因此，藏語句法分析的研究和實現(xiàn)對藏語自然語言處理的發(fā)展頗具推進(jìn)作用和現(xiàn)實意義[2]。

句法分析一般都依賴于某種語法體系，本文句法分析以喬姆斯基（N.Chomskyv）上下文無關(guān)文法為基本語法規(guī)則[3]。上下文無關(guān)文法是程序設(shè)計語言所使用的語法。它的特點是同樣的字符串在不同的語境下，意思不變，即本文所研究的藏語句子皆為非歧義性句子。

1 藏語句法分析概述

句法分析也被稱為句法剖析，就是利用語法規(guī)則和其他知識，將輸入句子中的詞與詞之間的線性次序轉(zhuǎn)化為一棵結(jié)構(gòu)化的語法樹。

句法分析可以簡單地分為基于統(tǒng)計方法和基于規(guī)則的方法兩大類，其中基于規(guī)則方法是利用所研究語言的語法知識和語法規(guī)則，用形式化的模型來描寫語言內(nèi)在的句法規(guī)律。對于任意一個字符串，根據(jù)規(guī)則可以推導(dǎo)出這個字符串的句法結(jié)構(gòu)，根據(jù)句法結(jié)構(gòu)又可以判斷該字符串是否合法。而基于統(tǒng)計的方法是用概率統(tǒng)計的方法表示語言單位的語法規(guī)律，通過概率矩陣計算出某句子在特定的語言環(huán)境中出現(xiàn)的概率，根據(jù)概率判斷該句子是否合法的可能性[4]。

自然語言是以句子為基本語義單位的，并都有自身的語法規(guī)律和特征，而句法分析的任務(wù)是按照給定的語法規(guī)則，通過計算機程序自動推導(dǎo)句子的結(jié)構(gòu)規(guī)律，根據(jù)結(jié)構(gòu)規(guī)律識別句子中的句法單位和彼此之間的關(guān)系，這種關(guān)系用一個層次分明，關(guān)系類型明確和主次明了的句法樹來表示。

2 藏語句法分析算法策略

句法分析的過程就是將小的語法成分不斷組合成大的語法成分的過程。雖然藏語句子的語法形式各異，但是在句法分析的過程中所采用的方法基本上是類似的，計算機根據(jù)形式化的語法規(guī)則判斷和分析句子，確定句子的結(jié)構(gòu)。

藏語句法分析系統(tǒng)可以用如下的三元組來表示：

其中S表示所要分析的藏語句子的非空集合；R表示產(chǎn)生藏語句子的規(guī)則的非空集合，即規(guī)則庫；A表示該系統(tǒng)所采用的分析算法，本文中A為厄爾利（Earley）分析算法。

在自然語言處理中，常見的基于規(guī)則的分析算法有：自頂向下分析算法、遞歸轉(zhuǎn)移網(wǎng)絡(luò)（RNT算法）、CYK算法、厄爾利（Earley）算法、LR算法和富田勝算法等[5]。

2.1 厄爾利（Earley）算法及實現(xiàn)

厄爾利（Earley）算法是處理上下文無關(guān)文法算法，是一種自底向上的分析算法，厄爾利算法用項目來表示已經(jīng)建成的完整或部分成分結(jié)構(gòu)。

項目指在規(guī)則右部插入圓點的規(guī)則，圓點插入的部位，把規(guī)則的右部分為兩半，直觀上理解，左半部是輸入字符串已經(jīng)被該規(guī)則匹配好的，右半部是尚待匹配的[6]。為了更直觀反映出與待分析字符串的哪些字符串匹配，厄爾利算法用字符間隔來記錄匹配字符串的起始點和結(jié)束點。厄爾利算法的字符間隔從0開始。

軟件運行截圖如圖4所示。

3 總結(jié)

本文對藏語句子的結(jié)構(gòu)和語法規(guī)律進(jìn)行深入研究的基礎(chǔ)上，利用厄爾利（Earley）分析算法，對藏語句子進(jìn)行結(jié)構(gòu)分析，并通過計算機程序?qū)崿F(xiàn)藏語句子自動分析推導(dǎo)和生成句法分析樹。為藏語句法分析的研究和藏語句法分析系統(tǒng)的開發(fā)提供了宏觀方法和具體做法。自然語言處理中藏語句法分析是其中的一個關(guān)鍵問題也是我們面臨的瓶頸，仍需我們繼續(xù)探索研究和不斷突破。

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

[1] 馮志偉.計算語言學(xué)基礎(chǔ)[M].商務(wù)印書館，2008.

[2] 扎西加.上下文無關(guān)文法與藏語句法分析[J].西藏大學(xué)學(xué)報（自然科學(xué)版），2013.2（28）：37-41

[3] 劉穎.計算語言學(xué)[M].清華大學(xué)出版社，2014.

[4] 馮志偉.語言與數(shù)學(xué)[M].世界圖書出版公司北京公司，2011.

[5] 安見才讓.基于規(guī)則的藏語句法分析研究[J].青海民族大學(xué)，2014.

[6] 高定國.藏文信息處理的原理與應(yīng)用[M].西南交通大學(xué)出版社，2014.