[ 大堀研 | 教育内容 | 講義関連資料 | コンパイラ， ]

コンパイラ（東北大学 工学部 情報知能システム総合学科，2012年度）

授業予定（講義室，休講，試験日等）

アナウンス

平成24年12月22日． 型推論のコードをSML#1.20版用にアップデートしました． Makefileを用意した．コマンドラインでmakeコマンド を実行すれば，PTSアルゴリズムを実装した型推論システムができます．

評価

（主に）試験＋宿題（１，２回）による．

宿題

2012年度宿題１ 2013年1月10日提出

講義資料

講義の主旨と目的

（特に，講義を聴講せずに本スライドを参考にされる方への序文です． より詳しくは講義のスライドの「序文」を参照ください．）

本講義を聴講する者や本スライドを参考にする者の大部分は，実際にコンパイラ を書く必用も機会もないと思われる．しかしにも拘らず，「コンパイラ」は，主 に以下の２つの理由から，それらの人々を含む計算機科学を学ぶすべての人にとっ て重要な，計算機科学のカリキュラムの中心をなす科目の一つである．

  1. 計算の記述とその計算機での実現は，情報処理の基礎である．
  2. コンパイル技術の確立の研究の過程には，計算機科学の典型的なアイデ アや考え方が豊富に含まれている．
これらを技術が構築される過程を追体験しそれらアイデアと原理を理解すること は，将来の斬新な情報処理システム構築にとって本質的で重要な示唆を与えると 考える．

本講義では，「コンパイラ」の科目のこれら役割を念頭におき，コンパイラの基 本概念および基本原理，さらにそれらの基礎となったアイデアの理解を主な目的 とした講義設計を試みる．

これら基本概念や原理，さらにそれらが基礎とする本質的な洞察やアイ デアは，種々のコンパイラの教科書では必ずしもきちんと扱われていないことが 多いようにおもわれる．

一例としてコンパイラの主要技術である「LR構文解析」を取り上げてみよう． この技術は，Knuthによる画期的でしかも（多くの優れたアイデアがそうである ように）単純な以下の２つのアイデアを基礎としている．

  1. 最右導出の（最後の）一ステップは，オートマトンを使い再構築できる． 従って， オートマトンを繰り返し使うことにより （ある範囲の）文脈自由文法を解析できる．
  2. 過去のオートマトンの状態遷移をスタックに記録することに より オートマトンによる繰り返しスキャンのオーバヘッドを抑止できる．
このアイデアと原理の理解は，（一般に複雑で難解と受け取られている） LR構文解析アルゴリズムの理解を見通しのよいものにするばかりでなく，計算 機科学における問題解決の典型を追体験する上でも貴重である．

しかし残念ながら，（コンパイル技術の詳細の解説を目的とした）既存 のコンパイラの教科書では，例えばこの基本的な原理その基礎となるアイデアな どが極めて分かりにくい構成になっているように思われる．

そこで，本講義では，コンパイラの細な実装技術の紹介に重きを置くの ではなく，これら基本原理や基礎となるアイデアを理解することに目標とし，以 下の内容を扱う予定である．

これら原理を理解した上で，さらにコンパイラやプログラミング言語処 理系に関してより深い理解を得たいと思う者のために，我々が実際に開発を行っ ている実用を目指した 次世代関数型言語SML#のコンパイラ を例に具体的なコンパイルの内部構造の紹介や，SML#コンパイラから抽出した各 コンパイルステップのスケルトンの提供などをも行っていく予定である．

本講義や本資料に関する質問やコメントを歓迎します． 直接著者まで電子メール等でお送り頂ければ幸です． なお，本資料は随時改訂いたします．

東北大学電気通信研究所 大堀 淳

Tohoku University   RIEC   Ohori Lab.