この章では埋め込み言語の非決定的なパーザの実装法を示す． まずATNパーザとは何か，またどのように文法規則を表現しているのかを説明する． 次に前章で定義された非決定的オペレータを使うATNコンパイラを示す． 最後に小さなATN文法を取り上げ，サンプル入力をパーズするさまを示す．
ATNとはAugmented Transition Networksの略称で，1970年にBill Woodsにより提唱されたパーザの一形態だ． それ以来，ATNは自然言語のパージングの形式的手法として広く用いられている． ちょっとした英文をパーズするATN文法は1時間もあれば書けるだろう． このため，初めてこれに出会った人はしばしば魔法に包まれたような気分になる．
1970年代には，いつかATNは真に知的なプログラムの一部になるかもしれないと考えた者もいた． この立場を取る者は現在では少ないが，ATNにはニッチ（適した居場所）が見つかった． 人間ほど上手くは英文をパーズできないが，それでも表現力を持ったかなりの文をパーズできる．
以下の制限に注意すればATNは役に立つ．
これらの制限を満たす有用な応用法は数多い． オーソドックスな例はデータベースのフロントエンドだ． データベースにATNを利用したインタフェイスを取り付ければ， ユーザは形式的なクエリを投げなくとも制限付きの英文で質問できる．
ATNを理解するためにはフルネーム Augmented Transition Networks（拡張遷移ネットワーク）を思い出そう． 遷移ネットワークとは矢印で結ばれたノードの集合で，本質的にはフローチャートだ． ノードのうち一つが始発ノードとして，別の幾つかのノードが終着ノードとして定められる． 各矢印に条件が付加され，矢印を辿るにはそれを満たさなければならない． ATNには文が入力されるが，文には現在の単語を指すポインタが付属する． 矢印を辿るとポインタが前進する． 遷移ネットワークにおいて文のパージングとは始発ノードから終着ノードへの経路を探すことだ． ここで経路に沿った条件が全て満たされていなければならない．
ATNはこのモデルにさらに2つの条件を加えたものだ．
終着ノードはレジスタに累積された情報を使ってリスト構造を生成し， 関数が値を返すのと全く同様にそれを返す． 実際，非決定性を用いる点を除けば，ATNは関数的プログラミング言語とそっくりの動作をする．
(defnode s
(cat noun s2
(setr subj *)))
(defnode s2
(cat verb s3
(setr v *)))
(defnode s3
(up `(sentence
(subject ,(getr subj))
(verb ,(getr v)))))
\caption{非常に小規模なATN．}
\label{fig:VerySmallATN}
\reffig{fig:VerySmallATN}で定義されたATNはほぼ一番単純なものだ． これは"Spot runs."という形の名詞--動詞から成る文をパーズする． このATNのネットワーク表現は\reffig{fig:GraphOfSmallATN}に示した．
このATNは(spot runs)という入力に対してどう反応するだろう？\
最初のノードから出る矢印は1つだけだ．
catすなわちカテゴリ(category)矢印で，ノードs2につながる．
これは実質的には
「現在見ている単語が名詞(noun)ならば矢印を辿ってよい．
そしてそのときは現在見ている単語（*で表される）をレジスタsubjに格納せよ」
という意味だ．
よってこのノードを離れる際にはレジスタsubjにspotが格納されている．
現在見ている単語を指すポインタが常に存在する．
それは最初は文の先頭の単語を指している．
カテゴリ矢印を辿るとき，そのポインタは1単語だけ前進する．
よってノードs2に到達したとき，見ている単語は2番目のrunsになる．
2つ目の矢印は最初のものと同様だが，動詞(verb)を求めている．
runsが見つかるとそれをレジスタvに格納し，処理はs3に進む．
最後のノードs3にはポップ矢印すなわち終端矢印しかない．
（ポップ矢印を持つノードは点線で描いた．）
入力を消費するにつれてポップ矢印に到達したので，パーズは成功だ．
ポップ矢印はその中のバッククォート付きの式を返す．
(sentence (subject spot)
(verb runs))
ATNはそれがパーズする言語の文法に対応している． 英文をパーズするための立派な規模のATNは， 文をパーズするための主ネットワークと， 名詞句，前置詞句，修飾句等をパーズするための副ネットワークから成る．
"the key on the table in the hall of the house on the hill"
という風に，名詞句の中に前置詞句が含まれ，その中に名詞句が含まれ... と無限に続いてもよいことを考えれば，再帰構造が必要なのは明らかだ．
先程の小さな例では現れなかったが，ATNでは非決定性を使ってよい． 一つのノードから複数の矢印が出ていてよく，与えられた入力に対してそれらのうち複数を辿ってよい． 例えばちゃんとしたATNは命令的な文と宣言的な文の両方をパーズできるようでなくてはならない． よって始発ノードからは外向きのカテゴリ矢印が2つ， 名詞（文のため）と動詞（命令のため）に対応して伸びているだろう．
文の最初の単語が"time"のように名詞でも動詞でもあり得るものならどうするのか？\ パーザはどちらの矢印を辿ればよいかどのように判断するのだろう？\ 「ATNは非決定性を持つ」と言うとき， それはどの矢印を辿るかパーザが適切に推定してくれると思ってよいということだ． パーズ失敗にしか行き着かない矢印をパーザが辿ることはない．
現実にはパーザは未来を予見することはできない． 矢印や入力が尽きたときにはバックトラックを行うことで，適切な推定をシミュレートする． ATNコンパイラの生成したコードにはバックトラックの仕組みが自動的に挿入される． ATNはどの矢印を辿るかパーザが本当に推定できるかのように書ける．
非決定性を使う多くの（恐らくは大半の）プログラムと同様，ATNは深さ優先の実装を使う．
さて英文をパーズしようとするとすぐ分かることだが，
任意の英文をパーズする方法は数多くあるが，ほとんどは意味をなさない．
伝統的なシングルプロセッサのマシンでは，意味のあるパーズ結果を素早く得たいものだ．
全てのパーズ結果を一度に得るのではなく「一番ありそうなもの」のみを得ることにする．
それについてまともな解釈ができれば，他のパーズ結果を求める手間が省けた訳だ．
解釈ができなければ，failを呼んでさらに別のパーズ結果を得る．
パーズ結果が生成される順番を制御するためには，
プログラマはどうにかしてchooseが選択肢を選ぶ順番を制御する必要がある．
深さ優先の実装が探索の順番を制御する唯一の方法ではない．
ランダム以外のどのような実装でも何らかの順番がもたらされる．
しかしATNは，Prologと同様に，概念的に深さ優先の実装と一体化している．
ATNでは，あるノードから伸びている矢印は定義された順に試される．
この規約によってプログラマは矢印を優先度順に並べることができる．
普通，ATNを基盤としたパーザには3つの部分が要る． ATNそのもの，それを探索するためのインタプリタ， そして，例えば"runs"が動詞であると判断するための辞書だ． 辞書はまた別の話題だ． ここでは初歩的な手製の辞書を使う． またネットワークインタプリタを扱う必要もない． ATNを直接Lispコードに変換するからだ． ここで解説するプログラムは，ATN全体をコードに変換するので，ATNコンパイラと呼ばれる． ノードは関数に，矢印はそのなかのコードブロックに変換される．
第6章では関数を表現の一形態として導入した．
普通，そうするとプログラムは速くなる．
ここで「速くなる」というのは実行時にネットワークを解釈するオーヴァヘッドがなくなるということだ．
欠点は何かがおかしくなったときに調べられる情報が少ないことだ．
特に使っているCommon Lispの実装が関数function-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))
\caption{ノードと矢印のコンパイル．}
\label{fig:CompilationOfNodesAndArcs}
\reffig{fig:CompilationOfNodesAndArcs}にはATNをLispコードに変換するために必要なコードの全てを示した．
マクロdefnodeはノードの定義に使う．
これはそれぞれの矢印に対して生成された式に単にchooseを適用するだけの短いコードを生成する．
ノードに対応する関数の2つの仮引数のうち，
posは現在の入力ポインタ（整数）で，
regsは現在のレジスタの集合（aリストのリスト）だ．
マクロdefnodeは対応するノードと同名のマクロを定義する．
ノードsはマクロsとして定義されるのだ．
この規約のおかげで，矢印の指すノードを参照するときは単にその名前のマクロを呼べばよい．
これはノード名を既存の関数やマクロの名前と被らせてはいけないということでもある．
それらが再定義されてしまうからだ．
ATNのデバッグにはある種のトレース機能が必要だ．
ノードは関数になるので独自のトレース機能を書く必要はなく，
Common Lisp組込みの関数traceを使えばよい．
rjzページで触れたように，=defunを使ってノードを定義すると，
(trace =mods)とすることでパージング処理がノードmodsを通過するのをトレースできる．
ノードの本体内の矢印は単なるマクロ呼び出しで，
defnodeの生成する，ノードに対応する関数に埋め込まれるコードを返す．
パーザは，各ノードにおいて，
伸びる矢印を表現するコードそれぞれに対してchooseを適用することで非決定性を使う．
次のような複数の矢印が外に伸びるノードは，
(defnode foo <矢印1> <矢印2> )
次の形の関数定義に変換される．
(=defun foo (pos regs)
(choose
<矢印1の変換結果>
<矢印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))))))
\caption{ノードに対応する関数の展開形．}
\label{fig:MacroexpansionOfNodeFunc}
\reffig{fig:MacroexpansionOfNodeFunc}には
\reffig{fig:SentenceNetwork}のATNの例の最初のノードのマクロ展開結果を示した．
sのようなノードに対応する関数は，実行時に呼び出されたとき，非決定的に辿る矢印を選ぶ．
仮引数posは入力文での現在の位置になり，regsは現在のレジスタの内容になる．
カテゴリ矢印は，元の例で見たように，入力の中の現在の単語がある文法的カテゴリに属することを表す．
カテゴリ矢印の本体コード内ではシンボル*が入力中の現在の単語に束縛される．
downで定義されるプッシュ矢印では副ネットワークの呼び出しが成功しなければならない．
それが引数に取るのは2つの目的地ノードで，
副ネットワークの終着ノードsubと，現在のネットワークの中で次に進むノードnextだ．
カテゴリ矢印から生成されたコードは単にネットワーク内の次の矢印を呼び出しているだけだが，
プッシュ矢印から生成されたコードは=bindを使っている点に注意．
プッシュ矢印ではそれが指すノードに進む前に副ネットワークの呼び出しが成功しなければならない．
空のレジスタの集合 (nil) は，regsの先頭にコンスされた後，副ネットワークに渡される．
他の種類の矢印の本体内では，シンボル*が入力の現在見ている単語に束縛されるが，
プッシュ矢印では副ネットワークの返した式に束縛される．
ジャンプ矢印は回路の短絡のようなものだ． パーザはそれが指すノードに即座に進む． 条件判断は必要なく，入力ポインタも動かない．
最後にポップ矢印という種類があり，upで定義される．
ポップ矢印は特別で，どのノードをも指さない．
Lispのreturnではサブルーチンでなく呼出側の関数に処理が進むように，
ポップ矢印からは新しいノードでなく「呼出側の」プッシュ矢印に進む．
ポップ矢印内の=valuesは一番近接したプッシュ矢印の=bindに値を「返す」．
しかし第20-2節で説明したように，Lispの関数から普通に戻っているわけではない．
=bindの本体は継続にまとめ上げられ，引数を通じて矢印に順繰りに渡されてゆき，
最後にポップ矢印の=valuesが「返り値」を引数にそれを呼び出す．
第22章では非決定的なchooseの実装を2通り説明した．
探索空間にループがあると終了する保証のない高速版choose（crqページ）と，
遅目だがそのようなループでも安全に機能する本物のchoose（gizページ）だ．
もちろんATNにはループがあり得るが，
各ループ内で最低1単語は入力ポインタが前進する限り，パーザはいつしか文を読み尽くす．
問題なのは入力ポインタを前進させないループだ．
そのとき選択肢は2つある．
choice（gizページで示した深さ優先版）を使う．
chooseを使うが，
ジャンプ矢印のみから成るループを含むネットワークの定義はエラーと定める．
\reffig{fig:CompilationOfNodesAndArcs}で定義したコードでは2番目の方法を取った．
\reffig{fig:CompilationOfNodesAndArcs}の残り4つのマクロ定義は， 矢印本体内でレジスタを読んだり書き換えるためのものだ． このプログラムではレジスタの集合はaリストとして表現されている． ATNはレジスタの集合を扱うのではなくレジスタの集合の集合を扱う． パーザが副ネットワークの処理に移るとき， 空のレジスタの集合が既存のレジスタの集合の集合の上にプッシュされて与えられる． よってレジスタの集合全体は任意の時点においてaリストのリストだ．
レジスタに対する定義済みオペレータは「現在の」すなわち一番上のレジスタの集合に作用する．
getrはレジスタを読み，setrはレジスタを書き換え，
pushrは値をレジスタにプッシュする．
getrとpushrは共にプリミティブなレジスタ操作マクロset-registerを使う．
レジスタは宣言する必要がないことに注意．
set-registerに何らかの名前が与えられると，その名前のレジスタが作られる．
レジスタに対するオペレータはいずれも一切破壊的でない．
cons，cons，cons，とset-registerは繰り返す．
このため処理は遅く，ごみも大量に生まれるが，ugzページで説明したように，
プログラムのうち継続が作られる部分で使われるオブジェクトには破壊的な変更を加えてはならない．
一つの制御スレッド内のオブジェクトは今のところ中断中の別のスレッドと共有されているかもしれない．
この場合，
あるパーズ結果内のレジスタは他の多くのパーズ結果内のレジスタと構造を共有しているだろう．
速度が問題になる場合は，レジスタをaリストでなくヴェクタに格納し，
使用済のヴェクタを共通のプールを使って再利用する手がある．
プッシュ，カテゴリ，ジャンプの各矢印はいずれも式を本体として持つことができる．
普通は単なるsetrだろう．
本体内でcompile-cmdsを呼ぶことで，
それらの種類の矢印の展開形の関数は一連のsetrを単一の式に撚り合わせることができる．
> (compile-cmds '((setr a b) (setr c d))) (SETR A B (SETR C D REGS))
それぞれの式には次の式が最終引数として挿入される．
ただし最後の式にはregsが挿入される．
よって矢印本体内の一連の式は新しいレジスタを返す単一の式に変換される．
この手法によって，任意のLispコードをprognで包むことで矢印の本体に挿入することができる．
例：
> (compile-cmds '((setr a b)
(progn (princ "ek!"))
(setr c d)))
(SETR A B (PROGN (PRINC "ek!") (SETR C D REGS)))
幾つかの変数が矢印本体内のコードで参照できるようになっている．
文全体はグローバルな*sent*に束縛される．
また2つのレキシカル変数が参照できる．
現在の入力ポインタを含むposと現在のレジスタの集合を含むregsだ．
これも意図的な変数捕獲の一例だ．
これらの変数を参照できないようにするのが望ましければgensymで置き換えればよい．
(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))))))
\caption{最上階のマクロ．}
\label{fig:ToplevelMacroATN}
\reffig{fig:ToplevelMacroATN}で定義したマクロwith-parsesによってATNを呼び出せるようになる．
これを呼び出すには始発ノードの名前，パーズする式，
パーズ結果を使って何をするかを記述したコード本体を与える．
with-parses内のコード本体は成功したパージングの結果それぞれにつき1回評価される．
本体内ではシンボルparseが現在のパーズ結果に束縛される．
一見，with-parsesはdolist等のオペレータに似ているが，
内部では単なる反復ではなくバックトラッキング検索を使っている．
with-parsesはいずれは@を返す．
それが選択肢を使い切ったときのfailの返り値だからだ．
表現力のあるATNを見る前に，上で定義したちっぽけなATNの生成したパーズ結果を見てみよう．
\reffig{fig:CompilationOfNodesAndArcs}のATNコンパイラは
typesを呼び出して単語の文法的役割を決定するコードを生成する．
よって最初にその定義が必要だ．
(defun types (w) (cdr (assoc w '((spot noun) (runs verb)))))
それでは始発ノードの名前を第1引数にしてwith-parsesを呼んでみよう．
> (with-parses s '(spot runs)
(format t "Parsing: ~A~%" parse))
Parsing: (SENTENCE (SUBJECT SPOT) (VERB RUNS))
@
ATNコンパイラ全体の説明が終わったので，サンプルのネットワークを使ってパージングを試してみよう． ATNパーザに豊富な種類の文を扱わせるにはATN自身を複雑にすることになる． しかしATNコンパイラはそのままでよい． ここで示されたコンパイラがおもちゃだというのは主に遅いせいであって， 能力が限られている訳ではない．
パーザの機能（速度とはまた別）は文法の作り込みに依るところが多く， この限られた紙幅ではおもちゃ程度のものを作ることしかできない． \reffig{fig:SubnetworkForStringsOfModifiers}から\reffig{fig:SentenceNetwork}では \reffig{fig:GraphOfLargerATN}で表現されたATN（もしくはATNの集合）を定義している． このネットワークは，パーザに食わせる入力としては古典的な"Time flies like an arrow."に対して 複数のパーズ結果を生成できる程度には規模の大きいものだ．
(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))))
\caption{僅かばかりの辞書．}
\label{fig:NominalDictionary}
複雑な入力のパージングにはそれなりに大きい辞書が必要になる．
関数types（\reffig{fig:NominalDictionary}）は最低限の辞書を提供する．
22語から成る語彙が定義され，各単語が1個もしくはそれ以上の単純な文法機能に関連付けられている．
(defnode mods
(cat n mods/n
(setr mods *)))
(defnode mods/n
(cat n mods/n
(pushr mods *))
(up `(n-group ,(getr mods))))
\caption{修飾語の列に対する副ネットワーク．}
\label{fig:SubnetworkForStringsOfModifiers}
ATNの要素はそれ自体がATNだ．
ここで定義するATNの集合の中で一番単純なものは\reffig{fig:NounPhraseSubnetwork}のもので，
修飾語の列をパーズする．
ただしここでは単なる名詞の列とした．
第1のノードmodsは名詞を受け付ける．
第2のノードmods/nは，さらに名詞を探すか，パーズ結果を返すかのどちらかだ．
第3-4節では関数的スタイルでプログラムを書くとどれ程テストし易くなるかを説明した．
これら2つの原則が相俟ってインタラクティブな開発が実現する． Lispで関数的なプログラムを書くとき，各部分を書くにつれてテストできる．
ATNは関数的なプログラムにとても似ており
---この実装ではATNは関数的プログラムにマクロ展開される---
インタラクティブな開発がやはり可能だ．
ATNのテストはどのノードから始めることもできる．
単にノード名をwith-parsesの第1引数にすればよい．
> (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))))
\caption{名詞句に対する副ネットワーク．}
\label{fig:NounPhraseSubnetwork}
(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)))))
\caption{前置詞句に対する副ネットワーク．}
\label{fig:PrepositionalPhraseSubnetwork}
次の2つのネットワークは相互に再帰的なので，一緒に説明しなければならない．
\reffig{fig:NounPhraseSubnetwork}で定義したネットワークはノードnpから始まり，
名詞句のパージングに使われる．
\reffig{fig:PrepositionalPhraseSubnetwork}で定義したネットワークは前置詞句をパーズする．
名詞句は前置詞句を，前置詞句は名詞句を含んでいてよい．
そのため2つのネットワークはそれぞれもう片方を呼ぶプッシュ矢印を含んでいる．
名詞句のネットワークには6個のノードがある．
1番目のノードnpには3つの選択肢がある．
代名詞を読み込んだ場合，処理はノードpronに進んでネットワークからのポップが行われる．
> (with-parses np '(it)
(format t "Parsing: ~A~%" parse))
Parsing: (NP (PRONOUN IT))
@
その他の矢印はどちらもノードnp/detにつながる．
片方の矢印は限定詞（"the"等）を読み込み，もう片方は入力を読まず単にジャンプするだけだ．
ノードnp/detでは両方の矢印がnp/modsにつながっている．
np/detでは副ネットワークmodsにプッシュして修飾語句の列を読み込むか，
ジャンプするかの選択肢がある．
ノードnp-modsは名詞を読み込んでnp/nに進む．
np/nでは結果をポップするか
前置詞句ネットワークにプッシュして前置詞句を読み込むかのいずれかが可能だ．
最後のノードnp/ppは結果をポップする．
名詞句の種類が異なればパージング過程も異なる． 名詞句ネットワークについての2つのパージング結果を示そう．
> (with-parses np '(arrows)
(pprint parse))
(NP (DET NIL)
(MODIFIERS NIL)
(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)))))
@
1番目のパージング結果はnp/detにジャンプし，np/modsに再びジャンプし，
名詞を読み込み，np/nでポップしたところで成功裡に終了した．
2番目は一切ジャンプせず，まず修飾語句の列に対してプッシュし，前置詞句に対して再びプッシュした．
パーザによくあることだが，
構文的に整った式が意味論的には無意味で人間には構文構造の判別すら難しい程だということがある．
ここで名詞句"a time fly like him"は"a Lisp hacker like him"と同じ構造を持っている．
(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)))))
\caption{文に対するネットワーク．}
\label{fig:SentenceNetwork}
> (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))))
(S (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)))))))
@
\caption{1つの文に対する2つのパージング結果．}
\label{fig:TwoParsingsForSentence}
さて，これから必要なのは文構造の認識のためのネットワークだ．
\reffig{fig:SentenceNetwork}に示したネットワークは命令文と叙述文の両方をパーズする．
始発ノードは慣習にしたがってsと名付けた．
そこからつながったノードの1番目は文の主語となる名詞句に対してプッシュする．
sから伸びる2番目の矢印は動詞を読み取る．
文が構文的に曖昧なときはどちらの矢印でも辿り得ることがあり，
\reffig{fig:SentenceNetwork}に示したように，究極的には2つ以上のパージング結果につながる．
1番目のパージング結果は"Island nations like a navy"に似ており
（訳注："Time flies"が主語，"like"が動詞），
2番目は"Find someone like a policeman"に似ている
（訳注："Time"は「時間を計る」という動詞，"like"は前置詞）．
さらに複雑なATNでは"Time flies like an arrow"に対し6つ以上のパージング結果が得られる．
この章のATNコンパイラは商品ソフトウェアというよりATNというアイディアの真髄として提示したものだ． 容易に思い付く変更をいくつか加えるだけであのコードはずっと効率が上がるだろう． 速度が重要なときはそもそもクロージャで非決定性をシミュレートするというアイディアそのものが 遅過ぎるかもしれない． しかし速度が本質的でないとき， ここで説明したプログラミング技法は非常に簡潔なプログラムにつながる．