ものがたり(旧)

atsushieno.hatenablog.com に続く

Ironyをいじってみた

Ironyについては以前ちらっとだけ紹介したこともあるのだけど改めて。

parser generator

.NETでプログラムを書いていて、テキストのパーサを作らなければならなくなることは割と普通にあるだろう。多くの場合はTextReaderを使って力技で書いて何とかするだろう。たとえばJSONくらいであれば、手作業で書いても難しくない。しかし、文法が複雑になってくると、たとえばC#のパーサを書けということになると、ある程度は状態遷移をロジックに任せると楽になる。

.NETで複雑なテキストパーサを書くのがどれくらい一般的なことかは分からないが、そういうものを実装するために使われるのがパーサジェネレータあるいはコンパイラコンパイラと呼ばれる仕組みだ。パーサジェネレータは、生成規則（構文）を所定の表記法で記述すると、それをもとにテキストパーサのコードを生成する。有名なのはCのコードを生成するyacc (yet another compiler compiler) だけど、その他にもいくつかの方法と実装がある。

多くはBNFのような構文で自分の文法ソースを記述するので、ひとつ覚えてしまえば（あるいは BNFが身についていれば）他の文法を覚えるのは多分そんなに難しくないだろう。ただ、生成されるコードは多くの場合は出力言語依存なので（たとえば yaccで生成されるのはC）、自分の求める言語、たとえばC#で書かれC#コンパイラでビルドできるパーサがほしければ、C#をサポートするパーサジェネレータが必要になる。

monoでmcsを実装するにあたって（つまり立ち上げの頃）、最初にMiguelが行った作業は、jayという Java用のyaccのようなものから、C#移植版の作成だった。僕らはそれ以来ずっとこのjayを使っている（たとえばRELAX NG compact syntaxのパーサやDataColumnの式のパーサはコレで書かれている）。antlrはJavaでも幅広く使われていて有名だが、C#もサポートしている。Coco/Rや grammatica, GOLD parserなど、C#をサポートする実装は多い。

Irony

パーサジェネレータでは、yaccのような構文を覚えないといけないので、気が引けるという人も少なくないかもしれない。そんな人でも比較的簡単に入り込めるのがIronyだ。Ironyは、分類上はyaccと同じ LALR(1)ということになって、おそらくパーサジェネレータの特性としては凡庸なもので、しかも機能的に完全とは言えないようだが、これの面白い点は、Ironyのサンプルを見ると分かるとおり、もう構文定義もC#で直接書いてしまおうというところだ。jay ではコードと構文が混在しているので分かりにくいし、C#のソースも別途ビルドしなければならないが、Ironyはその辺が楽だ。Ironyのソースはこんな感じになる:



NonTerminal if_statement = new NonTerminal("if_statement");

      ...

NonTerminal else_clause_opt = new NonTerminal("else_clause_opt");

      ...

if_statement.Rule = ToTerm("if") + Lpar + expression + Rpar + embedded_statement + else_clause_opt;

else_clause_opt.Rule = Empty | PreferShiftHere() + "else" + embedded_statement;

構文ツリーはNonTerminalと各種Terminalから構築されるのだけど、それらを演算子オーバーロードで簡単に連結してしまおうというのが、 Irony（や、僕の聞き及ぶ限りではgrammatica）の特徴だ。上記はC#の有効なコードになっている。Ironyの文法は Irony.Grammarというクラスから派生させ、そのRootプロパティにNonTerminalを設定してやることで、ツリーが出来上がる。

jay は古典的なyaccクローンなので、パーサの他にトークナイザを用意しなければならない*1 が、C#をサポートするようなモダンなパーサジェネレータにもなると、トークナイザを自動的にビルドしてくれるものも多い。Ironyも独自に Irony.Parsing.Parserというクラス名のトークナイザを提供している。僕がテスト的に書いた簡単なドライバコードはこんな感じだ。



var parser = new Parser (new ActionScriptGrammar ());

var s = File.ReadAllText (arg);

var pt = parser.Parse (s, arg);

foreach (var msg in pt.ParserMessages)

  Console.WriteLine ("{0} {1} {2} {3}", msg.Level, msg.ParserState, msg.Location, msg.Message);

これだけ。ちなみに、最近のビルドでは、パーサ生成の他にインタープリタモードなども提供しているようだ。

