C#のパーサコンビネータライブラリSpracheを使ってみる

Spracheを使ってみる

Spracheは、テキストパーサを組み立てる実用的なライブラリです。
XFile, JSON, VPD, MQO, OBJくらいなら楽勝であります。
C言語の複雑さくらいまでならいけるんでないか。

今回は題材としてBVHの前半の木構造をパースしてみます。
BVHというのはモーションキャプチャデータのテキストフォーマットで以下のようなものです。
Google先生にbvh、モーションキャプチャ、サンプルとかで聞くといろいろ出てきます。

HIERARCHY
ROOT Hips
{
    OFFSET 0 0 0
    CHANNELS 6 Xposition Yposition Zposition Zrotation Yrotation Xrotation
    JOINT Chest
    {
        OFFSET 0 1.00 0
        CHANNELS 3 Zrotation Yrotation Xrotation
        JOINT Head
        {
            OFFSET 0 0.58 0
            CHANNELS 3 Zrotation Yrotation Xrotation
            End Site
            {
                OFFSET 0 0 0
            }
        }
    }
    JOINT LeftHip
    {
        OFFSET 0.1 -0.1E-01 0
        CHANNELS 3 Zrotation Yrotation Xrotation
        End Site
        {
            OFFSET 0 0 0
        }
    }
    JOINT RightHip
    {
        OFFSET -0.1 -0.1E-01 0
        CHANNELS 3 Zrotation Yrotation Xrotation
        End Site
        {
            OFFSET 0 0 0
        }
    }
}
MOTION
Frames: 1
Frame Time: 0.033
0 0 0 0 0 0 0 0 0 0 0 0

こいつの前半HIERARCHYからMOTIONまでをパースします。
簡略化するとだいたいこんな感じの構成になってます。

HIERARCHY
ROOT
{
  OFFSET [xyz]
  CHANNELS n [channel]
  [JOINT name{}]|End Site
}

中括弧でJOINTが木構造になっていて末端はEnd Siteになっている。

実装

SampleCode

新しくプロジェクトを作ってNugetでSpracheを追加。
この時に気付いたが、SparcheじゃなくてSpracheだった。

コマンドライン引数でbvhを指定してParse

最初のコード

class Program
{
    static void Main(string[] args)
    {
        var path = args.First();
        var bvhtext=File.ReadAllText(path);

        Parser<String> parser = Parse.String("HIERARCHY").Text();
        var result = parser.Parse(bvhtext);

        Console.WriteLine(result);
    }
}

最低限ということで先頭のBVHマーカーたる"HIERARCHY"を読み取るパーサーを定義。

実行結果

HIERARCHY

実行すると成功裏に例外が発生することなく結果が返る。指定した文字列を消費できた。

Parse.String("HIERARCHY") // Parser<IEnumerable<Char>>型

Parse.Stringは指定した文字列を消費し、
IEnumerableを返すParserです。
Stringを返すように変形。

Stringに変換

Parse.String("HIERARCHY").Text() // Parser<String>型

次のステップ

HIERARCHY
ROOT Hips

まで消化するコード。

query構文を強いられる

var parser = from hierarchy in Parse.String("HIERARCHY").Text()
             from eol in Parse.LineEnd
             from root in Parse.String("ROOT").Text()
             from space in Parse.WhiteSpace
             from hips in Parse.String("Hips").Text()
             select new { hierarchy, root, hips };
var result = parser.Parse(bvhtext);

Console.WriteLine(result.hierarchy);
Console.WriteLine(result.root);
Console.WriteLine(result.hips);

突然のクエリ構文にOh...となるのだけど、ここはクエリ構文のシンタックスシュガーに乗った方がいい。
メソッド構文だと以下のようになる。

Parse.String("HIERARCHY").Text()
    .SelectMany(x => Parse.LineEnd, (x, y) => new { hierarychy=x, y })
    .SelectMany(x => Parse.String("ROOT").Text(), (x, y)=>new { x, root=y })
    .SelectMany(x => Parse.WhiteSpace, (x, y)=>new { x, y })
    .SelectMany(x => Parse.String("Hips").Text(), (x, y)=>new { x, hips=y })
    .Select(x => new { hierarchy = x.x.x.x.hierarychy, root = x.x.x.root, hips = x.hips })
    ;

