AccessViolation Exception

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

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

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,数式パーサのサンプルは用意されています。