コンパイラ (第 2 版)

コンパイラ定番の教科書、待望の改訂!
『情報工学入門選書 コンパイラ』を見直し、新たに第 2 版として発行するものです。
プログラミングの基礎知識のある人を対象とし、「コンパイラを構成するアルゴリズムの理解」「コンパイラ作成支援 (yacc、lex) ツールの理解」「コンパイラを自分で作成できる」を主たる目的としています。付録には、コンパイラの作成演習と実例を示しています。

『コンパイラ 第 2 版』 (辻野 嘉宏 著、オーム社、2019 年 12 月刊) は、プログラミング言語のソースコードを機械が実行できる形へ翻訳するコンパイラーについて、その中身を構成するアルゴリズムと作り方を順に学ぶ教科書です。版元の紹介文によると、本書は『情報工学入門選書 コンパイラ』を見直して第 2 版として発行したもので、プログラミングの基礎知識のある人を対象に、「コンパイラを構成するアルゴリズムの理解」「コンパイラ作成支援 (yacc、lex) ツールの理解」「コンパイラを自分で作成できる」を主な目的に掲げています。版元は読者として情報系の大学学部生や高専生、教員と、コンパイラーをより詳しく知りたい、作ってみたいエンジニアを挙げ、難易度の目安を中級としています。

「言語処理系とは」から「最適化とそのほかの話題」まで全 9 章

本文は全 9 章と付録 2 本、参考文献で構成されています。第 1 章「言語処理系とは」でコンパイラーの役割と基本的構造を押さえたあと、第 2 章「形式言語と形式文法」で正規表現、有限オートマトン、文脈自由文法とそれらの関係を扱います。第 3 章「字句解析」は EBNF 記法による字句の定義から非決定性有限オートマトン、決定性有限オートマトン、DFA の状態最小化へと進み、第 4 章「構文解析」は下向き構文解析と予測的構文解析 (LL 構文解析) に続いて、LR 構文解析アルゴリズムと SLR (1)、正準 LR (1)、LALR (1) の各構文解析表を取り上げます。第 5 章「型の検査と表管理」は型式の等価性や型変換、多重定義、記号表を、第 6 章「実行時環境」は駆動レコード (アクティベーションレコード) や手続き呼び出し、引数の引き渡しを扱います。後半の第 7 章「中間コード生成」と第 8 章「目的コード生成」では制御文や式の翻訳、基本ブロックとフローグラフ、バックパッチングが扱われ、第 8 章には RISC プロセッサーについての節もあります。第 9 章「最適化とそのほかの話題」は覗き穴最適化、大域的最適化とデータフロー解析の概要、誤り処理で締めくくられます。全 9 章の末尾に演習問題があり、付録 A は「コンパイラ作成演習」、付録 B は「サンプルコンパイラ」です。版元のサイトでは、本書で使うサンプルコンパイラーのプログラムファイルが購入者向けに配布されています。

字句解析と LR 構文解析を自分で組む意味

コンパイラーの学習で多くの人がつまずくのは、構文解析の理論と実際に動く処理系とのあいだの距離です。字句解析では、識別子や数値といった字句の形を 正規表現 で記述し、それを有限オートマトンに変換して入力を一文字ずつ読み進めます。構文解析では、文脈自由文法で書いた規則から解析表を作り、トークンの並びが文法に合うかを判定しながら構造を組み立てます。LL 方式は規則を先頭から予測的に展開するため手書きの再帰下降解析と相性がよい一方、左再帰を含む文法はそのままでは扱えません。LR 方式は入力を読み進めながら還元していく上向きの方式で、扱える文法が広く、yacc が生成する構文解析器は LALR (1) に基づいています。lex が字句解析器を、yacc が構文解析器を生成する道具なので、解析表の作り方を一度自分の手で追っておくと、生成系が出す衝突の警告や生成されたコードの振る舞いを読み解けるようになります。

構文解析の先にも難所は続きます。実用的な処理系の多くは、解析の結果を 抽象構文木 と呼ばれる木の形で保持し、その木をたどって後段の処理を進めます。同じ演算子が整数と浮動小数点数で別の処理になる場合や、暗黙の変換をどこで挿入するかの判断は意味の検査の段階で決まり、実行時には手続きを呼び出すたびに局所変数や戻り先を収める領域を確保して、呼び出しが終われば解放する管理が要ります。機械語を生成する段階では限られたレジスターと命令の選び方が性能を左右し、最適化はプログラムの意味を変えないことを保ちながらその出力を改善する工程です。本書はこれらを第 5 章から第 9 章で順に扱います。

プログラミングの基礎から自作の処理系へ進む読者に

前提知識は、版元の紹介文が示すとおりプログラミングの基礎知識です。形式言語と有限オートマトンの基礎は第 2 章で本書の中で扱われます。一方で、目次に挙がるのはコンパイラーの各工程のアルゴリズムと作成演習であり、GCC や LLVM のような既存の大規模な処理系のソースコードを読み解く章や、実行時コンパイルを扱う章はありません。低レイヤーの分野全体からどの本を選ぶか迷っている場合は、OS と低レイヤーを学ぶ技術書の選び方 で領域ごとの入口を確かめておくと選びやすくなります。

講義の教科書としてコンパイラーの工程を一通り押さえたい学生や、yacc と lex を使って小さな言語の処理系を自分で組んでみたいエンジニアにとって、アルゴリズムの理解からサンプルコンパイラーと作成演習までを一冊で通せる本書は、手を動かした分だけ処理系の見え方が変わる一冊です。