=== 1996年4月10日 10:15 --- 理学部1号館 450教室にて ===

レジュメがありますが、これは授業にそってまとめたものですが、教科書として、エイホの有名な本があります。2冊組でかなりの量がありますので、授業で足りないこととかがあったら読んでみて下さい。
参考書には、東工大の佐々先生が書いた「プログラミング言語処理系」という教科書があります。岩波書店ソフトウェア科学第5巻です。
これもなかなかよい教科書ですが、エイホの教科書とは、内容的にはよく似ています。だいたい、コンパイラまわりの話というのは、かなり確立していて、どの教科書をみてもだいたい同じような内容だと思います。

あともうひとつ参考書プリントにあげられていますが、「インサイドGNUCコンパイラ」えーと、これはGNUのCコンパイラの中身について解説してあるもので、実際的なコンパイラをしるのに実践的で良い本でしょう。
しょうらいGNUCコンパイラを改造してなにかするということをやるかもしれません。

ということで、この講義ではコンパイラを中心に言語処理系の話をします。
えーと予備知識としては、プログラミング言語に関する常識的な知識、さすがにプログラムを書いたことがないというひとはつらいですけど、プログラムを書いて実行したことがある人なら、いいです。

それから、従来構文解析について詳しく解説していたのですけど、構文解析というのはようするにプログラミング言語のプログラムを構文にしたがって、解析して、構文的なエラーを解析したり、それから次の機械語を生成するための前段階でプログラムの構造を解析するというものですけど、それは、形式言語の知識は前提とします。
これは4学期のとき、有限オートマトンとか、文脈自由文法の話はやりましたよね?両方とも関係していまして、そのへんがそのまま使います。
とくに用語とかいっぱい使いますので。
目次のところにも書いてありますけど、LLとかLRとかそういう構文解析の手法があって、基本的なことなので解説しますけど、そのときに文脈自由文法というのがなにかわかってないと非常に困ってしまうわけです。
まあ、すぐにでてきますね。


[目次] で、どういう内容をやるかというのは、目次のところをみてもらうとわかるのですけど 今年はコンパイラにかぎらないで、もうすこしインタプリタとかそのへんの話をすこし するつもりです。
ま、コンパイラに限りますと、字句解析、構文解析があって、つぎに意味解析の話、中間コード生成、コード生成の話、それからデータフロー解析とコード改良変換、いわゆる最適化ですね、が内容です。
いいでしょうか。

今年はこのほかに、インタプリタとか実行時の環境の話をすこし補うつもりですけど、、 なにか質問あります?

。。。

[処理系] じゃあ、少し中身にはいっていきましょう。
まず最初にイントロというところです。
これみなさんご存じだと思いますけど、ようするに、プログラマが書いた原始プログラムとうのは、コンピュータで実行するためには、最終的に機械語に翻訳されて実行されるわけですけど、その原始プログラムから機械語に翻訳されるまでにはいろいろな言語処理系を用いるわけです。
まず、プログラマが書いた原始プログラムは場合によっては前処理系、プリプロセッサ というものに、通して、いろんな前処理がおこなわれます。
前処理というのはマクロを展開したりとか、定数を置き換えたりとかいうのが主なものです。
あと条件付き、C言語でいう ifdef とかですね。例えば、UNIXとかWindowsの環境では違う部分を補うものです。
ときには前処理ですごいことをやることがあって、C言語の拡張としてC++というのがありますが、処理系によっては、C++のコードをCのコードに翻訳する部分がある意味前処理となります。
だから、前処理系といってもいろいろな意味がありますが、ま、さすがにこれはコンパイラの一部と考えた方がいいかもしれませんが。

前処理をした原始プログラムはコンパイラにかけられて、コンパイラによって、直接機械語を出力したりアセンブリになったりします。
そのアセンブリコードが、アセンブラによって、いわゆる再配置可能機械語コード ようするにいろんな番地で実行できるような、いろいろな情報を含んだ機械語コードに なるわけです。
この再配置可能機械語コードが、ローダーとかリンクエディタとかいわれている処理系によって絶対機械語コードに変換されて、最終的に実行されていくわけです。
このとき実行時に必要となるライブラリを最終的にくっつけてプログラムが機械語として実行されます。

以上が、コンパイラを用いてプログラムを実行するときの流れです。