SelectManyが連鎖する場合は、クエリ構文の方が簡潔になる。

SelectManyについては、
LINQで簡単DSL
がいいです。
Spracheの仕組みがなんとなくわかる。

引き続きSpracheについて。

LineEnd, WhtieSpaceをToken()に変える

var parser = from hierarchy in Parse.String("HIERARCHY").Token().Text()
             from root in Parse.String("ROOT").Token().Text()
             from hips in Parse.String("Hips").Token().Text()
             select new { hierarchy, root, hips }
             ;

前後をスペースや改行で区切られている場合はToken()で切り出すのが楽ちん。

本気を出す

突如難易度が上がる。
まずBVHの入れ物を作る。

BVH入れ物

public struct Vector3
{
    public Single X;
    public Single Y;
    public Single Z;
}

public enum ChannelType
{
    Xposition,
    Yposition,
    Zposition,
    Zrotation,
    Yrotation,
    Xrotation,
}

class Node
{
    public String Name { get; private set; }
    public Vector3 Offset { get; private set; }
    public ChannelType[] Channels { get; private set; }
    public List<Node> Children { get; private set; }

    public Node(String name, Vector3 offset, IEnumerable<ChannelType> channels = null, IEnumerable<Node> children = null)
    {
        Name = name;
        Offset = offset;
        Channels = channels != null ? channels.ToArray() : new ChannelType[] { };
        Children = children != null ? children.ToList() : new List<Node>();
    }

    public override string ToString()
    {
        return String.Format("{0}[{1}, {2}, {3}]{4}", Name, Offset.X, Offset.Y, Offset.Z, String.Join(", ", Channels));
    }

    public void Traverse(Action<Node, int> pred, int level = 0)
    {
        pred(this, level);

        foreach (var child in Children)
        {
            child.Traverse(pred, level + 1);
        }
    }
}

パーサも作る。
返り値の型がNodeに変わった。

static class BvhParser
{
    public static Parser<Node> Parser = from hierarchy in Parse.String("HIERARCHY").Text()
                                        from root in Parse.String("ROOT").Token().Text()
                                        from hips in Parse.String("Hips").Token().Text()
                                        select new Node("dummy", new Vector3())
                                    ;
}

使う。

var root = BvhParser.Parser.Parse(bvhtext);

root.Traverse((node, level) => {
    Console.WriteLine(String.Format("{0}{1}"
        , String.Join("", Enumerable.Repeat("  ", level).ToArray()) // indent
        , node
        ));
});

べた書きしていたParserをBvhParserクラスに移動して、返り値をNode型に変更した。

設計

こんな感じを構想。

static class BvhParser
{
    // todo
    public static Parser<Vector3> Offset;

    // todo
    public static Parser<IEnumerable<ChannelType>> Channels;

    // todo
    public static Parser<Node> EndSite;

    public static Parser<Node> Node(String prefix)
    {
        return from _ in Parse.String(prefix).Token()
               from name in Parse.LetterOrDigit.Many().Token().Text()
               from open in Parse.Char('{').Token()
               from offset in Offset
               from channels in Channels
               from children in Node("JOINT").AtLeastOnce().Or(EndSite
                    // 型をIEnumerable<Node>にそろえる
                    .Select(x => new Node[] { x }))
               from close in Parse.Char('}').Token()
               select new Node(name, offset, channels, children)
                                    ;
    }

    public static Parser<Node> Parser = from hierarchy in Parse.String("HIERARCHY").Token()
                                       from root in Node("ROOT")
                                       select root;
}

繰り返し

繰り返しについて。

指定回数

Rpeat。Channelsの実装で使う。

0回以上

Many

1回以上

AtLeastOnce

0 or 1

Optional。浮動小数の実装で使う。

数字

数字について。
不確か

整数1文字

Digit

整数

