右上➚

プログラミングに関するメモをのこしていきます

C++ の複雑な型を整形するプログラムを作りました

C++

テンプレートをバリバリ使っている C++ プログラムのコンパイルエラーが，死ぬほど辛かったので作りました． 型を綺麗に出力するだけです． C++の型版 jq みたいなやつありそうだけど無いのかな？

agatan/tf

たとえば，

boost::spirit::x3::raw_directive<boost::spirit::x3::lexeme_directive<boost::spirit::x3::sequence<boost::spirit::x3::alternative<boost::spirit::x3::char_class<boost::spirit::char_encoding::standard, boost::spirit::x3::alpha_tag>, boost::spirit::x3::literal_char<boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type> >, boost::spirit::x3::kleene<boost::spirit::x3::alternative<boost::spirit::x3::char_class<boost::spirit::char_encoding::standard, boost::spirit::x3::alnum_tag>, boost::spirit::x3::literal_char<boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type> > > > > >::parse<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::basic_string<char> >, boost::spirit::x3::context<boost::spirit::x3::error_handler_tag, const std::reference_wrapper<boost::spirit::x3::error_handler<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::basic_string<char> > > >, boost::spirit::x3::context<boost::spirit::x3::skipper_tag, const boost::spirit::x3::char_class<boost::spirit::char_encoding::ascii, boost::spirit::x3::space_tag>, boost::spirit::x3::unused_type> >, std::__cxx11::basic_string<char>, char>

こんなエラーがよく有りますよね．

これを tf の標準入力に流しこむと，

boost::spirit::x3::raw_directive<
    boost::spirit::x3::lexeme_directive<
        boost::spirit::x3::sequence<
            boost::spirit::x3::alternative<
                boost::spirit::x3::char_class<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::alpha_tag
                >,
                boost::spirit::x3::literal_char<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::unused_type
                >
            >,
            boost::spirit::x3::kleene<
                boost::spirit::x3::alternative<
                    boost::spirit::x3::char_class<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::alnum_tag
                    >,
                    boost::spirit::x3::literal_char<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::unused_type
                    >
                >
            >
        >
    >
>::parse<
    __gnu_cxx::__normal_iterator<
        constchar*,
        std::__cxx11::basic_string<
            char
        >
    >,
    boost::spirit::x3::context<
        boost::spirit::x3::error_handler_tag,
        conststd::reference_wrapper<
            boost::spirit::x3::error_handler<
                __gnu_cxx::__normal_iterator<
                    constchar*,
                    std::__cxx11::basic_string<
                        char
                    >
                >
            >
        >,
        boost::spirit::x3::context<
            boost::spirit::x3::skipper_tag,
            constboost::spirit::x3::char_class<
                boost::spirit::char_encoding::ascii,
                boost::spirit::x3::space_tag
            >,
            boost::spirit::x3::unused_type
        >
    >,
    std::__cxx11::basic_string<
        char
    >,
    char
>

こうなります．

単純に <, >, , を見てインデントを調整しながら出力しているだけです． 空白はスキップします．

構文解析とかは全くしていないので，コンパイルエラーをそのまま流し込んでも悲惨な事になります． あと今気がついたのですが，const hoge が consthoge になっていますね． 修正しました

boost::spirit::x3::raw_directive<
    boost::spirit::x3::lexeme_directive<
        boost::spirit::x3::sequence<
            boost::spirit::x3::alternative<
                boost::spirit::x3::char_class<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::alpha_tag
                >,
                boost::spirit::x3::literal_char<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::unused_type
                >
            >,
            boost::spirit::x3::kleene<
                boost::spirit::x3::alternative<
                    boost::spirit::x3::char_class<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::alnum_tag
                    >,
                    boost::spirit::x3::literal_char<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::unused_type
                    >
                >
            >
        >
    >
>::parse<
    __gnu_cxx::__normal_iterator<
        const char *,
        std::__cxx11::basic_string<
            char
        >
    >,
    boost::spirit::x3::context<
        boost::spirit::x3::error_handler_tag,
        const std::reference_wrapper<
            boost::spirit::x3::error_handler<
                __gnu_cxx::__normal_iterator<
                    const char *,
                    std::__cxx11::basic_string<
                        char
                    >
                >
            >
        >,
        boost::spirit::x3::context<
            boost::spirit::x3::skipper_tag,
            const boost::spirit::x3::char_class<
                boost::spirit::char_encoding::ascii,
                boost::spirit::x3::space_tag
            >,
            boost::spirit::x3::unused_type
        >
    >,
    std::__cxx11::basic_string<
        char
    >,
    char
>

Type Erasure による Visitor パターンの実装

C++ コンパイラ

プログラミングしていて，木構造をうまく扱いたいという状況は結構良くあると思います．
代数的データ型とパターンマッチを持つ言語であればとても美しく完結に表現できる木構造ですが，オブジェクト指向言語でやろうと思うと結構たいへんです．
典型的には Visitor パターンというやつを用います．デザインパターン - Visitor パターン再考 - Qiitaが非常にわかりやすく，理解の助けになりました．ありがとうございます．

