第 23 章 使用 ATN 分析句子

第 23 章 使用 ATN 分析句子

這一章將介紹這樣一種技術(shù)，它把非確定性分析器(parser) 實(shí)現(xiàn)成一種嵌入式的語(yǔ)言。其中，第一部分將會(huì)解釋什么是 ATN 分析器，以及它們是如何表示語(yǔ)法規(guī)則的。第二部分會(huì)給出一個(gè) ATN 編譯器，這個(gè)編譯器將會(huì)使用在前一章定義的非確定性操作符。最后的幾個(gè)小節(jié)則會(huì)展示一個(gè)小型的 ATN 語(yǔ)法，然后看看它在實(shí)際中是如何分析一段樣本代碼的。

23.1 背景知識(shí)

擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò)(ATN)，是 Bill Woods 在 1970 年提出的一種分析器。在那之后，ATN 在自然語(yǔ)言分析領(lǐng)域中作為一種形式化方法，被廣為使用。只消一個(gè)小時(shí)，你就能寫出一個(gè)能分析有意義的英語(yǔ)句子的 ATN 語(yǔ)法。出于這個(gè)原因，人們常常在初次見(jiàn)識(shí) ATN 之后，就會(huì)為之著迷。

在 1970 年代，一部分研究者認(rèn)為 ATN 有朝一日有可能會(huì)成為真正感覺(jué)有智能的程序的一部分。盡管時(shí)至今日，還持有這一觀點(diǎn)的人寥寥可數(shù)，不過(guò) ATN 的地位是不可磨滅的。它雖然沒(méi)有你分析英語(yǔ)句子那么在行，但是它仍然能分析數(shù)量可觀的各種句子。

如果你恪守下面的四個(gè)限制條件，ATN 就能大顯神通：

1. 僅限用于語(yǔ)義上有限制的領(lǐng)域，比如說(shuō)作為某個(gè)特定的數(shù)據(jù)庫(kù)前端。

2. 不能給它過(guò)于困難的輸入。比如說(shuō)，請(qǐng)不要認(rèn)為它們能像人一樣能理解非常沒(méi)有語(yǔ)法的句子。

3. 它們僅僅適用于英語(yǔ)，或者其他單詞的順序決定其語(yǔ)法結(jié)構(gòu)的語(yǔ)言。比如說(shuō)，ATN 就很可能無(wú)法被用來(lái)分析那種有屈折變化的語(yǔ)言，如拉丁語(yǔ)。

譯者注：屈折語(yǔ)言(inected language)，是語(yǔ)言學(xué)中的概念，指因?yàn)閱卧~的變格造成語(yǔ)句本身結(jié)構(gòu)和意思的變化。漢語(yǔ)和英語(yǔ)主要依靠單詞的順序來(lái)確定其語(yǔ)法結(jié)構(gòu)，而屈折語(yǔ)言則主要根據(jù)單詞的屈折變化(inection) 來(lái)表現(xiàn)句子中的語(yǔ)法關(guān)系，比如說(shuō)拉丁語(yǔ)和德語(yǔ)。雖然英語(yǔ)不是屈折語(yǔ)言，但是它里面還是保留著一些形式的屈折變化。比如我們常見(jiàn)的人稱代詞的"格" 的變化，主格的he 和賓格的him，屬格的his。它們的詞根相同，但是詞尾的變化導(dǎo)致了詞性和意思的變化，但是其在句子中的位置仍是決定其意義的主要因素。

1. 不要認(rèn)為它們總是能正常工作。如果一個(gè)應(yīng)用程序里，只要求它在 90% 的情況下正常工作就足夠了，那么 ATN 是可以勝任的。倘若要求它不能出絲毫的差錯(cuò)，那么就不應(yīng)該考慮用它。

盡管有種種限制，ATN 還是能在很多地方派上用場(chǎng)。最典型的應(yīng)用案例是用做數(shù)據(jù)庫(kù)的前端。如果你給這種數(shù)據(jù)庫(kù)系統(tǒng)配備一個(gè)用ATN 驅(qū)動(dòng)的接口，用戶查詢的時(shí)候就不用再構(gòu)造特定格式的請(qǐng)求，只要用一種形式受限的英語(yǔ)提問(wèn)就可以了。

23.2 形式化

要理解 ATN 的工作機(jī)制，我們首先要回憶一下它的全名：

擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò)(Augmented Transition Network)。