次に、コンパイラの中も、いくつかのフェーズからなりたっています。
コンパイラに入力さらた原始プログラムはまず字句解析ルーチンというで字句に変換されます。字句というのはあとで解説しますけど、簡単に言うと、、、プログラムというのはじっさいにはアスキーの文字列なわけですけど、この文字列がそのまま次の構文解析にかかるわけではなくて、これをもう少し意味のある固まりに分割します。
その固まりがトークンですけど、プログラムがトークン列になったときにはよけいな空白とかはなくってそれが構文解析にかけられるわけですね。
トークン列が構文解析部分に通されると、いわゆる構文木になります。

プリントに構文木というのが載っていますよね。

例:3 × 15

EとかTとかFが終端記号で、たとえばこんなスペースがはいったのがあったとして、この場合「3」と「かけ算」とそして1と5はまとめて「じゅうご」と解釈することにして「15」というトークン列になる、こういうのが字句解析です。
あ、すみません、この「3」というのは「number」という終端記号とするほうが正確ですね。3とか15とかいうのは「number」というトークンに付随した情報とみるのがいいですね。

[導出木] そうしてこのトークン列がどのように導出されるかを書いた物が、導出木です。

あ、これ絵で書きましたけど、実際に計算機のなかでは、ぐちゃぐちゃな構造になってるわけですけど。
文法からどのようにしてトークン列が導出されるかというのを絵に描いたのが 導出木。
それから、意味解析したりコード生成したりするためには、これまでの構造は必要なくて、もうちょっとこういう簡単なのでよい。

[構文木] これを構文木といいます。
純粋な構文解析だと、導出木をこういう構文木を生成することを指しますが、普通は、同時に意味解析も行ってしまって、コンパイラの次のフェーズである、例えば、中間コード生成とかにはこういった構文木の形がわたされるが普通です。
ここらへん混乱していてすみません。

ま、普通は、導出木というのは実際にはつくられるわけではないのですが、 純粋な構文解析の仕事というのは、こういった導出木を構文木に再構成するのが 構文解析の仕事。

意味解析というのは、構文解析が作り出す導出木を、もうちょっとプログラムの構造を反映した構文木にするといことです。まあ、型検査とか名前の検査とかするのが意味解析です。

次に、中間コード生成、ようするに機械語とソースコードの中間にいちづけられるような中間コードにするのが次のフェーズ。
なぜ中間コードというのがあるのかは、いろいろな意味があるのですが、一つの大きな 理由としては、コード最適化をやりやすくするためというのがあります。
つまり、ソースコードに対して直接コード最適化をするのはやりにくいし、機械語にたいしても直接的に最適化するのはやりにくいことがおおくって、ようするに最適化しやすいのが中間コード。
その他に、コンパイラのポータビリティー、ようするにいろいろな機械でコンパイラが 動くように、コンパイラを設計しているという意味もあります。

で、中間コード生成ルーチンで作られた中間コードが、コード最適化ルーチンで より効率がよいものになるわけです。効率が良いといのは、プログラムが小さくなるという意味もありますし、プログラムが速く実行されるという意味もあります。
さまざまな最適化をうけて、中間コードが中間コードに変換されます。

そして最終的に、最適化をへた中間コードがコード生成ルーチンで、機械語あるいはアセンブリコードになるわけです。

以上のようなフェーズがひととりの流れですが、各フェーズで共通して利用されるようなルーチンがありまして、記号表管理ルーチンとかがあげられます。

記号表の管理というのは、プログラムの中に現れている記号ようするに変数とかプログラム名とかそれから型の名前とか、プログラムの中に現れている識別子(identifier)を、記号表と呼ばれるテーブルに保持して、それを管理することです。
識別子に関する情報としては、例えば、変数であるならば、どこに記憶されているのか、あるいは型が何なのかといった情報が含まれるわけです。さらに手続きなどでは引数の型と個数とかが記号表に含まれます。
構文解析ルーチンが最初の記号表を作り出すわけですけど、意味解析はもちろん記号表を参照しますし、それからコード生成も、変数の記憶場所とかを参照するわけです。そんな感じで記号表言うのはさいしょから最後まで使われるわけです。


Next

 

〔トップページへ〕 〔言語処理系論の仮想講義のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 7 May, 1999