一方，C++ の有名なライブラリ，Boost には Boost.Variant というモジュールがあり，これまたとても美しく Visitor っぽいことが出来ます．

#include <boost/variant.hpp>
#include <string>
#include <iostream>

using sample = boost::variant<int, double, std::string>;

sample s1 = 1;
sample s2 = 2.0;
sample s3 = "sample3";

boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s1); // => 1
boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s2); // => 2.0
boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s3); // => sample3

しかし，Boost.Variant は非常に高機能ですが，テンプレートをガンガン使っていたりするので，コンパイルコストが大きいという問題があります．

そこで，Type Erasure を使って visitor パターンをうまく表せれば，コンパイルコストを下げられるのでは？というお話です．
Type Erasure は「型消去」とかでググると色々解説してくださっている記事などが出てくると思います．（ありがとうございます）

この話，私が考えたわけではなくて，どこかのソースコードで見たようなきがするんですが，当時は Type Erasure とか意味不明だったのでスルーしていました．
今ならなんとなくやりたいことは出来るような気がするので（＆ちょうど必要になったので）記事にしてみていますが，もしオリジナルっぽいものや同じようなことを提案しているソースコード・記事を見かけた方は是非ご連絡いただけると嬉しいです．

1st step

Visitor

今回表現したいデータ構造をまず定めます．簡単のために，足し算・掛け算・整数定数の 3 種類のノードを持つ木構造を考えます．
(1 + 2) * 3 なら， mul( add(1, 2), 3 ) みたいな感じです．

この構造を visit する Visitor クラスから先に考えます．
Visitor クラスは，visit というメンバ関数をもつ型の値を，型を消去して保持させます．

class visitor {
private:
  class visitor_base_holder {
  public:
    virtual void visit(add &) = 0;
    virtual void visit(mul &) = 0;
    virtual void visit(constant &) = 0;

    virtual ~visitor_base_holder() = default;
  };

  template <typename V> class visitor_holder : public visitor_base_holder {
  private:
    V &v;

  public:
    visitor_holder(V &v) : v(v) {}

    void visit(add &a) override { v(a); }
    void visit(mul &a) override { v(a); }
    void visit(constant &a) override { v(a); }

    virtual ~visitor_holder() = default;
  };

  std::unique_ptr<visitor_base_holder> holder;

public:
  template <typename V>
  visitor(V &v)
      : holder(std::make_unique<visitor_holder<V>>(v)) {}

  template <typename Visitable> void visit(Visitable &v) { holder->visit(v); }
};

