## 第 23 章 使用 ATN 分析句子 這一章將介紹這樣一種技術，它把非確定性分析器(parser) 實現成一種嵌入式的語言。其中，第一部分將會解釋什么是 ATN 分析器，以及它們是如何表示語法規則的。第二部分會給出一個 ATN 編譯器，這個編譯器將會使用在前一章定義的非確定性操作符。最后的幾個小節則會展示一個小型的 ATN 語法，然后看看它在實際中是如何分析一段樣本代碼的。 ### 23.1 背景知識 擴充轉移網絡(ATN)，是 Bill Woods 在 1970 年提出的一種分析器。在那之后，ATN 在自然語言分析領域中作為一種形式化方法，被廣為使用。只消一個小時，你就能寫出一個能分析有意義的英語句子的 ATN 語法。出于這個原因，人們常常在初次見識 ATN 之后，就會為之著迷。 在 1970 年代，一部分研究者認為 ATN 有朝一日有可能會成為真正感覺有智能的程序的一部分。盡管時至今日，還持有這一觀點的人寥寥可數，不過 ATN 的地位是不可磨滅的。它雖然沒有你分析英語句子那么在行，但是它仍然能分析數量可觀的各種句子。 如果你恪守下面的四個限制條件，ATN 就能大顯神通： 1. 僅限用于語義上有限制的領域，比如說作為某個特定的數據庫前端。 2. 不能給它過于困難的輸入。比如說，請不要認為它們能像人一樣能理解非常沒有語法的句子。 3. 它們僅僅適用于英語，或者其他單詞的順序決定其語法結構的語言。比如說，ATN 就很可能無法被用來分析那種有屈折變化的語言，如拉丁語。 > 譯者注：屈折語言(inected language)，是語言學中的概念，指因為單詞的變格造成語句本身結構和意思的變化。漢語和英語主要依靠單詞的順序來確定其語法結構，而屈折語言則主要根據單詞的屈折變化(inection) 來表現句子中的語法關系，比如說拉丁語和德語。雖然英語不是屈折語言，但是它里面還是保留著一些形式的屈折變化。比如我們常見的人稱代詞的"格" 的變化，主格的he 和賓格的him，屬格的his。它們的詞根相同，但是詞尾的變化導致了詞性和意思的變化，但是其在句子中的位置仍是決定其意義的主要因素。 1. 不要認為它們總是能正常工作。如果一個應用程序里，只要求它在 90% 的情況下正常工作就足夠了，那么 ATN 是可以勝任的。倘若要求它不能出絲毫的差錯，那么就不應該考慮用它。 盡管有種種限制，ATN 還是能在很多地方派上用場。最典型的應用案例是用做數據庫的前端。如果你給這種數據庫系統配備一個用ATN 驅動的接口，用戶查詢的時候就不用再構造特定格式的請求，只要用一種形式受限的英語提問就可以了。 ### 23.2 形式化 要理解 ATN 的工作機制，我們首先要回憶一下它的全名： > 擴充轉移網絡(Augmented Transition Network)。 所謂轉移網絡，是指由有向路徑連接起來的一組節點，從根本上可以把它看作一種流程圖。其中一個節點被指定為起始節點，而部分其他節點則被作為終結節點。每條路徑上都帶有測試條件，只有對應的條件被滿足的時候，狀態才能經由這條路徑轉移到新的節點。首先，輸入是一個序列，并有一個指向當前單詞的指針。根據路徑進行狀態轉移會使指針相應地前進。使用轉移網絡分析句子的過程，就是找到從起始節點走到某個終止節點的路徑的過程，在這個過程中，所有的轉移條件都要滿足。 ATN 在這個模型的基礎上另加入了兩個特性： 1. ATN 帶有寄存器。寄存器是有名字的 slot，它可以被用來保存分析過程中所需的有關信息。轉移路徑除了能進行條件判斷之外，還會設置和修改寄存器中的內容。 2. ATN 的結構可以是遞歸的。轉移路徑可以這樣要求： > 如果要通過這條路徑，分析過程必須能通過某個子網絡。 而終結節點則使用寄存器中累積得到信息來建立列表結構并返回它，這種返回結果的方式和函數返回值的方式非常像。實際上，除了它具有的非確定性之外，ATN 的行為方式和函數式編程語言很相似。 [示例代碼 23.1] 中定義的 ATN 幾乎是最簡單的ATN 了。它能分析形如 "Spotruns"("電視廣告插播中") 的名詞--動詞型句子。這種 ATN 的網絡表示如[示例代碼 23.2] 所示。 ~~~ (defnode s (cat noun s2 (setr subj *))) (defnode s2 (cat verb s3 (setr v *))) (defnode s3 (up '(sentence (subject ,(getr subj)) (verb ,(getr v))))) ~~~ [示例代碼 23.1]： 一個微型ATN ~~~ noun verb pop S S2 S3 ~~~ [示例代碼 23.2]： 微型ATN 的圖示  當 ATN 分析輸入序列 (spot runs) 時，它是如何工作的呢？ 第一個節點有一條出路徑(outgoingarc)，或者說一條類型路徑(cat)，這條路徑指向節點s2。這事實上是表示：如果當前單詞是個名詞的話，你就可以通過我；如果你通過我的話，你必須把當前單詞(即*) 保存在subj 寄存器中。因而，當離開這個節點時，subj 的內容就變成了spot。 總是有個指針指向當前的單詞。在開始的時候，它指向句子的第一個單詞。在經過cat 路徑的時候，指針會往前移動一個單詞。因此，在我們到達s2 節點的時候，當前節點會變成第二個單詞，即runs 。第二條路徑線和第一條一樣，不同之處在于它要求的是個動詞。它發現了runs ，并把它保存在寄存器v 里面，然后狀態就走到了s3。 在最后一個節點s3 上，只有一個pop 路徑(或稱為終止路徑)。(有pop 路徑的節點的外圍線是虛線)。由于我們正好在把輸入序列讀完的時候通過了pop 路徑，所以我們進行的句子分析是成功的。Pop 路徑返回的是一個反引用表達式： ~~~ (sentence (subject spot) (verb runs)) ~~~ 一個 ATN 是與它所要分析語言的語法相對應的。一個用來分析英語的 ATN，如果規模適中的話，那么它會有一個用來分析句子的主網絡，以及用來分析名詞短語、介詞短語，以及修飾詞組等語法元素的多個子網絡。讓我們想一想含有介詞短語的名詞短語，其中，介詞短語也是有可能含有名詞短語的，并且這種結構可能會無窮無盡地延續下去。顯而易見，要處理下面這種結構的句子，必須要能支持遞歸： ~~~ "the key on the table in the hall of the house on the hill" ~~~ ### 23.3 非確定性 盡管我們在這個簡單的例子里面沒有看出來，但是 ATN 的確是非確定性的。一個節點可以有多個出路徑，而特定的輸入可以同時滿足一個以上的出路徑的條件。舉個例子，一個像樣的 ATN 應該既能分析祈使句也能分析陳述句。所以第一個節點要有向外的 cat 路徑，與名詞(用于陳述句)和動詞(用于祈使句)。 要是句子開頭的單詞是 "time" 呢？"time" 既是名詞又是動詞。分析器如何知道該選哪條路徑呢？如果 ATN 是以不確定的方式運行的，那就意味著用戶可以認為分析器總是會猜到正確的那條路徑線。如果有路徑線會讓分析過程走進死胡同，那么它們是不會被選中的。 實際上，分析器是無法預見未來的。它只是在無路可走，或者讀完了輸入還沒能結束分析時，通過回溯的方式來表現出老是猜中的表象。不過所有這些回溯的機制是自動嵌入在 ATN 編譯器產生的代碼里面的。所以，在編寫 ATN 時，我們可以認為分析器能夠猜出來應該選擇哪一條路徑通過。 就像許多 (也許是絕大多數) 使用非確定性算法的程序所做的那樣，ATN 一樣，使用的也是深度優先搜索。 如果曾有過分析英語的經驗，就能很快了解到，任何句子都有大把的合法分析結果，但是它們中的絕大多數都是沒有意義的。在傳統的單處理器電腦上，一樣可以迅速得到較好的分析結果。我們不是一下子算出所有的分析結果，而只是得出最有可能的那個。如果分析結果是合理的，那么我們就用不著再去搜索其他的分析方式了；否則我們還可以調用 fail 繼續搜尋更多其它的方式。 為了控制生成分析結果的先后順序，程序員需要借助某種辦法來控 制choose 嘗試各待選項的順序。深度優先實現并不是唯一一種控制搜索順序的辦法。除非選擇是隨機的，否則任意一種實現都會按照其特定的順序進行選擇。不過，ATN 和 Prolog 一樣，深度優先實現是其內化了的實現方式。在 ATN 中，出路徑被選中的順序就是它們當初被定義的順序。使用這樣的設計，程序員就可以根據優先級來排列轉換路徑線的定義了。 ### 23.4 一個ATN 編譯器 一般來說，一個基于 ATN 的分析器由三個部分組成：ATN 本身，用來遍歷這個ATN 的解釋器，還有一個可以用于查詢的詞典。 舉個例子，借助詞典我們就可以知道 "run" 是個動詞。說到詞典，那是另一個話題了，我們在這里會使用一個比較初級的手工編制的詞典。我們也不用在網絡解釋器上費心，因為我們會把 ATN 直接翻譯成 Lisp 代碼。在這里要介紹的程序被稱為 ATN 編譯器的原因是，這個程序能把整個的 ATN 變成對應的代碼。節點會成為函數，而轉換路徑則會變成函數里的代碼塊。 第 6 章介紹了把函數作為表達方式的用法。這種編程習慣常常能讓程序的運行速度更快。在這里，這意味著會免去在運行時解析網絡的開銷。而這樣處理的缺點在于，如果出了問題的話，分析原因的線索就會更少了，特別是如果你用的 Common Lisp 實現沒有提 供function-lambda-expression 的時候。 [示例代碼 23.3] 中包含了所有用來把 ATN 節點轉換為 Lisp 代碼的源程序。其中 defnode 宏被用來定義節點。它本身生成的代碼很有限，就是一個 choose ，用來在每個轉換路徑產生的表達式中進行選擇。節點函數有兩個參數，分別是 pos 和 regs： > pos 的值是當前的輸入指針(一個整數)，而regs 是當前的寄存器組(為一個關聯表的列表)。 宏 defnode 定義了一個宏，這個宏的名字和對應的節點相同。節點s 將會被定義成宏 s 。這種習慣做法讓轉換路徑知道如何引用它們的目標節點 它們只要調用和節點同名的宏就可以了。這同時也意味著，你在給節點取名的時候應該避免和已有的函數或者宏重名，否則這些函數或宏會被重定義。 譯者注：見CLHS 中 FunctionFUNCTION-LAMBDA-EXPRESSION 一節。 ~~~ (defmacro defnode (name &rest arcs) '(=defun ,name (pos regs) (choose ,@arcs))) (defmacro down (sub next &rest cmds) '(=bind (* pos regs) (,sub pos (cons nil regs)) (,next pos ,(compile-cmds cmds)))) (defmacro cat (cat next &rest cmds) '(if (= (length *sent*) pos) (fail) (let ((* (nth pos *sent*))) (if (member ',cat (types *)) (,next (1+ pos) ,(compile-cmds cmds)) (fail))))) (defmacro jump (next &rest cmds) '(,next pos ,(compile-cmds cmds))) (defun compile-cmds (cmds) (if (null cmds) 'regs '(,@(car cmds) ,(compile-cmds (cdr cmds))))) (defmacro up (expr) '(let ((* (nth pos *sent*))) (=values ,expr pos (cdr regs)))) (defmacro getr (key &optional (regs 'regs)) '(let ((result (cdr (assoc ',key (car ,regs))))) (if (cdr result) result (car result)))) (defmacro set-register (key val regs) '(cons (cons (cons ,key ,val) (car ,regs)) (cdr ,regs))) (defmacro setr (key val regs) '(set-register ',key (list ,val) ,regs)) (defmacro pushr (key val regs) '(set-register ',key (cons ,val (cdr (assoc ',key (car ,regs)))) ,regs)) ~~~ [示例代碼 23.3]： 節點和路徑的編譯 調試ATN 時，需要借助某種 trace 工具。由于節點成為了函數，所以就用不著自己實現 trace 了。我們可以利用內建的 Lisp 函數 trace 。如同第 20.2 節提到的，只要用 =defun 定義節點，就意味著我們可以通過告訴 Lisp (trace =mods)來對節點 mods 的分析過程進行 trace。 節點函數體里面的轉移路徑就是宏調用，而宏調用返回的代碼被嵌入在 defnode 生成的節點函數中。因此，每個節點的出路徑都被表示為對應的代碼，分析器每碰到一個節點，都會通過執行 choose 使用非確定性的機制來對這些代碼擇一執行。比如下面這個有幾條出路徑的節點 ~~~ (defnode foo <arc 1> <arc 2>) ~~~ 就會被變換成如下形式的函數定義： ~~~ (=defun foo (pos regs) (choose <translation of arc 1> <translation of arc 2>)) (defnode s (down np s/subj (setr mood 'decl) (setr subj *)) (cat v v (setr mood 'imp) (setr subj '(np (pron you))) (setr aux nil) (setr v *))) ~~~ 被宏展開成： ~~~ (=defun s(pos regs) (choose (=bind (* pos regs) (np pos (cons nil regs)) (s/subj pos (setr mood 'decl (setr subj * regs)))) (if (= (length *sent*) pos) (fail) (let ((* (nth pos *sent*))) (if (member 'v (types *)) (v (1+ pos) (setr mood 'imp (setr subj '(np (pron you)) (setr aux nil (setr v * regs))))) (fail)))))) ~~~ [示例代碼 23.4]： 節點函數的宏展開 [示例代碼 23.4] 顯示了[示例代碼 23.11] 中作為 ATN 例子里第一個節點的宏展開前后的模樣。當節點函數(如s) 在運行時被調用時，會非確定性地選擇一條轉移路徑通過。pos 參數將會是在輸入句子中的當前位置，而regs 則是現有的寄存器數據。 就像在我們最初的那個例子中見到的，cat 路徑要求當前的輸入單詞在語法上屬于某個類型。在cat 路徑的函數體中，符號* 將會被綁定到當前的輸入單詞上。 由down 定義的 push 路徑，則要求對子網絡的調用能成功返回。這些路徑函數接受兩個目標節點作為參數，它們分別是：子網絡目標節點sub ，和當前網絡的下個節點，即next 。注意到，雖然為cat 路徑生成的代碼只是調用了網絡中的下一個節點，但是為push 路徑生成的代碼使用的是=bind 。在繼續轉移到push 路徑指向的節點前，程序必須成功地從子網絡返回。在regs 被傳入子網絡前，一組新的空寄存器(nil) 被cons 到它的前面。在其他類型的轉移路徑的函數體中，符號* 將會被綁定到輸入的當前單詞上，不過在push 路徑中，* 則是被綁定到從子網絡返回的表達式上。 jump 路徑就像發生了短路一樣。分析器直接跳到了目標節點，不需要進行條件測試，同時輸入指針沒有向前移動。 最后一種轉移路徑是pop 路徑，這種轉移路徑由up 定義。pop 路徑是比較不常見的，原因在于它們沒有目標節點。 就像Lisp 的return 類似，return 把程序帶到的不是一個子函數，而是主調函數，而pop 路徑指向的不是一個新節點，而是把程序帶回"調用方" 的push 路徑。pop 路徑的=values "返回" 的是最近的一個push 路徑的=bind 。 但是如第23.2 節所述，這產生的結果和一個普通的Lisp return 還不一樣，=bind 的函數體已經被包在一個續延里了，并且被作為參數順著之后的轉移路徑一直傳下去，直到pop 路徑的=values 把"返回" 值作為參數調用這個續延。 第22 章描述的兩個版本的非確定性choose，分別是：一個快速的choose (第 22.3 節)，雖然它無法保證在搜索空間里有環的情況下能正常終止；以及一個較慢的true-choose (第 22.6 節)，它能在有環的情況下仍然正常工作。當然，在一個ATN 同樣有可能存在環，不過只要在每個環里至少有一個轉移路徑能推進輸入指針，那么分析器遲早都會走到句子末尾。問題是出在那種不會推進輸入指針的那種環上。這里我們有兩個方案： 1. 使用較慢的、真正的非確定性選擇操作符(**附注**給出了其深度優先版本)。 2. 使用快速的 choose ，同時指出：如果定義的網絡含有只需要順著 jump 路徑就能遍歷的環，那么這個定義是錯誤的。 在[示例代碼 23.3] 采用的是第二個方案。 [示例代碼 23.3] 中的最后四個定義定義了用來讀取和設置轉移路徑函數體中寄存器的宏。在這個程序里，寄存器組是用關聯表來表示的。ATN 所使用的并不是寄存器組，而是一系列寄存器組。當分析器進入一個子網絡時，它獲得了一組新的空寄存器，這組寄存器被壓在了已有寄存器組的上面。因此，無論何時，所有寄存器構成的集合都是作為一個關聯表的列表存在的。 這些預先定義好的寄存器操作符的操作對象都是當前，或者說是最上面的那一組寄存器：getr 讀一個寄存器；setr 設置寄存器；而 pushr 把一個值加入寄存器。setr和pushr 都使用了更基本的寄存器操作宏：set-register。注意到，寄存器不需要事先聲明。不管傳給 set-register 的是什么名字，它都會用這個名字新建一個寄存器。 這些寄存器操作符都是完全非破壞性的。"Cons，cons，cons"，set-register 念念有詞。這拖慢了操作符運行的速度，同時也產生了大量無用的垃圾。不過，正如第20.1 節解釋的，如果程序某一部分構造了一個續延，那么就不應該破壞性地修改在這個部分用到的對象。一個正在運行的線程中的對象有可能被另一個正被掛起的線程共享。在本例中，在一個分析過程中發現的寄存器會與許多其他分析過程共享數據結構。如果速度成了問題，我們可以把寄存器保存在vector 里面，而不是關聯表里，并且把用過的vector 回收到一個公用的vector 池中。 push、cat 和jump 路徑都可以包含表達式體。通常情況下，這些表達式只不過會是一些setr 罷了。通過對它們的表達式體調用compile-cmds ，這些幾類轉移路徑的展開函數會把一系列setr 串在一起，成為一個單獨的表達式： ~~~ > (compile-cmds '((setr a b) (setr c d))) (SETR A B (SETR C D REGS)) ~~~ 每個表達式把它后面的那個表達式作為它的最后一個參數安插到自己的參數列表中，不過最后一個表達式除外，它就是regs 。因此轉移路徑的函數體中的一系列表達式就會被轉換成一個單獨的表達式，這個表達式將會返回新的那些寄存器。 這個辦法讓用戶能在轉移路徑的函數體里安插任意的Lisp 代碼，只要把這些Lisp 代碼用一個progn 包起來就可以了。舉例來說： ~~~ > (compile-cmds '((setr a b) (progn (princ "ek!")) (setr c d))) (SETR A B (PROGN (PRINC "ek!") (SETR C D REGS))) ~~~ 我們有意讓轉移路徑的函數體中的代碼能訪問到部分變量。被分析的句子將被放到全局的*sent*?里。還有兩個詞法變量也將是可見的，它們是：pos ，它保存著當前的輸入指針；以及regs ，它被用來存放當前的所有寄存器。這是又一個有意地利用變量捕捉的實例。如果期望讓用戶不能引用這些變量，可以考慮把它們換成生成符號。 譯者注：原文為 getr ，根據上下文應為setr。 宏 with-parses 是在[示例代碼 23.5] 中定義的，它讓我們有個辦法能調用ATN。要調用它，我們應該傳給它起始節點的名字、一個需要分析的表達式，以及一個代碼體。這段代碼告訴with-parses 應該如何處理返回的分析結果。表面上，with-parses 的功能和dolist 這種操作符差不多。實際上，在它內部進行的并不是簡單的疊代操作，而是回溯搜索。每次成功的分析動作都會引起對with-parses 表達式中的代碼體的一次求值。在代碼體中，符號parse 將會綁定到當前的分析結果上。with-parses 表達式會返回@ ，因為這正是fail 在窮途末路時的返回值。 ~~~ (defmacro with-parses (node sent &body body) (with-gensyms (pos regs) '(progn (setq *sent* ,sent) (setq *paths* nil) (=bind (parse ,pos ,regs) (,node 0 '(nil)) (if (= ,pos (length *sent*)) (progn ,@body (fail)) (fail)))))) ~~~ [示例代碼 23.5]： toplevel 宏 在進一步研究表達能力更強的ATN 之前，讓我們先看一下之前定義的一個微型ATN 產生的分析結果。 ATN 編譯器([示例代碼 23.3]) 產生的代碼會調用types ，通過它了解單詞的在語法上所擔當的角色，所以我們需要先給它下個定義： ~~~ (defun types (w) (cdr (assoc w '((spot noun) (runs verb))))) ~~~ 現在我們只要把起始節點作為第一個參數傳給with-parses ，并調用它： ~~~ > (with-parses s '(spot runs) (format t "Parsing: ~A~%" parse)) Parsing: (SENTENCE (SUBJECT SPOT) (VERB RUNS)) @ ~~~ ### 23.5 一個 ATN 的例子 既然我們把ATN 編譯器從頭到尾都說清楚了，接下來可以找個例子小試牛刀了。為了讓 ATN 的分析器能處理的句子的類型更多些，你需要把 ATN 網絡，而不是 ATN 編譯器弄得更復雜一些。這里展示的編譯器之所以還只是個玩具，其原因是因為它的速度比較慢，而不是它在處理能力上的局限性。 分析器的處理能力(與處理速度相區別) 源自于它的語法，由于這里篇幅的限制，所以我們不得不用一個玩具版本來說明問題。從[示例代碼 23.8] 到[示例代碼 23.11] 定義了[示例代碼 23.6] 中所示的ATN(或者說一組ATN)。這個網絡的規模正好足夠大，使得它能在分析那句經典的分析素材"Timeieslikeanarrow" 時，能夠得出多種分析結果。 如果要分析更復雜的輸入的話，我們就需要一個稍大的詞典。函數types ([示例代碼 23.7]) 提供了一個最基本的詞典。它里面定義了一個由22 個詞組成的詞匯庫，同時把每個詞都和一個列表相關聯，列表由一個或多個單詞對應的語法角色構成。 ATN 也是由ATN 本身連接而成的。在本例中，我們的ATN 部件中最小的一個是[示例代碼 23.8] 中的ATN。它分析的是修飾語的字符串，在這里，指的就是名詞的字符串。mods 是第一個節點，它接受一個名詞。第二個節點是mods/n ，它會去尋找更多的名詞或者返回一個分析結果。 第2.4 節介紹了把程序寫成函數式風格能讓程序更易于測試的緣由： 1. 在函數式程序中，可以單獨地測試程序的組成部件。 2. 在Lisp 中，可以在toplevel 的循環里交互地測試函數。 s/subj NP v v NP s v s/obj ~~~ pron pron det MODS noun NP np np/det np/mod np/n np/pp prep NP pp pp/prep pp/np noun mods mods/n noun ~~~ [示例代碼 23.6]： 一個規模更大的ATN ~~~ (defun types (word) (case word ((do does did) '(aux v)) ((time times) '(n v)) ((fly flies) '(n v)) ((like) '(v prep)) ((liked likes) '(v)) ((a an the) '(det)) ((arrow arrows) '(n)) ((i you he she him her it) '(pron)))) ~~~ [示例代碼 23.7]： 象征性的詞典 ~~~ (defnode mods (cat n mods/n (setr mods *))) (defnode mods/n (cat n mods/n (pushr mods *)) (up '(n-group ,(getr mods)))) ~~~ [示例代碼 23.8]： 修飾詞字符串的子網絡 這兩條原因合在一起，成為了我們能進行交互式開發的理由：當我們用Lisp 寫函數式程序的時候，我們就 可以每寫一部分代碼，就測試它們。 ATN 和函數式程序非常相像，從它的實現上看，ATN 宏展開成了函數式的程序。這個相似點使得交互式的開發方式也一樣適用于ATN 的開發。我們可以把任意一個節點作為起點來測試ATN，只要把節點的名字作為with-parses 的第一個參數傳入： ~~~ > (with-parses mods '(time arrow) (format t "Parsing: ~A~%" parse)) Parsing: (N-GROUP (ARROW TIME)) (defnode np (cat det np/det (setr det *)) (jump np/det (setr det nil)) (cat pron pron (setr n *))) (defnode pron (up '(np (pronoun ,(getr n))))) (defnode np/det (down mods np/mods (setr mods *)) (jump np/mods (setr mods nil))) (defnode np/mods (cat n np/n (setr n *))) (defnode np/n (up '(np (det ,(getr det)) (modifiers ,(getr mods)) (noun ,(getr n)))) (down pp np/pp (setr pp *))) (defnode np/pp (up '(np (det ,(getr det)) (modifiers ,(getr mods)) (noun ,(getr n)) ,(getr pp)))) ~~~ [示例代碼 23.9]： 名詞短語子網絡 接下來的兩個網絡需要放在一起討論，因為它們之間是互相遞歸調用的。[示例代碼 23.9] 中定義的網絡被用來分析名詞短語，它從節點np 開始。在[示例代碼 23.10] 中定義的網絡則被用來分析介詞短語。名詞短語有可能含有介詞短語，反之亦然。所以它們兩個各自有一個push 路徑，分別調用另一個網絡。 名詞短語網絡中有六個節點。其中，第一個節點np 有三個選擇。如果它讀到了一個代詞，那么它就可以轉移到節點pron ，這會讓它彈出這個網絡： ~~~ > (with-parses np '(it) (format t "Parsing: ~A~%" parse)) Parsing: (NP (PRONOUN IT)) @ ~~~ 另外兩個轉移路徑都指向了節點np/det ：一條路徑讀入一個限定詞(比如說"the")，而另一條路徑則直接跳轉，不從輸入讀取任何詞。在節點np/det ，兩條出路徑都通向np/mods ；np/det 可以選擇push 到子網絡mods ，以此來找出修飾詞的字串，或者直接jump。節點np/mods 讀入一個名詞，然后轉移到np/n 。這個節點要么彈出結果，要么進入介詞短語網絡，看看能不能碰到個介詞短語。最后的節點，即np/pp ，彈出結果。 分析不同類型的名詞短語所走過分析路徑也各不相同。下面是兩個名詞短語網絡的分析結果： ~~~ > (with-parses np '(arrows) (pprint parse)) (NP (DET NIL) (MODIFIERS NIL) ~~~ 220 第23 章 使用ATN 分析句子 ~~~ (NOUN ARROWS)) ~~~ @ > (with-parses np '(a time fly like him) (pprint parse)) (NP (DET A) (MODIFIERS (N-GROUP TIME)) (NOUN FLY) (PP (PREP LIKE) (OBJ (NP (PRONOUN HIM))))) @ 第一次分析在最后jump 到np/det ，再jump 到np/mods 讀入一個名詞，然后pop 到np/n ，從而成功結束。 第二次的嘗試過程中沒有jump 過，它首先為了匹配一個修飾詞字符串push 進一個子網絡，然后為了介詞短語也進入了一個子網絡。這應該是分析器的通病，我們的分析器也不例外：有些在句法上沒有問題的表述在語義上卻毫無意義，以致于人都沒有辦法看出它們的句法結構。這里，名詞短語"atimeylikehim" 和"aLisphackerlikehim" 的形式就是一樣的。 ~~~ (defnode pp (cat prep pp/prep (setr prep *))) (defnode pp/prep (down np pp/np (setr op *))) (defnode pp/np (up '(pp (prep ,(getr prep)) (obj ,(getr op))))) ~~~ [示例代碼 23.10]： 介詞短語子網絡 萬事俱備，只欠東風。現在我們缺的就是一個能識別整句結構的網絡了。[示例代碼 23.11] 中的網絡同時能分析祈使句和陳述句。按照習慣，起始節點被叫做s。第一個節點首先從一個名詞短語開始。第二條出路徑讀入一個動詞。當句子在句法結構上有歧義時，兩條轉移路徑都可能被滿足，最終得到兩個或更多的分析結果，如[示例代碼 23.12] 所示。第一個分析結果和"Island nations like a navy" 類似，而第二個和"Find someone like a policeman" 是同一種。對于"Timeieslikeanarrow"，更復雜的ATN 能找出六種以上的分析結果。 在這一章給出ATN 編譯器的目的更多的在于展示如何提煉出一個ATN 思路的精髓，而不是實現一個產品級的軟件。如果進行一些很明顯的改進，代碼的效率就能顯著提升。當速度很重要的時候，用閉包來模擬非確定性這個思路從整體上說，也許就太慢了。但是如果速度不是關鍵問題，用本章介紹的這種編程技術可以寫出十分簡潔明了的程序。 ~~~ (defnode s (down np s/subj (setr mood 'decl) (setr subj *)) (cat v v (setr mood 'imp) (setr subj '(np (pron you))) (setr aux nil) (setr v *))) (defnode s/subj (cat v v (setr aux nil) (setr v *))) (defnode v (up '(s (mood ,(getr mood)) (subj ,(getr subj)) (vcl (aux ,(getr aux)) (v ,(getr v))))) (down np s/obj (setr obj *))) (defnode s/obj (up '(s (mood ,(getr mood)) (subj ,(getr subj)) (vcl (aux ,(getr aux)) (v ,(getr v))) (obj ,(getr obj))))) ~~~ [示例代碼 23.11]： 句子網絡 ~~~ > (with-parses s '(time flies like an arrow) (pprint parse)) (S (MOOD DECL) (SUBJ (NP (DET NIL) (MODIFIERS (N-GROUP TIME)) (NOUN FLIES))) (VCL (AUX NIL) (V LIKE)) (OBJ (NP (DET AN) (MODIFIERS NIL) (NOUN ARROW)))) (MOOD IMP) (SUBJ (NP (PRON YOU))) (VCL (AUX NIL) (V TIME)) (OBJ (NP (DET NIL) (MODIFIERS NIL) (NOUN FLIES) (PP (PREP LIKE) (OBJ (NP (DET AN) (MODIFIERS NIL) (NOUN ARROW))))))) ~~~ @ [示例代碼 23.12]： 一個句子的兩種分析方式