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

# [Sprache](https://github.com/sprache/Sprache)を使ってみる
Spracheは、テキストパーサを組み立てる実用的なライブラリです。
XFile, JSON, VPD, MQO, OBJくらいなら楽勝であります。
C言語の複雑さくらいまでならいけるんでないか。

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

```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](https://github.com/ousttrue/SpracheSample)

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

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

```csharp:最初のコード
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"を読み取るパーサーを定義。

```dos:実行結果
HIERARCHY
```

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

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

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

```csharp:Stringに変換
Parse.String("HIERARCHY").Text() // Parser<String>型
```

## 次のステップ

```bvh
HIERARCHY
ROOT Hips
```
まで消化するコード。

```csharp: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...となるのだけど、ここはクエリ構文のシンタックスシュガーに乗った方がいい。
メソッド構文だと以下のようになる。

```csharp
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](http://karino2.livejournal.com/277374.html)
がいいです。
Spracheの仕組みがなんとなくわかる。

引き続きSpracheについて。

## LineEnd, WhtieSpaceをToken()に変える

```csharp:
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の入れ物を作る。

```csharp: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に変わった。

```csharp:
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())
                                    ;
}
```

使う。

```csharp:
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型に変更した。

## 設計
こんな感じを構想。

```csharp:
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は似て非なるものであることに注意。
別物。

```csharp
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。

```csharp
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があるので簡単

```csharp

        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で消化できないこれ。

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

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]
```

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