「言語処理系論」の講義を聞いてみよう!

話の流れ

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

なお、以下の講義録ででてくる「レジュメ」は萩谷先生の御厚意によって、以下のFTPサイトに 掲載されています。
ftp://nicosia.is.s.u-tokyo.ac.jp/pub/staff/hagiya/kougiroku/compiler/

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

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

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

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

。。。

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

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

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

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

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

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

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

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

ここらへん混乱していてすみません。

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

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

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

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

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

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

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

では、字句解析の解説からはじめます。 (2ページ) トークンというのが字句なわけですが、このトークンとうのは何かというと、 文法の最小単位が終端記号なわけですが、構文解析にとっての終端記号というのがあるいみ トークンというわけです。 具体的にはどのようなものがトークンかというと、たとえばキーワードとか、ようするに if とか while とかっていうのは、文字列としてみればiとかhとかの文字なわけですが、 構文解析でみるとこれらはひと固まりのもので、つまりこれがトークン。 それから、区切り記号、括弧とか演算子、というような文法にとっての最小単位がトークンです。

それで、さっきちょっとでてきましたけど、 identifierとか定数は、終端記号なわけですが、そうすともとのソースコードの3とか4とか 15とかいった情報が消えてしまうので、これはどうするのかというと、保持するわけですね。 こういったくっついた値を字句値といいます。

では、トークン解析の実践ということで書いたものがつぎのlex. どういうことが難しいのかというと、べつに難しいことはなくって、

どういうものが識別子としてゆるされるのかっていうのは、普通は正則表現で簡潔にかけます。 例えば、英文字で始まる英数字列とかは、Emacs風の書き方をすると $ はこのように書けます。 だから、正則表現を認識できれば、字句解析はいいわけです。 トークンとしてはその他にキーワードとかありますけど、若干これはきたなくって、 まず最初に識別子を認識してからそのあとで特殊な識別子をキーワードとしてピックアップする という若干変則的な処理になります。 その他のトークンとしては、区切り記号とか演算子とかがあります。 それから空白文字はトークンではありません。ようするに適当にトークンとトークンを区切る 記号なわけですね。だからトークンとしては意味がないわけです。 それから空白文字がたくさんあってもそれは意味がない。 通常はトークンの間には複数個のトークンを挿入することができて、となりあう識別子 キーワード整数の間には、1つ以上の空白文字をいれなければならないわけです。 昔、FORTRANという変な言語があったんですが、FORTRANだと空白がいみがなくて、 今のFORTRANは良く知らないのですが、昔のFORTRANだと空白を全くいれなくても 解析できるというすさまじいものだったわけです。 あ、あとキーワードも認識の仕方もへんで、Cだとifという変数名をつかえないんですけど FORTRANだとifという変数でもつかえるんですね。 FORTRANは、なんか非常にかわった言語なんです。

字句解析は難しいことをいうとですね、なぜ正則言語という話がでてきたかというと、 字句解析をやるためには、正則言語を認識する必要がある、ということでそうすると オートマトンを作らなければならないとかそういう話になってきてしまうわけです。 もちろんそうやってオートマトンをつくってやることもできますが、普通はそこまで やる必要はあまりなくて、プログラムで書いても非常に簡単にかくことができます。 キーワードをどう認識するかとか演算子のかたまりをどう認識するかとかが重要なんだと おもいます。

レジュメの2ページに字句解析の実践ということで、えーこれはですね大変恐縮ですが Emacs-Lispで書いてあって、雰囲気だけあじわってもらえばいいとおもいますが、 以降にLL構文解析のプログラムがかいてあってそれと完結するようになっています。 字句解析とLL構文解析2つ組になって、x+y*x1+y2 というような式をちゃんと 認識できるようになっているということです。

レジュメ(thanks to Prof. Hagiya)

それで、字句解析はどうやるかというとむずかしいことはなくって、 あ、キーワードのテーブルとか演算子のテーブルとかはもちろん必要になります。 keyword-alist token-alist という変数が用意してあって、ここにキーワードとか演算子の テーブルがかいてあります。 ここには next-token という関数が用意してあります。 これはこの関数を引数なしでよびだすと、Emacsのカーソルの次のトークンを読んで トークンを返して、カーソルは次のトークンにすすむというものです。 だからこの next-token という関数を繰り返しよびだしていくと、次々とトークン値が 返ってきて、カーソルはすすんでいくというようになります。 どんなかんじかというと、まず最初に、空白もじを読み飛ばします。Emacs-Lisp だと簡単で skip-chars-forward と呼び出すと空白スペース改行をよみとばします。 そして読み飛ばしたあと、先頭の文字が何かをしらべて英文字ならどうする、数字ならどうする、 それ以外ならどうする、ということをやるわけです。 次の文字が英字ならば、英数字を読み飛ばして、というか先にすすんで、そこまでに読んだ 英数字を切り出してきて、キーワードの連想リストをしらべます。 ようするに、英文字だったら identifier ですから、英数字の列がキーワードか調べます。 連想リストにあればキーワードですから、キーワードに対応するトークンを返します。 連想リストになければ identifier ですから、この場合 identifier だというトークンと それに付随してそれの文字列を返すわけです。 例えば、

英字の場合は今の処理ですが、数字の場合の同じようですね。 numというトークンを返す。 そうじゃなければ、特殊記号がならんでいる場合ですから、特殊記号のならびを抜き出して きて、まあ1文字しかない場合もありますが、それをtoken-alistというところを 調べて、対応するトークンを返します。

たとえば、左括弧はlparとしてtoken-alistの中で登録されていますので、 トークンとしては左括弧に対してはlparと返します。 で、次にxというのを読むとidというトークンで、その付随した情報としてxという 情報がつきます。

以上まあ簡単な処理ですが。

トークン解析を難しいことをいうと、正則表現とかいう話になりますが、まあこれ 正則表現ですが、べつにオートマトンの知識がなくてもいいです。 ちなみにahoの教科書にはもう少し詳しく書いてあって、正則表現をどうやって 解析したらいいかという話も書いてあります。

字句解析の話はこれくらいでおわってしまうのですが、次に構文解析の話を やっていきます。 4学期にやったことをどのくらい覚えているか気になりますが、 えーと さきほどからいっているように、字句解析が返したトークン列を文脈自由文法 にしたがって構文解析をします。

それで、いろんな構文解析の手法があるのですが、まず最初にLL予測型構文解析 の話をします。

これはかけ算と足し算しかない例ですが、 こういう1こ1この規則を生成規則といいます。 左端は書き換え可能なわけですが、これは非終端記号です。 変数という言葉は誤解を招くので使いません。 非終端記号は生成規則で書き換えることができます。 あと開始記号というものがあります。 Eが開始記号と宣言してもかまいません。 ようするに非終端記号のどれか一つが開始記号として宣言されます。 この例では非終端記号はEとT。終端記号は(、)、それからid。これiとdという二つの 文字でなくて、ひとつの記号です。

こうやって繰り返し書き換えをおこなって、 Eからはじめて終端記号だけからなるものになる過程を

というように書きます。

あと、あとで出てきますが、最左導出とか最右導出とかいうはなしがあって、 この場合下線を引いた部分が書き変わるわけですが、この書き変わる部分が常に 一番左の非終端である場合を最左導出といいます。

最後に文法が生成する言語について。

この例の場合はTから導出できるwという終端記号列の集まり全体を、生成する 言語といいます。 このへんは、まあならったことがあると思いますが。

あと、いろいろな種類の記号についてまとめておきます。