所謂轉(zhuǎn)移網(wǎng)絡(luò)，是指由有向路徑連接起來(lái)的一組節(jié)點(diǎn)，從根本上可以把它看作一種流程圖。其中一個(gè)節(jié)點(diǎn)被指定為起始節(jié)點(diǎn)，而部分其他節(jié)點(diǎn)則被作為終結(jié)節(jié)點(diǎn)。每條路徑上都帶有測(cè)試條件，只有對(duì)應(yīng)的條件被滿足的時(shí)候，狀態(tài)才能經(jīng)由這條路徑轉(zhuǎn)移到新的節(jié)點(diǎn)。首先，輸入是一個(gè)序列，并有一個(gè)指向當(dāng)前單詞的指針。根據(jù)路徑進(jìn)行狀態(tài)轉(zhuǎn)移會(huì)使指針相應(yīng)地前進(jìn)。使用轉(zhuǎn)移網(wǎng)絡(luò)分析句子的過(guò)程，就是找到從起始節(jié)點(diǎn)走到某個(gè)終止節(jié)點(diǎn)的路徑的過(guò)程，在這個(gè)過(guò)程中，所有的轉(zhuǎn)移條件都要滿足。

ATN 在這個(gè)模型的基礎(chǔ)上另加入了兩個(gè)特性：

1. ATN 帶有寄存器。寄存器是有名字的 slot，它可以被用來(lái)保存分析過(guò)程中所需的有關(guān)信息。轉(zhuǎn)移路徑除了能進(jìn)行條件判斷之外，還會(huì)設(shè)置和修改寄存器中的內(nèi)容。

2. ATN 的結(jié)構(gòu)可以是遞歸的。轉(zhuǎn)移路徑可以這樣要求：

如果要通過(guò)這條路徑，分析過(guò)程必須能通過(guò)某個(gè)子網(wǎng)絡(luò)。

而終結(jié)節(jié)點(diǎn)則使用寄存器中累積得到信息來(lái)建立列表結(jié)構(gòu)并返回它，這種返回結(jié)果的方式和函數(shù)返回值的方式非常像。實(shí)際上，除了它具有的非確定性之外，ATN 的行為方式和函數(shù)式編程語(yǔ)言很相似。

[示例代碼 23.1] 中定義的 ATN 幾乎是最簡(jiǎn)單的ATN 了。它能分析形如 "Spotruns"("電視廣告插播中") 的名詞--動(dòng)詞型句子。這種 ATN 的網(wǎng)絡(luò)表示如[示例代碼 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]： 一個(gè)微型ATN

noun verb pop
S S2 S3

[示例代碼 23.2]： 微型ATN 的圖示

當(dāng) ATN 分析輸入序列 (spot runs) 時(shí)，它是如何工作的呢？

第一個(gè)節(jié)點(diǎn)有一條出路徑(outgoingarc)，或者說(shuō)一條類型路徑(cat)，這條路徑指向節(jié)點(diǎn)s2。這事實(shí)上是表示：如果當(dāng)前單詞是個(gè)名詞的話，你就可以通過(guò)我；如果你通過(guò)我的話，你必須把當(dāng)前單詞(即*) 保存在subj 寄存器中。因而，當(dāng)離開(kāi)這個(gè)節(jié)點(diǎn)時(shí)，subj 的內(nèi)容就變成了spot。

總是有個(gè)指針指向當(dāng)前的單詞。在開(kāi)始的時(shí)候，它指向句子的第一個(gè)單詞。在經(jīng)過(guò)cat 路徑的時(shí)候，指針會(huì)往前移動(dòng)一個(gè)單詞。因此，在我們到達(dá)s2 節(jié)點(diǎn)的時(shí)候，當(dāng)前節(jié)點(diǎn)會(huì)變成第二個(gè)單詞，即runs 。第二條路徑線和第一條一樣，不同之處在于它要求的是個(gè)動(dòng)詞。它發(fā)現(xiàn)了runs ，并把它保存在寄存器v 里面，然后狀態(tài)就走到了s3。

在最后一個(gè)節(jié)點(diǎn)s3 上，只有一個(gè)pop 路徑(或稱為終止路徑)。(有pop 路徑的節(jié)點(diǎn)的外圍線是虛線)。由于我們正好在把輸入序列讀完的時(shí)候通過(guò)了pop 路徑，所以我們進(jìn)行的句子分析是成功的。Pop 路徑返回的是一個(gè)反引用表達(dá)式：

(sentence (subject spot)
  (verb runs))

