kazuk は null に触れてしまった

C# / .NET 系技術ネタ縛りでお送りしております

カテゴリーアーカイブ: NParsec

NParsec+ …で Excel を…CLI…(4) NParsec で Lexer/Lexeme をTDD


という訳で Lexer / Lexeme です。この2つを何とかするとコードの字句解析( Lexial Parse )は終了でその先は Token の並びに基づいた構文解析という事になります。

まず、Lexer と Lexeme が何なのかです。

前回の Lexers.Lex の呼びでLexer の方は事実上わかりきった話なんですが、PatternとTokenizer を結び付けてトークン値を作るのが Lexer です。

Lexeme はなんなのか、Lexers.Lexeme の定義に飛んでみればあっさりした話です。

    public static Lexeme Lexeme (Scanner delim, Parser<Tok> token_scanner) {
       return delim.Optional ().Seq (token_scanner.SepEndBy (delim));
     }

頭に delim があることの Optional で token_scanner が delim で SepEndBy されているシーケンスってことですね。

そしてこのコードの意味です。まず先頭の delim にマッチした物を捨てます。この捨てるってのが字句解析としての役目なんですが、どこにも捨てるなんて書いてないよーって思うでしょう。

Parser.Seq を見るとわかるとおりです。

public Parser < R > Seq<R>(Parser < R > p){
       return Parsers.Seq (this, p);    
}

何がわかるのさ!ですね。 NParsec のソースで R を返すって事は、 R が該当パーサーの出力値になります。出力値でない物は捨てられるって事です。

Parsers.cs では複数の Seq が定義されてます。

    public static Parser<R> Seq<A,R> (Parser<A> p1, Parser<R> p2)
    public static Parser<R> Seq<A, B, R> (Parser<A> p1, Parser<B> p2, Parser<R> p3)
    public static Parser<R> Seq<A, B, C, R> (Parser<A> p1, Parser<B> p2, Parser<C> p3, Parser<R> p4)

戻り値が Parser<R> 型でわかるとおりで、Parser<A>, Parser<B>, Parser<C>とかはパーサーが読むうえで構文チェックとして確認に行きますけど、出力にはなりません。

同じ Parsers.cs にある FollowedByParser を見るとこうなっています。

  class FollowedByParser<R, A> : Parser<R>

Rが前にあるから、FollowedByParser は前のトークンを返すわけです。当然に後ろの A は存在することは確認されるけど捨てられます。

んで、Lexeme の定義に戻ると delim.Optional().Seq(…)の前半の delim.Optional()は捨てられました。そしてその中が返されるという事がわかります。

SepEndBy を定義に移動、定義に移動でどんどん飛んでいくと

    public Parser<T[]> SepEndBy1<A> (Parser<A> sep, ArrayFactory<T> factory) {
      /*
      Binder<T, T[]> array_builder = delegate (T initial_value) {
        return sep.step(0).Seq(this).Many
(Functors.getArrayAccumulatable (initial_value, factory));
      };
      return bind (array_builder);*/
      object end = new object ();
      Parser<T[]> one = Parsers.One<T[]> ();
      Catch<T[]> catcher = delegate (T[] val, object e) {
        if (end==e) {
          return one;
        }
        else {
          return Parsers.Raise<T[]> (e);
        }
      };
      Parser<T> exceptionable = sep.Seq (this | Parsers.Raise<T> (end));
      //return this.Seq (exceptionable.Many(factory).Try(catcher));
      Binder<T, T[]> array_builder = delegate (T initial_value) {
        return exceptionable.Many (Functors.ToArrayAccumulatable (initial_value, factory)).Try(catcher);
      };
      return Bind(array_builder);
    }

にたどり着くはずです。

Many でとってますね、Manyは連続する要素の各要素を集めて T –> T[] にする Accumulator パターンを実装しています。結果として Lexer でTokenize された物がめでたく Tok[] になります。

ちなみに、ここに支障はないけどガッカリなバグがありますので紹介しましょう。 SepEndBy なのに、 sep.Seq でとってますよね。パターンマッチとしては { sep this }* です、sep が前ですね。本当ならば Many( this.FollowedBy( sep ) ) がSepEndByでとるべきパターン { this sep }* ですので間違ってますよね。

交互の繰り返しをとってるので逆に鶏と卵どっちが先かって話なんで気にしなければそれでいいってレベルですが、どっか他で SepEndBy を使う場合には気を付けましょう。

んで、中身は分かったので TDD です。

Lexer のテストは文字列を渡して Tok の token プロパティに指定の値が入るかが確認内容になります。

それがすんだら delimiter に指定するパターンと合わせて Lexeme を通すと文字列はTok[]になりますんで delimiter で無視されるべき物が Tok[] に拾われてない事、Tok[] に拾われるべきものが拾われてる事を確認します。

