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