本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

実際の授業をいくつか文書におこしてみました。先生方の仮想講義を体験してみてください。情報科学科の講義は90分授業です。午前中の講義は10時15分から、午後の講義は13時から始まります。14時45分からの講義がある曜日もあります。

言語処理系論 | 細谷 晴夫
開講時間:木曜2限 | 1
シラバス
コンパイラを含む言語処理系の構築のための理論と技術を学ぶ。古典的技法である構文解析、コード生成、最適化などを網羅し、より現代的な関数型言語やオブジェクト指向言語の実装技術、ガべージコレクションなどにも触れる。
概要
この講義では、コンパイラを作成するためのノウハウについて学びます。実際的なコンパイラで用いられている構文解析や最適化の方法およびそのための知識を習得することが目標です。ここで学んだ知識は、主に6学期のCPU実験で生かされることになります。CPU実験では、CPUのアーキテクチャを構成するだけでなく、そのアーキテクチャのためのコンパイラを作成することも課題の一つとなっているからです。
授業の内容について
コンパイラとは、人間が書いたプログラミング言語をコンピュータが直接理解できる機械語に翻訳するプログラムのことです。すなわち、プログラムのソースコードを読んでそれを解釈し、機械語の命令列に変換するのがコンパイラの仕事です。授業では、ソースコードを読み込んで機械を出力するまでに一般的なコンパイラが行う作業のほとんどを、実際にコンパイラが処理を行うのとほぼ同じ順番で扱ってゆきます。

コンパイラが最初に行う作業は、プログラミング言語で書かれたコードを読み込んでそれを文法的に解釈することです。ここで、4学期に形式言語理論で学んだ正規文法や文脈自由文法というものが登場します。

まずコンパイラはコードを字句に分解します。これは「本日は晴天なり」という日本語を「本日」「は」「晴天」「なり」という四つの単語に分けるようなものです。多くのコンパイラはこの作業を正規文法に基づいて行います。予め定義された正規文法に合致する部分をそれぞれ字句として取出すのです。これは形式言語理論で学んだオートマトンの理論を用いれば難しいことではないので、授業でもあまり深くは触れられません。

次にコンパイラが行うのは、構文解析です。上の日本語の例でたとえるなら、「本日」「晴天」が名詞であることとか、「本日は」が主語で「晴天なり」が述語であることなどを見分けることだといえます。この作業は、字句の列を文脈自由文法に当てはめてゆく作業になりますが、字句解析よりもはるかに難しいものです。これは、字句解析で用いられている正規文法よりも、構文解析で用いる文脈自由文法の方がより複雑な文法を定義できるというところによります。

形式言語理論では、文脈自由文法を解釈するアルゴリズムとしてCYKアルゴリズムというものを習いますが、実際のコンパイラは構文解析にこのアルゴリズムを使いません。というのも、このアルゴリズムは時間が掛かりすぎるのです。そのため、より速く解析できるように制限を加えた文脈自由文法を使います。授業では、文法にどのような制限を加えるか、そしてそれをどのようなアルゴリズムで解析するかについて、詳しく述べられます。すなわち、構文解析はこの授業のメインテーマの一つとなります。

さて、構文解析が済んだら、コンパイラは型チェックなどを含む意味解析を行った後、プログラムを中間コードというものに変換します。中間コードとは、その名のとおり元のプログラミング言語と機械語との中間に位置する言語です。そして、コンパイラはこの中間コードに対して最適化という作業を行います。

最適化とは、コンピュータができるだけ効率的に処理を行うように、コードを書き換えることです。例えば、「ここは同じ計算を何度も繰り返しているけど最初に一回だけ計算すれば済むよね」とか「この値は結局後で使われないからそもそも計算しなくていいよね」というようなことをコンパイラが判断して、コードを書き換えるのです。授業では、実際に使われている代表的な最適化技法をいくつか紹介し、それの元になっている理論について説明されます。これがこの授業のもう一つのメインテーマです。

上に「後で使われない値は計算しない」という例を挙げましたが、ある値が結局使われないことをコンパイラはどのようにして知ることが出来るのでしょうか。それを知るためには、どの値がどこで使われているのかを解析しなくてはなりません。これは、値の使われ方を示すデータフロー方程式を立てて解くことで求めます。すなわち、この最適化技法はデータフロー方程式の理論に基づいているわけです。

授業では、このような最適化技法のための理論として、他にループの帰納変数や上位関係について述べられます。

最適化が終わったら、コンパイラの最後の仕事は中間言語を機械語に変換することです。ここでも、効率の良い機械語を出力するための技法が存在します。例えば、複数の中間コード命令を一つの機械語命令に変換できる場合にどのように変換するのがもっとも効率的かとか、CPUのどのレジスタにどの値を入れるのがもっとも効率的かとかいったことがあります。

以上が大まかな授業内容です。理論的な話は多いですが、どれも実際にコンパイラを作るために応用されている理論なので、形式言語理論は抽象的な話ばかりでつまらないと感じていた人も、ここで言語理論が実際に使われている様を見ることができるでしょう。
授業の進行
授業では資料や教材などはほとんど配られないので、各々まじめにノートを取る必要があります。

10000円もする分厚い教科書がありますが、授業で直接教科書を参照することはありません。とはいえ授業で触れられないこともたくさん載っているので、CPU実験でコンパイラ係をやる人やコンパイラ作成に興味がある人にとっては必需品です。

月に一回程度、レポート課題が出ます。課題内容は過去の期末試験問題から指定された問題を解いて提出するというものです。習ったことがらを確認するための良い演習となります。(コンパイラに関する演習科目は5学期にはなく、CPU実験の一環として6学期に行われます)
試験について
試験問題は割りとシンプルで、主に用語の定義やアルゴリズムを書かせる問題や、実際に簡単なデータフロー方程式等を解かせる問題などが出ます。難しくはありませんが、授業でやったことをきちんと覚えていないと解けない問題です。
次のステップへ
CPU実験でコンパイラ係をやる人にとっては、この授業で学んだことは大いに役に立つでしょう。もっとも、授業で紹介される最適化技法の数は限られているので、高性能のコンパイラを作ることを目指す人にはこの授業で習うことだけでは物足りないかもしれません。

一方コンパイラ係をやらない人にとってはこの授業で学んだ知識はすぐには役立たないかもしれませんが、形式言語理論や離散数学で学んだ理論が実際にどのように応用されているのかを知るための良い実例となるでしょう。