確認する為には呼ばないとね!って事で呼ぶ方法ですが、Grammer のParser<Expression> の呼び方と結局は一緒です。Lexer を呼べば Tok が帰ってくるし、Lexemeを呼べば Tok[] が帰ってきます。

            // Lexer のテスト
            Tok tok = Parsers.RunParser(“100”, Calculator.lNumber, “test”);
            Assert.IsInstanceOfType(tok.Token, typeof (double));
            Assert.AreEqual(100.0, tok.Token);
            // Lexeme のテスト
            Tok[] tokens = Parsers.RunParser(“100 200”, Calculator.lexeme, “test”);
            Assert.AreEqual(2,tokens.Length);
            Assert.IsInstanceOfType(tokens[0].Token, typeof(double));
            Assert.IsInstanceOfType(tokens[1].Token, typeof(double));

簡単に TDD できますね。やったね。

という訳で 本日はNParsecでの字句解析でした。

ここまでの内容で出てくる Tok[] とかからそのまま出力を作れるなら(構文的な意味での再マッピングが必要ない単純な字句解析であれば(CSVの読み込みとか))これだけで十分に役に立つよねと!

みなさんの消化不良を防ぐために、構文解析編については数日後に、ではでは。

NParsec+ …で Excel を…CLI…(3) NParsec で Tokenizer をTDD


ってわけで、Pattern での切り出し範囲とかをTDDしたら次は Tokenizer です。

Tokenizerの役割としては Pattern で指定された範囲を Parser にとって意味のある形式にすることと、その分類のタグ付をすることです。

さて、Pattern の記述はちゃんと仕様を見ましたか、Excelの字句仕様をちゃんと見てPatternを書いてる人は以下の numeric-constant の仕様が引っかかるに違いありません。

見たい人は ECMA のサイトからダウンロードできるドキュメントにありますんで、ダウンロードしましょう。(Standard ECMA-376)

式の字句構造の詳細は ECMA-376 1st edition Part 4 にあります。3.17 Formulas-3.17.2 Syntax がその定義です。

という訳で Excel の変態っぷりとおつきあいするのが始まりです。

numerical-constant:
    whole-number-part [ . ] [ exponent-part ]
    . fractional-part [ exponent-part ]
    whole-number-part . fractional-part [ exponent-part ]

Excelの式では字句仕様として 小数点から始まる浮動小数点表記を認めるんですね。また、10.e2 等、少数点下に数字がなく、いきなり exponent-part が現れるパターンを許しています。

また NParsecデフォルトの exponential の実装は

    public static Pattern IsExponential () {
        return Patterns.Sequence (
            Among (new char[] { 'e', 'E' }),
            IsChar ('-').Optional(),
            IsInteger ());
      }

となってます。一方 Excel は

exponent-part:
  e [ sign ] digit-sequence
  E [ sign ] digit-sequence

sign:
  +
  –

これもあいませんね、 + を許さなければいけないです。

これは上記をもろもろ踏まえてパターンを書くとこうなります。

        internal static readonly Pattern digits = Patterns.InRange('0', '9').Many(1);
        internal static readonly Pattern exponentPart = Patterns.Sequence(
              Patterns.Among('e', 'E'),
              Patterns.Among('+', '-').Optional(), digits);
        internal static Pattern wholeNumberPart = Patterns.InRange('0','9' ).Many(1);
        internal static Pattern numericalConstant =
              Patterns.Or(Patterns.Or(
                  Patterns.Sequence(digits, Patterns.IsChar('.').Optional(), exponentPart.Optional()),
                  Patterns.Sequence( Patterns.IsChar('.'),digits, exponentPart.Optional())),
                  Patterns.Sequence(digits, Patterns.IsChar(','), digits, exponentPart.Optional()));

んで、こういう変態文字列を CLR の double.ToString に与えた場合が怖いので、 numberTokenizer を実装します。

        internal static Tokenizer numberTokenizer =
              (src, begin, len) =>
                  {
                      string substring = src.Substring(begin, len);
                      if (src[begin] == '.') substring="0"+substring;
                      substring = substring.Replace(".e", ".0e");
                      return double.Parse(substring);
                  };

ドウセ短い文字列なのでコピーとか気にしない。って実装ですが神は細部に宿るんで気になる人はもっといい実装考えてください。

という訳で、こいつはフィールドにラムダが入ってるだけなんで、テストメソッドからガンガン呼んでテストできますね。Pattern と Tokenizer はこんな感じでTDD進められます。

Assert.AreEqual( (double)12.0, numberTokenizer( “aaa 12”,4,2 ));

その他 Excel が許す物を文字列として書いてパース結果が期待値とあうかをテストすればOKですね。パターンマッチ結果をもらう部分なんで、パターンが match しないような変な文字列での挙動をテストする必要性はありません。

