パーサの話の続き

Erlangでどう書くかはほっておいて、どんなことをやりたいかについて、ちょっと考えてみた。
たとえば Top, Middle, Last という3つのパターンがあったとして、それをStrという文字列(それはリストに他ならないのだが)にマッチさせることを考える。

たとえばLast(Middle(Top(Str)))がtrueを返せば、文字列がマッチしたという使い方

ただ、その場合、それぞれのパターンにStrのどの部分がマッチしたか、という情報が使いづらい。
そして、Middleが .* で、Lastが [a]+ みたいなパターンだった場合、greedyであるか否かによってマッチの対応が違うだろう。
その場合、すべての可能性を網羅した形で結果を得るとしたら、どんなことになるだろうか?

ちょっと思いついたのは、treeの構造だ。

たとえばStrが4文字でできていたとして、可能なマッチのパターンを列挙すると、

[Top, Top, Top, Top]
[Top, Top, Top, Middle]
,,,
[Top, Middle, Middle, Middle]
,,,
[Top, Middle, Last, Last ]
,,
[Last, Last, Last, Last]

といった形になるのだろう。これをまとめると、treeになるのではないか、ということだ。
要するに、適用するパターンの(半?)順序が保存されたリストの集合のうち、さらに各パターンの属性によって枝刈りがされた形のものだ。

となると、マッチングの入力は

  • パターンのリスト
  • 対象となる文字列(リスト)

となっているのが便利そうであり、よって、めでたく(?)

MatchingTree = match([Top,Middle,Last], Str).

という、なじみの形式に収まるような気がする。

(追記:http://www.erlang.org/doc/man/re.html ってのが出てたんですね.mixiErlangコミュを覗いて知りました)

ところで、greedyなマッチとかいう話は、MatchingTreeから、ある規則に従って枝を選ぶ(かなりうろ覚えだが、デザインパターンでいうところの)Visitor(もしくはIterator)の性質に依存することになるだろう。このVisitorは、各パターンの性質(型)を参照することができても良いだろう。
(追記:Visitorパターンについて、Visitorパターンを読んでみた。うーむ)