2014年2月17日月曜日

Raccを使って言語処理系作ってた

緒言


みなさま、あけましておめでとうございます(遅っ

しばらくブログの更新がなかったわけですが、その間に実は色々書きすすめていました(ということにしてください)。

さて、事の発端は、年末ぐらいに作ってたTwitterアプリ(?)のUpdateNameです。アカウントの名前の変更権を第3者に開放するという大変危険な遊びですが、これを実装した後にこんなことを思いました。

『Twitterのタイムラインからプログラム実行できないかなーwwwwwwwwwwwwwwwww』

でも、ヘタなコードを自由に実行できる状態では大変危険です。ではどうするか。

――よし、システムに害のない安全な言語作ってしまおう。

はっきり言ってRubyのサブセットを処理できるような処理系でも作ればよかったのですが、それはあんまりやる気が出なかったので、言語から作ることにしたのでした。

ということで、今回の記事ではその作った言語の話と、Rubyで構文解析器を生成できるRaccの紹介です。



現物のインタプリタはご使用いただけます


こちらのウェブページで公開しております。
言語処理系はRubyで実装しています。ここでダウンロードできるのはRubyのソースコードです。実行にはRubyの実行環境が必要です。
スパゲッティですが許してください。

TLang Home

バグなどあれば実行コードを教えていただけると有難いです。



言語処理系実装の話


学校の授業や技術書でつまみ食い的に得た知識ですが簡単に実装の話をします。

コンパイラやインタプリタの処理はだいたい次のような流れで行われます。

字句解析 → 構文解析(構文木作成) → 型解析 → (中間コード生成) → 実行orコード生成

インタプリタは実行器なのに対しコンパイラは翻訳器なので、コンパイラのほうが作るのは一般に難しいです。今回作ったのはインタプリタです。
できたものはかなり自己流の要素が含まれているのですが、処理の大体の流れはこんな感じです。

字句解析 → 構文解析・構文木作成 → (型解析) → 実行

僕のインタプリタの場合、型解析というか型チェックは実行時に行います。そういう意味では動的型付け言語。
ただし、関数の定義の時には引数と返り値の型推論(と言っていいのか)は簡単に行います。これは静的型付けなのか動的型付けなのか。

さて、ここからが本題です。

言語処理系実装で面倒くさいのが、構文解析です。
字句解析によるトークンの取得は、比較的簡単にできます。空白読み飛ばしや、演算子の判定などをうまく使って実装できます。もちろん、高速に動く優秀なものを作るのは簡単ではないですが。
あと、コードの操作的意味を定義して実行器を作るのは……。まあ、頑張るしかないです。頑張れば作れることにします。

問題は構文解析器です。これを作るには、文脈自由文法だとか非決定性プッシュダウンオートマトンがいるとか、非決定性プッシュダウンオートマトンは決定性機械に変換できないので現実には実装できないとか、実は正規文法とか決定性オートマトンで解析できるとかっていう話があるんですが、はたしてそれをフルスクラッチで実装できるのかという話。有体に言って面倒なのです。

そこで便利なのが、Raccです。



Raccを使うと構文解析器が簡単に作れるよ!


構文解析器生成系(パーサジェネレータ)として有名なものに、Yacc(Yet Another Compiler Compiler)があります。その名の通り、構文解析器の生成システム、コンパイラのコンパイラです。Raccは、これのRubyで使える奴です。

さて、このRaccですが、これさえあれば何でもできるのか、というと、そうもいかないような気がします。というのも、Raccを使うためには最低限『文脈自由文法』に関する知識が必要なように思われます。文の『導出』の概念がわからないと少々厳しい。

その話は熱く語れるほど僕は詳しくないので(逃)、ここでは割愛します。一応参考になるものとして、東北大学電気通信研究所 大堀研究室の講義資料として公開されているスライド(トップページ→講義関連資料→コンパイラ→講義スライド)を挙げておきます。



Raccの使い方


Raccは、文法ファイルを読み込んで、構文解析器を生成します。これがごく簡単な文法ファイル。



足し算引き算掛け算割り算余り算(?)、負符号、括弧を解析できます。これを用意して、

$ racc sample.y -o parser.rb

を実行すると、パーザ parser.rb が生成されます。文法ファイルの書き方は後程。
Raccがインストールされていなければ、

$ gem install racc

でインストールできたはずです。

さて、生成されたparser.rbですが、これは別途字句解析を行うコードを記述しておく必要があります。
例えば、使える文字は括弧()と演算子+-*/%、数字、変数名だけ、すべて空白区切り、という文字列のみであれば、こんなコードで字句解析から構文解析、構文木生成までができます。



実行例がこちら。拡大してみてください。



lex_parse_sample.rbのポイントとしては、パーザに渡すトークンの形式に注意してください。実行結果と見比べていただけるとわかると思いますが。1個1個のトークンは [種類, "文字列"] という組になっています。ただし演算子と括弧は、種類はそのまま文字列にしています。これは文法定義ファイルの中の演算子も文字列で表現されていることに対応します。一方、変数と整数については、 :var と :int というシンボルで種類を指定しています。これらは文法定義ファイル中の終端記号 var と int に対応します。

また、トークン列の最後には、コードの終わりを表す [false, '$'] を付けます。これが無いと構文解析でエラーになります。この部分に関しては、サンプルではパーザの文法定義ファイルの中に含めています。



文法定義ファイル sample.y の解説


1行目:パーザはクラスですので、クラス名を適当につけます。

2行目~6行目:演算子の結合強度です。prechighに近いほど強いです。また、leftというのは左結合を表します。右結合であればrightです。nonassocは結合方向無しです。

8行目:終端記号を定義します。サンプルでは var と int が終端記号です。ついでですが、開始記号は EXP です。

10行目~27行目:文法定義です。EXPは : や | の右側の式を導出する、という意味です。中括弧の中身は、各規則が発見されたときに行う処理をRubyで記述したものです。16行目の MINUS は、3行目の MINUS と対応していて、減算の - と区別するために名前を付けています。

29行目~39行目:inner以下に書かれたコードは、SampleParserクラスの中に記述されます。ここにメソッドを記述すれば、SampleParserクラスのメソッドになります。文法定義の中に記述したRubyのコードで、ここに書いたメソッドを呼び出すこともできます。



まとめ


以上、Raccの紹介でした。これで(比較的)簡単に、オリジナルの言語が作れますね!!(けっこう大変)

というわけで、 TLang をよろしくお願いします。

当初の目的は忘れた。

0 件のコメント:

コメントを投稿