こんにちは、Team C# の竹井です。なんかだんだんこの日記もカオスな感じになってきたのは気のせいだと信じたいですけど・・・。
はいそれで前回は、コンパイラというのはどんなものなのかについて簡単に説明したんですが、今日は実際にどのような処理を経てコンパイルが行われるかについて、具体的に少し踏み込んで説明します。プログラミング言語の種類やコンパイラの製作者によって少しずつ処理内容や順番がもちろん変わってくるのですが、大まかには次のような流れを経ます。
やー、こうみるとコンパイラというのは本当にたくさんの仕事をこなしています、一つ一つが立派な Wikipedia の項目になってしまうほど・・・。大まかに二分して、中間コード生成までをフロントエンド部と呼び、それ以降をバックエンド部と呼ぶこともあります。ちょっとこの blog では詳細を全部書ききれるほど体力があるか自信ないのですが、それでも僕自身がやってる仕事を追いかけながら、少しずつ解説出来ればいいなぁと思っています。ちなみにうちの班 Team C# のコンパイラは、バックエンド部の開発をちょうど今日明日から開始します。
それで今回のエントリでは、最初の字句解析と構文解析について説明しようと思います。この 2 つの処理、あわせて文法解析といいますが、これは基本的に入力されたプログラムの表面上の意味を汲み取るというのが仕事です。たとえば簡単のために、次のようなプログラムを見てください (こーゆー意味のないプログラムを作るのって色々つらいんですけどー・・・)。
y = 10 + x;
if y > 3.14 then
write("hello world");
else
stop();
こういう人間が書いたプログラムを、字句解析のレベルでまずは単語ごとに分解していきます。たとえばこんな感じ:
[識別子 (y)] [イコール] [整数値 (10)] [プラス] [識別子 (x)] [セミコロン]
[IF キーワード] [識別子 (y)] [大なり] [浮動小数点値 (3.14)] [THEN キーワード]
[識別子 (write)] [左括弧] [文字列 (hello world)] [右括弧] [セミコロン]
[ELSE キーワード]
[識別子 (stop)] [左括弧] [右括弧] [セミコロン]
これって、勘がいい人だと気づくかもしれないんですが、高校のころにやった古文の文法解釈に似てるんですよね。名詞、助詞、動詞の連体形があって助動詞がナンタラカンタラ・・・、ひたすら苦労した覚えがありますよ。今になってみれば当然のような分析の手段だと思いますが、この方法はとっても強力です。話を戻すと、このようにして、人さまのコードをコンピュータが読めるデータに直していくんです。ちなみに、プログラム中のコメントはこの段階でカットされます。
さて、単語 (トークンと呼びます) ごとに分解されたプログラムは、次の構文解析の段階でより構造的なデータに置き換えられていきます。たとえば、1 + 1 のような並びが出てきたら、これは数式だとみなすことができます。そこで、先ほど字句解析でトークン列の中で [整数] [プラス] [整数] を [式] というような一つの別のトークンに置き換えていけばいけばいいはずです。具体的に、先ほど出したプログラムを解釈するためには、たとえば次のようなルールがあれば [プログラム] というトークンから派生したものだと見なせます。
[プログラム] ::= [文]*
[文] ::= [識別子] [イコール] [式] [セミコロン]
[IF キーワード] [式] [THEN キーワード] [文] [ELSE キーワード] [文]
[識別子] [左括弧] [パラメータ リスト]opt [右括弧] [セミコロン]
[式] ::= [リテラル]
[識別子]
[式] [プラス] [式]
[式] [大なり] [式]
[パラメータ リスト] ::= [パラメータ リスト] [カンマ] [式]
[式]
[リテラル] ::= [整数値]
[浮動小数点値]
[文字列]
トークン右上の * は 0 回以上の繰り返しを示し、右下の opt は任意であることを示します。
このようにして、字句解析を通ってトークン列になったプログラムは、構文解析を通して一つのトークンに集約されます。ちょっと専門用語を使うと、上のような「あるトークンは別のトークン列の並びである」というルールを生成規則、逆にトークン列を見て派生元となるトークンへ戻す作業を還元、そして派生のおおもとになるトークンを開始記号 (この例では [プログラム])、といいます。言語学的にはこのような構造を持つ文法を文脈自由文法といい、僕の知る限りすべてのプログラミング言語の文法はすべて、この文法クラスに入ります。ちなみに、先ほどのようなトークン (言語学的には終端記号、非終端記号という呼び方をします) を開始記号に還元するアルゴリズムとしては、いろんな方法がありますが、LALR 法という手法が一番使われてます (詳細は省きます)。ちょっと詳しくなりすぎましたね、構文解析をすると、次のようなツリー構造のプログラムが得られます。
(Program
(Sentence
(Assignment
(Identifier y)
(Add
(Int 10)
(Identifier x))))
(Sentence
(If
(Greater
(Identifier y)
(Float 3.14))
(Function
(Identifier write)
(Parameters
(String "hello world")))
(Function
(Identifier stop)))))
このようなツリー構造のデータにした後、ここからさまざまな分析を行って、プログラムを機械が実行しやすい方法に変換していきます。僕のお仕事紹介、次回はいつになるかわかりませんが、たぶん次は型チェックとかについて説明出来たらと思ってます。
(後世の理情生でこの日記を読むような奇特な人へ) この記事の前半に出てくる文脈自由文法という概念については、4 学期の形式言語理論の授業で習います。最初にオートマトンについて勉強しますが、そのあと正規文法とよばれる一番簡単な文法クラスについて学び、そののちオートマトンを利用した正規文法の受理方法を学びます。そして、文脈自由文法が導入され、チョムスキー標準形という特殊な形式での表記と正規表現との関係などまでを最終的に学びます (したがって文脈自由文法もオートマトンで受理できます)。正規文法と文脈自由文法はチョムスキー階層では下位のレベルに属し、上位には文脈依存文法 (生成規則の左辺が複数の記号からなる) などがあります。また、後半に出てくる文脈自由文法の解析方法については、言語処理系論という 3 年夏の授業で、LL 法, LR 法, SLR 法を学んでから、最終的に LALR 法を学びます。そのほか同じく 3 年夏の Prolog 演習で、チョムスキー標準形の文脈自由文法についてのみ対応できる CYK アルゴリズムの実装を行います。参考まで。
おまけ、今日の僕、たぶんまじめに仕事してます。そういえば僕が登場したのは初めてかなー・・・、僕がいつもカメラ持ってるから、撮られることがほとんどないんですよね。別にいつもこんなスタイルなわけぢゃないです。
つづいて Session #3 理情生はよく twitter を使ってるんですけど、けっこうその中からも面白い (?) 発言がぽろぽろ出てきます。こんな感じ:
