基于自頂向下算法的維吾爾語句法分析初探

摘要:該文通過研究國內外相關的句法分析算法與理論，再結合維吾爾語自身的特點對基于規則的維吾爾語句法分析方法進行討論，由于維吾爾語作為一種自然語言，具有自然語言所共有的一些規則，發現國外經典的句法分析方法同樣適合于維吾爾語的句法分析，本論文主要討論了自頂向下的的自動句法分析方法。

關鍵詞:維吾爾;句法分析;自頂向下

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2010)05-1182-02

Research and Analysis of a Rule-based Uyghur Top-Down Parsing

Abudoukeram.abulizi1， Halidanmu.Abudoukeram2， Tuergen.Yibulayin2， Palidan.Tursun3， Aishan.Wumaier2

(1.College of philology， Xinjiang University， Urumqi 830046， China;2. College of Information Science Engineering， Xinjiang University， Urumqi 830046， China; 3.Software College， Xinjiang University， Urumqi 830046， China)

Abstract: In this paper， we discuss the Rule-based Uyghur syntactic analysis through research the relevant abroad parsing algorithm and theory， at the same time， the characteristics of Uyghur sentence structure. For the reasons that Uyghur is a natural language and have some common rules with the natural language， abroad typical syntacic analysis also adapt to the Uyghur parsing. This paper mainly discuss about the Top-Down automatic parsing.

Key words: Uyghur; parsing; syntactic analysis; top-down

隨著社會的信息化程度越來越高，信息資源的日益豐富，人們希望使用本民族語言能夠與計算機進行交互。自然語言作為人與機器進行溝通的重要方式，使得自然語言的處理顯得非常重要。句法分析是自然語言處理中一個很重要的研究內容。對一個語言的分析包括詞法分析、句法分析、語義和語用分析幾個層面，因此句法分析的好壞直接影響到后繼工程的進程[7]。

句法分析的任務是通過運用句法規則和計算機算法等一些知識，將輸入的字串變換成句子的句法結構。句法分析的研究大體上可以分為兩個途徑:基于規則的句法分析方法和基于統計的句法分析方法[1]?；谝巹t的方法是以語言學理論為基礎，通過人工組織語法規則建立規則庫。在句法分析的研究中，此方法一直是句法分析的主要方法?；诮y計的方法是以數學模型和大規模語料庫為基礎進行句法分析。不管采用哪種方法，為了分析一個句子的句法結構，必須要考慮兩個方面的因素:一是形式語法體系，二是句法分析技術。形式語法體系主要有匹配模式、短語結構語法、擴充轉移網絡等。句法分析技術也有多種:如自頂向下分析算法、自底向上分析算法、CYK(Cocke-Younger-Kasami)分析算法、GLR(Tomina)算法、Chart算法、鏈分析算法等[6]。

由于維吾爾語作為一種自然語言，具有自然語言所共有的一些規則，因此，本文采用了基于短語結構語法規則的自頂向下的句法分析方法。文章余下部分的安排如下:第二部分給出形式語法體系的相關知識及維吾爾語規則庫的建立思路。第三部分結合維吾爾語的特點介紹自頂向下的句法分析方法。第四部分對當前存在的問題進行討論。

2基于自頂向下的維吾爾語句法分析方法

自頂向下的句法分析(Top-Down Parsing Method)是從開始符開始，根據產生式規則，不斷用右邊的式子替換左邊的式子，反復執行直到替換后的符號表與輸入句子詞類相匹配的終結符序列為止，通過自頂向下的推導過程將會得到一個句法樹。

在進行句法分析之前先要建立維吾爾語字典和規則庫，字典中存放詞的詞性，規則庫中存放維吾爾語語法規則，由于維吾爾語與英語、漢語在句法結構上有很大的區別，如英、漢屬于SVO(主+謂+賓)語言，而維吾爾語是SOV(主+賓+謂)語言。漢語為無形態語言，而維吾爾為形態豐富的語言，即維吾爾語中有明顯形態標志的格，一般出現在句子的末尾。英語中有標句成分，其位置在句首，而維語卻沒有。英語中有屈折變化成分，是整個句子的核心，而維吾爾語屬于黏著型語言，句子的核心用黏著型附加成分表示。因此，我們不能照搬漢語或英語已建立好的規則庫和字典，而需要根據維吾爾語自身的特點建立規則庫和字典。

我們使用已詞性和短語標注過的新疆大學信息學院多語種信息技術重點實驗室詞性標注語料庫(XJU UPOS Corpus)的自動詞性標注系統建立字典。由于維吾爾語屬于阿爾泰語系，在建立規則庫的過程中我們借鑒了力提甫#8226;托合提教授的著作《阿爾泰語言的句法結構》，在這本著作里，力提甫#8226;托合提教授通過對諾姆#8226;喬姆斯基的生成語法理論的深入研究，建立了維吾爾語的句法結構。由這個句法結構，我們總結了一部基本的規則庫。例如句子:Alimnig hdisi kynk sitwalgili sodasarayga ktdi。通過自動標注系統，我們得到字典:

