1. Bisonの概念

この章では、Bisonの詳細を理解するのに欠くことのできない、 多くの基礎概念を説明します。 まだBisonやyaccの使い方を知らない方は、 この章を注意深く読むことから始めてください。

1.1 言語と文脈自由文法

Bisonが言語を解析するためには、その言語が 文脈自由文法（context-free grammar）で記述されている必要があります。 すなわち、1個以上の文法グループ（syntactic groupings）を定め、 その文法グループを部品から組み立てる規則を与える必要があります。 たとえば、C言語では、ある種のグループは「式」と呼ばれます。 式を作る規則の1つは、 「1つの式とは、別の式にマイナス記号を付けたものでもよい」かもしれません。 別の規則は、「1つの式とは、整数でもよい」かもしれません。 ここから解るように、規則はしばしば再帰的になりますが、 再帰を始めるための少なくとも1個の規則が必要です。

このような規則を人間が読めるように表現する、もっとも一般的な形式的な方法は、 バッカス-ナウア記法（Backus-Naur form）略して"BNF"です。 これは、Algol 60言語を定義するために開発されました。 BNFで表現された任意の言語は、文脈自由言語です。 Bisonへの入力は、本質的には、機械可読なBNFです。

すべての文脈自由言語をBisonで扱えるわけではありません。 LALR(1)だけを扱えます。 簡単に説明すると、ちょうど1個のトークンを先読みすることによって、 入力文字列の任意の部分を解析できる必要があるということです。 厳密に説明すると、これはLR(1)文法の説明で、 LALR(1)には簡単に説明できない追加の制限があります。 しかし、LALR(1)になれないLR(1)文法は、現実にはまれです。 より詳しい説明は See 節 Mysterious Reduce/Reduce Conflicts。

ある言語についての形式文法的な規則では、 文法的な単位またはグループを記号（symbol）と呼びます。 文法規則に従って小さい部分から組み立てられた記号を 非終端記号（nonterminal symbol）といい、 終端記号（terminal symbol）またはトークン型（token type）と呼ばれる ものに分解できます。 本書では、1個の終端記号に対応する入力の一部分をトークン（token）、 1個の非終端記号に対応する入力の一部分をグループ（grouping）と呼びます。

何が終端記号で何が非終端記号かを示すために、 例としてC言語を使います。 Cのトークンは、識別子、定数（数値または文字列）、さまざまな予約語、 算術演算子、区切り記号です。 C言語の終端記号には、「識別子」、「数値」、「文字列」、そして、 予約語、演算子、区切り記号のそれぞれに対する記号、 すなわち、「if」、「return」、「const」、「static」、「int」、「char」、 「プラス記号」、「開きブレース」、「閉じブレース」、「カンマ」、 などが含まれます （これらのトークンは文字に分解できますが、 それは文法の問題ではなく、字句解析の問題です）。

次の例は、トークンに分解されたCの関数です。

int             /* 予約語 `int' */
square (x)      /* 識別子, 開きかっこ, */
                /* 識別子, 閉じかっこ */
     int x;     /* 予約語 `int', 識別子, セミコロン */
{               /* 開きブレース */
  return x * x; /* 予約語 `return', 識別子, */
                /* アスタリスク, 識別子, セミコロン */
}               /* 閉じブレース */

Cの文法的なグループには、式、文、宣言、関数定義が含まれます。 これらは、Cの文法で、非終端記号、「式」、「文」、「宣言」、 「関数定義」として表されます。 完全な文法では、上記の4つの意味を表現するために、 それぞれの非終端記号について、数十個の追加の言語構築が必要です。 上記の例で、関数定義は、宣言と文を含みます。 文の中で、それぞれの`x'は式であり、 `x * x'も式です。

それぞれの非終端記号には、それがより単純な構成要素からどのように作られるか 示すために、文法規則が必要です。 たとえば、Cの文の1つであるreturn文について、 文法規則を形式ばらずに書くと、次のようになります。

「文」は、キーワード「return」、「式」、「セミコロン」から 作ることができる。

Cの各種の文について、「文」には多くの他の規則があるでしょう。

1つの非終端記号が、言語の全体を表現するように、 特別なものとして識別される必要があります。 これを開始記号（start symbol）と呼びます。 コンパイラでは、これは完全な入力プログラムを意味します。 C言語では、非終端記号「定義と宣言の並び」が、この働きをします。

