という生成規則によって, 
が生成され
る
に非終端記号xが
生成された(つまり, 解析木の言葉でいえば, 文 
に対す
る, 記号xを根に持つ解析木ができた)場合, ここからさらに, この解析木を
左または右の子に持つ, より大きな解析木が構築可能になる. 具体的には,
かまたは,
の両方の可能性がある. 言葉で書けば,という生成規則によって,
が生成され る
pを左端, qを右端とする構文木(図で書くと図5.10のようになる. つまり, 斜線で塗ら れた構文木が生成されると, 点線で書かれたような構文木と, 生成規則により 結びついて, さらに大きな木を生成する可能性が生まれる.という二つの発展の可能性がある.
- その右にqを左端とする構文木を組み合わせて新しい構文木を作る. その際には,
- その左にpを右端とする構文木を組み合わせてより大きな構文木を作 る. その際には,
図5.11: 構文木の発展. 斜線部の構文木が生成されると,
さらに点線部のような大きな構文木が生成される可能性が生まれる.
PAXでは以下のようなデータ構造とプロセスを組み合わせて, この構文木の発 展を実現している.
: kを右端とする構文木を貯めておく集合である.
CKYアルゴリズムと大雑把な対応をとると, 
で
ある. より正確には, 以下のようになる. 今, あるi, s'に対して, 
であることがわかったとする. この時, 集合 には,
という形をしたルールの識別子(一意に割り当てられ
た番号)全てを挿入する. つまり単に記号そのものを入れるのではなく, 自分
を左の子に持つような構文木を作るに当たって
適用可能なルールを入れておくのである.
また, 構文木の左端の位置を示すために, 
も合わせて挿入する.
集合 はKL1ではもちろん, 不完全データ構造として生成し, mergeによっ
てflatなlistに変形し, それを読むプロセスが, 順番にそれを読み込む.
: kを左端, jを右端とす
る構文木で, 根がs''であるものを表すプロセスである. 集合 から要素
を一つずつ取り出しては, s''が, その要素で指定されているルールの右端
の記号であるかどうかを検査し, そうであれば, それは新たにiを左端, j
を右端とする構文木ができたということなので, 適切な操作( 
への挿入お
よび, プロセス 
の起動)を行なう.
図で書くと図5.11のようになる. 実線で示された構文木
L-- 
を覆い, s'を根とする構文木--Lに対して,
実際に に格納されるのは, 
という形をした要素全てである(つまり, 
という形をし
たルールの数分だけ挿入される). 点線で示された構文木
R-- 
を覆い, s''を根とする構文木--は実際にはデー
タとして存在するのではなく, プロセスであり, から要素を一つずつ取
り出しては, それが, 
という形をした要素であるかどうかを調べ, 一致していれば, より大
きな構文木を生成する.
図5.11: PAXの動作. L は, wi+1 ... w_k を覆い,
s'を根とする構文木で, この時実際には,
Akという集合に, s'¥;c, Ai>という要素が
全て(?-> s'?という形をした規則の数だけ)挿入される.
Rは, wk+1 ... wjを覆い, s''を根とする構文木で,
この時実際にはこれに対応するプロセスが作られる.
そのプロセスは, Akの要素を一つずつ取り出しては,
それが, y ; s'', A>という形であるかどうかを検査し,
そうであれば, wi+1 ... wjを覆い,
根がxであるような構文木を生成する.