Irony のもうひとつの長所は、Irony.GrammarExplorer.exeという文法チェッカーのGUIで、これがあると、割と込み入った構文定義の間違いを、比較的簡単にチェックしやすい（確かGOLD parserなんかもこの種のGUIを提供していたと思う）。

Ironyには豊富なサンプルパーサが入っていて（他の実装でも多いものは多い）、適宜参考にしながら自分のコードを書けるのではないかと思う。もっとも、サンプルの完成度がどれほどのものかは疑わしい。ほとんどのサンプルはパーサだけでしかなく、解析後の構文ツリーが実用に耐えるものになっているかどうかも分からない。 C#のパーサのサンプルもあるが、LINQには対応していなかったりする。

使ってみた

ちょっと ActionScriptを勉強してみようかなと思ったことがあったので、とりあえずパーサを書いてみた（この時点でもうASの勉強には全然なっていない）。僕は普段jayを使うのだけど、今回はまあ実験みたいなものだ。で、どんなハマりどころがあるか書いてみる。ちなみにIrony のハマりどころではなく、一般的なハマりどころの話だと思う。

まず、C++やC#など、ジェネリック型に<Foo>を使う言語の場合、次のような記述を解析するところでハマるだろう。



Foo<Bar<T>> x = null;

ここでは >> という文字列が含まれているが、通常 >> はシフト演算子に使われている。トークナイザは通常は最長一致でトークンを返すことになるから、 >> は2つの > ではなく1つの >> として返されるだろう。これを解決するには、トークナイザがパーサの状態遷移と連動する必要がある。ちなみに0x年代には出そうもないC++0xでも、このような記述でも問題無く解決できることを要求している。

C#のジェネリクスの構文では巧妙にも回避されているが、一部の言語はそこまでエレガントに設計されていないので、ジェネリック型名の後に = が続き得る構文では、>= との競合の回避が必要になる。次の例はAS3のものだが、どハマりである（まあAS3のはジェネリクスとは言えないもののようだけど）。型名を後置する goにはまだジェネリクスが無いけど、どうなるかはちょっと気になる。



protected void X (a : Vector.=null)

Ironyの場合、パーサのトークンスキャナに対する操作を加えることもできる。C#パーサのサンプルがあるので、それを参考にすると良いと思う。と言いながら僕はまだ実装していないけど。

ジェネリクスの次にハマった例としては、次のような辞書リテラルのサポートがある。



if (b) x = {X:a, Y:b};

これがなぜ問題になったかというと、文法定義でそれなりに制約しておかないと、 { によって開始されるものが、式ブロックなのか辞書リテラルなのか、しばらく先まで読んでみないと分からないのだけど、IronyのようなLALR(1)だと1トークンしか先読みせず、足りなくなってしまうためだ。上記の例で if (b) の次が { だったら、きちんと式ブロックとして判断してもらわないと困る。これを実現するためには、単一の式のいずれも、辞書リテラルで開始されないようにする必要がある*2。そのためには、たとえば（多くの場合任意の式を受け付けるようにしているであろう）代入式の左辺値を、パーサのレベルで辞書ハッシュが入り込まないように限定すればよい。

ちなみに、この問題を解決するにはGrammarExplorerが便利だった。解析過程を状態遷移へのリンク付きで提示してくれるし、特定の状態での入力にどの生成規則が対応するかを知ることもできるので、これで犯人捜ししたのだ（代入式がどうのと書いているのは、それで判明したことだった）。

他にハマっている問題としては、式の最後が必ずしもコンマで終わらなくて良い（改行で終わっても良い）言語の場合に、曖昧になる文法が増えることなどがある。気が向いたらそのうち調べてみようと思っている。

〆

パーサジェネレータは複雑な文法があるところで、必ずしも万能薬になるわけではない。たとえば僕らはXmlTextReaderを作るのにjayを使ったりはしていない。手書きで作った方がパフォーマンスが良い。複雑な状態遷移が必要でなければ、手書きで作った方がいろんな意味ではやいかもしれない。

とりあえずパーサは何となくそれっぽいものが作れたので、今度はASTを操作するものがまともに作れるかどうか、その辺の観点でいじってみたいと思う。

*1:lexerとも言われる。yaccに対応する例がflex

*2:ちなみに多分それも方法としてはやっつけで、最終的にはLALR(1)を越えたトークンの先読みが必要になるようにも思う