Alim N nig Khd Nsi Agrkynk NsitwalV

sodasarayga Nkt Vdi Igili ADLZga K

再根據力提甫#8226;托合提教授的著作中的內容我們得到該句的規則庫，如下所示:

1.IP->S I 2.S->KP VP3.S->NP VP 4.KP->NP K

5.NP->KP N(pos)6.NP->N 7.VP-> SUBSP VP 8.VP->NP V

9.VP-> KP V 10.VP->V11.SUBSP->S ADLZ 12.N(pos)->N Agr

13.K-> Φ14.N->e

在以上的字典和規則庫中包含14個非終結符號，分別為:IP(充足句)，S(單句)，I(屈折成分)，NP(名詞短語)，VP(動詞短語)，KP(格短語)，SUBSP(靜詞化成分)，ADLZ(副動詞)，N(pos)(從屬名詞)，N(名詞)，V(動詞)，Agr(從屬名詞的一致關系)。

建立好字典和規則庫以后，我們就可以進行自頂向下維吾爾語句法分析，以下是算法的實現過程的偽代碼描述:

1) 初始化:規則庫Loadrules和字典Loaddictionary，當前狀態current state，后備狀態為wait state。

LoadRules(string fileName);

LoadDictionary(string fileName);

current state=((IP)1);

wait state=NULL;

2) sentence=Alimnig hdisi kynk sitwalgili sodasarayga ktdi.對輸入的句子進行位置標注:sentence=1 Alimnig 2 hdisi 3 kynk 4 sitwalgili 5 sodasarayga 6 ktdi 7。

3) 掃描字典:

for i=0至maxlength(字典)

標注句子中每個詞的詞性。

4) 循環執行以下語句:

① if current state=1 and 詞位置=7，則算法成功，返回

② if (current state= wait state =1 and 詞位置!=7)，則算法失敗，return.

else if current state 的第一個字符是句子中下一個詞的詞類，則從current state 刪除第一個字符，并修改詞位置。

else if current state 的第一個字符是非終結符，訪問規則庫改寫current state 和 wait state.

elsecurrent state=pop(wait state );

3 實驗

維吾爾語句子“Alimnig hdisi kynk sitwalgili sodasarayga ktdi”(阿力木的姐姐去商場買裙子了)在理想情況下的分析過程如表1所示(為了書寫方便，在后備狀態中用字母a，c等來表示某一狀態，當前狀態中有下劃線的符號表示要用P規則的左邊部分替換右邊部分)。

分析結果為:

IP[S[KP[NP[KP[NP[N Alim] [K nig]] N(pos)[[N hd] [Agr si]] [KΦ]] VP[SUBSP[S[NP[N e] VP[NP[N kyn] [V sitwal]]] [ADLZ gili]] VP[KP[NP[N sodasara ] [K ga]] [V kat]]]][I di ]]

通過句法分析的結果可以畫出維吾爾文句子“Alimnig hdisi kynk sitwalgili sodasarayga ktdi”的句法樹表示如圖1所示。

3結論

通過以上分析注意到，采用自底向上的句法分析算法進行基于規則的維吾爾語句法分析在某些方面不夠理想，主要原因分析如下:

1)不能保證產生式規則間的相容性和一致性，隨著系統中規則數量的增加，規則之間常常會發生沖突，使得對一些句子的分析產生錯誤，嚴重的可能會導致死循環，如:KP->NP K，NP->KP N(pos)，KP和NP可以相互推導，但這樣可能會出現分析無止境的進行下去。

2)試驗所選取的字典和規則庫規模較小，而規則的獲取完全依賴于開發規則的工程師的語言知識和經驗，因此獲取大規模語法規則非常困難。

3)系統中采用的自頂向下算法只是普通的算法，如果要提高分析的效率而需要對算法進行進一步的改進。

總而言之，自頂向下的句法分析還只能處理一些相對簡單的句子，下一步的工作是不斷改進產生式規則和自頂向下算法，使得分析的過程能夠順利的進行。

參考文獻:

[1] 馮志偉.基于短語結構語法的自動句法分析方法[J].當代語言學，2000，2(2):84-98.

[2] 力提甫#8226;托合提.阿爾泰語言的句法結構.北京:中國人民大學出版社.2004.

[3] 吳江寧，朱國華.基于改進線圖分析算法的淺層漢語句法分析器的設計與實現[J].計算機應用研究，2007(9):164-167.

[4] 王賧，李中志.基于期待類型的Chart句法分析算法[J].計算機應用，2009(5):1251-1253.

[5] 俞士汶.計算語言學[M].北京:商務印書館，2003.

[6] 劉群.自然語言理解[M].北京:電子工業出版社，2005.

[7] 劉穎.計算語言學[M].北京:清華大學出版社，2002.

[8] 江銘虎.自然語言處理[M].北京:清華大學出版社，2006.