「ツリーパターン入門」のツリーを、テキスト記法で表す

「ツリーパターン入門」ではたくさんのツリーの絵を載せました。でも、毎回絵を描くのはめんどくさいので、テキストによる表現も必要ですね。場合によっては、テキスト記法のほうが事情が分かりやすいこともありますし。ツリーの表現にどのような構文を使うかは多分に趣味的・恣意的な決定となりますが、とりあえず次のような構文を使うことにします。

  親ノード{子ノード1, 子ノード2, ...}

子ノード群をカンマ区切りで並べたリストをブレイスで囲むことにします。ノードそのものが構造を持つときは、ノードの表現も複雑になります。しかし今回のツリーでは、ノードにも辺にも、名前／種別／値／属性などが何も付いてません。絵と同じ黒丸「・」でノードを表現しましょう。

例として、次のツリーたちをテキスト表現します（図のすぐ下にテキスト表現）。

1. ・{・, ・, ・}
2. ・
3. ・{・{・}}
4. ・{・{・, ・}, ・}

絵とテキスト表現とで、黒丸の数は同じになります。

εノードはテキストでも同じくεと書くことにします。下の図のεの消去をテキストで書いてみます（図のすぐ下にテキストあります）。

1. ・{・, ε, ・} ⇒ ・{・, ・}
2. ・{・{・{ε, ・, ・}, ε}} ⇒ ・{・{・{・, ・}}}

次は選択肢です。

各選択肢（choice）を縦棒（'|'）を区切りに並べて、全体を丸括弧で囲むことにします。選択肢ノードのサブツリーだけを表すと (・|・{・, ・, ・}) です。上の図の選択肢の展開は、次のようになります。

• ・{(・|・{・, ・, ・})} ⇒ ・{・}, ・{・{・, ・, ・}}

選択肢＋ε の場合は、上記2つの組み合わせとなります。

• ・{(・|ε|・{・, ・, ・})} ⇒ ・{・}, ・, ・{・{・, ・, ・}}

中間で、・{ε} というツリーができますが、これは ・{ε} ⇒ ・ と簡略化されます。

サイクルの扱いは少し工夫が必要です。

サイクルに名前を付けて、さらに切り離した後の状態、次の図の一番右に注目してください。

一番右のツリーを、[A](・{・, A}) と書くことにします。先頭の[A]はIDラベルです。後続するツリーにAという名前を付けることになります。わかりやすいように後続するツリーを丸括弧で囲みましたが、この括弧はなくても大丈夫です； [A]・{・, A} 。

サイクルの展開を表現してみます。

• [A]・{・, A} ⇒ ・{・, [A]・{・, A}}

次のような、等式の代入計算と考えたほうが分かりやすいかもしれません。

• A = {・, A} の右辺内側のAに、右辺全体を代入すると、{・, {・, A}} （A = {・, A}）。

---

では最後に、εノード、選択肢ノード、それに逆行辺を含む次のツリーはどうでしょうか。

逆行する辺が戻って入り込むノードには名前を付ける必要があるので、ルートとその直下は ・{・, [A]…} となります。「…」のところにサブツリーが入ります。そのサブツリーは選択肢ノードからはじまるので、次の形をしています。

• (ε|・{・,・}|A)

名前Aは、逆行する辺の行き先のノード（のラベル）です。これらを組み立てると次のようになります。

• ・{・, [A]・{(ε|・{・,・}|A)}}

A = ・{(ε|・{・,・}|A)}} という等式を使って、サイクルを何度か展開してみます。

1. ・{・, ・{(ε|・{・,・}|A)}} （A = ・{(ε|・{・,・}|A)}}）
2. ・{・, ・{(ε|・{・,・}|・{(ε|・{・,・}|A)}})}} （A = ・{(ε|・{・,・}|A)}}）
3. ・{・, ・{(ε|・{・,・}|・{(ε|・{・,・}|・{(ε|・{・,・}|A)}})}})}} （A = ・{(ε|・{・,・}|A)}}）

入れ子が深くなるとかなり見にくいですね。状況に応じて、図とテキストを使い分けるのが良いようです。