redboltzの日記 このページをアンテナに追加 RSSフィード

2011-02-07

[] qiを使って構文ツリーを構築

boost::spirit::qiのサンプルをネット上で探すと、セマンティックアクションを用いて何らかの処理を行うものが多い。そしてその多くが、そこで最終結果を得る形式となっている。

例えば、いつもお世話になっている、稲葉さんのサイトでは、

http://www.kmonos.net/alang/boost/classes/spirit.html

四則演算のサンプルがあり、当然ながら、四則演算の結果を求める形となっている。

今回、そのような最終結果ではなく、構文解析した結果をTree形式で構築したいという状況にぶつかった。

一度Treeを手に入れれば、後でいろんな処理を追加したり、加工(ツリーのノードを削除など)したりすることが容易である。

実は、boostの次のリリースである、1.46では、spiritに関して、

https://sites.google.com/site/boostjp/document/version/1_46_0

抽象構文木を表現することができる、ジェネリックで、階層的で、動的なデータ構造である utree を追加。

との記載があり、これがそのものズバリ、Tree構造を提供してくれるのかも?という話もあるのだが、詳細を確認していないのと、自分の勉強をかねて、オレオレツリーを作ってみた。

基本的には、稲葉さんサイトの四則演算のサンプルを使い、計算結果に加えて、解析した式をTree表示するプログラムを作ってみた。

Treeをテキストで表示するため、括弧を付けた形で数式を表示する。

つまり、

1*2+3*4

と入力すると、計算結果として

14

Tree表示として

((1*2)+(3*4))

と表示される。

#include <boost/config/warning_disable.hpp>

#include <iostream>
#include <string>

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/format.hpp>

class ValueNode;
class BinOpNode;

typedef boost::shared_ptr<ValueNode> ValueNodeSp;
typedef boost::shared_ptr<BinOpNode> BinOpNodeSp;

typedef boost::variant<ValueNodeSp, BinOpNodeSp> Node;

class ValueNode {
public:
    static Node create(int v);
private:
    ValueNode(int v):v_(v) {}
    int v_;
    friend class tostr_visitor;
};

class BinOpNode {
public:
    static Node create(std::string const& op, Node const& lhs, Node const& rhs);
private:
    BinOpNode(std::string const& op, Node const& lhs, Node const& rhs):op_(op), lhs_(lhs), rhs_(rhs) {}
    std::string op_;
    Node lhs_;
    Node rhs_;
    friend class tostr_visitor;
};

Node ValueNode::create(int v) {
    return ValueNodeSp(new ValueNode(v));
}

Node BinOpNode::create(std::string const& op, Node const& lhs, Node const& rhs) {
    return BinOpNodeSp(new BinOpNode(op, lhs, rhs));
}

class tostr_visitor : public boost::static_visitor<std::string>
{
public:
    std::string operator()(ValueNodeSp const& node) const {
        return boost::lexical_cast<std::string>(node->v_);
    }
    std::string operator()(BinOpNodeSp const& node) const {
        return (boost::format("(%1%%2%%3%)") 
            % boost::apply_visitor(*this, node->lhs_)
            % node->op_
            % boost::apply_visitor(*this, node->rhs_)).str();
    }
};

namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;

template<typename Iterator>
struct calc
    : qi::grammar<Iterator, int(), qi::space_type>
{
    qi::rule<Iterator, int(), qi::space_type> expr, term, fctr;
    calc() : calc::base_type(expr) {
        expr = term[qi::_val = qi::_1] >> *( ('+' >> term[qi::_val += qi::_1])
                                           | ('-' >> term[qi::_val -= qi::_1]));
        term = fctr[qi::_val = qi::_1] >> *( ('*' >> fctr[qi::_val *= qi::_1])
                                           | ('/' >> fctr[qi::_val /= qi::_1]));
        fctr = qi::int_ | '(' >> expr >> ')';
    }
};

template<typename Iterator>
struct makeTree
    : qi::grammar<Iterator, Node(), qi::space_type>
{
    qi::rule<Iterator, Node(), qi::space_type> expr, term, fctr;
    makeTree() : makeTree::base_type(expr) {
        expr =           term       [qi::_val = qi::_1] 
            >> *(('+' >> term       [qi::_val = phx::bind(&BinOpNode::create, "+", qi::_val, qi::_1)])
                |('-' >> term       [qi::_val = phx::bind(&BinOpNode::create, "-", qi::_val, qi::_1)]));
        term = fctr                 [qi::_val = qi::_1] 
            >> *(('*' >> fctr       [qi::_val = phx::bind(&BinOpNode::create, "*", qi::_val, qi::_1)])
                |('/' >> fctr       [qi::_val = phx::bind(&BinOpNode::create, "/", qi::_val, qi::_1)]));
        fctr = qi::int_             [qi::_val = phx::bind(&ValueNode::create, qi::_1)]
             | ('(' >> expr >> ')') [qi::_val = qi::_1] ;
    }
};

int main() {
    for(std::string str; getline(std::cin,str) && str.size()>0;)    {
        {
            calc<std::string::iterator> c;
            int result = -1;
            std::string::iterator it = str.begin();
            if (qi::phrase_parse(it, str.end(), c, qi::space, result) )
                std::cout << result << std::endl;
        }
        {
            makeTree<std::string::iterator> mt;
            Node result;
            std::string::iterator it = str.begin();
            if (qi::phrase_parse(it, str.end(), mt, qi::space, result) )
                std::cout << boost::apply_visitor(tostr_visitor(), result) << std::endl;
        }
    }
}

まず、各ノードを表す部品として、数字を表す、ValueNodeと、2項演算子を表す、BinOpNodeを作った。

そして、これら各Nodeの内容を表示させる際は、Visitorパターンを使いたいので、boost::variantを利用した。

また、各ノードは動的にHeapから獲得するため、boost::shared_ptrを利用している。

メインとなる文法を表現するクラスが makeTreeで、ここで構文解析を行っている。

qi::_valに、Nodeを設定しなければならないことから、staticメンバ関数createを用意し、ここで、先ほどのboost::variantである、Nodeを返している。

ここは、もうちょっときれいに書けるのだと思うのだが、今の知識ではこんな感じになってしまった。

Tree構造を構築するために、qi::_valをcreateの引数に渡しているのがポイントだ。

こんな感じで、Treeが構築され、最終的に一番根っこの要素が、resultに帰ってくる。

そしたら、apply_visitorを用いて、resultにtostr_visitorを適用する。

ここで、boost::variantの各型ごとに処理をディスパッチしている。

Treeを再帰的に枝に向かって処理するため、visitorのoperator()の内部でもapply_visitorを呼び出している。

とりあえず、目的は達成できたのだが、私がspiritに不慣れなこともあり、そんな面倒なことしなくても簡単にできるよ!

といった点が多々あるかもしれない。

コメント歓迎です。

2011/02/13 追記 無駄なコピーをしていた箇所をconst& などに修正。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/redboltz/20110207/1297080251