一個(gè) ATN 是與它所要分析語(yǔ)言的語(yǔ)法相對(duì)應(yīng)的。一個(gè)用來(lái)分析英語(yǔ)的 ATN，如果規(guī)模適中的話，那么它會(huì)有一個(gè)用來(lái)分析句子的主網(wǎng)絡(luò)，以及用來(lái)分析名詞短語(yǔ)、介詞短語(yǔ)，以及修飾詞組等語(yǔ)法元素的多個(gè)子網(wǎng)絡(luò)。讓我們想一想含有介詞短語(yǔ)的名詞短語(yǔ)，其中，介詞短語(yǔ)也是有可能含有名詞短語(yǔ)的，并且這種結(jié)構(gòu)可能會(huì)無(wú)窮無(wú)盡地延續(xù)下去。顯而易見(jiàn)，要處理下面這種結(jié)構(gòu)的句子，必須要能支持遞歸：

"the key on the table in the hall of the house on the hill"

23.3 非確定性

盡管我們?cè)谶@個(gè)簡(jiǎn)單的例子里面沒(méi)有看出來(lái)，但是 ATN 的確是非確定性的。一個(gè)節(jié)點(diǎn)可以有多個(gè)出路徑，而特定的輸入可以同時(shí)滿足一個(gè)以上的出路徑的條件。舉個(gè)例子，一個(gè)像樣的 ATN 應(yīng)該既能分析祈使句也能分析陳述句。所以第一個(gè)節(jié)點(diǎn)要有向外的 cat 路徑，與名詞(用于陳述句)和動(dòng)詞(用于祈使句)。

要是句子開(kāi)頭的單詞是 "time" 呢？"time" 既是名詞又是動(dòng)詞。分析器如何知道該選哪條路徑呢？如果 ATN 是以不確定的方式運(yùn)行的，那就意味著用戶可以認(rèn)為分析器總是會(huì)猜到正確的那條路徑線。如果有路徑線會(huì)讓分析過(guò)程走進(jìn)死胡同，那么它們是不會(huì)被選中的。

實(shí)際上，分析器是無(wú)法預(yù)見(jiàn)未來(lái)的。它只是在無(wú)路可走，或者讀完了輸入還沒(méi)能結(jié)束分析時(shí)，通過(guò)回溯的方式來(lái)表現(xiàn)出老是猜中的表象。不過(guò)所有這些回溯的機(jī)制是自動(dòng)嵌入在 ATN 編譯器產(chǎn)生的代碼里面的。所以，在編寫 ATN 時(shí)，我們可以認(rèn)為分析器能夠猜出來(lái)應(yīng)該選擇哪一條路徑通過(guò)。

就像許多 (也許是絕大多數(shù)) 使用非確定性算法的程序所做的那樣，ATN 一樣，使用的也是深度優(yōu)先搜索。

如果曾有過(guò)分析英語(yǔ)的經(jīng)驗(yàn)，就能很快了解到，任何句子都有大把的合法分析結(jié)果，但是它們中的絕大多數(shù)都是沒(méi)有意義的。在傳統(tǒng)的單處理器電腦上，一樣可以迅速得到較好的分析結(jié)果。我們不是一下子算出所有的分析結(jié)果，而只是得出最有可能的那個(gè)。如果分析結(jié)果是合理的，那么我們就用不著再去搜索其他的分析方式了；否則我們還可以調(diào)用 fail 繼續(xù)搜尋更多其它的方式。

為了控制生成分析結(jié)果的先后順序，程序員需要借助某種辦法來(lái)控 制choose 嘗試各待選項(xiàng)的順序。深度優(yōu)先實(shí)現(xiàn)并不是唯一一種控制搜索順序的辦法。除非選擇是隨機(jī)的，否則任意一種實(shí)現(xiàn)都會(huì)按照其特定的順序進(jìn)行選擇。不過(guò)，ATN 和 Prolog 一樣，深度優(yōu)先實(shí)現(xiàn)是其內(nèi)化了的實(shí)現(xiàn)方式。在 ATN 中，出路徑被選中的順序就是它們當(dāng)初被定義的順序。使用這樣的設(shè)計(jì)，程序員就可以根據(jù)優(yōu)先級(jí)來(lái)排列轉(zhuǎn)換路徑線的定義了。

23.4 一個(gè)ATN 編譯器

一般來(lái)說(shuō)，一個(gè)基于 ATN 的分析器由三個(gè)部分組成：ATN 本身，用來(lái)遍歷這個(gè)ATN 的解釋器，還有一個(gè)可以用于查詢的詞典。

舉個(gè)例子，借助詞典我們就可以知道 "run" 是個(gè)動(dòng)詞。說(shuō)到詞典，那是另一個(gè)話題了，我們?cè)谶@里會(huì)使用一個(gè)比較初級(jí)的手工編制的詞典。我們也不用在網(wǎng)絡(luò)解釋器上費(fèi)心，因?yàn)槲覀儠?huì)把 ATN 直接翻譯成 Lisp 代碼。在這里要介紹的程序被稱為 ATN 編譯器的原因是，這個(gè)程序能把整個(gè)的 ATN 變成對(duì)應(yīng)的代碼。節(jié)點(diǎn)會(huì)成為函數(shù)，而轉(zhuǎn)換路徑則會(huì)變成函數(shù)里的代碼塊。

