AccessViolation Exception

仕事でもはんだづけ、家でもはんだづけ

トップ > パーサジェネレータ

c#でSpracheを使った構文解析(4)

c# パーサジェネレータ 技術ネタ

c#でSpracheを使った構文解析(3) - AccessViolation Exception

前回記事です。

目標

var csv = "hoge,foo,bar,\nhoge1,foo1,bar1\nhoge2,foo2,bar2,bazz";

今回はcsvのような区切り文字や改行で仕切られているものを無事に展開することを目標とします。

セル単体を定義

static readonly Parser<string> Cell = 
    Parse.CharExcept(',').AtLeastOnce().Text()
         .Or(Parse.Return(""));

前回のParse.LetterやParse.LetterOrDigitでは記号等を扱うことが出来ず、またスペースがあったらそこで途切れてしまいます。

Parse.AnyCharでは区切り文字ひっくるめて持ってきてしまうのでNG。

そこで指定文字以外を扱えるCharExcept()を使います。

.Or(Parse.Return(""))してるのは、セルには文字がない場合があります。その時に例外を起こさないようにする対策です。

これで "hoge,foo,bar" からhogeを取り出せるようになりました。

カンマで区切られた文字をパース

from begin in Parse.Char('\'')
from content in Cell
from end in Parse.Char('\'')

これでも最初と最後のカンマがない場合などを処理すれば出来ないこともないですが、DelimitedByという便利なものがあるので

static readonly Parser<IEnumerable<string>> Line =
    Cell.DelimitedBy(Parse.Char(','));

こう書くことが出来ます。最初と最後の区切り文字がない場合も考慮してくれます。

これで",hoge,foo,bar,,"は["", "hoge", "foo", "bar", "", ""]にパースすることが出来ます。

CSV全体をパース

今度は改行で区切られたLineを定義すればいいので

static readonly Parser<IEnumerable<IEnumerable<string>>> CSV =
    Line.DelimitedBy(Parse.Char('\n'));

いいはずですがこれだけではダメ。先ほどカンマを例外文字に追加したように、改行も例外に追加しないとCellとして認識されてしまいます。

static readonly Parser<string> Cell =
    Parse.AnyChar.Except(Parse.Chars(',', '\n'))
         .AtLeastOnce().Text()
         .Or(Parse.Return(""));

'Parse.AnyChar.Expect()'で適当な文字から例外を指定、例外に追加するのは'Parse.Chars'で複数指定しておくように修正すればよし。

これで最初の目標に掲げていた

var csv = "hoge,foo,bar,\nhoge1,foo1,bar1\nhoge2,foo2,bar2,bazz";

が

[
    ["hoge", "foo", "bar", ""],
    ["hoge1", "foo1", "bar1"],
    ["hoge2", "foo2", "bar2", "baz"]
]

にパースできるようになりました。めでたしめでたし。

番外

カンマで区切られてかつダブルクォートでくくられている場合

csvってたまに

var csv = "\"hoge\",\"foo\",\"bar\",\nhoge1,\"foo1\",bar1\nhoge2,foo2,bar2,bazz";

みたいにダブルクォートでくくられている場合があります。現状ではダブルクォートごと文字列として識別してしまいます。これにも対応させてみましょう。

まずはクォートされたセルを定義

static readonly Parser<string> QuotedCell =
    from begin in Parse.Char('"')
    from cell in Cell
    from end in Parse.Char('"')
    select cell;

セルの例外文字にダブルクォートを追加

static readonly Parser<string> Cell =
    Parse.AnyChar.Except(Parse.Chars(',', '\n', '\"'))
         .AtLeastOnce().Text()
         .Or(Parse.Return(""));

あとはLineで識別するセルにQuotedCellを追加

static readonly Parser<IEnumerable<string>> Line =
    QuotedCell.Or(Cell).DelimitedBy(Parse.Char(','));

これで先ほどのダブルクォート付きのセルが混ざっていてもパース可能になりました。

今回はほぼDelimitedByとExceptの紹介のようなものでしたが以上になります。

