かまたは,という生成規則によって,
が生成され る
の両方の可能性がある. 言葉で書けば,という生成規則によって,
が生成され る
pを左端, qを右端とする構文木(図で書くと図5.10のようになる. つまり, 斜線で塗ら れた構文木が生成されると, 点線で書かれたような構文木と, 生成規則により 結びついて, さらに大きな木を生成する可能性が生まれる.に対する構文木)で, 根に記号xを持つものが見つかると,
という二つの発展の可能性がある.
- その右にqを左端とする構文木を組み合わせて新しい構文木を作る. その際には,
という規則を用いる.
- その左にpを右端とする構文木を組み合わせてより大きな構文木を作 る. その際には,
という規則を用いる.
図5.11: 構文木の発展. 斜線部の構文木が生成されると, さらに点線部のような大きな構文木が生成される可能性が生まれる.
PAXでは以下のようなデータ構造とプロセスを組み合わせて, この構文木の発 展を実現している.
図で書くと図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であるような構文木を生成する.