第 6 章介紹了把函數(shù)作為表達(dá)方式的用法。這種編程習(xí)慣常常能讓程序的運(yùn)行速度更快。在這里，這意味著會(huì)免去在運(yùn)行時(shí)解析網(wǎng)絡(luò)的開(kāi)銷。而這樣處理的缺點(diǎn)在于，如果出了問(wèn)題的話，分析原因的線索就會(huì)更少了，特別是如果你用的 Common Lisp 實(shí)現(xiàn)沒(méi)有提 供function-lambda-expression 的時(shí)候。

[示例代碼 23.3] 中包含了所有用來(lái)把 ATN 節(jié)點(diǎn)轉(zhuǎn)換為 Lisp 代碼的源程序。其中 defnode 宏被用來(lái)定義節(jié)點(diǎn)。它本身生成的代碼很有限，就是一個(gè) choose ，用來(lái)在每個(gè)轉(zhuǎn)換路徑產(chǎn)生的表達(dá)式中進(jìn)行選擇。節(jié)點(diǎn)函數(shù)有兩個(gè)參數(shù)，分別是 pos 和 regs：

pos 的值是當(dāng)前的輸入指針(一個(gè)整數(shù))，而regs 是當(dāng)前的寄存器組(為一個(gè)關(guān)聯(lián)表的列表)。

宏 defnode 定義了一個(gè)宏，這個(gè)宏的名字和對(duì)應(yīng)的節(jié)點(diǎn)相同。節(jié)點(diǎn)s 將會(huì)被定義成宏 s 。這種習(xí)慣做法讓轉(zhuǎn)換路徑知道如何引用它們的目標(biāo)節(jié)點(diǎn) 它們只要調(diào)用和節(jié)點(diǎn)同名的宏就可以了。這同時(shí)也意味著，你在給節(jié)點(diǎn)取名的時(shí)候應(yīng)該避免和已有的函數(shù)或者宏重名，否則這些函數(shù)或宏會(huì)被重定義。 譯者注：見(jiàn)CLHS 中 FunctionFUNCTION-LAMBDA-EXPRESSION 一節(jié)。

(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]： 節(jié)點(diǎn)和路徑的編譯

調(diào)試ATN 時(shí)，需要借助某種 trace 工具。由于節(jié)點(diǎn)成為了函數(shù)，所以就用不著自己實(shí)現(xiàn) trace 了。我們可以利用內(nèi)建的 Lisp 函數(shù) trace 。如同第 20.2 節(jié)提到的，只要用 =defun 定義節(jié)點(diǎn)，就意味著我們可以通過(guò)告訴 Lisp (trace =mods)來(lái)對(duì)節(jié)點(diǎn) mods 的分析過(guò)程進(jìn)行 trace。

節(jié)點(diǎn)函數(shù)體里面的轉(zhuǎn)移路徑就是宏調(diào)用，而宏調(diào)用返回的代碼被嵌入在 defnode 生成的節(jié)點(diǎn)函數(shù)中。因此，每個(gè)節(jié)點(diǎn)的出路徑都被表示為對(duì)應(yīng)的代碼，分析器每碰到一個(gè)節(jié)點(diǎn)，都會(huì)通過(guò)執(zhí)行 choose 使用非確定性的機(jī)制來(lái)對(duì)這些代碼擇一執(zhí)行。比如下面這個(gè)有幾條出路徑的節(jié)點(diǎn)

(defnode foo
  <arc 1>
  <arc 2>)

就會(huì)被變換成如下形式的函數(shù)定義：

(=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 *)))

被宏展開(kāi)成：

(=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]： 節(jié)點(diǎn)函數(shù)的宏展開(kāi)

[示例代碼 23.4] 顯示了[示例代碼 23.11] 中作為 ATN 例子里第一個(gè)節(jié)點(diǎn)的宏展開(kāi)前后的模樣。當(dāng)節(jié)點(diǎn)函數(shù)(如s) 在運(yùn)行時(shí)被調(diào)用時(shí)，會(huì)非確定性地選擇一條轉(zhuǎn)移路徑通過(guò)。pos 參數(shù)將會(huì)是在輸入句子中的當(dāng)前位置，而regs 則是現(xiàn)有的寄存器數(shù)據(jù)。

就像在我們最初的那個(gè)例子中見(jiàn)到的，cat 路徑要求當(dāng)前的輸入單詞在語(yǔ)法上屬于某個(gè)類型。在cat 路徑的函數(shù)體中，符號(hào)* 將會(huì)被綁定到當(dāng)前的輸入單詞上。