たとえば、`1 + 2'は有効なCの式で、 Cのプログラムの有効な一部分ですが、 Cプログラム全体としては無効です。 したがって、Cの文脈自由文法では、「式」は開始記号でないとわかります。

Bison構文解析器は、入力としてトークンの列を読み、 文法規則を使ってトークンをグループにします。 もし入力が有効であれば、最終的な結果として、トークンの列全体が 文法の開始記号である1つのグループの記号に還元されます。 もしわれわれがCの文法を使うならば、入力全体は 「定義と宣言の列」の必要があります。 もしそうでなければ、構文解析器が文法エラーを報告します。

1.2 形式規則からBisonの入力へ

形式文法（formal grammer）は、数学的な構成です。 Bisonのために言語を定義するためには、Bisonの書式で文法を記述した Bison文法（Bison grammer）ファイルを書く必要があります。 See 節 Bison Grammar Files。

形式文法の中での1つの非終端記号は、Bisonの入力の中で、 Cの識別子のような、1つの識別子として表現されます。 expr、stmt、declarationのように、 通常、非終端記号は小文字で書きます。

終端記号に対するBisonの表現は、 トークン型（token type）ともいいます。 トークン型は、C言語で使われるような識別子であるかもしれません。 通常、非終端記号からこれらを区別するために、大文字で書きます。 たとえば、INTEGER、IDENTIFIER、IF、RETURN のように書きます。 言語の個々のキーワードを表す終端記号は、 キーワードを大文字に変換してから命名するべきです。 終端記号errorは、エラーからの回復処理のために予約されています。 See 節 3.2 記号、終端と非終端。

ある終端記号は、C言語の文字定数のような、1文字リテラルを表している かもしれません。 トークンがちょうど1文字である（たとえば、かっこ、プラス記号など）ならば必ず、 そのトークンに対する終端記号として、同じ文字を使うべきです。

終端記号を表す第3の方法は、何文字かを含むC言語の文字列定数です。 詳細はSee 節 3.2 記号、終端と非終端。

文法規則は、Bisonの文法の中で、もう1つの式を持ちます。 たとえば、C言語のreturn文に対するBisonの規則があります。 クォート（'）で囲まれたセミコロンは、文に対するC言語の文法の一部分を表す、 1文字のリテラルトークンです。 クォートで囲まれていないセミコロンとコロンは、 あらゆる規則の中で使われる、Bisonの区切り文字です。

stmt:   RETURN expr ';'
        ;

See 節 Syntax of Grammar Rules。

1.3 意味値

形式文法は、トークンを分類法に基づいてのみ、選びます。 たとえば、ある規則が`integer constant'という終端記号について言及するならば、 それは、文法的にそこに現れてよい任意の整数型定数を意味します。 その定数の正確な値は、入力が解析される方法と無関係です。 もし、`x+4'が文法的に正しいならば、`x+1'も、`x+3989'も、 同様に文法的に正しいのです。

しかし、いったん解析されれば、入力にとって正確な値はきわめて重要です。 プログラム中の定数として4と1と3989を区別できないコンパイラは、 役に立ちません。 そこで、Bison文法の中のそれぞれのトークンは、トークン型のほかに、 意味値（semantic value）を持ちます。詳細については、 See 節 Defining Language Semantics。

トークン型は、INTEGER、IDENTIFIER、','のように、 文法の中で定義される終端記号です。 これは、そのトークンが正しい位置に現れているか確かめ、 他のトークンとどのようにグループ化するか決めるために必要な、 すべての情報を含んでいます。 文法規則は、トークンの型以外の何も知りません。

意味値は、トークンに関する、たとえば、整数の値や識別子の名前のような、 トークン型以外のあらゆる情報を持っています （','のような区切り記号であるトークンは、 意味値を持つ必要がありません）。

たとえば、ある入力されたトークンは、トークン型がINTEGERで、 意味値が4であると分類されるかもしれません。 別の入力されたトークンは、同じINTEGER型で、 値が3989であるかもしれません。 文法規則がINTEGERの出現を許すのならば、 どちらのトークンもINTEGER型なので、受け入れられます。 構文解析器は、トークンを受け入れるときに、その意味値を記憶します。

それぞれのグループ化は、それに対応する非終端記号とともに、意味値を持てます。 たとえば、電卓の中では、1つの式は、通常、数値である意味値を持ちます。 プログラミング言語のコンパイラの中では、1つの式は、通常、 式の意味を表す木構造の意味値を持ちます。

1.4 意味アクション

役に立つようにするためには、プログラムは、入力を解析するだけでなく、 入力に基づくなんらかの出力を生成する必要があります。 Bison文法の中では、文法規則は、 Cで書かれたアクション（action）を持てます。 そのルールへのマッチを構文解析器が認識するたびに、アクションが実行されます。 See 節 3.5.3 アクション

多くの場合に、アクションの目的は、部品の意味値から全体の意味値を 計算することです。 たとえば、1つの式とは2つの式の和でありうると仮定します。 構文解析器が和を認識すると、 部分式それぞれは、それがどのように構成されたかを表す意味値を持っています。 アクションは、新しく認識された合成式について、 同様の意味値を構成するべきです。

