概要

■概要

1. 背景

2. 目的と構成

参考資料・リンク集

←目次へ戻る

2006年6月19日 13:59 更新

1. 背景

コンピュータが発明されて以来、その上で稼働させるための「仕事」の内容を記述する「プログラム言語」は重要である。MPU（Micro Processing Unit）やメモリ、バスや外部インターフェースで構成されるコンピュータハードウェアは、近年、ますます高速かつ大規模となってきている。ハードウェアを様々な目的に応じて柔軟に使用するためには、その目的に応じた、豊かな記述性を有するプログラム言語の整備が欠かせない。ユーザの要求の大規模化、高度化に伴い、要求仕様を満たすように実装可能、かつ再利用性の高いプログラム言語が開発されてきた。

「プログラム」は、一連の仕事の内容の有限列を、何らかの形式で表したものである。たとえば、C言語、Java言語などの高級言語を用いた場合、プログラマが与えられた仕様に従って、テキストエディタ等を用いて作成（コーディング）し、テキスト形式のファイルとして適当なファイルシステム上に格納するのが常である。

「一連の仕事の内容」は、稼働させるコンピュータシステムによって様々に変化する。いわゆる「パソコン」に搭載されているような大規模MPU上で稼働させる場合、外部インターフェースで接続されたネットワークデバイスやビデオ出力を制御するような「仕事」を行わせたい。他方、電子レンジやエアコンなどに組み込まれている小型MPU上で稼働させる場合、温度センサなどの入力に応じてインバータやモータの回転数を制御するような「仕事」を行わせたい。

プログラムを人間が記述するためには、人間が容易に判読できるような単語と文法で規定された言語を用意すべきである。数値の演算を行う関数名や、外部インターフェースに文字を出力するような命令は、できれば英単語に近い形の命令とパラメータの組の列で表現したい。プログラムの流れは、テキスト形式で左から右、上から下の方向へと進んで行くと読みやすい。

このような単語と文法で作成された「プログラムソース」を、対象とするMPU（あるいは仮想マシン）上で実行させるためには、そのMPU（あるいは仮想マシン）が有する命令やスタック、メモリ配置に応じた機械コードまたはアセンブリコードに変換する必要がある。この変換作業を行う応用ソフトウェアは「コンパイラ」と呼ばれており、現在のところ、大変よく用いられている手法となっている。コンパイラ方式の代表的なプログラム言語としては、FORTRAN, C, C++, Javaなどが挙げられる。

他方、プログラムソースに記述された仕事の内容を１ステップづつ直接に解釈しながら、対象システム上で逐次実行させるような仕組みも存在する。このステップ実行作業を行う応用ソフトウェアは「インタープリタ」と呼ばれており、異機種上で同一のソースプログラムを流用しながら実行させたいような場合に、大変よく用いられている手法となっている。インタープリタ方式の代表的なプログラム言語としては、BASIC, Perl, PHPなどが挙げられる。

上記のようなプログラム言語の翻訳作業あるいは逐次実行を行うためには、与えられたプログラムソースに対して、以下のような解析処理が必要である。

字句解析：命令やパラメータを表す単語（トークン）毎に区切る
構文解析：文法に基づいて、各トークンを節・葉に持つようなツリー（構文木）を構成する

構文木が構成された後は、コンパイラ方式／インタープリタ方式によって、以下のようにコード生成／逐次実行を行う。

コード生成：構文木を探索して、プログラム中のエラーを検出した後、対象システム向けの機械語あるいはアセンブリコードへ変換・生成する。
逐次実行：構文木を探索して、節毎に割り当てられた命令を解釈しながら実行を行う。

字句解析（lexer, tokenizer）や構文解析（parser, syntax analysis）を行うための様々なフレームワークが開発されている。代表的な lexer/parser generatorは、lex/yacc (GNU flex/bison) である。実際に、GNU gcc Cコンパイラをビルドする過程で、flex/bison を用いて (x)gcc コンパイラのための字句解析器と構文解析器を生成している。Javaのクラスライブラリには、トークン解析を行うための StringTokenizer class が存在する。また、プログラミング言語の他にも、XML形式で記述された構造化ハイパーテキストを処理するための構文解析ライブラリも各種存在しており、ユーザはそれらの既存ライブラリを適宜呼び出すことで、目的とする応用アプリケーションやサービスを実現することができる。

2. 目的と構成

この講義・演習マテリアルは、コンパイラ方式／インタープリタ方式でのソース翻訳を行う応用プログラムを構成する際に必要となる、字句解析ならびに構文解析の仕組みについて説明し、実際に lexer/parser の自動生成を行うツールキット（SableCC）を用いて演習を実施することで、字句解析／構文解析とコンパイラ／インタープリタへの理解を深めることが目的である。

この講義・演習マテリアルは、以下の各章で構成されている。

0. 概要

1. 字句解析（lexer）
2. 構文解析（parser）

3. 四則演算式の文法と解析
4. 四則演算式の実行

5. MiniBasicの文法と解析
6. MiniBasicの実行

7. SmallPascalコンパイラ

付録A. SableCCのインストール

CAI演習課題