由down 定義的 push 路徑，則要求對(duì)子網(wǎng)絡(luò)的調(diào)用能成功返回。這些路徑函數(shù)接受兩個(gè)目標(biāo)節(jié)點(diǎn)作為參數(shù)，它們分別是：子網(wǎng)絡(luò)目標(biāo)節(jié)點(diǎn)sub ，和當(dāng)前網(wǎng)絡(luò)的下個(gè)節(jié)點(diǎn)，即next 。注意到，雖然為cat 路徑生成的代碼只是調(diào)用了網(wǎng)絡(luò)中的下一個(gè)節(jié)點(diǎn)，但是為push 路徑生成的代碼使用的是=bind 。在繼續(xù)轉(zhuǎn)移到push 路徑指向的節(jié)點(diǎn)前，程序必須成功地從子網(wǎng)絡(luò)返回。在regs 被傳入子網(wǎng)絡(luò)前，一組新的空寄存器(nil) 被cons 到它的前面。在其他類型的轉(zhuǎn)移路徑的函數(shù)體中，符號(hào) 將會(huì)被綁定到輸入的當(dāng)前單詞上，不過(guò)在push 路徑中， 則是被綁定到從子網(wǎng)絡(luò)返回的表達(dá)式上。

jump 路徑就像發(fā)生了短路一樣。分析器直接跳到了目標(biāo)節(jié)點(diǎn)，不需要進(jìn)行條件測(cè)試，同時(shí)輸入指針沒(méi)有向前移動(dòng)。

最后一種轉(zhuǎn)移路徑是pop 路徑，這種轉(zhuǎn)移路徑由up 定義。pop 路徑是比較不常見(jiàn)的，原因在于它們沒(méi)有目標(biāo)節(jié)點(diǎn)。

就像Lisp 的return 類似，return 把程序帶到的不是一個(gè)子函數(shù)，而是主調(diào)函數(shù)，而pop 路徑指向的不是一個(gè)新節(jié)點(diǎn)，而是把程序帶回"調(diào)用方" 的push 路徑。pop 路徑的=values "返回" 的是最近的一個(gè)push 路徑的=bind 。

但是如第23.2 節(jié)所述，這產(chǎn)生的結(jié)果和一個(gè)普通的Lisp return 還不一樣，=bind 的函數(shù)體已經(jīng)被包在一個(gè)續(xù)延里了，并且被作為參數(shù)順著之后的轉(zhuǎn)移路徑一直傳下去，直到pop 路徑的=values 把"返回" 值作為參數(shù)調(diào)用這個(gè)續(xù)延。

第22 章描述的兩個(gè)版本的非確定性choose，分別是：一個(gè)快速的choose (第 22.3 節(jié))，雖然它無(wú)法保證在搜索空間里有環(huán)的情況下能正常終止；以及一個(gè)較慢的true-choose (第 22.6 節(jié))，它能在有環(huán)的情況下仍然正常工作。當(dāng)然，在一個(gè)ATN 同樣有可能存在環(huán)，不過(guò)只要在每個(gè)環(huán)里至少有一個(gè)轉(zhuǎn)移路徑能推進(jìn)輸入指針，那么分析器遲早都會(huì)走到句子末尾。問(wèn)題是出在那種不會(huì)推進(jìn)輸入指針的那種環(huán)上。這里我們有兩個(gè)方案：

1. 使用較慢的、真正的非確定性選擇操作符(附注給出了其深度優(yōu)先版本)。

2. 使用快速的 choose ，同時(shí)指出：如果定義的網(wǎng)絡(luò)含有只需要順著 jump 路徑就能遍歷的環(huán)，那么這個(gè)定義是錯(cuò)誤的。

在[示例代碼 23.3] 采用的是第二個(gè)方案。

[示例代碼 23.3] 中的最后四個(gè)定義定義了用來(lái)讀取和設(shè)置轉(zhuǎn)移路徑函數(shù)體中寄存器的宏。在這個(gè)程序里，寄存器組是用關(guān)聯(lián)表來(lái)表示的。ATN 所使用的并不是寄存器組，而是一系列寄存器組。當(dāng)分析器進(jìn)入一個(gè)子網(wǎng)絡(luò)時(shí)，它獲得了一組新的空寄存器，這組寄存器被壓在了已有寄存器組的上面。因此，無(wú)論何時(shí)，所有寄存器構(gòu)成的集合都是作為一個(gè)關(guān)聯(lián)表的列表存在的。