c#でSpracheを使った構文解析(3)

c# パーサジェネレータ 技術ネタ brainf*ck

c#でSpracheを使った構文解析(2) - AccessViolation Exception

の続きです。

構文解析できるならbrainf*ck、作りたくなりますよね（ならない

以前にも

"brainf*ck" - 記事一覧 - AccessViolation Exception

こんなものばかり書いてまるでbrainf*ckが好きに見えますけど手軽で適当に中身濁すのにお手頃なだけなんです...。

処理系を作る

大した労力もかからないので適当に処理を書いたクラスを作ります。

class BrainfuckProcessor {
    public const int BUFFER_SIZE = 300000;
    public int Pointer { get; private set; }
    public char[] Buffer { get; private set; }
    public string Result {
        get { return outputList.Aggregate("", (s, x) => s + x); }
    }
    private List<char> outputList;
    public BrainfuckProcessor() {
        Reset();
    }
    public void Reset() {
        Pointer = 0;
        Buffer = new char[BUFFER_SIZE];
        outputList = new List<char>();
    }
    public void IncrementPtr() { Pointer++; }
    public void DecrementPtr() { Pointer--; }
    public void Increment() { Buffer[Pointer]++; }
    public void Decrement() { Buffer[Pointer]--; }
    public void Print() {
        Console.Write(Buffer[Pointer]);
        outputList.Add(Buffer[Pointer]);
    }
    public void Read() { Buffer[Pointer] = (char)Console.Read(); }

    public bool IsLoop() { return Buffer[Pointer] != 0; }
}

ResultとかoutputListは出力をリストで持ってるだけです、特に気にしなくていいです。

動作については

Brainfuck - Wikipedia

を参照

パース後の型を定義

class BrainfuckToken {
    public enum TokenType {
        IncrementPtr,// >
        DecrementPtr,// <
        Increment,//    +
        Decrement,//    -
        Print,//        .
        Read,//         ,
        Loop,//     []
        Master,
    }
    public TokenType Token { get; private set; }
    public IEnumerable<BrainfuckToken> Children { get; private set; }
    public BrainfuckToken(TokenType t, IEnumerable<BrainfuckToken> children = null) {
        this.Token = t;
        this.Children = children != null ? children : Enumerable.Empty<BrainfuckToken>();
    }
}

最初はenumのリストでいいかと思ったのですが、[]でループしなきゃいけないことも考え、xmlと同じように[]もひとつの要素として持ってループさせるように定義。

最上位だけリストで持つのもキモいのでTokenTypeにMasterを追加。

再びBrainfuckProcessorに戻りRunメソッドを追加

class BrainfuckProcessor {
    public const int BUFFER_SIZE = 300000;
    public int Pointer { get; private set; }
    public char[] Buffer { get; private set; }
    public string Result {
        get { return outputList.Aggregate("", (s, x) => s + x); }
    }
    private List<char> outputList;
    public BrainfuckProcessor() {
        Reset();
    }
    public void Reset() {
        Pointer = 0;
        Buffer = new char[BUFFER_SIZE];
        outputList = new List<char>();
    }
    public void IncrementPtr() { Pointer++; }
    public void DecrementPtr() { Pointer--; }
    public void Increment() { Buffer[Pointer]++; }
    public void Decrement() { Buffer[Pointer]--; }
    public void Print() {
        Console.Write(Buffer[Pointer]);
        outputList.Add(Buffer[Pointer]);
    }
    public void Read() { Buffer[Pointer] = (char)Console.Read(); }

    public bool IsLoop() { return Buffer[Pointer] != 0; }

