読者です 読者をやめる 読者になる 読者になる

Kokudoriing

技術系与太話ブログ

C#でPEGパーサー

C#

PEGって何?って方はWikipediaを御覧ください。
(正直ボクもよくわかってない・・)
ざっくりと、BNFよりも曖昧性のないものを扱うのが得意みたいで、Shift/Reduceコンフリクトが発生しないとのこと。
Perl6がPerl6 rulesとかで言語レベルに組み込んでるアレです。

PEG自体の解説はkmizushimaさんのPEG基礎文法最速マスターを見ていただくとして、
以下はC#で使えるPEGパーサー、peg-sharpについてのお話し。

昨日辺りから触りだして、ようやく簡単なJSONパーサー作ってみました。
https://gist.github.com/kokudori/5252810

Xxx.pegにPEGを書いて、peg-sharpでパーサーをジェネレートして使う感じです。
ただ、PEGファイル内でバッククォート(`)で囲まれた部分がC#として解析されます。
この時、非終端記号、終端記号毎に解析結果がResult型として保持され、非終端記号毎にList型のresults変数が割り当てられます。

Result型は以下の様な構造体です。
struct Result
{
/ 解析されたテキスト。
public string Text { get; }

// 1から始まる行番号。
public int Line { get; }

// 1から始まる列番号。
public int Col { get; }

// セマンティックアクションの結果
public Expression Value { get; }
}

セマンティックアクションっていうのはバッククォートで囲んだC#の振る舞いのことです。
また、セマンティックアクション内で使える変数が存在します。
expected 非終端記号の文字列表現。パーサーエラーの時のエラーメッセージで役立つ。
fatal パーサーエラーを起こす。また、その時のエラーメッセージを設定する。
results 上記で説明した非終端記号、終端記号毎の解析結果のリスト。
text よくわかんない。使ったことない。
value Result型のValueプロパティに対応。基本的にはここに解析結果を渡していく。

また、独自のルールが存在し、ルールはPEGルールの前に書かないとダメです。
ルールは色々あるので詳しくはドキュメントを見ていただくとして、重要なのはstartとvalue。
startは非終端記号のエントリポイントを指定します。
valueは解析結果を意味する値の型を指定します。

パースの流れとしては、非終端記号毎に意味のある値をvalueに渡して、
1レイヤー上の非終端記号でresult.Valueがnullじゃないものを補足して云々みたいな感じですかね。
因みにパーサーの部分クラスを定義できるのでそこでvalueに渡す時に使うヘルパメソッドとか書いとくといいんじゃないですかね。
ただあっというまにメンテきつくなりそうですけども。
startで指定した非終端記号のvalueがパーサーのParseメソッドの戻り値になります。

使ってみた感想として、まずvalueの型が1つのみっていうのは辛いです。
ドキュメントではUnion的な型作ればOKとか書いてますけど、やっぱりきついです。
あと公式のサンプルだとExpression抽象クラスがEval持って、それを継承していくインタプリタパターン使ってました。
なのでJSONパーサー作ったときは全部dynamicに突っ込んでます。
これ、本当は木構造にして各ノードがChildren持つとかの方がいいんでしょうが、それをこれで作るの面倒だなー。

あ、そういえばdynamicって、内部が構造体の時にnullチェックすると例外出るんですね。(当たり前か)
なので if(dynamicobj is ValueType || dynamicobj != null) some() とかしてたんですが、スマートな方法ないんですかね。
以上、備忘録。