這些預(yù)先定義好的寄存器操作符的操作對(duì)象都是當(dāng)前，或者說(shuō)是最上面的那一組寄存器：getr 讀一個(gè)寄存器；setr 設(shè)置寄存器；而 pushr 把一個(gè)值加入寄存器。setr和pushr 都使用了更基本的寄存器操作宏：set-register。注意到，寄存器不需要事先聲明。不管傳給 set-register 的是什么名字，它都會(huì)用這個(gè)名字新建一個(gè)寄存器。

這些寄存器操作符都是完全非破壞性的。"Cons，cons，cons"，set-register 念念有詞。這拖慢了操作符運(yùn)行的速度，同時(shí)也產(chǎn)生了大量無(wú)用的垃圾。不過(guò)，正如第20.1 節(jié)解釋的，如果程序某一部分構(gòu)造了一個(gè)續(xù)延，那么就不應(yīng)該破壞性地修改在這個(gè)部分用到的對(duì)象。一個(gè)正在運(yùn)行的線程中的對(duì)象有可能被另一個(gè)正被掛起的線程共享。在本例中，在一個(gè)分析過(guò)程中發(fā)現(xiàn)的寄存器會(huì)與許多其他分析過(guò)程共享數(shù)據(jù)結(jié)構(gòu)。如果速度成了問(wèn)題，我們可以把寄存器保存在vector 里面，而不是關(guān)聯(lián)表里，并且把用過(guò)的vector 回收到一個(gè)公用的vector 池中。

push、cat 和jump 路徑都可以包含表達(dá)式體。通常情況下，這些表達(dá)式只不過(guò)會(huì)是一些setr 罷了。通過(guò)對(duì)它們的表達(dá)式體調(diào)用compile-cmds ，這些幾類轉(zhuǎn)移路徑的展開(kāi)函數(shù)會(huì)把一系列setr 串在一起，成為一個(gè)單獨(dú)的表達(dá)式：

> (compile-cmds '((setr a b) (setr c d)))
(SETR A B (SETR C D REGS))

每個(gè)表達(dá)式把它后面的那個(gè)表達(dá)式作為它的最后一個(gè)參數(shù)安插到自己的參數(shù)列表中，不過(guò)最后一個(gè)表達(dá)式除外，它就是regs 。因此轉(zhuǎn)移路徑的函數(shù)體中的一系列表達(dá)式就會(huì)被轉(zhuǎn)換成一個(gè)單獨(dú)的表達(dá)式，這個(gè)表達(dá)式將會(huì)返回新的那些寄存器。

這個(gè)辦法讓用戶能在轉(zhuǎn)移路徑的函數(shù)體里安插任意的Lisp 代碼，只要把這些Lisp 代碼用一個(gè)progn 包起來(lái)就可以了。舉例來(lái)說(shuō)：

> (compile-cmds '((setr a b)
    (progn (princ "ek!"))
    (setr c d)))
(SETR A B (PROGN (PRINC "ek!") (SETR C D REGS)))

我們有意讓轉(zhuǎn)移路徑的函數(shù)體中的代碼能訪問(wèn)到部分變量。被分析的句子將被放到全局的sent?里。還有兩個(gè)詞法變量也將是可見(jiàn)的，它們是：pos ，它保存著當(dāng)前的輸入指針；以及regs ，它被用來(lái)存放當(dāng)前的所有寄存器。這是又一個(gè)有意地利用變量捕捉的實(shí)例。如果期望讓用戶不能引用這些變量，可以考慮把它們換成生成符號(hào)。

譯者注：原文為 getr ，根據(jù)上下文應(yīng)為setr。

宏 with-parses 是在[示例代碼 23.5] 中定義的，它讓我們有個(gè)辦法能調(diào)用ATN。要調(diào)用它，我們應(yīng)該傳給它起始節(jié)點(diǎn)的名字、一個(gè)需要分析的表達(dá)式，以及一個(gè)代碼體。這段代碼告訴with-parses 應(yīng)該如何處理返回的分析結(jié)果。表面上，with-parses 的功能和dolist 這種操作符差不多。實(shí)際上，在它內(nèi)部進(jìn)行的并不是簡(jiǎn)單的疊代操作，而是回溯搜索。每次成功的分析動(dòng)作都會(huì)引起對(duì)with-parses 表達(dá)式中的代碼體的一次求值。在代碼體中，符號(hào)parse 將會(huì)綁定到當(dāng)前的分析結(jié)果上。with-parses 表達(dá)式會(huì)返回@ ，因?yàn)檫@正是fail 在窮途末路時(shí)的返回值。