んでこの状態で ExpressionTree な実装おかしくなりましたよね。

pNumber が OnDecimal のままだと doubleに反応しないからです。OnDecimal でやっていた pNumber の文字列変換処理は Tokenizer に移っていますので、 pNumber の定義を以下に書き換えます。

        private static readonly Grammar pNumber = Terms.OnToken<double,Expression>(
              (from, len, data)=>Expression.Constant( data ));

これであなたのパーサーは Excel が受け入れる形式の浮動小数点値を受け入れて計算するパーサーになりました。

後は文字列リテラル、boolリテラル等のリテラル処理をちゃんとするのと、識別子とか(セル範囲の文字列とか、関数名)をパターンを用意して取り出すようにすると Excel 式のパースの前半、Lexical Parsing (Scanner/Tokenizer) としてはデリミタを除いて実装完了になります。

次回は Lexical Parsing のまとめとして、Lexeme とデリミタの処理についてです。

NParsec+ …で Excel を…CLI…(2) NParsec で Lexial Pattern をTDD


ぶっちゃけて言うと、NParsec のサンプルコードはTDD的な意味でイケテないです。

関数型言語でコンソールで結果がパタパタ出るのをそのままで置き換えるとしたら、いろんな要素宣言はどこに置くかって言ったら、当然にクラススコープでしょう、それを Parser プロパティの getter の中に置いちゃってるからどうにもなりません。

とりあえず中にある物を全部一回クラススコープに置きます。Field Initializer は記述順に動くことになってますので実行順序の問題とかは起こらないです。

ほんと?っていう人は C# Language Specification の 10.5.5 を見ましょう。

C:\Program Files(x86)\Microsoft Visual Studio 10.0\VC#\Specifications\1041

に規定でインストールされているドキュメントファイルです。

CSharp Language Specification 10.5.5 変数初期化子

10.5.4 で説明されている既定値の初期化は、変数初期化子を持つフィールドを含めて、すべてのフィールドに対して実行されます。したがって、クラスが初期化されると、そのクラスのすべての静的フィールドは最初に既定値に初期化され、その後、静的フィールド初期化子が記述順に実行されます。同様に、クラスのインスタンスが作成されると、そのインスタンスのすべてのインスタンス フィールドは最初に既定値に初期化され、その後、インスタンス フィールド初期化子が記述順に実行されます。

ちゃんと記述順に実行されるって書いてあるよね。

唯一の実行文である lazyExpr[0] = pExpr の前までをクラススコープでのフィールド定義とその初期化子に移します。

image

赤いニョロニョロの所を ReSharper でQuickFixする事のMake field ‘…’ static 連打です。(ReSharper無い人は頑張って static を打ち込め)

image

これでテストを書き加える事ができます。フィールド見てテストするって感じで… private だよ、って言われたら Make field ‘…’ internal でReSharper さんよろしく。(ReSharper無い人は頑張って internal を打ち込め)

image

って感じで、Pattern のテストはMatch メソッドを文字列を指定して呼び出すことの、想定されるマッチ長でテストを書きます。マッチしちゃいけない時はMISSMATCH( int で-1) が返されるようにします。

後は Pattern の書き方ですが、 Patterns には以下のメソッドがあります。

 

All( params Pattern[] pps ) パラメータで指定されたすべてのパターンにマッチする範囲を返します。

(AllPatternをReSharperで2回クリックでこんな結果。)

foreach (int l in
pps.Select(t => t.Match(underlying_text, starting_index, ending_index)))
{
    if (l == MISMATCH)
        return MISMATCH;
    if (l > ret)
        ret = l;
}

Enumerable.TakeWhile( l=>l!=MISSMATCH ).Aggregate( int.MaxValue, Math.Min )…としたい所なんですが TakeWhileはbraking した要素を返さないんでアレです。

拡張メソッドを作ってリファクタリングするかは各位にお任せ。

拡張メソッド追加で TakeWhileWithBrakingElement を作れば一行になりますね。

IsChar( char ch ) 指定された文字とマッチします。

InRange( char ch, char ch ) は指定された範囲とマッチします。

IsString( string pattern) 指定された文字列とマッチします。

Regex(Regex ) / Regex(string) 正規表現とマッチします

HasAtLeast(int n) 入力に残り文字数がn文字以上あればマッチします。

HasExact( int n) 入力に残り文字数がちょうど n文字あればマッチします。

Eof()  終わりにマッチします(HasExact(0)のエイリアス)

NotInRange( char c1,char c2 ) 範囲外の文字にマッチします。

Among ( params char[] cs) パラメータで指定された文字とマッチします。

NotAmong( params char[] cs) パラメータで指定された文字以外とマッチします。

Or( Pattern pp1, Pattern pp2) 二つのパターンの長い側のマッチ長を返します。