Number

小数

Decimal

?

Numerial

Offsetの実装

クエリ構文のselectとメソッド構文のSelectは似て非なるものであることに注意。
別物。

public static Parser<Vector3> Offset = from _ in Parse.String("OFFSET").Token()
                                       from x in Parse.Decimal.Token().Select(x => Convert.ToSingle(x))
                                       from y in Parse.Decimal.Token().Select(x => Convert.ToSingle(x))
                                       from z in Parse.Decimal.Token().Select(x => Convert.ToSingle(x))
                                       select new Vector3 {
                                           X=x,
                                           Y=y,
                                           Z=z
                                       };

Channelsの実装

指定回数を繰り返すRepeat。
即値を返すReturn。

public static Parser<IEnumerable<ChannelType>> Channels = from _ in Parse.String("CHANNELS").Token()
                                                          from n in Parse.Number.Select(x => Convert.ToInt32(x))
                                                          from channels in Parse.String("Xposition").Token().Return(ChannelType.Xposition)
                                                              .Or(Parse.String("Yposition").Token().Return(ChannelType.Yposition))
                                                              .Or(Parse.String("Zposition").Token().Return(ChannelType.Zposition))
                                                              .Or(Parse.String("Xrotation").Token().Return(ChannelType.Xrotation))
                                                              .Or(Parse.String("Yrotation").Token().Return(ChannelType.Yrotation))
                                                              .Or(Parse.String("Zrotation").Token().Return(ChannelType.Zrotation))
                                                              //.Many()
                                                              .Repeat(n) // Repeatに書き直し
                                                          select channels
                                                            ;

EndSiteの実装

すでにoffsetがあるので簡単

        public static Parser<Node> EndSite = from _ in Parse.String("End Site").Token()
                                             from open in Parse.Char('{').Token()
                                             from offset in Offset
                                             from close in Parse.Char('}').Token()
                                             select new Node("EndSite", offset);

エラー修正

Parsing failure: unexpected 'J'; expected } (Line 20, Column 5); recently consumed:    }    

このエラーメッセージが優れものでどこまで正常に消化できたかがわかる。
今回は2個目のJOINT内のどこかで死んだ。

-0.1E-01

Decimalで消化できないこれ。

指数表記の浮動小数を消化する新たなパーサ

public static Parser<String> Exponent = from _ in Parse.Char('E')
                                       from sign in Parse.Chars("+-")
                                       from num in Parse.Number
                                       select String.Format("E{0}{1}", sign, num);

public static Parser<Single> FloatEx = from negative in Parse.Char('-').Optional().Select(x => x.IsDefined ? x.Get().ToString() : "")
                                       from num in Parse.Decimal
                                       from exponent in Exponent.Optional().Select(x => x.IsDefined ? x.Get() : "")
                                       select Convert.ToSingle(negative+num+exponent);

public static Parser<Vector3> Offset = from _ in Parse.String("OFFSET").Token()
                                       from x in FloatEx.Token().Select(x => Convert.ToSingle(x))
                                       from y in FloatEx.Token().Select(x => Convert.ToSingle(x))
                                       from z in FloatEx.Token().Select(x => Convert.ToSingle(x))
                                       select new Vector3 {
                                           X=x,
                                           Y=y,
                                           Z=z
                                       };

Optionalの値は

IOptional<String>

のようになるのでSelectで中身を取り出し、無ければ空文字にしている。

動くようになった。

Hips[0, 0, 0]Xposition, Yposition, Zposition, Zrotation, Yrotation, Xrotation
  Chest[0, 1, 0]Zrotation, Yrotation, Xrotation
    Head[0, 0.58, 0]Zrotation, Yrotation, Xrotation
      EndSite[0, 0, 0]
  LeftHip[0.1, -0.01, 0]Zrotation, Yrotation, Xrotation
    EndSite[0, 0, 0]
  RightHip[-0.1, -0.01, 0]Zrotation, Yrotation, Xrotation
    EndSite[0, 0, 0]

ちょっとしたテキストパーサを書くのに大変便利。