(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 宏

在進(jìn)一步研究表達(dá)能力更強(qiáng)的ATN 之前，讓我們先看一下之前定義的一個(gè)微型ATN 產(chǎn)生的分析結(jié)果。

ATN 編譯器([示例代碼 23.3]) 產(chǎn)生的代碼會(huì)調(diào)用types ，通過(guò)它了解單詞的在語(yǔ)法上所擔(dān)當(dāng)?shù)慕巧?，所以我們需要先給它下個(gè)定義：

(defun types (w)
  (cdr (assoc w '((spot noun) (runs verb)))))

現(xiàn)在我們只要把起始節(jié)點(diǎn)作為第一個(gè)參數(shù)傳給with-parses ，并調(diào)用它：

> (with-parses s '(spot runs)
  (format t "Parsing: ~A~%" parse))
Parsing: (SENTENCE (SUBJECT SPOT) (VERB RUNS))
@

23.5 一個(gè) ATN 的例子

既然我們把ATN 編譯器從頭到尾都說(shuō)清楚了，接下來(lái)可以找個(gè)例子小試牛刀了。為了讓 ATN 的分析器能處理的句子的類型更多些，你需要把 ATN 網(wǎng)絡(luò)，而不是 ATN 編譯器弄得更復(fù)雜一些。這里展示的編譯器之所以還只是個(gè)玩具，其原因是因?yàn)樗乃俣缺容^慢，而不是它在處理能力上的局限性。

分析器的處理能力(與處理速度相區(qū)別) 源自于它的語(yǔ)法，由于這里篇幅的限制，所以我們不得不用一個(gè)玩具版本來(lái)說(shuō)明問(wèn)題。從[示例代碼 23.8] 到[示例代碼 23.11] 定義了[示例代碼 23.6] 中所示的ATN(或者說(shuō)一組ATN)。這個(gè)網(wǎng)絡(luò)的規(guī)模正好足夠大，使得它能在分析那句經(jīng)典的分析素材"Timeieslikeanarrow" 時(shí)，能夠得出多種分析結(jié)果。

如果要分析更復(fù)雜的輸入的話，我們就需要一個(gè)稍大的詞典。函數(shù)types ([示例代碼 23.7]) 提供了一個(gè)最基本的詞典。它里面定義了一個(gè)由22 個(gè)詞組成的詞匯庫(kù)，同時(shí)把每個(gè)詞都和一個(gè)列表相關(guān)聯(lián)，列表由一個(gè)或多個(gè)單詞對(duì)應(yīng)的語(yǔ)法角色構(gòu)成。

ATN 也是由ATN 本身連接而成的。在本例中，我們的ATN 部件中最小的一個(gè)是[示例代碼 23.8] 中的ATN。它分析的是修飾語(yǔ)的字符串，在這里，指的就是名詞的字符串。mods 是第一個(gè)節(jié)點(diǎn)，它接受一個(gè)名詞。第二個(gè)節(jié)點(diǎn)是mods/n ，它會(huì)去尋找更多的名詞或者返回一個(gè)分析結(jié)果。

第2.4 節(jié)介紹了把程序?qū)懗珊瘮?shù)式風(fēng)格能讓程序更易于測(cè)試的緣由：

1. 在函數(shù)式程序中，可以單獨(dú)地測(cè)試程序的組成部件。

2. 在Lisp 中，可以在toplevel 的循環(huán)里交互地測(cè)試函數(shù)。

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]： 一個(gè)規(guī)模更大的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]： 修飾詞字符串的子網(wǎng)絡(luò)

這兩條原因合在一起，成為了我們能進(jìn)行交互式開(kāi)發(fā)的理由：當(dāng)我們用Lisp 寫函數(shù)式程序的時(shí)候，我們就

可以每寫一部分代碼，就測(cè)試它們。

ATN 和函數(shù)式程序非常相像，從它的實(shí)現(xiàn)上看，ATN 宏展開(kāi)成了函數(shù)式的程序。這個(gè)相似點(diǎn)使得交互式的開(kāi)發(fā)方式也一樣適用于ATN 的開(kāi)發(fā)。我們可以把任意一個(gè)節(jié)點(diǎn)作為起點(diǎn)來(lái)測(cè)試ATN，只要把節(jié)點(diǎn)的名字作為with-parses 的第一個(gè)參數(shù)傳入：

> (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]： 名詞短語(yǔ)子網(wǎng)絡(luò)

接下來(lái)的兩個(gè)網(wǎng)絡(luò)需要放在一起討論，因?yàn)樗鼈冎g是互相遞歸調(diào)用的。[示例代碼 23.9] 中定義的網(wǎng)絡(luò)被用來(lái)分析名詞短語(yǔ)，它從節(jié)點(diǎn)np 開(kāi)始。在[示例代碼 23.10] 中定義的網(wǎng)絡(luò)則被用來(lái)分析介詞短語(yǔ)。名詞短語(yǔ)有可能含有介詞短語(yǔ)，反之亦然。所以它們兩個(gè)各自有一個(gè)push 路徑，分別調(diào)用另一個(gè)網(wǎng)絡(luò)。