Repeat( int n, CharPredicate cp) 指定文字条件の n 文字の繰り返しにマッチします。

Many( int n,CharPredicate cp) 指定文字条件の n文字以上の繰り返しにマッチします。

Many( CharPredicate cp) 指定文字条件の 0 文字以上の繰り返しにマッチします。(存在しなかった場合にはマッチ長0が返されマッチ成功になります)

Some( int min,int max,CharPredicate cp) min文字以上、max文字以下の文字条件へのマッチを行います。

Longer(p1,p2) /Longest( params Pattern) 指定されたパターンの中で最長のマッチを返します。

Shorter/Shortest 最短のマッチを返します。

Never 常にミスマッチを返します。

Always 常にマッチ長0を返します。

IsWord() 正規表現 [a-zA-Z_][0-9a-zA-Z]* とマッチします。

…長くなってきたので割愛(飽きてきたともいう)

後は Pattern の Seq で連接だって知ってればいいんじゃないかな!

 

次回は Tokenizer でトークンの切り出しをします。

NParsec + Open XML SDK で Excel を Managed CLI Language に(1)


ちょっと、奥さん聞いてよ。

JParsec – NParsec Tutorial

の一番上の downloaded here でとったソースと、一番したのフルコード

The final parser code is as following: …をべたっと cs ファイルに張り付けて

Binary, Unary, Grammar の double を System.Linq.Expressions.Expressionにする。

plus の delegate ( double a,double b ){ return a+b; } を Expression.Add に…それぞれ Expression のビルダ関数にマップする。

Grammar p_number = Terms.OnDecimal<double> を Terms.OnDecimal<Expression>にして、 return Expression.Constant( double.Parse(s) ); にする。

それを

[TestMethod]
public void TestMethod1()
{
    var calculator = new Calculator();
    var exp = Parsers.RunParser(“10+20”, calculator.Parser, “test”);
    var lambda = System.Linq.Expressions.Expression.Lambda(exp);
    var result = lambda.Compile().DynamicInvoke();
    Console.WriteLine(result);
    Assert.AreEqual((double)30,result );
}

でドライブすると Success!

やったねってことで、ちゃんとパースして、コンパイルして実行するって事ができたわけ。

ソースはこちら

でねでね、 Excel なんですよ。

どこの会社でもある事だと思うんだけど、日本語ベースで色々ゴニョゴニョお客とネゴされてきて、エンジニアからすると「で、いったいどんな式?」って聞き返す。Excel開いて、セルに数値入れて式設定して結果見ると何だか非常識な値になってたり、DB定義と突き合わせると明らかに式で見なきゃいけない物を見てなかったり、それを組み入れるとお客との折衝内容と食い違っちゃうトカトカで突き返すと「確認してきます」そして毎回言葉尻はちろっと変わるんだけど、結局いつまでも決まらない罠にはまる。

最後には「Excel シートを渡して、式設定して返して」って言ってそれが帰ってきてから「やっと俺が仕事できる」的な状況。

そんな事って普通ですよね。

んで、「俺が仕事できる」時に「仕事したくないでゴザル」モードだったり、Excelとコピペを繰り返す事に「お刺身にタンポポ(ry」な気がして「俺はこんなことをする為にこの職業を選んだんだっけ…」って思うじゃないですか。

おまけに常時「仕事したくないでゴザル」だったりする奴や、ちっとDB使わせると「SQLとかよくわからなくて」(お前、それ半年前にも言ってなかったか、進歩してないのね…)だって感じで( to be continue…)

あぁ、Excelですよ。

Open XML SDK 2.0 for Microsoft Office

こいつで、Excel ファイルを開くことができて、ブック、シート、セルの順で中身に下りて行って CellFormula プロパティ にたどり着けば、セルに指定された式にたどり着くわけです。

やったね!ってわけで、この CellFormula を NParsec でパースして、式木相当のオブジェクトを構築して、それを元に T4 でコード生成すれば Excel の Cell 相当のプロパティを持って、設定した計算式での計算処理を持ったクラスができちゃうわけですね。

これで「仕事したくないでゴザル」に「特に仕事は無いでゴザル」って言えるじゃん。

顧客との折衝担当が Excel ファイル持ってきたら「やっと決まったのかね」とか上から的にいって「ぽちっとな」すれば良いわけですね。

素晴らしい生産性の向上!これで中々決まらなくても大丈夫だね。

いいか、「まだ決めなくても大丈夫と言ってる間は絶対に決まらないんだ、結果として最後に決まった事に矛盾が出た場合に解決する余裕まですべて食いつぶされるんだ」。

ま、そんなわけで、こんなもんが有ると良いねという題材なので作っております。& NParsec関係は情報少ないっていうか皆無な感じなんで実際の作成時にTDDする方法とか色々絡めて連載しようかねーってことでタイトルの(1)がついております。