今回は const 修飾についてすべて無視しています．( const を考慮するならば，各 visit について，visitor の const 性と node の const 性を考える必要があります．つまり 4 種類のメンバ関数を定義しなければなりません．）
visit した対象となるそれぞれのデータについてオーバーロードする形で visit を定義しています．
visitor のコンストラクタに，operator()(add&), operator()(mul&), operator()(constant&) を全て持つオブジェクト（C++14 のジェネリックラムダでもOK）を渡すことで，型消去された visitor が出来上がります．
visitor のコンストラクタにどんな型の値を渡しても，出来上がる visitor にはその型情報は含まれないので，様々な visitor を統一して扱う（ vector に突っ込むとか）事ができるようになります．

Node

次にノードの方について考えます． 通常，Visitor パターンでは， visit される側のクラスに accept を実装します．
visit される側のデータを統一的に扱う（ vector に突っ込むとか）ためには，継承やインターフェースを用いるのが普通です．
C++ では，Visitor 側に使った Type Erasure のテクニックが使えます．
std::vector<node> などのように，統一的にノードを扱いつつも，visit される際には，visit(add&) や visit(mul&) のような適切なオーバーロード関数を呼び出すようにしてやればオッケーです．

class node {
private:
  class node_base_holder {
  public:
    virtual void accept(visitor &v) = 0;

    virtual ~node_base_holder() = default;
  };

  template <typename T> class node_holder : public node_base_holder {
  public:
    node_holder(T const &n) : node(n) {}
    node_holder(T &&n) : node(n) {}

    void accept(visitor &v) override { v.visit(node); }

    ~node_holder() = default;

  private:
    T node;
  };

  std::shared_ptr<node_base_holder> holder;

public:
  template <typename Node>
  node(Node const &n)
      : holder(std::make_shared<node_holder<Node>>(n)) {}

  template <typename Node>
  node(Node &&n)
      : holder(std::make_shared<node_holder<Node>>(n)) {}

  void accept(visitor &v) { holder->accept(v); }

  template <typename Visitor> void accept(Visitor &v) {
    visitor visit(v);
    holder->accept(visit);
  }
};

これ結構わかりにくと思うのですが，自分でもコンパイラに怒られながら書いたのでいまいちよく分かってません．
先ほどの visitor の場合と異なり，node には特別満たすべきインターフェースは有りません．
Type Erasure を使う理由は，適切な visit 関数へのディスパッチのためです．

使う

visitor と node が出来たので，使ってみます．
その前にデータ構造を定義しておきます．

struct constant {
  int value;
};

struct add {
  node lhs;
  node rhs;
};

struct mul {
  node lhs;
  node rhs;
};

add や mul のフィールドに，node が使用されている点が大事です．
add.lhs や mul.rhs には，constant が来るか add が来るか mul が来るか分かりません．
そこで，visit 可能な型なら何でもOKという意味で，node 型の値をフィールドとします．

node n = mul{add{constant{1}, constant{2}}, constant{3}};

これで，(1 + 2) * 3 が表現できています． add や constant から node へと暗黙変換が行われていることに注意してください．

次に visitor を定義します．これは，operator() をオーバーロードした関数オブジェクトです．
式を出力する printer と 式を計算する calculator を定義します．

struct printer {
  void operator()(add &a) {
    std::cout << "(";
    a.lhs.accept(*this);
    std::cout << ")";
    std::cout << "+";
    std::cout << "(";
    a.rhs.accept(*this);
    std::cout << ")";
  }

  void operator()(mul &a) {
    std::cout << "(";
    a.lhs.accept(*this);
    std::cout << ")";
    std::cout << "*";
    std::cout << "(";
    a.rhs.accept(*this);
    std::cout << ")";
  }

  void operator()(constant &c) { std::cout << c.value; }
};

struct calculator {
  int result;
  void operator()(add &a) {
    calculator l, r;
    a.lhs.accept(l);
    a.rhs.accept(r);
    result = l.result + r.result;
  }

  void operator()(mul &m) {
    calculator l, r;
    m.lhs.accept(l);
    m.rhs.accept(r);
    result = l.result * r.result;
  }

  void operator()(constant &c) { result = c.value; }
};

こんな感じです．
visit や accept を void を返す関数として定義したので，calculator は自前のフィールドに結果を保持する必要があります． (あとで改善します)

使い方は

  node n = mul{add{constant{1}, constant{2}}, constant{3}};
  printer p;
  n.accept(p);
  calculator calc;
  n.accept(calc);
  std::cout << std::endl;
  std::cout << calc.result << std::endl;
  return 0;

です．

まとめ

この方法の利点としては，データの定義そのものに Visitor パターンのためのノイズが入らないことが挙げられます．
普通の Visitor パターンでは継承必須ですし．

const つけてないせいで一時オブジェクトが使えないので printer p; という行が必要になってしまっています．これはconstをがんばってつけるだけなのでまぁ問題有りません．
一方，calculator の方はダサいですね．値を返す visitor も定義できるようにしたい．
visitor の定義もツライです．const を考慮した場合，同じような内容のメンバ関数を 4 回ずつ書く必要がある．

このへんの問題点は解決可能な気がするので出来たら後で記事にするつもりです．

難しすぎて普通の visitor パターンで良くね？感出てきた

#include をソートするVimプラグインを作りました

C++ Vim

Haskellでimport文をソートするプラグイン vim-haskell-sort-import を作りました - プログラムモグモグという記事を拝見して，コードを見たらすごくわかりやすくて，これの C/C++ 版がほしいと思い，書いてみました．

vim script はほとんど書いたことがないんですが，やっぱりエディタ拡張用のスクリプトなので，普通の言語と違う部分は多いですね… でもその分エディタという UI が既に用意されている状態なので，なんというか書いていて楽しかったです．さくっと書けますし．（先ほどのコードを参考にしているというのもありますが）

使い方

NeoBundle や vim-plug のようなプラグインマネージャを使うなどして runtime path に突っ込んでください． 提供する機能は SortInclude コマンドのみです．

f:id:agtn:20160124191335g:plain

こんな感じの動作をします．

#include は "" を使う場合と <> を使う場合があり，それぞれファイルパスの探索場所が異なるので，それぞれ別のグループとしてソートするようにしました．

#include <iostream>
#include "a.h"
#include "z.h"

が

#include "a.h"
#include <iostream>
#include "z.h"

にソートされたら気持ち悪いと思うので．

あとは参考にさせていただいたプラグインと同様，空行を挟むなどブロック化されている場合は，ブロック内でソートします．

#include をソートするとか既にありふれてそうですが，はじめての vim プラグインということで． せっかくなのでドキュメントなども vim の help フォーマットにしたがって書いてみました．

コンパイラ内部の AST 表現について

コンパイラ

コンパイラは大体，ソースコードを構文解析し，AST を作り，意味解析，コード生成という流れで実装されると思います．

さて，AST は単純に書くと

type expr =
  | Int of int
  | Add of expr * expr
  | Apply of expr * expr list
  | ...

みたいな感じに書けると思います．

これで確かにソースコードの syntax 上の余計な飾りをとっぱらった木構造になっているので抽象構文木としては十分機能します． 一方，既存のコンパイラを見ると，構文解析の後，型検査などの意味解析時にプログラムの不正を見つけた場合，きちんとソース上の位置を合わせて通知してくれます． このためには，AST に位置情報を含める必要があります．

また，型推論の前後で，木構造としては同じ構造だけれども，型情報の持ち方に違いがあるという状況もあります．

(* 型推論前 *)
type expr =
  | Int of int
  | Add of expr * expr
  | Apply of expr * expr list

(* 型推論後 *)
type texpr =
  | Typed_int of int
  | Typed_add of texpr * texpr
  | Typed_apply of texpr * texpr list

このように AST の表現は，木構造としては同じだが付随する情報だけが異なるという場合があります．

いろいろな言語のコンパイラの AST 表現を調査してみたところ，Elm コンパイラの方式が良かったのでまとめておきたいと思います．

type Expr annotation definition variable tipe =
    A.Annotated annotation (Expr' annotation definition variable tipe)


data Expr' ann def var typ
    = Literal Literal.Literal
    | Var var
    | Range (Expr ann def var typ) (Expr ann def var typ)
    | ExplicitList [Expr ann def var typ]
    | Binop var (Expr ann def var typ) (Expr ann def var typ)
    | Lambda (Pattern.Pattern ann var) (Expr ann def var typ)
    | App (Expr ann def var typ) (Expr ann def var typ)
    | If [(Expr ann def var typ, Expr ann def var typ)] (Expr ann def var typ)
    | Let [def] (Expr ann def var typ)
    | Case (Expr ann def var typ) [(Pattern.Pattern ann var, Expr ann def var typ)]
    | Data String [Expr ann def var typ]
    | Access (Expr ann def var typ) String
    | Update (Expr ann def var typ) [(String, Expr ann def var typ)]
    | Record [(String, Expr ann def var typ)]
    -- for type checking and code gen only
    | Port (PortImpl (Expr ann def var typ) typ)
    | GLShader String String Literal.GLShaderTipe

Elm コンパイラは Haskell で実装されています． Expr が型引数として，annotation などを持っています．(definition, tipe についてはいまいちなんのための抽象化か理解していません...) annotation は，AST に付随する情報です．A.Annotated という型が，核となる情報に，情報を annotate する役割を担います．

data Annotated annotation a
    = A annotation a

そして，AST の核となる構造自体は Expr' が持ちます．

こうすることで，annotation の内容を変えるだけで，木構造を何度も書き直す必要なく，コンパイラの各ステップに適した AST 表現を作る事ができます． ちなみに variable はどうやら変数などの名前を表現する型を表しているようです．(始めは単なる String)

Boost.Spirit.X3 で簡易電卓を実装 1

C++ Boost コンパイラ

agtn.hatenablog.com agtn.hatenablog.com

引き続き，Boost.Spirit.X3 です．
今回は，前回までの知識をつかって，簡易電卓を実装してみます．

仕様

今回定義する電卓は，

  • +
  • -
  • *
  • /

の 4 つの演算と単項の - をサポートします．
また，整数型のみを扱うものとします．
(, ) でくくることで，演算子の結合優先順位を書き換えられ，* と / は + と - より優先されるとします．

要するに整数の四則演算のみをサポートする電卓です．

このような電卓を実装するサンプルは Boost.Spirit.X3 以外のライブラリ/ツールでも大量に出てくると思います．
今回は，構文解析そのものというよりは Boost.Spirit.X3 の使い方についてメモしたいので，構文解析そのものの話はぐぐってみてください．

パーサの骨格

演算子の結合規則をサポートするために，primary(定数と () で囲まれた式), neg_expr(単項 -), mul_expr(*, /), add_expr(+, -), expression というパーサをそれぞれ定義します．
先頭から順に結合強度が強くなっています．(expression が最弱, primary が最強)

primary は () で囲まれた式，つまり "(" > expression > ")" を受け付ける必要があり，また，primary 自体も expression の一部です．
したがって，この規則を定義するためには，再帰的なパーサを記述する必要があります．

X3 で再帰的なパーサを記述する方法は前回の記事にまとめました．

  struct primary;
  struct neg_expr;
  struct mul_expr;
  struct add_expr;
  struct expression;

  x3::rule<primary, int> const primary;
  x3::rule<neg_expr, int> const neg_expr;
  x3::rule<mul_expr, int> const mul_expr;
  x3::rule<add_expr, int> const add_expr;
  x3::rule<expression, int> const expression;

それぞれのパーサは attribute として整数型を持ちます．ここに演算結果が格納されることになります．
struct primary などは，今は前方宣言のみで十分です．on_error などを実装したくなった時に定義します．

primary

まずは primary を定義します.
primary は整数定数か， () で囲まれた expression を受理します．

auto const primary_def =
    x3::int_
  | "(" > expression > ")"
  ;

attribute を考慮しなければこんな感じでしょうか．expression は既に宣言されているので使用可能です．(expression の実装がこの時点で見えていなくても使用できます.)

単純に attribute を結果として返すセマンティックアクションはこの後もよく出てくるので，ヘルパとして定義しておきます．

namespace detail {

  decltype(auto) assign()
  {
    using x3::_attr;
    using x3::_val;
    return [](auto&& ctx) { _val(ctx) = _attr(ctx); };
  }

} // namespace detail

assign は attribute を結果に代入する関数オブジェクトを返します．
関数にする必要が特にありませんが，この後出てくるヘルパと見た目を合わせたいので関数にしました．

これを使うと，

auto primary_def =
    x3::int_[detail::assign()]
  | ("(" > expression > ")")[detail::assign()]
  ;

こんな感じで primary が定義できます．

単項マイナス

次に neg_expr を定義します． セマンティックアクションを考えなければ，

auto const neg_expr_def =
    primary
  | "-" > primary
  ;

となります．
"-" > primary のセマンティックアクションとしては，attribute を符号反転して結果に格納するというアクションが求められます．
ここはちょっと汎用的に，attribute に関数オブジェクトを適用して結果に格納するアクションを返すような関数を定義して解決してみます．

namespace detail {
  template <typename F>
  decltype(auto) assign_f(F&& func)
  {
    return [func](auto&& ctx) { _val(ctx) = func(_attr(ctx)); };
  }
} // namespace detail

assign_f は assign と異なり，関数オブジェクトを１つ引数に取ります．
そして，その関数オブジェクトを _attr(ctx) に適用し結果に格納します．

これを使って，neg_expr は

auto const neg_expr_def =
    primary[detail::assign()]
  | ("-" > primary)[detail::assign(std::negate<int>{})]
  ;

となります．std::negate は <functional> で定義された型で，ここでは int 型の値を符号反転する関数オブジェクトとして使用しています．

乗除

次に結合強度が強いのは * と / です．
ちょっとわかりにくいですが，セマンティックアクションを無視すれば，mul_expr は

auto const mul_expr_def =
    neg_expr
    >> *(
        ("*" >> neg_expr)
      | ("/" >> neg_expr)
    )
  ;

と定義できます．mul_expr は 1 や (1 + 2), -1 の後に，* 1 とか / -3 とか * (1 - 2) とかが 0 回以上現れるような式です．
1 * -2 はちょっと気持ち悪い気もしますが… 今気がついたので許してください．

セマンティックアクションとしては，("*" >> neg_expr) が現れる度に，_val(ctx) を _val(ctx) * _attr(ctx) に更新すれば良いです．
始めの neg_expr の結果を _val(ctx) に格納すれば，_val(ctx) は常に現在の計算結果を表すことになります．("*" >> neg_expr) は現在の計算結果に，今処理した式(* の後に続く式のこと) を処理した結果をかければ良いということです．

というわけで分かりにくいとは思いますが，ほしいアクションは，

[](auto&& ctx) { _val(ctx) = _val(ctx) * _attr(ctx); }

です．

さて，では / の場合を考えます．
/ の場合であってもほとんどは * と同じであることがわかります．
ほしいアクションは

[](auto&& ctx) { _val(ctx) = _val(ctx) / _attr(ctx); }

であり，* と / の違いしか有りません．

そこでこれも関数にまとめてしまいます．

namespace detail {

  template <typename Op>
  decltype(auto) calc_op(Op&& op)
  {
    return [op](auto&& ctx) { _val(ctx) = op(_val(ctx), _attr(ctx)); };
  }

} // namespace detail

こんな関数を定義して，

auto const mul_expr_def =
    neg_expr[detail::assign()]
    >> *(
        ("*" >> neg_expr)[detail::calc_op(std::multiplies<int>{})]
      | ("/" >> neg_expr)[detail::calc_op(std::divides<int>{})]
    )
  ;

と使います．
calc_op は関数オブジェクトを引数に取り，_val(ctx) と _attr(ctx) に適用した結果を格納するアクションを返します．

add_expr は mul_expr とほぼおなじなので詳細はスキップします．

expression

最後に expression です．これは単純に add_expr と一致します．
命名のわかりやすさと，今後拡張していく際に便利そうということで分けてあるだけです．

auto const expression_def =
    add_expr[detail::assign()]
  ;

確認

コード全体を掲載します．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>
#include <functional>

namespace x3 = boost::spirit::x3;

namespace grammar {

  namespace detail {

    decltype(auto) assign()
    {
      using x3::_attr;
      using x3::_val;
      return [](auto&& ctx) { _val(ctx) = _attr(ctx); };
    }

    template <typename F>
    decltype(auto) assign_f(F&& func)
    {
      return [func](auto&& ctx) { _val(ctx) = func(_attr(ctx)); };
    }

    template <typename Op>
    decltype(auto) calc_op(Op&& op)
    {
      return [op](auto&& ctx) { x3::_val(ctx) = op(x3::_val(ctx), x3::_attr(ctx)); };
    }

  } // namespace detail

  struct primary;
  struct neg_expr;
  struct mul_expr;
  struct add_expr;
  struct expression;

  x3::rule<primary, int> const primary;
  x3::rule<neg_expr, int> const neg_expr;
  x3::rule<mul_expr, int> const mul_expr;
  x3::rule<add_expr, int> const add_expr;
  x3::rule<expression, int> const expression;

  auto const primary_def =
      x3::int_[detail::assign()]
    | ("(" > expression > ")")[detail::assign()]
    ;

  auto const neg_expr_def =
      primary[detail::assign()]
    | ("-" > primary)[detail::assign_f(std::negate<int>{})]
    ;

  auto const mul_expr_def =
      neg_expr[detail::assign()]
      >> *(
          ("*" >> neg_expr)[detail::calc_op(std::multiplies<int>{})]
        | ("/" >> neg_expr)[detail::calc_op(std::divides<int>{})]
      )
    ;

  auto const add_expr_def =
      mul_expr[detail::assign()]
      >> *(
          ("+" > mul_expr)[detail::calc_op(std::plus<int>{})]
        | ("-" > mul_expr)[detail::calc_op(std::minus<int>{})]
      )
    ;

  auto const expression_def =
      add_expr[detail::assign()]
    ;

  BOOST_SPIRIT_DEFINE(
      primary,
      neg_expr,
      mul_expr,
      add_expr,
      expression
      );

} // namespace grammar
using grammar::expression;

int main()
{
  std::string str;
  std::getline(std::cin, str);

  auto first(std::cbegin(str));
  auto const last(std::cend(str));

  int result;
  bool success = x3::phrase_parse(first, last, expression, x3::ascii::space, result);

  if (!success || first != last) {
    std::cerr << "Parse failed." << std::endl;
    return 1;
  }

  std::cout << "Parsed: " << result << std::endl;
  return 0;
}

実行してみます．

$ clang++ -std=c++14 main.cpp
$ ./a.out
1 + 2 * 3
Parsed: 7
$ ./a.out
(1 + 2) * 3
Parsed: 9

演算子の優先順位が正しく解決できていることが確認出来ます．

まとめ

今回は，セマンティックアクションで計算自体を行ってしまいましたが，普通は抽象構文木(AST) に変換するためにセマンティックアクションを使うのが正道だと思います．
X3 は AST のための色々を提供してくれていますが，自前で作った AST でもちょっと苦労はするかもしれませんが変換できるはずなので，時間があれば，自前 AST に変換してから実行する電卓も作ってみたいと思います．

また，AST に変換して計算する場合，AST に位置情報を付与することで，エラーレポートが便利になったりするはずです( 0 除算のエラーを通知する際，どの部分でのエラーなのかを吐いてくれればうれしいですよね).
パース失敗時にもどこで失敗したのかをレポートしてくれたほうが便利です．
X3 で on_error, on_success を使ってこれらを実装してみようと考えています．

今回のコードでは decltype(auto) など，C++14 の機能を使っています．X3 は C++14 前提のライブラリなので，迷いなくこういった機能を使用できて幸せデスね．

Boost.Spirit.X3 の練習 2

C++ コンパイラ Boost

Boost.Spirit.X3 の練習1 - プログラミングのメモ帳➚に引き続き，Boost.Spirit.X3 のお勉強メモです．

セマンティックアクション

構文解析にはセマンティックアクションというのがつきものです．
yacc や parsec など有名な構文解析のためのツール/ライブラリにもありますね．

セマンティックアクションとは，定義したパーサのルールにマッチした時に実行するプログラムのことです．
といってもわかりにくいと思うので，コードを出してしまいます．

以下のコードは，浮動小数点数にマッチしてその値を標準出力に出力するパーサの定義です．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

auto const print_action =
  [](auto& ctx) { std::cout << _attr(ctx) << std::endl; };

int main()
{

  std::string src{ "( 123.4 )" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);

  auto parser = ("(" >> x3::double_ >> ")")[print_action];

  bool success = x3::phrase_parse(first, last, parser, x3::ascii::space);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  }
}

$ clang++ -std=c++14 main.cpp
$ ./a.out
123.4

パーサの結果を受け取らないようにしています．parser は double を返しますが，その結果は無視しています．
そして，セマンティックアクション部分で，出力を行っています．

auto const print_action の定義が，セマンティックアクションです．
C++14 のジェネリックラムダの機能をつかっています．
セマンティックアクションは，X3 パーサのコンテキストを第一引数に取ります．
その具体的な型を気にしてはいけません．ジェネリックラムダで受け取ります．
_attr(ctx) で，現在マッチしているパーサの attribute にアクセス出来ます． "(" >> x3::double_ >> ")" の attribute は double 型なので，_attr(ctx) はマッチした浮動小数点数になります．

Qi のセマンティックアクションは，関数オブジェクトなどを単純に使用することが出来ませんでした(?) が，X3 ではセマンティックアクションはただの関数オブジェクトです．
パーサのコンテキストを引数に受け，結果や attribute への参照をそのまま関数内で扱えるようになったため，セマンティックアクションの記述がより 普通 の関数っぽくかけるようになったと感じました．

名前付きパーサの定義

今までのサンプルでは，シンプルなパーサを１つ定義しているだけでした．
一方現実には，パーサが再帰的になることは珍しくありません．

そこで，パーサの名前を前方宣言し，あとから定義を記述するようなパーサの書き方を使用します．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

namespace detail {

  x3::rule<class constant, int> const constant;

  auto const constant_def = x3::int_;

  BOOST_SPIRIT_DEFINE(constant);

} // namespace detail

using detail::constant;

int main()
{

  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);


  int result;
  bool success = x3::phrase_parse(first, last, constant, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

namespace detail の中身がパーサの定義になっています． (namespace を分けたのは，constant そのものの名前以外を隠すためです．) X3 では，x3::rule<class, result type> というテンプレートクラスがパーサルールになります．class 部分は今は前方宣言だけで構わないようです．(後で on_error とかの属性を付与する際に必要になる？)
result type はそのパーサが返すべき値になります．

つまり，x3::rule<class constant, int> const constant; は，int 型の値を返す，特別な属性を持たない constant という名前のパーサを宣言したことになります．

そして，その実装は constant_def という名前で与えられます．
hogehoge_def という名前にする規約のようです．(BOOST_SPIRIT_DEFINE 部分を書き換えれば違う名前にしても大丈夫のようだが，素直に従っておけば良さそう)
今回はシンプルに x3::int_ そのものとしています．

最後に BOOST_SPIRIT_DEFINE することで，constant というパーサの宣言と，constant_def という実装をひも付けます．

使い方は今までと全く同じです．

使ってみる

セマンティックアクションと名前付きパーサの両方を使って，整数を受け取って2倍にした値を返すパーサを書いてみます．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

namespace detail {

  auto const twice = [](auto& ctx) { _val(ctx) = _attr(ctx) * 2; };

  x3::rule<class constant, int> const constant;

  auto const constant_def = x3::int_[twice];

  BOOST_SPIRIT_DEFINE(constant);

} // namespace detail

using detail::constant;

int main()
{

  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);


  int result;
  bool success = x3::phrase_parse(first, last, constant, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

セマンティックアクション内では，パーサの result type に _val(ctx) でアクセス出来ます． _val(ctx) は参照を返すので，ここに適当な値を代入してやれば，パーサの返り値にすることが出来ます．
_attr(ctx) は先程と同じです．x3::int_ の attribute は int です．

実行してみると，Parse: 246 が返るはずです．

一旦まとめ

セマンティックアクションと名前付きパーサの宣言と定義をまとめました．
Qi のころより，セマンティックアクションはかなり書きやすくなっている気がします．
今回の例では，_attr(ctx) が単純な値だったのでわかりやすいですが，x3::int_ >> x3::double_ の _attr(ctx) は Boost.Fusion が登場したりしてちょっとややこしそうです．

また，再帰的パーサを定義できるようにパーサの宣言をまとめたのに，再帰的パーサを書いていませんが，これは別記事に電卓でも作ってまとめたいと思います．

Boost.Spirit.X3 の練習1

C++ Boost コンパイラ

Boost.Spirit.X3 の練習1

Boost.Spirit.X3 という C++ のための パーサコンビネータライブラリを使ってみています．
Boost.Spirit というと， C++ の黒魔術の塊みたいなイメージがあります． ちなみに Boost.Spirit.Qi が安定版のパーサコンビネータライブラリで， X3 はまだ開発中のようなので注意してください．

X3 は Qi と異なり，C++14 以降の規格を前提にしています．そのため，ジェネリックラムダなどを用いてよりわかりやすいプログラムが書けるようになっているようです．
Qi はコンパイル時間が爆発していたのですが， X3 だと多少マシのようです．

第一歩

まずは猛烈にシンプルなパーサを使ってみましょう． X3 も Qi 同様に定義済みのパーサがあるので，それを単純に使用するだけのサンプルです．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


int main()
{
  namespace x3 = boost::spirit::x3;

  int result;
  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);
  bool success = x3::parse(first, last, x3::int_, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

コンパイル & 実行

$ clang++ -std=c++14 int_parser.cpp
$ ./a.out
Parse: 123

Boost.Spirit.X3 を使用する場合は, #include <boost/spirit/home/x3.hpp> とすればオッケーです．(これは使用していない機能のヘッダも読み込んでしまっているので，コンパイルは重くなります… が，これ以降使う機能を増やす度にヘッダを書き換えるのは面倒ですし，X3 の機能の多くを使用するプログラムの場合は，大差ないと思います．)

名前空間は boost::spirit::x3 です．頻繁に出てくるので namespace x3 でエイリアスしました．

実際にパースしている部分は,

bool success = x3::parse(first, last, x3::int_, result);

の部分です．
x3::parse は，第一引数にソース文字列の先頭イテレータ，第二引数にソース文字列の終端イテレータをとります．
第三引数が，パーサの定義です．ここでは， x3::int_ という定義済みパーサを使用しました． これは, 整数を表す文字列を受けて，それを整数に変換するパーサです． たとえば "1" を 1 に変換します．整数以外にあたった場合はマッチせず，パースに失敗します．(x3::parse の返り値が false になる) 第四引数は，指定したパーサの返す値です．ここちょっと説明が難しいですね．
x3::int_ は int 型の値を返すパーサです(これを x3::int_ の attribute が int 型であると表現している？).
そこで，x3::int_ の返す値を格納する変数として，int result の参照を渡しているという感じです．
パースが成功していれば，result の中身は x3::int_ の返り値になっているはずです．

パースの成否判定は success と first == last で行います．

if (!success || first != last) {

success はそもそもパーサにソースがマッチしなかった場合, false になります．
また，"123abc" に x3::int_ をマッチさせると，"123" だけが消費され，"abc" が残ります．この時，first は "a" の位置まで進んでいます． もしソースが先頭から終端まで，パーサにマッチしていたならば，first == last となるはずです．

というわけでこのプログラムは，x3::int_ に "123" をパースさせるプログラムでした．結果，きちんと整数の 123 が取得できていることがわかります．

コンビネータ

Boost.Spirit.X3 はパーサコンビネータライブラリです．個々のパーサを組み合わせてみましょう．

" ( 1234.5)" とか "(67.8 ) " にマッチして，double を返すようなパーサを定義してみます．

auto parser = x3::lit("(") >> x3::double_ >> x3::lit(")");
bool success = x3::phrase_parse(first, last, parser, x3::ascii::space, result);

まずは parser の定義です． x3::lit はリテラルを表します．引数にとった文字列にマッチし，何も返さないパーサです．x3::lit("(") は ( にマッチし，何も返さないパーサということになります．
x3::double_ は x3::int_ と同じく，定義済みパーサで，浮動小数点数にマッチしその値を返します．

そして重要なのが，>> です．
これは，「左辺にマッチした後，右辺にマッチするパーサ」を作り出すコンビネータです．
ここでは，x3::lit("(") >> x3::double_ ですから，( にマッチした後，浮動小数点数にマッチするパーサ，ということになります.

通常，>> は左辺の返す値と右辺の返す値のタプルを返します．(x3::int_ >> x3::double_ ならば，int と double のタプル)
しかし，左辺右辺どちらか一方が値を返さない(正確には x3::unused_type を返す) 場合には，もう一方の値だけを返します．
つまり，x3::lit("(") >> x3::double_ は double だけを返し，>> x3::lit(")") と続けても double だけが返ります．

次に，空白の読み飛ばしについてです．

bool success = x3::phrase_parse(first, last, parser, x3::ascii::space, result);

ひとつ目の例と異なり，x3::parse ではなく x3::phrase_parse を使っています．
こちらは，attribute を示す最後の引数の前に，スキップパーサを取ります． スキップパーサとは，文字通り，スキップしてほしい文字列にマッチするパーサです．
x3::ascii::space は定義済みのパーサで，スペース，改行文字，タブにマッチします．したがって，これらの文字はスキップされます． スキップ判定のタイミングは >> の部分です．つまり，"12 3" は x3::int_ でパースすると, 12 までしかマッチしません．x3::int_ >> x3::int_ とすることで，スペースがスキップされます．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


int main()
{
  namespace x3 = boost::spirit::x3;

  std::string src{ "( 123.4 )" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);
  double result;
  auto parser = x3::lit("(") >> x3::double_ >> x3::lit(")");
  bool success = x3::phrase_parse(first, last, parser, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

ちなみに，x3::lit("(") >> x3::double_ >> x3::lit(")") の部分ですが，operator<< の引数の内，片方がパーサであれば，char const* から暗黙変換が働くので， "(" >> x3::double_ >> ")" と書くことが出来ます．

コンビネータは他にもあります．

  • |
    • a | b で，a にマッチするか b にマッチするか
    • a を先に試すので，両方にマッチする場合でも a にマッチしたことになる (PEG の特徴ですね)
    • 返り値は boost::variant<a, b> です．a と b が同じ型を返す場合はその型を返します
  • >
    • >> とほぼ同じです．
    • a >> b は a にマッチして b にマッチしなかった場合，a の前にバックトラックします.
    • a > b はその場合，即座にパース失敗を通知します．
  • *
    • *a という形で使う
    • a の 0 回以上の繰り返し
    • 返り値は std::vector<a>
  • +
    • +a という形で使う
    • * の一回以上繰り返し版
  • -
    • -a という形で使う
    • a が来ても来なくても良いというパーサ
    • 返り値は boost::optional<a>

...

> と >> の違いはわかりにくいですね．
(x3::lit("(") >> ")") | ("(" >> x3::int_ >> ")") に "(123)" を食わせると，| の後半部分にマッチしてくれます． 一方, >> を > に置換えた場合，ソース先頭の"(" がx3::lit("(") にマッチするにもかかわらず，その直後に")" が来ていないため，その時点でエラーを通知してしまいます．

一旦むすび

とりあえず最も基本的な部分をまとめてみました．
ここまでは Qi と同じなんですよね．

セマンティックアクションや on_error などの扱いががっつり変わっているようなので，一旦ここで切って，それぞれ調べてからまとめたいと思います． 何か間違い等あればぜひご指摘お願いします．