Comments
Description
Transcript
Bison の概念
cp01 :
1999/7/12 (17:22)
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) 文法は、現実
にはまれです。より詳しい説明は「 5.7 不可解な還元/還元衝突」
（ 86 ページ）を参照してください。
21
cp01 :
1章
1999/7/12 (17:22)
Bison の概念
ある言語についての形式文法的な規則では、文法的な単位またはグループを記号（ symbol ）
と呼びます。文法規則に従って小さい部分から組み立てられた記号を非終端記号（ nonterminal
symbol ）といい、終端記号（ terminal symbol ）またはトークン型（ token type ）と呼ばれる
ものに分解できます。本書では、1 個の終端記号に対応する入力の一部分をトークン（ token ）、
1 個の非終端記号に対応する入力の一部分をグループ（ grouping ）と呼びます。
何が終端記号で何が非終端記号かを示すために、例として C 言語を使います。C のトークン
は、識別子、定数（ 数値または文字列）、さまざまな予約語、算術演算子、区切り記号です。C
言語の終端記号には、
「識別子」、
「数値」、
「文字列」、そして、予約語、演算子、区切り記号の
それぞれに対する記号、すなわち、
「 if 」、
「 return 」、
「 const 」、
「 static 」、
「 int 」、
「 char 」、
「プラ
ス記号」、
「開きブレース」、
「閉じブレース」、
「カンマ」、などが含まれます（ これらのトーク
ンは文字に分解できますが、それは文法の問題ではなく、字句解析の問題です）
。
次の例は、トークンに分解された C の関数です。
int
square (x)
/*
/*
/*
int x;
/*
{
/*
return x * x; /*
/*
}
/*
予約語 ‘int’ */
識別子, 開きかっこ, */
識別子, 閉じかっこ */
予約語 ‘int’, 識別子, セミコロン */
開きブレース */
予約語 ‘return’, 識別子, */
アスタリスク, 識別子, セミコロン */
閉じブレース */
C の文法的なグループには、式、文、宣言、関数定義が含まれます。これらは、C の文法で、非終
端記号、
「式」、
「文」、
「宣言」、
「関数定義」として表されます。完全な文法では、上記の 4 つの意味
を表現するために、それぞれの非終端記号について、数十個の追加の言語構築が必要です。上記の
例で、関数定義は、宣言と文を含みます。文の中で、それぞれの x は式であり、x * x も式です。
それぞれの非終端記号には、それがより単純な構成要素からどのように作られるか示すため
に、文法規則が必要です。たとえば、C の文の 1 つである return 文について、文法規則を形
式ばらずに書くと、次のようになります。
「式」、
「セミコロン」から作ることができる。
「文」は、キーワード「 return 」、
「文」には多くの他の規則があるでしょう。
C の各種の文について、
1 つの非終端記号が、言語の全体を表現するように、特別なものとして識別される必要があ
ります。これを開始記号（ start symbol ）と呼びます。コンパイラでは、これは完全な入力プ
ログラムを意味します。C 言語では、非終端記号「定義と宣言の並び」が、この働きをします。
22
cp01 :
1999/7/12 (17:22)
1.2 形式規則から Bison の入力へ
たとえば、1 + 2 は有効な C の式で、C のプログラムの有効な一部分ですが、C プログラム全
「式」は開始記号でないとわかります。
体としては無効です。したがって、C の文脈自由文法では、
Bison 構文解析器は、入力としてトークンの列を読み、文法規則を使ってトークンをグループに
します。もし入力が有効であれば、最終的な結果として、トークンの列全体が文法の開始記号であ
る 1 つのグループの記号に還元されます。もしわれわれが C の文法を使うならば、入力全体は「定
義と宣言の列」の必要があります。もしそうでなければ、構文解析器が文法エラーを報告します。
1.2 形式規則から Bison の入力へ
形式文法（ formal grammer ）は、数学的な構成です。Bison のために言語を定義するために
は、Bison の書式で文法を記述した Bison 文法（ Bison grammer ）ファイルを書く必要があり
ます。
「 3 Bison 文法ファイル」（ 47 ページ）を参照してください。
形式文法の中での 1 つの非終端記号は、Bison の入力の中で、C の識別子のような、1 つの識
別子として表現されます。expr 、stmt 、declaration のように、通常、非終端記号は小文字で
書きます。
終端記号に対する Bison の表現は、トークン型（ token type ）ともいいます。トークン型は、
C 言語で使われるような識別子であるかもしれません。通常、非終端記号からこれらを区別す
るために、大文字で書きます。たとえば、INTEGER 、IDENTIFIER 、IF 、RETURN のように書き
ます。言語の個々のキーワードを表す終端記号は、キーワードを大文字に変換してから命名す
るべきです。終端記号 error は、エラーからの回復処理のために予約されています。
「 3.2 記
号、終端と非終端」（ 48 ページ）を参照してください。
ある終端記号は、C 言語の文字定数のような、1 文字リテラルを表しているかもしれません。
トークンがちょうど 1 文字である（たとえば、かっこ、プラス記号など）ならば必ず、そのトー
クンに対する終端記号として、同じ文字を使うべきです。
終端記号を表す第 3 の方法は、何文字かを含む C 言語の文字列定数です。詳細は「 3.2 記号、
終端と非終端」（ 48 ページ）を参照してください。
文法規則は、Bison の文法の中で、もう 1 つの式を持ちます。たとえば、C 言語の return 文
に対する Bison の規則があります。クォート（ ' ）で囲まれたセミコロンは、文に対する C 言語
の文法の一部分を表す、1 文字のリテラルトークンです。クォートで囲まれていないセミコロ
ンとコロンは、あらゆる規則の中で使われる、Bison の区切り文字です。
23
cp01 :
1章
1999/7/12 (17:22)
Bison の概念
stmt:
RETURN expr ’;’
;
「 3.3 文法規則の構文」（ 50 ページ）を参照してください。
1.3 意味値
形式文法は、トークンを分類法に基づいてのみ、選びます。たとえば、ある規則が‘ integer
constant ’という終端記号について言及するならば、それは、文法的にそこに現れてよい任意
の整数型定数を意味します。その定数の正確な値は、入力が解析される方法と無関係です。も
し、x+4 が文法的に正しいならば、x+1 も、x+3989 も、同様に文法的に正しいのです。
しかし、いったん解析されれば、入力にとって正確な値はきわめて重要です。プログラム中
の定数として 4 と 1 と 3989 を区別できないコンパイラは、役に立ちません。そこで、Bison 文
法の中のそれぞれのトークンは、トークン型のほかに、意味値（ semantic value ）を持ちます。
詳細については、
「 3.5 言語の意味の定義」（ 52 ページ）を参照してください。
トークン型は、INTEGER 、IDENTIFIER 、’,’ のように、文法の中で定義される終端記号です。
これは、そのトークンが正しい位置に現れているか確かめ、他のトークンとどのようにグルー
プ化するか決めるために必要な、すべての情報を含んでいます。文法規則は、トークンの型以
外の何も知りません。
意味値は、トークンに関する、たとえば、整数の値や識別子の名前のような、トークン型以
外のあらゆる情報を持っています（ ’,’ のような区切り記号であるトークンは、意味値を持つ
必要がありません）
。
たとえば、ある入力されたトークンは、トークン型が INTEGER で、意味値が 4 であると分類
されるかもしれません。別の入力されたトークンは、同じ INTEGER 型で、値が 3989 であるかも
しれません。文法規則が INTEGER の出現を許すのならば、どちらのトークンも INTEGER 型なの
で、受け入れられます。構文解析器は、トークンを受け入れるときに、その意味値を記憶します。
それぞれのグループ化は、それに対応する非終端記号とともに、意味値を持てます。たとえ
ば、電卓の中では、1 つの式は、通常、数値である意味値を持ちます。プログラミング言語の
コンパイラの中では、1 つの式は、通常、式の意味を表す木構造の意味値を持ちます。
24
cp01 :
1999/7/12 (17:22)
1.5 Bison の出力――構文解析器ファイル
1.4 意味アクション
役に立つようにするためには、プログラムは、入力を解析するだけでなく、入力に基づくな
んらかの出力を生成する必要があります。Bison 文法の中では、文法規則は、C で書かれたア
クション（ action ）を持てます。そのルールへのマッチを構文解析器が認識するたびに、アク
ションが実行されます。
「 3.5.3 アクション」（ 53 ページ）を参照してください
多くの場合に、アクションの目的は、部品の意味値から全体の意味値を計算することです。
たとえば、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 はその方法を知りません。
「 4.2
字句解析器関数 yylex 」（ 68 ページ）を参照してください。
Bison 構文解析器ファイルは、C のプログラムで、yyparse という名前の、文法を実装する関
25
cp01 :
1章
1999/7/12 (17:22)
Bison の概念
数を定義します。この関数は、完全な C のプログラムを構成しません。いくつかの関数を補っ
てやる必要があります。1 つは、字句解析器です。もう 1 つは、エラーを報告するために構文解
析器が呼び出す、エラー報告関数です。さらに、完全な C プログラムは main 関数から実行を
始める必要がありますので、これを補って、そこから yyparse を呼び出してください。
「4 構
文解析器の C 言語インターフェイス」（ 67 ページ）を参照してください。
あなたが書くアクションの中でのトークンの型名と記号に関係なく、Bison 構文解析器の中で使
われるすべての変数と関数の名前は、yy または YY で始まります。これは、字句解析関数 yylex
とエラー報告関数 yyerror および構文解析関数 yyparse のようなインターフェイス関数も含み
ます。また、内部で使われる多数の識別子も同様です。したがって、本書で定義されている場合を
除いて、Bison 文法ファイルの中で yy または YY で始まる C の識別子の利用は避けるべきです。
1.6 Bison を使う手順
Bison を使って、文法の定義から実際に動くコンパイラやインタープリタを作るまでの、言
語設計手順は、次のようになります。
1. Bison が認識できる形式で、文法を形式的に指定します（「 3 Bison 文法ファイル」（ 47
ページ）を参照）
。言語の各文法規則に対して、その規則のインスタンスが認識されたとき
に実行されるアクションを記述します。アクションは、C 言語の文の並びで書きます。
2. 入力を処理し、トークンを構文解析器に渡すために、字句解析器を書きます。字句解析器は、
（ 68 ページ）を参照）
。Lex
C で手作業で書いてもかまいません（「 4.2 字句解析器関数 yylex 」
を使って生成することも可能ですが、本書では Lex の使い方については解説していません。
3. Bison が生成した構文解析器を呼び出す、制御関数を書きます。
4. エラー報告関数を書きます。
このソースプログラムを実行可能なプログラムにするために、次の手順が必要です。
1. 構文解析器を生成するために、Bison を実行します。
2. Bison が生成したソースプログラムとその他のソースプログラムを、コンパイルします。
3. オブジェクトファイルをリンクして、最終的なプログラムを得ます。
26
cp01 :
1999/7/12 (17:22)
1.7 Bison 文法の全体像
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 や文法規則の中のアクションから呼ばれる関数をここに書きます。単純なプログラムで
∗1
は、
ここに残りのプログラム全部を書きます。
注1 【訳注】他のファイルに書くのではなく
27
cp02 :
1999/7/12 (17:22)
2
例
本章では、Bison 文法を使って書いた例を 3 つ示します。逆ポーランド記法電卓、算術（ 中
置）記法電卓、多機能電卓です。すべて BSD UNIX 4.3 上でテストしました。限定的ではあり
ますが、対話的な電卓として利用可能です。
これらの例は単純ですが、現実のプログラミング言語に対する Bison 文法も、書き方は同じ
です。
2.1 逆ポーランド記法電卓
最初の例は、逆ポーランド記法（ reverse polish notation ）を使う倍精度の電卓で、演算子
を後に書きます。この例は、演算子の優先順位の問題がないので、入門には適しています。第
2 の例では、演算子の優先順位をどのように扱うかを示します。
この電卓のソースファイルを rpcalc.y とします。Bison の入力ファイルには、通常.y とい
う拡張子を付けます。
2.1.1 rpcalc のための宣言
逆ポーランド記法電卓のための C と Bison の宣言を示します。C と同様に/*...*/はコメン
トです。
/* 逆ポーランド 記法電卓 */
%{
#define YYSTYPE double
#include <math.h>
%}
%token NUM
%% /* 文法規則とアクションが続く */
29
cp02 :
2章
1999/7/12 (17:22)
例
C 宣言部（「 3.1.1 C 宣言部」（ 47 ページ）を参照）には、2 つのプリプロセッサディレクティ
ブがあります。
#define ディレクティブで、トークンとグループの意味値に対する C のデータ型を指定するた
めに、マクロ YYSTYPE を定義します（「 3.5.1 データ型と意味値」（ 53 ページ）を参照）
。Bison
構文解析器は、YYSTYPE に定義された型を使います。定義しないと、int 型が使用されます。各
トークンと式は、浮動小数点数である記録値を持つので、ここでは double を指定します。
べき乗関数 pow の宣言を使うために、#include ディレクティブを使っています。
第 2 の部、Bison 宣言は、Bison のためにトークン型についての情報を用意します（「 3.1.2
（ 48 ページ）を参照）
。1 文字リテラルでない終端記号は、ここで宣言する必要があ
Bison 宣言部」
ります（通常、1 文字のリテラルを宣言する必要はありません）
。この例では、すべての算術演算子
が 1 文字リテラルなので、数値定数に対するトークン型 NUM だけを、終端記号として宣言します。
2.1.2 rpcalc のための文法規則
逆ポーランド記法電卓のための文法規則を示します。
input:
;
line:
;
exp:
/* 空 */
| input line
’\n’
| exp ’\n’
{ printf ("\t%.10g\n", $1); }
NUM
{
| exp exp ’+’
{
| exp exp ’-’
{
| exp exp ’*’
{
| exp exp ’/’
{
/* べき乗関数 */
| exp exp ’^’
{
/* 単項のマイナス */
| exp ’n’
{
$$
$$
$$
$$
$$
=
=
=
=
=
$1;
$1 +
$1 $1 *
$1 /
$2;
$2;
$2;
$2;
}
}
}
}
}
$$ = pow ($1, $2); }
$$ = -$1;
}
;
%%
ここで定義される rpcalc「言語」のグループは、式（ exp ）と、入力行（ line ）と、完全な入
「論理和」という|記号で区切られた、いく
力の写し（ input ）です。これらの非終端記号には、
つかの規則があります。以下の項で、これらの規則の意味を説明します。
言語の意味は、グループが認識されたときのアクションによって決まります。アクションとは、
ブレースで囲まれた C のプログラムです。
「 3.5.3 アクション」（ 53 ページ）を参照してください。
30
cp02 :
1999/7/12 (17:22)
2.1 逆ポーランド記法電卓
これらのアクションを C で書く必要がありますが、Bison には規則の間で意味値を受け渡し
する方法があります。それぞれのアクションで、擬似変数$$は、その規則が構成しようとして
いるグループの意味値を示します。$$に値を代入することが、アクションの主な仕事です。規
則の部品の意味値は、$1 、$2 などの名前で参照されます。
2.1.2.1
input の説明
input の定義について考えます。
input:
/* 空 */
| input line
;
この定義の意味は、
「完全な入力とは、空文字列であるか、あるいは、完全な入力に入力行が
続いたものである」ということです。
「完全な入力」が、それ自身を使って定義されていること
に注意してください。列の中で input が常に左端の記号なので、このような定義を左再帰（ left
「 3.4 再帰的規則」（ 51 ページ）を参照してください。
recursive ）と呼びます。
最初の選択肢は、:と|の間に記号がないので空です。これは、
（トークンを含まない）空の入力文
字列にマッチします。電卓を起動した直後に Ctrl-d ∗1 を押しても、正しい入力と扱われるように、
この規則を入れました。通常、空に対応する選択肢を最初に置き、そこに/* 空 */と書きます。
2 つめの選択肢である規則（ input line ）は、自明（ 空）でないすべての入力を扱います。
その意味は、
「任意の数の行を読み込んだ後で、もし可能ならば、もう 1 行読み込む」というこ
とです。左再帰が、この規則を繰り返しにします。最初の選択肢が空の入力にマッチするので、
0 回以上任意の回数の繰り返しになります。
構文解析器関数 yyparse は、文法エラーが発生するか、あるいは、字句解析器がもうトーク
ンがないと判定するまで、入力の処理を続けます。ファイルの終わりで起きることについては、
後で考慮します。
2.1.2.2
line の説明
次に、line の定義について考えます。
line:
’\n’
| exp ’\n’
{ printf ("\t%.10g\n", $1); }
;
注1 【訳注】UNIX の標準的なコンソールの設定で、入力の終わりを示す制御文字で、MS-DOS では代わり
に Ctrl-z。
31
cp02 :
2章
1999/7/12 (17:22)
例
最初の選択肢は、改行文字であるトークンです。これは、rpcalc が空行を受け入れ、それに
対応するアクションがないので、無視することを示します。第 2 の選択肢は、式の後に改行が
続いたものです。これが、rpcalc を有用にする選択肢です。問い合わせの中の exp が、この選
択肢に現れる最初の記号なので、exp グループの意味値は、$1 の値です。アクションは、問い
合わされた計算の結果である、この値を表示します。
このアクションは、値を$$に代入しないので、例外的です。したがって、line に対応する意
味値は、初期化されず、その値は予想できなくなります。もし、その値が使われると、この仕
様はバグになりますが、われわれはこの値を使いません。ユーザーが入力した行に対する値を
表示したら、その値はもはや必要ありません。
2.1.2.3
expr の説明
exp グループは、いくつかの規則を持ち、それぞれが式の種類に対応しています。最初の規
則は、数値そのものであるもっとも単純な式を処理します。第 2 の規則は、2 個の式に加算記
号が続くような、加算式を処理します。第 3 の規則は、減算式を処理する、といった具合です。
exp:
NUM
| exp exp ’+’
| exp exp ’-’
...
;
{ $$ = $1 + $2;
{ $$ = $1 - $2;
}
}
すべての exp 規則をまとめるために|を使っていますが、次のように別々に書くことも可能です。
exp:
exp:
exp:
NUM ;
exp exp ’+’
exp exp ’-’
...
{ $$ = $1 + $2;
{ $$ = $1 - $2;
} ;
} ;
規則のほとんどは、式の部品の値から式の値を計算するための、アクションを持っています。
たとえば、加算のための規則では、$1 は式の第 1 の部品を、$2 は式の第 2 の部品を表します。
第 3 の部品’+’ は、意味値には関連する情報を持ちませんが、もし値を持っていれば、$3 とし
て参照できます。yyparse がこの規則を使って加算式を認識すると、式全体の値として、2 個
の部分式の値の和が生成されます。
「 3.5.3 アクション」（ 53 ページ）を参照してください。
すべての規則に対してアクションを書く必要はありません。アクションを省略すると、Bison
は$1 の値を$$に複写します。第 1 の規則では、NUM の値をそのまま複写するために、このよう
になっています。
32
cp02 :
1999/7/12 (17:22)
2.1 逆ポーランド記法電卓
ここで示したリストは、望ましい書式ですが、Bison がこのように要求するわけではありま
せん。必要に応じて、空白、タブ、改行を置けます。次のような書き方も可能です。
exp
: NUM | exp exp ’+’ {$$ = $1 + $2; } | ...
これは、次のリストと等価です。
exp:
NUM
| exp exp ’+’
| ...
{ $$ = $1 + $2; }
しかし、後者のほうが可読性が優れています。
2.1.3 rpcalc 字句解析器
字句解析器の仕事は、低水準の構文解析で、文字または文字列をトークンに変換します。Bison
構文解析器は、字句解析器を呼び出してトークンを得ます。
「 4.2 字句解析器関数 yylex 」（ 68
ページ）を参照してください。
RPN（逆ポーランド記法）電卓には、簡単な字句解析器のみが必要です。この字句解析器は、
空白とタブを読み飛ばし、数値を読み込んで double 型の NUM トークンとして返します。数値
の一部分ではないその他の文字は、独立のトークンです。1 文字トークンのトークン符号はそ
の文字自身であることに注意してください。
字句解析関数の戻り値は、トークン型を表す数値です。Bison 規則の中でトークン型を表すた
めに使われる文字列と同じものが、その型の数値符号を表す C の式でもあります。これには、2
種類の働きがあります。もし、トークン型が文字リテラルならば、その数値符号は文字の ASCII
符号であり、数値を表すために字句解析器の中と同じ文字リテラルを使えます。もし、トーク
ン型が識別子ならば、適切な番号を定義する C のマクロとして、その識別子が Bison によって
定義されます。したがって、この例では、NUM は、yylex のために使えるマクロにもなります。
トークンの意味値は、もし存在すれば、大域変数 yylval に記憶され、Bison 構文解析器はそ
「 2.1.1
こを見にいきます（ yylval の C データ型は、文法の最初で定義される YYSTYPE です。
。
rpcalc のための宣言」（ 29 ページ）を参照）
ファイルの終わりに達すると、トークン型のコード 0 が返されます（ Bison は、正でない任
意の値を入力の終わりと認識します）
。
字句解析器のプログラムの例を示します。
33
cp02 :
2章
1999/7/12 (17:22)
例
/*
* 字句解析器は、数値を読めば 、double 型の値をスタックに積んで
* トークン「 NUM 」を返し 、数値以外を読めば 、その文字のアスキー符号を返す。
* 空白とタブは読み飛ばされる。ファイルが終わると 0 を返す。
*/
#include <ctype.h>
yylex ()
{
int c;
/* 空白類を読み飛ばす */
while ((c = getchar ()) == ’ ’ || c == ’\t’)
;
/* 数値を処理する */
if (c == ’.’ || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval);
return NUM;
}
/* ファイルの終わりを処理する */
if (c == EOF)
return 0;
/* 1 文字を返す */
return c;
}
2.1.4 制御関数
この例の精神に則って、制御関数は、飾りのない最小限のものです。唯一必要なことは、構
∗2
文解析の処理を始めるために、yyparse 関数を呼び出すことです。
main ()
{
yyparse ();
}
注2 【訳注】古い K&R-C 処理系を使う場合には前述の例のままでよいのですが、ANSI-C 処理系を使う場
合には、main 関数が返す値が int 型なので、次のように書くべきです。他の関数についても同様です。
本書の例のすべては古い書式で書かれています。
int main ()
{
return yyparse ();
}
34
cp02 :
1999/7/12 (17:22)
2.1 逆ポーランド記法電卓
2.1.5 エラー報告関数
yyparse は、構文エラーを検出すると、エラーメッセージ（ 必ずそうとはかぎりませんが、
通常は"parse error" ）を表示するために、エラー報告関数 yyerror を呼び出します。
#include <stdio.h>
yyerror (s) /* エラーが起きると yyparse から呼び出される */
char *s;
{
printf ("%s\n", s);
}
yyerror から戻った後に、Bison 構文解析器は、文法に適切なエラー規則（「 6 エラーから
の回復」（ 89 ページ）を参照）があれば、エラーから回復し、解析を継続できます。そうでな
い場合には、yyparse が 0 でない値を返します。この例では、エラー規則を書いていないので、
不正な入力はすべて電卓プログラムを終了させます。これは、実際の電卓としてはきれいな動
作ではありませんが、最初の例としては十分です。
2.1.6 構文解析器を生成するために Bison を実行
構文解析器を生成するために Bison を実行する前に、1 つ以上のソースファイルのすべてを
どのように整えるか、決める必要があります。このような単純な例では、すべてを 1 個のファ
イルに詰め込む方法がいちばん簡単です。yylex 、yyerror 、main の定義を、ファイルの「追
。
加の C コード」部の最後に置きます（「 1.7 Bison 文法の全体像」（ 27 ページ）を参照）
大きなプロジェクトでは、ソースコードを複数のファイルに分け、まとめてリコンパイルす
るために make を使うでしょう。
1 つのファイルにすべてのソースが入っているならば、次のコマンドで、それを構文解析器
ファイルに変換できます。
bison file _name.y
この例では、ファイルは rpcalc.y（ 逆ポーランド記法電卓）と呼ばれています。Bison は、
元のファイル名から.y を取り除いて、file _name.tab.c というファイルを生成します。Bison
が出力したファイルには、yyparse のソースコードが含まれています。入力ファイル中の追加
の関数（ yylex 、yyerror 、main ）は、出力にそのまま複写されます。
35
cp02 :
2章
1999/7/12 (17:22)
例
2.1.7 構文解析器ファイルのコンパイル
∗3
構文解析器ファイルをコンパイルする方法を示します。
# カレントディレクトリのファイルの一覧を見る。
% ls
rpcalc.tab.c rpcalc.y
# Bison 構文解析器をコンパイルする。
# 数学ライブラリ内の pow 関数をリンクするために -lm を指定する。
% cc rpcalc.tab.c -lm -o rpcalc
# 再び 、ファイルの一覧を見る。
% ls
rpcalc rpcalc.tab.c rpcalc.y
できた rpcalc ファイルは、実行可能プログラムです。rpcalc を実行させる例を示します。
% rpcalc
4 9 +
13
3 7 + 3 4 5 *+-13
3 7 + 3 4 5 * + - n
13
5 6 / 4 n +
-3.166666667
3 4 ^
81
^D
%
単項マイナスを示す n に注意
べき乗関数
入力の終わり
2.2 中間記法電卓：calc
後置記法演算子に代わって中間記法演算子を扱うように rpcalc を変更します。中間記法には、
演算子の優先順位の概念と、適切な深さに入れ子できるかっこが必要です。中間記法電卓を作
るための Bison ソースファイル calc.y を示します。
/* 中間記法電卓 -- calc */
%{
#define YYSTYPE double
#include <math.h>
注3 【訳注】UNIX 上で cc コマンドを使ってコンパイルする方法を示します。
36
cp02 :
1999/7/12 (17:22)
2.2 中間記法電卓：calc
%}
/* BISON 宣言 */
%token NUM
%left ’-’ ’+’
%left ’*’ ’/’
%left NEG
/* 否定 -- 単項の負 */
%right ’^’
/* べき乗 */
/* 文法規則が続く */
%%
input:
/* 空文字列 */
| input line
;
line:
’\n’
| exp ’\n’ { printf ("\t%.10g\n", $1); }
;
exp:
NUM
{ $$ = $1;
}
| exp ’+’ exp
{ $$ = $1 + $3;
}
| exp ’-’ exp
{ $$ = $1 - $3;
}
| exp ’*’ exp
{ $$ = $1 * $3;
}
| exp ’/’ exp
{ $$ = $1 / $3;
}
| ’-’ exp %prec NEG { $$ = -$2;
}
| exp ’^’ exp
{ $$ = pow ($1, $3); }
| ’(’ exp ’)’
{ $$ = $2;
}
;
%%
yylex 、yyerror 、main 関数は、前の例のものと同じです。
このプログラムには、2 つの重要な特徴があります。
第 2 の部分（ Bison 宣言部）では、%left がトークンの型とそれが左結合演算子であると宣
言します。宣言%left と%right（ 右結合演算子）は、結合性を持たないトークン型名を宣言す
るために使われる%token の代わりになります（ 1 文字のリテラルであるトークンは、通常、宣
言する必要がありません。ここでは、結合性を宣言します）
。
演算子の優先順位は、宣言が書かれる行の順序で決まります。後から宣言された演算子ほど、
高い優先順位を持ちます。したがって、べき乗の優先順位がもっとも高く、単項の負（ NEG ）、
「 * 」と「 / 」と続きます。
「 5.3 演算子の優先順位」（ 80 ページ）を参照してください。
もう 1 つの重要な特徴は、単項の負の演算子のために文法部分にある%prec です。%prec は、
単純に Bison に対して、規則| ’-’ exp は NEG と同じ優先順位を持つように指示し、この例で
はどちらも 2 番目に高い優先順位を持ちます。
以下は calc.y の実行例です。
37
cp02 :
2章
1999/7/12 (17:22)
例
% calc
4 + 4.5 - (34/(8*3+-3))
6.880952381
-56 + 2
-54
3 ^ 2
9
2.3 単純なエラー回復
今まで、本書では、エラー回復（ error recovery ）、つまり、構文エラーを検出した後で構文
解析を続ける方法については言及していませんでした。今までに扱ったことは、yyerror を使っ
てエラーを報告することだけでした。yyerror を呼び出した後で、特に指定しないと yyparse
は処理を終わることを思い出してください。つまり、エラーを含む入力行が、電卓プログラム
を終了させます。この欠陥をどのように改善するか示しましょう。
Bison 言語の文法規則には、予約語 error があります。次の例では、line に対する選択肢群
に error を追加する方法を示します。
line:
’\n’
| exp ’\n’
{ printf ("\t%.10g\n", $1); }
| error ’\n’ { yyerrok;
}
;
文法へのこの追加によって、構文解析エラーが発生した場合に、簡単なエラー回復が可能に
なります。評価不可能な式が読み込まれると、line に対する第 3 の規則によってエラーが認識
され、構文解析が続けられます。この場合にも、関数 yyerror は呼び出され、メッセージを表
示します。アクションは、Bison によって自動的に定義されるマクロである yyerrok 文を実行
します。これはエラー回復の完了を意味します（「 6 エラーからの回復」（ 89 ページ）を参照）
。
yyerrok と yyerror の違いに注意してください。
この形式のエラー回復は、構文エラーを扱います。他の種類のエラーもあります。たとえば、
0 による除算は、例外シグナルを発生し、通常は致命的です。実際の電卓プログラムは、この
シグナルをつかまえて、longjmp を使って main に戻り、入力行の構文解析を続ける必要があ
ります。さらに、現在の入力行の残りは破棄されるべきです。しかし、これらの問題は、Bison
のプログラムに固有の問題ではないので、本書では解説しません。
38
cp02 :
1999/7/12 (17:22)
2.4 多機能電卓：mfcalc
2.4 多機能電卓：mfcalc
Bison の基礎についての説明が終わったので、より高度な話題に移りましょう。前述の電卓
は、5 種類の機能、+ 、- 、* 、/ 、^を持っています。この電卓に、その他の数学関数、たとえば、
sin 、cos などを追加するとよいでしょう。
中間記法電卓への新しい演算子の追加は、その演算子が 1 文字リテラルならば簡単です。字句解
析器 yylex は、数値以外のすべての文字をトークンとして渡すので、追加の演算子に対応する文
法規則を追加するだけです。しかし、次のような表記方法の、より柔軟な組み込み関数が必要です。
関 数 名（ 引 数 ）
さらに、電卓にメモリを追加し、名前付き変数を作り、そこに値を記憶し、後で使えるよう
にしましょう。以下に多機能電卓を使う作業の例を示します。
% mfcalc
pi = 3.141592653589
3.1415926536
sin(pi)
0.0000000000
alpha = beta1 = 2.3
2.3000000000
alpha
2.3000000000
ln(alpha)
0.8329091229
exp(ln(beta1))
2.3000000000
%
複数の代入∗4 と関数の入れ子∗5 が許されることに注意してください。
2.4.1 mfcalc のための定義
以下には、多機能電卓のための、C と Bison の宣言があります。
%{
#include <math.h>
#include "calc.h"
/* cos(), sin() などの数学関数のため */
/* ‘symrec’ の定義を含む */
注4 【訳注】例の alpha = beta1 = 2.3
注5 【訳注】例の exp(ln(beta1))
39
cp02 :
2章
1999/7/12 (17:22)
例
%}
%union {
double
val;
/* 数値を返すため */
symrec *tptr;
/* 記号表へのポインタを返すため */
}
%token <val> NUM
/* 単純な倍精度数値 */
%token <tptr> VAR FNCT
/* 変数と関数 */
%type <val> exp
%right ’=’
%left ’-’ ’+’
%left ’*’ ’/’
%left NEG
/* 単項の負 */
%right ’^’
/* べき乗 */
/* 文法が続く */
%%
この文法の導入部分では、Bison 言語の新しい 2 つの機能を使っています。これらの機能に
よって、意味値がいろいろなデータ型を持てます（「 3.5.2 複数の値型」（ 53 ページ）を参照）
。
%union 宣言は、YYSTYPE の定義の代わりで、可能な型の一覧を指定します。ここで許される
「 3.6.3
型は、
（ exp と NUM のための）倍精度浮動小数点型と、記号表の項目へのポインタです。
値型の集合」（ 60 ページ）を参照してください。
値がいろいろな型を持つことができるので、意味値を使うそれぞれの文法記号に対して、型
を関連づける必要があります。これらの記号は NUM 、VAR 、FNCT 、exp です。それらの宣言は、
不等号で囲まれた（ <...> ）データ型に関する情報を付加されています。
Bison は、ちょうど%token がトークン型の宣言に使われるのと同じように、%type が非終端記
号の宣言に使われるようにします。非終端記号は通常それらを定義する規則によって暗黙に宣言さ
れるので、%type をその規則よりも先に使ってはいけません。しかし、exp は、その値の型を指定す
るので、明示的に宣言する必要があります。
「 3.6.4 非終端記号」
（ 61 ページ）を参照してください。
2.4.2 mfcalc のための文法規則
多機能電卓のための文法規則を示します。大部分は、calc の文法規則からの複写です。VAR 、
FUNCT に関連する 3 つの規則が新しいものです。
input:
/* 空 */
| input line
;
line:
’\n’
| exp ’\n’
{ printf ("\t%.10g\n", $1); }
| error ’\n’ { yyerrok;
}
40
cp02 :
1999/7/12 (17:22)
2.4 多機能電卓：mfcalc
;
exp:
|
|
|
|
|
|
|
|
|
|
NUM
VAR
VAR ’=’ exp
FNCT ’(’ exp ’)’
exp ’+’ exp
exp ’-’ exp
exp ’*’ exp
exp ’/’ exp
’-’ exp %prec NEG
exp ’^’ exp
’(’ exp ’)’
{
{
{
{
{
{
{
{
{
{
{
$$
$$
$$
$$
$$
$$
$$
$$
$$
$$
$$
=
=
=
=
=
=
=
=
=
=
=
$1;
$1->value.var;
$3; $1->value.var = $3;
(*($1->value.fnctptr))($3);
$1 + $3;
$1 - $3;
$1 * $3;
$1 / $3;
-$2;
pow ($1, $3);
$2;
}
}
}
}
}
}
}
}
}
}
}
;
/* 文法の終わり */
%%
2.4.3 mfcalc の記号表
変数と関数の名前と意味を保持するために、多機能電卓は記号表を必要とします。これは、アク
ションを除く文法規則と Bison 宣言には影響しませんが、追加の C の関数がいくつか必要です。
記号表は、レコードのリンクリストからなります。その定義は、後述の、ヘッダファイル
calc.h にあります。関数と変数の両方を表に置くことができます。
/* 記号表のリンクを表すデータ型 */
struct symrec
{
char *name; /* 記号の名前 */
int type;
/* 記号の種類：VAR または FNCT */
union {
double var;
/* VAR の値 */
double (*fnctptr)(); /* FNCT の値 */
} value;
struct symrec *next;
/* 次の項目へのリンク */
};
typedef struct symrec symrec;
/* ‘struct symrec’ のリンクである記号表 */
extern symrec *sym_table;
symrec *putsym ();
symrec *getsym ();
新しい main 関数は、記号表を初期化する関数である init_table を呼びます。main と init_
table を以下に示します。
41
cp02 :
2章
1999/7/12 (17:22)
例
#include <stdio.h>
main ()
{
init_table ();
yyparse ();
}
yyerror (s) /* エラーがあると yyparse から呼び出される */
char *s;
{
printf ("%s\n", s);
}
struct init
{
char *fname;
double (*fnct)();
};
struct init arith_fncts[]
= {
"sin", sin,
"cos", cos,
"atan", atan,
"ln", log,
"exp", exp,
"sqrt", sqrt,
0, 0
};
/* 記号表：‘struct symrec’ のリスト */
symrec *sym_table = (symrec *)0;
init_table () /* 数学関数を表に登録する */
{
int i;
symrec *ptr;
for (i = 0; arith_fncts[i].fname != 0; i++)
{
ptr = putsym (arith_fncts[i].fname, FNCT);
ptr->value.fnctptr = arith_fncts[i].fnct;
}
}
単純に初期化リストを編集して、必要なインクルードファイルを追加するだけで、電卓に関
数を追加できます。
記号表に記号を登録して検索するために、2 個の重要な関数があります。関数 putsym は、登
録すべきオブジェクトの名前と型（ VAR や FNCT ）を渡されます。オブジェクトはリストの先頭に
リンクされ、オブジェクトへのポインタが返されます。関数 getsym は、検索すべき記号の名前
を渡されます。もし見つかれば記号へのポインタが返され、見つからなければ 0 が返されます。
42
cp02 :
1999/7/12 (17:22)
2.4 多機能電卓：mfcalc
symrec *
putsym (sym_name,sym_type)
char *sym_name;
int sym_type;
{
symrec *ptr;
ptr = (symrec *) malloc (sizeof (symrec));
ptr->name = (char *) malloc (strlen (sym_name) + 1);
strcpy (ptr->name,sym_name);
ptr->type = sym_type;
ptr->value.var = 0; /* 関数の場合にも値を 0 にする */
ptr->next = (struct symrec *)sym_table;
sym_table = ptr;
return ptr;
}
symrec *
getsym (sym_name)
char *sym_name;
{
symrec *ptr;
for (ptr = sym_table; ptr != (symrec *) 0;
ptr = (symrec *)ptr->next)
if (strcmp (ptr->name,sym_name) == 0)
return ptr;
return 0;
}
今度の関数 yylex は、変数、数値、1 文字の算術演算子を認識する必要があります。英字で
始まり英数字からなる文字列は、記号表にどう書かれているかに応じて、変数と関数のどちら
とも認識されます。
文字列は、記号表を検索するために getsym に渡されます。もし名前が表にあれば、その場
所へのポインタと名前の型（ VAR または FNCT ）が、yyparse に返されます。名前がまだ表にな
ければ、putsym を使って、VAR として登録されます。そして、ポインタと型（ この場合には必
ず VAR ）が yyparse に返されます。
yylex の中で、数値と算術演算子の扱いに関する部分は、変更する必要がありません。
#include <ctype.h>
yylex ()
{
int c;
/* 空白を読み飛ばし 、空白以外を得る */
while ((c = getchar ()) == ’ ’ || c == ’\t’);
if (c == EOF)
return 0;
43
cp03 :
1999/7/12 (17:22)
3
Bison 文法ファイル
Bison は、文脈自由文法の仕様を入力として受け取り、その文法の正しいインスタンスを認
識する、C 言語の関数を生成します。
Bison 文法ファイルの名前は、通常.y で終わります。
3.1 Bison 文法の概要
Bison 文法ファイルは 4 つの主要な部分からなります。それらを、適切な区切り文字ととも
に示します。
%{
C 宣 言 部（ C declarations ）
%}
Bison 宣 言 部（ Bison declarations ）
%%
文 法 規 則 部（ Grammar rules ）
%%
追 加 の C プ ロ グ ラ ム 部（ Additional C code ）
/* ...
*/で囲まれたコメントは、どの部分にも書けます。
3.1.1 C 宣言部
C 宣言部（ C declarations ）には、マクロ定義と、文法定義のアクションで使うための関数と
変数の宣言があります。これらは、yyparse の定義に優先するように、構文解析器ファイルの
最初に複写されます。ヘッダファイルから宣言を得るには#include を使います。C 宣言がまっ
たく必要ない場合は、この部分を囲む%{と%}を省略できます。
47
cp03 :
3章
1999/7/12 (17:22)
Bison 文法ファイル
3.1.2 Bison 宣言部
Bison 宣言部（ Bison declarations ）は、終端記号と非終端記号の宣言、演算子の優先順位
の指定などを含みます。単純な例では、宣言を省略できます。
「 3.6 Bison 宣言」（ 58 ページ）
を参照してください。
3.1.3 文法規則部
文法規則部（ grammar rules ）は、1 つ以上の Bison 文法規則を含み、それ以外は含みませ
ん。
「 3.3 文法規則の構文」（ 50 ページ）を参照してください。
少なくとも 1 つの文法規則が存在する必要があります。また、文法規則より先に%%が必要で、
もしそれ以前に何も記述されていなくても、省略できません。
3.1.4 追加の C プログラム部
追加の C プログラム部（ additional C code ）は、C 宣言部が構文解析器ファイルの先頭に
複写されるのと同じように、構文解析器ファイルの末尾にそのまま複写されます。構文解析器
ファイル中に置く必要があって、yyparse の定義よりも前に置く必要のないものを、ここに置
「 4 構文解析
くと便利です。たとえば、yylex と yyerror の定義は、よくここに置かれます。
器の C 言語インターフェイス」（ 67 ページ）を参照してください。
もし直前の部が空ならば、文法規則と区別するための%%を省略できます。
Bison 構文解析器は、名前が yy で始まる多くの静的変数と、名前が YY で始まる多くのマク
ロを含んでいます。本書で解説しているものを意図的に使う場合を除いて、そのような名前を
文法ファイルの追加の C プログラム部で使うのは避けるべきです。
3.2 記号、終端と非終端
Bison 文法の記号（ symbols ）は、言語の文法的分類を表現します。
終端記号（ terminal symbol ）（ トークン型（ tokens types ）ともいいます）は、構文的に
等価なトークンのクラスを表します。そのクラスのトークンが許されることを表すために、文
法規則の中で記号を使えます。その記号は、Bison 構文解析器の中で番号で表現され、yylex
関数は、どのような種類のトークンが読み込まれたかを示すために、トークン番号を返します。
これを表す記号を知っていればよく、その番号を知っている必要はありません。
非終端記号（ nonterminal symbol ）は、構文的に等価なグループを表現します。記号名は文
48
cp03 :
1999/7/12 (17:22)
3.2 記号、終端と非終端
法規則の記述に使われます。通常、非終端記号名を小文字で書きます。
記号名は、英字、先頭以外での数字、下線記号（_）とピリオドからなります。ピリオド記号
（ . ）は、非終端記号の名前には使えますが、終端記号の名前には使えません。
文法中で終端記号を記述するには 3 種類の方法があります。
• 名前付きトークン型（ named token type ）を、C 言語における識別子と同様な、識別子と
ともに書きます。通常、大文字で書きます。これらは%token のような Bison 宣言とともに
定義する必要があります。
「 3.6.1 トークン型名」（ 58 ページ）を参照してください。
• 文字トークン型（ character token type ）、すなわちリテラル文字トークン（ literal char
acter token ）は、C 言語の文字定数と同じ構文で書かれ、たとえば’+’ は文字トークン型
です。意味値データ型（「 3.5.1 データ型と意味値」（ 53 ページ）を参照）、結合性、優先
順位（「 5.3 演算子の優先順位」（ 80 ページ）を参照）を指定する必要がなければ、文字
トークン型を宣言する必要はありません。
通常、文字トークン型は、特別な文字∗1 からなるトークンを表すためだけに使います。たと
えば、トークン型’+’ を、トークンとしての+文字を表すために使います。このようにする義
務はありませんが、そうしないと、あなたが書いたプログラムを読む人が混乱するでしょう。
C 言語の文字リテラルで使われる通常のエスケープシーケンス∗2 を、Bison でも使えます。
しかし、’\0’ だけは ASCII 符号の 0 を表し、yylex がファイルの終わりを示す符号なので、
文字リテラルとしては使えません（「 4.2.1 yylex を呼び出す方法」（ 68 ページ）を参照）
。
•
リテラル文字列トークン（ literal string token ）は、C 言語における文字列定数と同様に
書きます。たとえば、"<="がリテラル文字列トークンです。意味値（「 3.5.1 データ型と意
味値」（ 53 ページ）を参照）、結合性、優先順位（「 5.3 演算子の優先順位」（ 80 ページ）を
参照）を指定する必要がなければ、リテラル文字列トークンを宣言する必要はありません。
%token 宣言（「 3.6.1 トークン型名」（ 58 ページ）を参照）を使って、リテラル文字列トー
クンを、記号名の別名として関連づけられます。そうしないと、字句解析器は、yytname
表（「 4.2.1 yylex を呼び出す方法」（ 68 ページ）を参照）を使って、リテラル文字列トー
クンからトークン番号を検索する必要があります。
【警告】yacc ではリテラル文字列トークンを使えません。
通常、特殊文字の列からなるトークンの表現にのみ、リテラル文字列トークンを使います。
注1 【訳注】英数字以外の文字。
注2 【訳注】\に続く表現。
49
cp03 :
3章
1999/7/12 (17:22)
Bison 文法ファイル
たとえば、トークンとしての<=を表すために、トークン型"<="を使うべきです。そうする義
務はありませんが、そうしないと、あなたが書いたプログラムを読む人が混乱するでしょう。
C 言語で使えるエスケープシーケンスはすべて Bison でも使えます。リテラル文字列トー
クンは、2 文字以上からなります。もし、トークンが 1 文字ならば、前述の 1 文字トーク
ンを使ってください。
終端記号を書く方法は、終端記号の文法的意味に関係なく、規則の中に現れる位置と、構文
解析器関数が記号を返す方法に関係します。
yylex が返す値は、終端記号のどれかを表し、入力の終わりでは 0 です。文法規則の中でど
の方法でトークン型を書いても、yylex を定義する書き方は同じです。1 文字トークン型に対す
る符号は、その文字の ASCII 符号なので、yylex は必要な符号を生成するために同一の文字定
数を使えます。名前を付けられたトークン型はそれぞれ、構文解析器ファイルの中で C のマク
ロになるので、yylex は符号に対するマクロ名を使えます。これが、終端記号の名前にピリオ
ド記号を使えない理由です。
「 4.2.1 yylex を呼び出す方法」（ 68 ページ）を参照してください。
yylex が構文解析器と別のソースファイルの中に書かれる場合には、そこでトークン型マク
ロ定義を使えるように準備する必要があります。-d オプションを付けて Bison を実行してくだ
さい。すると、マクロ定義が name.tab.h というファイルに書かれ、必要に応じて別のソース
ファイルからインクルードできます。
「 9 Bison の実行」（ 99 ページ）を参照してください。
記号 error は、エラー回復用に予約された終端記号（「 6 エラーからの回復」（ 89 ページ）
を参照）で、他の目的に使うべきではありません。実際に、yylex がこの値を返すことは決し
てありません。
3.3 文法規則の構文
Bison 文法規則は、一般的に次の書式です。
result: components...
;
result は、この規則が記述する非終端記号で、components は、この規則で一緒に置かれる
さまざまな終端および非終端記号です。例を示します。
exp:
exp ’+’ exp
;
50
cp03 :
1999/7/12 (17:22)
3.4 再帰的規則
この例では、+トークンを間にはさんで型 exp の 2 つのグループ化が行われ、型 exp のより
大きなグループができます。
規則の中の空白∗3 は、記号を分けるだけの意味を持ちます。必要に応じて、余分な空白を書
いてもかまいません。
components の周辺にあるものは、規則の意味を決定するアクション（ action ）になること
ができます。アクションは、次のようになります。
{C statements}
通常、1 つだけのアクションと、それに続く components があります。
「 3.5.3 アクション」
（ 53 ページ）を参照してください。
同一の result に対する複数の規則は、別々に書くこともできますし、次の例のように縦線記
号|で区切ってまとめて書くことも可能です。
result:
rule1-components...
| rule2-components...
...
;
まとめて書いても、それぞれの規則は別々のものとみなされます。
もし、規則中の components が空ならば、result が空の列にマッチできることを意味します。
例として、カンマで区切られた 0 個以上の exp のグループを定義する方法を示します。
/* 空 */
| expseq1
;
expseq1: exp
| expseq1 ’,’ exp
;
expseq:
空の component を持つ規則には、通常/* 空 */という注釈を書きます。
3.4 再帰的規則
result である非終端記号が規則の右側にも現れる場合に、その規則は再帰的（ recursive ）で
あるといいます。Bison 文法の大部分は再帰的規則を使います。なぜならば、任意の数の並び
注3 【訳注】任意の数の空白文字、タブ符号、改行符号。
51
cp03 :
3章
1999/7/12 (17:22)
Bison 文法ファイル
を定義する唯一の方法が、再帰的規則だからです。1 つ以上のカンマで区切られた式の並びの
定義を考えてみましょう。
expseq1: exp
| expseq1 ’,’ exp
;
expseq1 で使われている再帰は、規則の右側の中でもっとも左側にあるので、このような再
帰を左再帰（ left recursion ）と呼びます。逆に、同じ構造を右再帰（ right recursion ）を使っ
て書いてみます。
expseq1: exp
| exp ’,’ expseq1
;
あらゆる並びを、左再帰を使っても、右再帰を使っても、定義できます。しかし、限られた
スタック容量で任意の数の並びを走査できるので、つねに左再帰を使うべきです。右再帰では、
規則が適用される前にすべての要素をスタックに積む必要があるので、要素の数に比例するス
タック領域を消費します。詳細については、
「 5 Bison 構文解析器のアルゴリズム」（ 77 ペー
ジ）を参照してください。
規則の結果が直接その右側には含まれず、右側にある非終端記号の中に含まれるとき、間接
（ indirect ）すなわち相互（ mutual ）再帰が起きます。
例を示します。
expr:
primary
| primary ’+’ primary
;
primary: constant
| ’(’ expr ’)’
;
この例では、それぞれの規則が互いに参照しているので、2 個の相互再帰が定義されています。
3.5 言語の意味の定義
言語に対する文法規則は、文法だけを決めます。意味は、各種のトークンとグループ化に対
応する意味値により、各種のグループ化が認識されるときに、決定されます。
電卓の例では、式のそれぞれに対応する値が適切な数値なので、電卓は正確に計算できます。
グループ x + y に対応するアクションが、x と y に関する数値の和を計算します。
52
cp03 :
1999/7/12 (17:22)
3.5 言語の意味の定義
3.5.1 データ型と意味値
単純なプログラムでは、言語の要素のすべての意味値に対して同じデータ型を使えば十分で
す。逆ポーランド記法と中間記法電卓の例では、そうでした（「 2.1 逆ポーランド記法電卓」（ 29
ページ）を参照）
。
特に指定しないと、Bison はすべての意味値に対して int 型を使います。他の型を使うには、
次の例のように、マクロ YYSTYPE を定義します。
#define YYSTYPE double
このマクロ定義は、文法ファイルの C 宣言部に置く必要があります（「 3.1 Bison 文法の概
要」（ 47 ページ）を参照）
。
3.5.2 複数の値型
多くのプログラムでは、異なる種類のトークンとグループに対して、異なるデータ型が必要
です。たとえば、数値定数は int 型や long 型を必要とし、文字列定数は char *型を必要とし、
識別子は記号表の項目へのポインタを必要とするでしょう。
同一の構文解析器内で、意味値に対して 2 つ以上のデータ型を使うには、次の 2 項目が必要
です。
• Bison 宣言の%union で、考えられるデータ型全体の集合を指定します（「 3.6.3 値型の集
合」（ 60 ページ）を参照）
。
• 終端または非終端記号のそれぞれについて、その意味値を使うために、上記の型のどれか 1
つを選びます。トークンに対する型の指定には、Bison 宣言の%token を使います（「 3.6.1
トークン型名」（ 58 ページ ）を参照 ）。グループ化に対する型の指定には、Bison 宣言
。
の%type を使います（「 3.6.4 非終端記号」（ 61 ページ）を参照）
3.5.3 アクション
文法規則にともなうアクションは、その規則が認識されるたびに実行される C のプログラム
からなります。アクションの仕事のほとんどは、関連するトークンまたは小さいグループから
規則にしたがって構成されるグループの、意味値の計算です。
アクションは、C の複文のように、ブレースで囲まれた C の文からなります。アクションは、
規則のどの場所にも置け、その場所で実行されます。規則のほとんどは、規則の終わりの構成要
53
cp03 :
3章
1999/7/12 (17:22)
Bison 文法ファイル
素の並びの後に、1 つだけアクションを持ちます。規則の途中に置かれたアクションは、手の込
。
んだ方法で特別な目的に使われます（「 3.5.5 規則の途中のアクション」（ 55 ページ）を参照）
アクションの中の C で書かれたプログラムは、規則の第 n 番目の要素に対応する意味値を、
$n という書式で参照できます。また、その規則が構成するグループの意味値を、$$という書式
で参照できます。アクションが構文解析器ファイルに複写されるときに、Bison は、上記の構
成要素を配列要素への参照に変換します。
例を示します。
exp:
...
| exp ’+’ exp
{ $$ = $1 + $3; }
この規則は、加算記号で結び付けられた 2 つの小さい exp グループから、1 つの exp を構成し
ます。このアクションの中で、$1 と$3 は、規則の右側の最初と 3 番目の記号である exp グルー
プの意味値を参照します。この規則によって認識される加算式の値になるように、和が$$に代
入されます。もし、+トークンに有用な値があるならば、それを$2 として参照できるでしょう。
規則に対してアクションを指定しなければ、Bison は、省略時アクション$$ = $1 を補いま
す。したがって、規則の最初の記号の値が規則全体の値になります。もちろん、両者の型が一致
する場合にのみ、省略時アクションは有効です。空規則に対する省略時アクションは無意味で
す。すべての空規則は、その規則の値が必要ならば、明示的なアクションを持つ必要があります。
$n の n は 0 または負が許され、現在の規則にマッチする前にスタックに積まれていたトークン
とグループの意味値を参照します。これは非常に危険な手法で、安全に使うためには、その規則が
適用される文脈をあなたが完全に理解している必要があります。これを安全に使える例を示します。
foo:
bar:
expr bar ’+’ expr { ... }
| expr bar ’-’ expr { ... }
;
/* 空 */
{ previous_expr = $0; }
;
bar がここに書かれた方法でのみ使われるならば、foo の定義の中で bar より前の expr の
値を$0 が参照します。
54