    public void Run(BrainfuckToken token) {
        switch (token.Token) {
            case BrainfuckToken.TokenType.IncrementPtr:
                IncrementPtr();
                break;
            case BrainfuckToken.TokenType.DecrementPtr:
                DecrementPtr();
                break;
            case BrainfuckToken.TokenType.Increment:
                Increment();
                break;
            case BrainfuckToken.TokenType.Decrement:
                Decrement();
                break;
            case BrainfuckToken.TokenType.Print:
                Print();
                break;
            case BrainfuckToken.TokenType.Read:
                Read();
                break;
            case BrainfuckToken.TokenType.Loop:
                while (IsLoop()) {
                    foreach (var c in token.Children) {
                        Run(c);
                    }
                }
                break;
            case BrainfuckToken.TokenType.Master:
                foreach (var c in token.Children) {
                    Run(c);
                }
                break;
        }

    }
}

パーサを定義

><+-.,[]からBrainfuckTokenを生成するパーサを書きます

static readonly Parse<BrainfuckToken> IncrementPtr = 
    Parse.Char('>').Token().Return(new BrainfuckToken(BrainfuckToken.TokenType.IncrementPtr));

これを量産するのは少し不格好なので

static readonly Func<char, BrainfuckToken.TokenType, Parser<BrainfuckToken>> CreateToken =
    (c, t) => Parse.Char(c).Token().Return(new BrainfuckToken(t));
static readonly Parser<BrainfuckToken> IncrementPtr = CreateToken('>', BrainfuckToken.TokenType.IncrementPtr);
static readonly Parser<BrainfuckToken> DecrementPtr = CreateToken('<', BrainfuckToken.TokenType.DecrementPtr);
static readonly Parser<BrainfuckToken> Increment = CreateToken('+', BrainfuckToken.TokenType.Increment);
static readonly Parser<BrainfuckToken> Decrement = CreateToken('-', BrainfuckToken.TokenType.Decrement);
static readonly Parser<BrainfuckToken> Print = CreateToken('.', BrainfuckToken.TokenType.Print);
static readonly Parser<BrainfuckToken> Read = CreateToken(',', BrainfuckToken.TokenType.Read);
static readonly Parser<BrainfuckToken> Loop;//TODO:Implement here

CreateTokenを作って全部に適用しました。Loopに関してはToken本体が定義できていないのでまだ保留で。

Tokenは至ってシンプルです。

static readonly Parser<BrainfuckToken> Token =
    IncrementPtr
    .Or(DecrementPtr)
    .Or(Increment)
    .Or(Decrement)
    .Or(Print)
    .Or(Read)
    .Or(Loop);

先ほど定義した中のどれかが必ず要素になるので、Orでつないでやれば終了。

Loopの定義は[]に囲ってあるTokenたちになるので

Parse.Char('[') Token.Many() Parse.Char(']')

こうですね。

static readonly Parser<BrainfuckToken> Loop =
    from open in Parse.Char('[')
    from children in Token.Many()
    from close in Parse.Char(']')
    select new BrainfuckToken(BrainfuckToken.TokenType.Loop, children);

最後にTokenType.Masterを定義する大元のパーサを定義して

public static readonly Parser<BrainfuckToken> BrainFuck =
    from children in Token.Many()
    select new BrainfuckToken(BrainfuckToken.TokenType.Master, children);

動かしてみる

public void HelloWorld() {
    var input = "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.";
    var token = BrainFuck.Parse(input);

    var process = new BrainfuckProcessor();
    process.Run(token);//"Hello, world!"
}

ここまでくればいろいろ作れそうな気がしてきますね。

c#でSpracheを使った構文解析(4) - AccessViolation Exception

c#でSpracheを使った構文解析(2)

c# Sprache 技術ネタ パーサジェネレータ

c#でSpracheを使った構文解析(1) - AccessViolation Exception

の続きです。長くなりそうなので分割しました。

前回までで、文字や数値、指定文字単体のパーサは作れるようになりました。今回はそれらを組み合わせて構文に対応するパーサを作っていきます。

今回は簡単なxmlのようなものを解析してみます。*1

目標

var input = "<html><body>hello</body></html>";

タグを識別すること、入れ子になっているタグを識別させることが大きな目標です。

クラス定義

ノードを表す適当なクラスを定義しておきましょう。

