parser combinator in C++ (parser その3)

買って登録したはいいがほとんど使っていなかったVS.net。
C++使うときもg++使っちゃったりして、もう散々な扱いだったのだが、
g++のエラーメッセージが訳わからんかったので
VC++に頑張ってもらった。

とりあえず今回は息抜き+ネタ企画。(ネタ企画はいつもだけど)
Haskellばかりだと頭が疲れてしまう。
ということで、前回のやつをC++で書いてみることにした。
ネタ企画なので実用性は期待しないように。
書きやすさ、実行効率ともに最悪である。

C++はもちろんクロージャが扱えない。
関数は一階のオブジェクトではないのである。
そこで、パーザはオブジェクトとして表すことにする。
パーザクラスは以下のように定義した。

template 
class parser{
public:
  typedef pair parsed;
  virtual ~parser() {};
  virtual void parse(char *p,list &dest)=0;
};

文字列を受け取り、解析結果のリストを返すと考える。
listというのがいかにも効率が悪そうである。
しかもHaskellとは違いstrictだし。

次に一文字の解析。

class char_parser : public parser{
public:
  char_parser(char c){
    this->c=c;
  }

  void parse(char *p,list &dest){
    dest.clear();
    if (*p==c) dest.push_back(parsed(c,p+1));
  }
  
private:
  char c;
};

こうなる。汎用バージョン。

template 
class satisfy_parser : public parser{
public:
  satisfy_parser(Pred uf){
    this->uf=uf;
  }

  void parse(char *p,list &dest){
    dest.clear();
    char c=*p;
    if (uf(c)) dest.push_back(parsed(*p,p+1));
  }
private:
  Pred uf;
};

成功・失敗も作っておく

// 常に成功
template 
class success : public parser{
public:
  success(T v){
    this->v=v;
  }

  void parse(char *p,list &dest){
    dest.clear();
    dest.push_back(parsed(v,p));
  }
private:
  T v;
};

// 常に失敗
template 
class failure : public parser{
public:
  failure(){}

  void parse(char *p,list &dest){
    dest.clear();
  }
};

いよいよコンビネータである。
パーザから新たなパーザを作り出すパーザである。

// 順次
template 
class seq_parser : public parser<pair<T,U>>{
public:
  seq_parser(parser *t,parser<U> *u){
    this->t=t;
    this->u=u;
  }
  ~seq_parser(){
    delete t;
    delete u;
  }

  void parse(char *p,list &dest){
    dest.clear();
    
    list::parsed> d1;
    t->parse(p,d1);

    for (list::parsed>::iterator it1=d1.begin();
         it1!=d1.end();it1++){
      list d2;
      u->parse(it1->second,d2);
      for (list::iterator it2=d2.begin();
           it2!=d2.end();it2++){
        dest.push_back(parsed(make_pair(it1->first,it2->first),it2->second));
      }
    }
  }
private:
  parser *t;
  parser<U> *u;
};

長い、しかもややこしい。
型をいちいち全部書かなければならないのはこの手のプログラムにとって
相当負担になる…。続いて選択。

// 選択
template 
class sel_parser : public parser{
public:
  sel_parser(parser *p,parser *q){
    this->p=p;
    this->q=q;
  }
  ~sel_parser(){
    delete p;
    delete q;
  }

  void parse(char *s,list &dest){
    p->parse(s,dest);
    list tmp;
    q->parse(s,tmp);
    dest.insert(dest.end(),tmp.begin(),tmp.end());
  }
private:
  parser *p,*q;
};

後必要なのは解析結果の変換コンビネータである。

// 結果変換
template 
class mutate_parser : public parser<U>{
public:
  mutate_parser(parser *p,U (*f)(T&)){
    this->p=p;
    this->f=f;
  }
  ~mutate_parser(){
    delete p;
  }

  void parse(char *s,list &dest){
    list::parsed> tmp;
    p->parse(s,tmp);

    dest.clear();
    for (list::parsed>::iterator it=tmp.begin();
         it!=tmp.end();it++)
      dest.push_back(parsed(f(it->first),it->second));
  }
private:
  parser *p;
  U (*f)(T&);
};

変換関数が関数オブジェクトを許すように作ることが出来なかった。
最初そういうふうに作っていたのだが、
C++は型推論を持っていないのでコンパイルできなかった。
もし出来るという方がおられたら連絡願いたい。
あとはあんまりコードをずらずら並べ立てるのもあれなので、

parser *charp(char c);

template 
parser *satisfy(Pred uf);

template 
parser > *seq(parser *t,parser<U> *u);

template 
parser *sel(parser *p,parser *q);

template
parser<U> *mut(parser *p,U (*f)(T&));

template 
parser > *many(parser *p);

template 
parser > *many1(parser *p);

template 
parser > *list_of(parser *p,parser<U> *s);

template 
parser *chainl(parser *p,parser *s);

ラッパも含めて以上のような関数を作成した。

なんかもう、途中で馬鹿らしくなってきたのだが、
一応四則演算の解析ぐらいは作ってみた。

int toInt(list &l)
{
  int ret=0;
  for (list::iterator it=l.begin();
       it!=l.end();it++)
    ret=ret*10+(*it)-'0';
  return ret;
}

bool is_digit(char c)
{
  return isdigit(c)!=0;
}

int listsum(list &d)
{
  int ret=0;
  for (list::iterator it=d.begin();
       it!=d.end();it++)
    ret+=*it;
  return ret;
}

typedef int (*int_bin_op)(int,int);

int int_plus (int x,int y){ return x+y; }
int int_minus(int x,int y){ return x-y; }
int int_mult (int x,int y){ return x*y; }
int int_div  (int x,int y){ return x/y; }

int_bin_op addop(char &c){ return int_plus; }
int_bin_op subop(char &c){ return int_minus;}
int_bin_op mulop(char &c){ return int_mult; }
int_bin_op divop(char &c){ return int_div;  }

int main()
{
  typedef parser pa;
  pa *natural=mut(many1(satisfy(is_digit)),toInt);

  pa *fact=chainl(
    natural,
    sel(mut(charp('*'),mulop),
        mut(charp('/'),divop)));

  pa *expr=chainl(
    fact,
    sel(mut(charp('+'),addop),
        mut(charp('-'),subop)));

  string s;
  while(cin>>s){
    list dest;
    expr->parse((char*)s.c_str(),dest);

    for (list::iterator it=dest.begin();
         it!=dest.end();it++)
      cout<first<<":"<second<

とりあえず内部関数が使えないので大変なことになってる。
一応正しく動作することは確認したのだが…

http://fxp.hp.infoseek.co.jp/arti/frag/parser.cpp

完全なソースをアップしときます。
C++も最近あんまり使ってないし、もっとちゃんと
実装できるのかもしれないなぁ。