擴充轉移網路文法:ATN理論,BNF描述,相關說明,示例,ATN算法,ATN算法的

擴充轉移網路文法

擴充轉移網路文法，即擴充轉移網路(Augmented Transition Network)，簡稱ATN，是美國哈佛大學人工智慧專家伍茲(W. Woods)於1969年提出的。ATN就是用上下文無關文法的擴充來實現上下文相關文法。ATN是自然語言語法的一種多功能表示及語言自動分析的一種嶄新的方法，ANT對自然語言處理領域產生了重要影響，並曾成功地套用於有限領域的問題應答系統中，如LUNAR程式。

基本介紹

中文名：擴充轉移網路文法
外文名：Augmented Transition Network Grammar
領域：計算機
提出者：伍茲(W. Woods)
提出時間：1969年
套用：LUNAR程式等

ATN理論,BNF描述,相關說明,示例,ATN算法,ATN算法的特點,ATN的優缺點,優點,缺點,

ATN理論

ATN就是用上下文無關文法的擴充來實現上下文相關文法，它用一組暫存器存放語法分析信息，每走一步都要測試一下當前情況，並根據測試結果決定做什麼動作，最後把暫存器中的信息綜合起來，即得到被分析句子的語法結構。

BNF描述

ATN有一種描述語言，該語言不僅刻畫了轉移網路的結構，並且指明了每一步應該做什麼。該語言的BNF描述大致如下：

::= <狀態弧>{<狀態弧>};

<狀態弧> ::= <狀態> <弧>{<弧>}

<弧> ::=CAT<範疇> <分析動作>

|PUSH<狀態> <分析動作>

|TST<標號> <分析動作>

|POP<表達式> <測試>

<分析動作> ::= <測試>{<動作>}<結束動作>

<動作> ::=SETR<暫存器> <表達式>

|SENDR<暫存器> <表達式>

|LIFTR<暫存器> <表達式>

<結束動作> ::=TO<狀態>

|JUMP<狀態>

<表達式> ::=GETR<暫存器> | *

|GETF<特性>

|APPEND<暫存器> <表達式>

|BUILD<片段>{<暫存器>}

示例

假設有下列語法公式(語法規則1)：

圖1 語法公式的擴充轉移網路

<句子> ::= <主語> <動詞> <賓語或空>

<主語> ::= <名詞短語>

<賓語或空> ::= <賓語>| <空>

<賓語> ::= <名詞短語>

<名詞短語> ::= <名詞組>| <名詞>

<名詞組> ::= <冠詞> <可修飾名詞> ;

<可修飾名詞> ::= <名詞>| <形容詞> <名詞>

處理這組語法公式的擴充轉移網路如圖1所示。從圖1中，可以判斷一個句子是否符合上述語法規則。例如,句子：The little boy kicked the ball(句1)，可以順利地通過上面的各條路逕到達終點；句子：The littleboy in the swimsuit kicked the ball(句2)，就沒辦法通過。

ATN算法

可以將上面這種形象的擴充轉移網路圖轉化成相應的處理算法。用圖1的擴充轉移網路處理語句時，按圖2中的指令執行。意義為：若走x則做測試y且執行動作z。其中的測試y是對該弧的額外測試，並非是“該不該走x”的測試。走哪條弧的測試應該是自動進行的。

圖2擴充轉移網路的處理方法

擴充轉移網路(小型ATN)的處理算法如圖2所示。圖2中，主、名、動、形、數、冠都是暫存器名，分別代表主語、名詞、形容詞、數量屬性、冠詞。此外，數[主]和數[*]分別代表存放主語數量屬性和當前被加工部分數量屬性的臨時工作單元。

ATN算法的特點

(1) 通過各種暫存器中記錄的信息，能夠較準確地表達句子的意義。語義網路作為知識表示的工具，是一種對人腦功能的模似。語義內容對語法形式的決定性和語法形式對語義內容表達的強制性,也反映了人的思維過程。

(2) 擴充轉移網路受語法的制約很嚴格，因而不可能接收一些雖不合語法但有實際意義的語句。但是，可以接收語法上正確但沒有意義的句子。

(3) 使用擴充轉移網路來組織詞典就可以構成一個動態詞典。詞法擴充轉移網路的使用使分詞處理和自然語言理解系統的句法處理階段互動成為可能，並且有效地解決了分詞的歧義。

(4) 在分析過程中，擴充轉移網路同時構造出樹形圖來表示這個句子的結構。

(5) 在分析句子時，擴充轉移網路必須嚴格按照算法流程圖由句首開始。

(6) 擴充轉移網路允許擁有許多子網路，當運行到某個子網時，就可以調用另外的子網路，還可以遞歸調用。如果處理結束或處理失敗，可再回到原來的網路繼續進行分析，直到分析完整個句子為止。

ATN的優缺點

優點

(1) ATN的生成能力相當於圖靈機(0型語法)。換言之，ATN具有與轉換生成語法同樣的生成能力，卻又得以維持在上下文無關語法的基本框架之下(無需一個獨立的轉換部分)；

(2) 對自然語言進行分析，從上下文無關語法出發，無論是過渡到轉換生成語法(如MITRE及佩德里克的工作)，還是過渡到上下文有關語法(如凱依的工作)，相應算法所需要的時間會急劇增加。ATN則保證了分析的高效性(計算上可實現)；

(3) ATN既可用於分析，英語如LUNAR系統、漢語如RJD一80人機對話系統；也可用於生成如Simmons和Slocum 1972年設計的自然語言系統，即根據ATN產生句子的表層結構；