kazuk は null に触れてしまった

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

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の読み込みとか))これだけで十分に役に立つよねと!

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

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。