以下に、1つの式が2つの部分式の和となる規則の例を示します。

expr: expr '+' expr   { $$ = $1 + $3; }
        ;

このアクションは、2個の部分式の値から、 式の和の意味値を生成する方法を示しています。

1.5 Bisonの出力――構文解析器ファイル

Bisonを使うときには、入力としてBison文法ファイルを指定します。 文法で記述された言語を解析する、Cのソースファイルが出力になります。 このファイルをBison構文解析器（Bison parser）と呼びます。 BisonユーティリティとBison構文解析器は、 別のプログラムであることに注意してください。 Bisonユーティリティの出力がBison構文解析器で、 あなたのプログラムの一部分になるのです。

Bison構文解析器の仕事は、文法規則に従って、トークンをグループ化することです。 たとえば、識別子と演算子から式を組み立てます。 このために、文法規則に対応するアクションを実行します。

トークンは、字句解析器（lexical analyzer）と呼ばれる関数によって得られ、 その関数を（Cで書くような）なんらかの方法で与える必要があります。 Bison構文解析器は、新しいトークンを必要とするたびに、 字句解析器を呼び出します。 Bison構文解析器は、トークンの「内部」がなんであるか知りません （しかし、トークンの意味値は関係します）。 一般に、字句解析器は、テキスト中の文字を解析してトークンを得ますが、 Bisonはその方法を知りません。 See 節 The Lexical Analyzer Function yylex。

Bison構文解析器ファイルは、Cのプログラムで、yyparseという名前の、 文法を実装する関数を定義します。 この関数は、完全なCのプログラムを構成しません。 いくつかの関数を補ってやる必要があります。 1つは、字句解析器です。 もう1つは、エラーを報告するために構文解析器が呼び出す、 エラー報告関数です。 さらに、完全なCプログラムはmain関数から実行を始める必要がありますので、 これを補って、そこからyyparseを呼び出してください。 See 節 Parser C-Language Interface。

あなたが書くアクションの中でのトークンの型名と記号に関係なく、 Bison構文解析器の中で使われるすべての変数と関数の名前は、 `yy'または`YY'で始まります。 これは、字句解析関数yylexとエラー報告関数yyerrorおよび 構文解析関数yyparseのようなインターフェイス関数も含みます。 また、内部で使われる多数の識別子も同様です。 したがって、本書で定義されている場合を除いて、 Bison文法ファイルの中で`yy'または`YY'で始まる Cの識別子の利用は避けるべきです。

1.6 Bisonを使う手順

Bisonを使って、文法の定義から実際に動くコンパイラやインタープリタを作るまでの、 言語設計手順は、次のようになります。

1. Bisonが認識できる形式で、文法を形式的に指定します （see 節 Bison Grammar Files）。 言語の各文法規則に対して、 その規則のインスタンスが認識されたときに実行される アクションを記述します。 アクションは、C言語の文の並びで書きます。

2. 入力を処理し、トークンを構文解析器に渡すために、字句解析器を書きます。 字句解析器は、Cで手作業で書いてもかまいません （see 節 The Lexical Analyzer Function yylex）。 Lexを使って生成することも可能ですが、本書ではLexの使い方については解説 していません。

3. Bisonが生成した構文解析器を呼び出す、制御関数を書きます。

4. エラー報告関数を書きます。

このソースプログラムを実行可能なプログラムにするために、 次の手順が必要です。

1. 構文解析器を生成するために、Bisonを実行します。

2. Bisonが生成したソースプログラムとその他のソースプログラムを、 コンパイルします。

3. オブジェクトファイルをリンクして、最終的なプログラムを得ます。

1.7 Bison文法の全体像

Bisonユーティリティへの入力は、 Bison文法ファイル（Bison grammar file）です。 Bison文法ファイルの一般的な書式は、次のとおりです。

%{
C宣言部（C declarations）
%}

Bison宣言部（Bison declarations）

%%
文法規則部（Grammar rules）
%%
追加のCプログラム部（Additional C code）

Bison文法ファイル中の`%%'、`%{'、`%}'は、 ファイルを節に分ける区切り記号です。

C宣言部では、 アクションの中で使われる型と変数を定義できます。 マクロを定義するためのプリプロセッサディレクティブや、 ヘッダファイルをインクルードするための#include命令も使用できます。

Bison宣言部には、終端記号、非終端記号、さらに、 演算子の優先順位、さまざまな記号の意味値のデータ型を記述できます。

文法規則部では、各非終端記号をその部品から組み立てる方法を 定義します。

追加のCプログラム部には、 あなたが望むCプログラムを記述できます。 よく字句解析関数yylexや 文法規則の中のアクションから呼ばれる関数をここに書きます。 単純なプログラムでは、(2)ここに 残りのプログラム全部を書きます。