class Tag {
    public string Name { get; set; }
}
class Node {
    public Tag Identifier { get; set; }
    public string Content { get; set; }
    public IEnumerable<Node> Children { get; set; }
}

最終的に

Node:
    Identifier = Tag("html")
    Content = ""
    Children = [
        Node:
            Identifier = Tag("h1")
            Content = "hello" 
    ]

のようになればいい感じになります。

タグの識別

static readonly Parser<string> TokenText = Parse.Letter.AtLeastOnce().Token().Text();

タグの中身はスペースがあっても無視するので、トークンにして文字列を定義しておきます。

つぎにタグを識別するためにパーサの組み合わせをするわけですが

Parse.Char('<')  TokenText Parse.Char('>')

このように合成するのにメソッドを数珠つなぎにしていくのでは見づらい、そこでクエリ構文を使って次のように書きます。

static readonly Parser<string> BeginTag = 
    from begin in Parse.Char('<')
    from content in TokenText
    from end in Parse.Char('>')
    select content;

まずParse.Char('<')したものをbeginに入れ、TokenTextをcontentに入れ、Parse.Char('>')をendに入れ、最終的にcontentを返す。

これで"<html>"は識別可能になりました。先ほどのクラスを返すように少し書き換えれば

static readonly Parser<Tag> BeginTag = 
    from begin in Parse.Char('<')
    from content in TokenText
    from end in Parse.Char('>')
    select new Tag() { Name = content };

同様に終了タグも定義すると

static readonly Parser<Tag> EndTag = 
    from begin in Parse.Char('<')
        from slash in Parse.Char('/')
    from content in TokenText
    from end in Parse.Char('>')
    select new Tag() { Name = content };

これで開始、終了タグのパーサが完成しました。

タグに囲まれたテキストのパース

開始、終了タグが識別できるので同じようにしてタグに囲まれたテキストを取得してみます。

static readonly Parser<Node> NodeGrammer =
        from begin in BeginTag
        from content in TokenText
        from end in EndTag
        select new Node() { Identifier = begin, Content = content };

開始タグが来て、中身が来て、終了タグが来て、クラスを作って返す。

これで

"<body></body>"

が出来るのですが、ここままでは開始終了タグが一致していなくても取得できてしまいます。タグが一致しているもののみ選択するように変更すると

static readonly Parser<Node> NodeGrammer =
        from begin in BeginTag
        from content in TokenText
        from end in EndTag
        where begin.Name == end.Name
        select new Node() { Identifier = begin, Content = content };

タグに囲まれたテキストがない場合もあります。考慮すると

static readonly Parser<Node> NodeGrammer =
        from begin in BeginTag
        from content in TokenText.Or(Parse.Return(""))
        from end in EndTag
        where begin.Name == end.Name
        select new Node() { Identifier = begin, Content = content };

Or()を使えばパース出来なかった時に別のパーサを走らせることが出来ます。またReturn()でパースで来た時に任意の値を返すことができるのでTokenTextがなかった時は空の文字列を返すようにしました。

ここまででタグに囲まれたテキストの取得が出来るようになりました。

入れ子になっている要素を取得

NodeGrammerに自身を参照させる構文を追加します。

static readonly Parser<Node> NodeGrammer =
        from begin in BeginTag
        from children in NodeGrammer.Many()
        from content in TokenText.Or(Parse.Return(""))
        from end in EndTag
        where begin.Name == end.Name
        select new Node() { Identifier = begin, Content = content, Children = children };

子要素は一つとは限らないので最初のクラス定義の時点でIEnumerable<Node>にしてあります。Many()自体も要素がなければIEnumerable.Empty<T>()を返すので先ほどみたいになかった時の処理は必要ありません。

完成

パーサジェネレータは自分で簡単に構文の追加、編集ができることがいいところです。他にもタグ内にパラメータがあったり、コメントアウトなども追加してみるといいかもしれません。

c#でSpracheを使った構文解析(3) - AccessViolation Exception

*1:Spracheのgithubにもcsv,xml,数式パーサのサンプルは用意されています。