パーサの話の続き
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 ってのが出てたんですね.mixiのErlangコミュを覗いて知りました)
ところで、greedyなマッチとかいう話は、MatchingTreeから、ある規則に従って枝を選ぶ(かなりうろ覚えだが、デザインパターンでいうところの)Visitor(もしくはIterator)の性質に依存することになるだろう。このVisitorは、各パターンの性質(型)を参照することができても良いだろう。
(追記:Visitorパターンについて、Visitorパターンを読んでみた。うーむ)