あなたのIDEがどうやって構文エラーを検出しているのか、考えたことはありますか？ コードを構成する文字の集まりが、どのようにしてマシンに解釈されるのか、気になったことはないでしょうか？
私はエンジニアリングの学生時代にコンパイラを開発しました。そして、これは何人かの人にとって興味深いかもしれないと思ったのです。
このプロジェクトで得た知識を、皆さんと共有しながら自分でも思い出していきたいと思います。
もう少し背景を説明すると、3〜4人の学生で取り組んだこのプロジェクトは、手続き型言語Tigerを対象とし、言語理論とコンパイラの技術的な実装の両方を扱うものでした。
そもそもコンパイラの目的は、ソース言語（ここではTiger）をターゲット言語（ここではアセンブリ）へ翻訳することです。
そのために、一般的には次の4つの段階を経ます。
- Tiger言語を代数的文法（すなわち文脈自由文法）によって数学的に形式化し、その文法をパーサが正しく処理できるようにする（無限ループを起こさない、演算子の優先順位を守る、など）。
- 字句解析（正しく構成された「単語」）と、続いて構文解析（正しく構成された「文」）を、次のものを使って行う。
- 字句解析器（レキサ）：文字の並びからトークンを抽出する。
- パーサ：それらのトークンの構造を認識し、構文木を構築する。
- 意味解析を行い、「文」が意味をなしているかを検証する（型・名前空間・参照などのチェック）。
- 妥当な「文」からアセンブリコードを生成する（この段階だけで、時間的にはプロジェクトの後半すべてを占めます）。
これらの各段階を、複数の記事に分けて取り上げていく予定です。
そして今回はまず、文法の話から始めます。文法は最も短期間で構築できる部分ですが、だからといって最も重要でないわけではありません。
この記事シリーズを、理論と実践の講義にするつもりはありません（そのために必要な正確さはもう持ち合わせていませんし、私はこの部分ではなく技術的な部分のプロジェクトリーダーでした）。あくまで、コンパイラの中で実際に何が起きているのかを大まかに紹介するものです。
この文法に関する記事は、その理論的な側面と、網羅的に説明するために必要な前提知識のために、特に難解です。
そのため、あえて軽めの記事にし、数学的な原理には深入りせず、私たちのTiger文法から取った具体例で説明していくつもりです。
※本記事はフランス語から日本語へ Claude を使って翻訳しています。
Tigerとは？
細かい部分には立ち入りませんが、Tigerは次のような見た目の手続き型プログラミング言語です。
let /* The eight queens solver from Appel */
var N := 4
type intArray = array of int
var row := intArray [ N ] of 0
var col := intArray [ N ] of 0
var diag1 := intArray [ N+N-1 ] of 0
var diag2 := intArray [ N+N-1 ] of 0
function printboard() = (
for i := 0 to N-1 do (
for j := 0 to N-1 do (
print(if col[i]=j then (0) else (1)));
print(666)
)
)
function try(c:int) =
if c = N then (printboard())
else (
for r := 0 to N-1 do(
if row[r]=0 & diag1[r+c]=0 & diag2[r+N-1-c]=0 then (
row[r] := 1;
diag1[r+c] := 1;
diag2[r+N-1-c] := 1;
col[c] := r;
try(c+1);
row[r] := 0;
diag1[r+c] := 0;
diag2[r+N-1-c] := 0
)
)
)
in try(0) end
さらに詳しく知りたい場合は、プロジェクト開始時に提供されたドキュメントを参照してください。これは、私たちが文法を構築するうえでの唯一の資料でした（出典を参照）。
文法とは？
日本語を話すとき、私たちはあり得るすべての文を丸暗記しているわけではありません。
私たちが学ぶのは、単語とその言語の文法です。たとえば「文 = 主語 + 補語 + 述語（動詞）」のように。こうした構成要素と一般的な規則さえあれば、無限の文を作り出し、また認識することができます。
プログラミング言語もまさにこれと同じです。ただし1つだけ追加の制約があります。それは、文法がいかなる曖昧さも残してはならない、ということです。
その構文は、妥当なTigerプログラムとは何かを決定的に記述しなければなりません。そのために文法を形式化します。すなわち、生成規則のリストを作るのです。
要するに、ある料理がレシピ通りに作られているかどうかをロボットが判定できるような、一連のレシピを作りたいわけです（料理のたとえはここまでにしておきます）。
4つの構成要素
どんな文法も、4つの基本要素の上に成り立っています。
-
終端記号（terminal）：言語の「単語」にあたる、これ以上分解できない最小の要素（例：
if、+、数値INT、識別子ID）。 -
非終端記号（non-terminal）：「文法的なカテゴリ」。実際のテキストではなく、構造を表すラベル（例：
expr、expr_plus、declaration_list）。 -
生成規則：非終端記号がどのように構成され、どのような形を取り得るかを定義するもの（例：
expr_plus : ...）。 -
開始記号（axiome）：すべてのプログラムの出発点（
program）。
結局のところ、プログラム中に実際に現れるのは終端記号だけです。非終端記号は、言語の構造を記述するためだけに使われます。これらによって、葉が終端記号、根が開始記号となる木を構築できます。
生成規則とは？
例を挙げましょう。加算や減算を記述する生成規則は、次のように書けます。
expr_plus : INT ('+'|'-') INT ;
この規則は次のように読めます。
expr_plusは、1つの数値、それに続く+または-、そしてもう1つの数値から構成される。
たとえば、次の式は認識されます。
1 + 215 - 8
一方、次のものは
11 ++ 2
この規則には当てはまりません。
パーサ
文法を定義したら、次は、あるテキストがその文法に従っているかどうかを認識できるプログラムが必要になります。それがパーサの役割です。
私たちのプロジェクトでは、LL(1) パーサを使用しています。
具体的には、このパーサは次のように動作します。
- トークンを左から右へ読み取る。
- 開始記号から出発して、構文木を段階的に構築する。
- どの規則を適用するかを決めるために、1つ先のトークン（先読み / lookahead）を利用する。
実際には、LL(1) パーサはさまざまな仕組み（予測表、スタック、入力バッファなど）に支えられていますが、これらは次の記事で詳しく取り上げます。
構文木が構築されると、それを訪問者（Visitorパターン）で走査することで、コンパイラの後続の段階（意味解析、コード生成など）を実現できます。
LL(1) パーサは、比較的理解しやすく手作業でも実装しやすいため、教育の場で広く使われています。もっとも、現代のコンパイラはより強力な手法を用いることが多いです。
左再帰
生成規則が何であるかは見てきましたが、実際には、規則の集まりがいくつかの問題を引き起こすことがあります。
例として、Tigerリファレンスマニュアルから取った次の規則を見てみましょう。
expr : expr binary_operator expr ;
ここで binary_operator は、+、-、*、/、=、<>、<、>、<=、>=、&、| のいずれかになり得ます。
この規則は二項演算（たとえば 1 + 2 や a | b）を記述できますが、現在の形のままでは左再帰を含んでしまっています。
ある規則が、トークンを1つも消費しないうちに自分自身を参照するとき、その規則は「左再帰である」と言います。
問題は、私たちが LL(1) パーサを使っていることです。LLパーサは構文木を上から下へ（下降的に）構築するため、規則の左側から展開を始めなければなりません。具体的には、次のような関数になるイメージです。
fonction lireExpr():
lireExpr() # 規則によって課される最初の命令
lireOperateur()
lireExpr()
つまり、いちばん最初の命令は……lireExpr() を再び呼び出すことなのです。
まだトークンが1つも消費されていないため、関数は再び自分自身を呼び出し、さらにもう一度、と繰り返し、ついにはスタックオーバーフローを引き起こします。
パーサは終端記号に決してたどり着けません。
これを解決するために、文法を変形して左再帰を取り除きます。
たとえば、加算と乗算については次のようにします。
expr_plus : expr_mult (('+'|'-') expr_plus)?;
expr_mult : INT (('*'|'/') expr_mult)?;
今度は、パーサはまず終端記号（INT）を認識してから、必要に応じて式の読み取りを続けます。
たとえば式 1 + 2 * 3 に対しては、次のような構文木が得られます。
これで、無限ループに陥ることなく式を正しく認識できるようになりました。
さらに、おまけとして演算子の優先順位も手に入ります。生成規則の階層構造のおかげで、乗算が加算よりも先に認識されるのです。
結合性
しかし、まだ1つ問題が残っています。
新しい規則は確かに左再帰を取り除けていますが、今度は右に傾いた構文木を生成してしまいます。
たとえば、次の規則では、
expr_plus : expr_mult (('+'|'-') expr_plus)?;
次の式は
1 - 2 - 3
次のように解析されます。
つまり、
1 - (2 - 3)
しかし、これは通常期待される挙動ではありません。
算術演算子の多く（+、-、*、/）は左結合です。括弧がない場合、式は次のように解釈してほしいわけです。
(1 - 2) - 3
解決策は、この右再帰を取り除き、繰り返しを使うことです。
expr_plus : expr_mult (('+'|'-') expr_mult)*;
この規則は次のように読めます。
- まず最初の乗算を認識する。
- 続いて、「演算子と新たな乗算」の組を0回、1回、または複数回繰り返す。
構文木を構築する際、パーサは新しい演算のたびに、それをすでに構築済みの結果へと結びつけていきます。
すると、次のような木が得られます。
これはまさに次に対応します。
(1 - 2) - 3
この書き方には、したがって2つの利点があります。
- LL(1) パーサと互換性を保てる。
- 自然に左結合を生み出せる。
まとめ
Tigerリファレンスマニュアルに記載された、曖昧でLL(1) パーサと互換性のなかった規則から出発して、最終的に演算については次のようなLL(1) 文法が得られます。
expr_or : expr_and ('|' expr_and)* ; // 論理和（OR）
expr_and : expr_test ('&' expr_test)* ; // 論理積（AND）
expr_test : expr_plus (('='|'<>'|'<'|'>'|'<='|'>=') expr_plus)? ; // 比較
expr_plus : expr_mult (('+'|'-') expr_mult)* ; // 加算・減算
expr_mult : expr (('*'|'/') expr)* ; // 乗算・除算
こうして、次のような文法が得られます。
- 無限ループに陥らない。
- 演算子の優先順位を守る。
- 算術演算子および論理演算子（
+、-、*、/、&、|）の左結合を保証する。 - 比較演算子（
=、<>、<、>、<=、>=）の連鎖を、期待される挙動に従って禁止する。
ここでは演算しか取り上げませんでしたが、文法には関数、データ構造、ループなども含まれています。
私たちのプロジェクトでは、Tiger言語に対応する代数的文法の構成要素をすべて洗い出すために、手元にある唯一の資料を細部まで分析し、一文一文の解釈について議論を重ねました。
次回以降の記事では、この文法を作り上げる際に下した決定が、コンパイラの後続の段階にいかに決定的な影響を与えるかを見ていきます。
というのも、ここで理論的に確立したことはすべて、この後コードへと落とし込まれ、パーサや、解析を担う訪問者（Visitorパターン）、そして何よりアセンブリコードの生成を実装することになるからです！