名詞短語(yǔ)網(wǎng)絡(luò)中有六個(gè)節(jié)點(diǎn)。其中，第一個(gè)節(jié)點(diǎn)np 有三個(gè)選擇。如果它讀到了一個(gè)代詞，那么它就可以轉(zhuǎn)移到節(jié)點(diǎn)pron ，這會(huì)讓它彈出這個(gè)網(wǎng)絡(luò)：

> (with-parses np '(it)
  (format t "Parsing: ~A~%" parse))
Parsing: (NP (PRONOUN IT))
@

另外兩個(gè)轉(zhuǎn)移路徑都指向了節(jié)點(diǎn)np/det ：一條路徑讀入一個(gè)限定詞(比如說(shuō)"the")，而另一條路徑則直接跳轉(zhuǎn)，不從輸入讀取任何詞。在節(jié)點(diǎn)np/det ，兩條出路徑都通向np/mods ；np/det 可以選擇push 到子網(wǎng)絡(luò)mods ，以此來(lái)找出修飾詞的字串，或者直接jump。節(jié)點(diǎn)np/mods 讀入一個(gè)名詞，然后轉(zhuǎn)移到np/n 。這個(gè)節(jié)點(diǎn)要么彈出結(jié)果，要么進(jìn)入介詞短語(yǔ)網(wǎng)絡(luò)，看看能不能碰到個(gè)介詞短語(yǔ)。最后的節(jié)點(diǎn)，即np/pp ，彈出結(jié)果。

分析不同類型的名詞短語(yǔ)所走過(guò)分析路徑也各不相同。下面是兩個(gè)名詞短語(yǔ)網(wǎng)絡(luò)的分析結(jié)果：

> (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 讀入一個(gè)名詞，然后pop 到np/n ，從而成功結(jié)束。

第二次的嘗試過(guò)程中沒(méi)有jump 過(guò)，它首先為了匹配一個(gè)修飾詞字符串push 進(jìn)一個(gè)子網(wǎng)絡(luò)，然后為了介詞短語(yǔ)也進(jìn)入了一個(gè)子網(wǎng)絡(luò)。這應(yīng)該是分析器的通病，我們的分析器也不例外：有些在句法上沒(méi)有問(wèn)題的表述在語(yǔ)義上卻毫無(wú)意義，以致于人都沒(méi)有辦法看出它們的句法結(jié)構(gòu)。這里，名詞短語(yǔ)"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]： 介詞短語(yǔ)子網(wǎng)絡(luò)

萬(wàn)事俱備，只欠東風(fēng)?，F(xiàn)在我們?nèi)钡木褪且粋€(gè)能識(shí)別整句結(jié)構(gòu)的網(wǎng)絡(luò)了。[示例代碼 23.11] 中的網(wǎng)絡(luò)同時(shí)能分析祈使句和陳述句。按照習(xí)慣，起始節(jié)點(diǎn)被叫做s。第一個(gè)節(jié)點(diǎn)首先從一個(gè)名詞短語(yǔ)開(kāi)始。第二條出路徑讀入一個(gè)動(dòng)詞。當(dāng)句子在句法結(jié)構(gòu)上有歧義時(shí)，兩條轉(zhuǎn)移路徑都可能被滿足，最終得到兩個(gè)或更多的分析結(jié)果，如[示例代碼 23.12] 所示。第一個(gè)分析結(jié)果和"Island nations like a navy" 類似，而第二個(gè)和"Find someone like a policeman" 是同一種。對(duì)于"Timeieslikeanarrow"，更復(fù)雜的ATN 能找出六種以上的分析結(jié)果。

在這一章給出ATN 編譯器的目的更多的在于展示如何提煉出一個(gè)ATN 思路的精髓，而不是實(shí)現(xiàn)一個(gè)產(chǎn)品級(jí)的軟件。如果進(jìn)行一些很明顯的改進(jìn)，代碼的效率就能顯著提升。當(dāng)速度很重要的時(shí)候，用閉包來(lái)模擬非確定性這個(gè)思路從整體上說(shuō)，也許就太慢了。但是如果速度不是關(guān)鍵問(wèn)題，用本章介紹的這種編程技術(shù)可以寫出十分簡(jiǎn)潔明了的程序。

(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]： 句子網(wǎng)絡(luò)

> (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]： 一個(gè)句子的兩種分析方式